| 题目 | 难度 | 算法 |
|---|---|---|
| 1. 两数之和 | Easy | Hash |
| 2. 两数相加 | Meidum | 数学 |
| 3. 无重复字符的最长子串 | Medium | 滑动窗口 |
| 4. 寻找两个正序数组的中位数 | Hard | 分治 |
| 5. 最长回文子串 | Medium | 动态规划 |
| 7. 整数反转 | Easy | 限制判断 |
| 8. 字符串转换整数 (atoi) | Medium | 数学 |
| 9. 回文数 | Easy | 字符串，Two points |
| 10. 正则表达式匹配 | Hard | 动态规划 |
| 11. 盛最多水的容器 | Medium | 双指针 |
| 12. 整数转罗马数字 | Medium | 数学 |
| 13. 罗马数字转整数 | Easy | 字符串，技巧 |
| 14. 最长公共前缀 | Easy | 字符串比较 |
| 17. 电话号码的字母组合 | Medium | 回溯 |
| 20. 有效的括号 | Easy | 栈 |
| 21. 合并两个有序链表 | Easy | 单链表 |
| 22. 括号生成 | Medium | 回溯 |
| 23. 合并K个排序链表 | Hard | 分治/非递归归并 |
| 24. 两两交换链表中的节点 | Medium | 链表 |
| 26. 删除排序数组中的重复项 | Easy | 数组去重 |
| 27. 移除元素 | Easy | 数组去重 |
| 28. 实现strStr | Easy | KMP算法 |
| 29. 两数相除 | Medium | 数学 |
| 31. 下一个排列 | Medium | 双指针 |
| 32. 最长有效括号 | Hard | 字符串/动态规划 |
| 33. 搜索旋转排序数组 | Medium | 二分查找 |
| 35. 搜索插入位置 | Easy | 二分查找 |
| 37. 解数独 | Hard | 解数独 |
| 38. 报数 | Easy | 字符串 |
| 39. 组合总和 | Medium | 回溯 |
| 40. 组合总和 II | Medium | 回溯 |
| 43. 字符串相乘 | Medium | 模拟 |
| 44. 通配符匹配 | Hard | 动态规划 |
| 46. 全排列 | Medium | 回溯 |
| 47. 全排列 II | Medium | 回溯 |
| 48. 旋转图像 | Medium | 数组 |
| 50. Pow(x, n) | Medium | 二分查找 |
| 51. N 皇后 | Hard | 回溯 |
| 52. N皇后 II | Hard | 回溯 |
| 53. 最大子序和 | Easy | 动态规划 |
| 54. 螺旋矩阵 | Medium | 数组 |
| 55. 跳跃游戏 | Medium | 贪心 |
| 56. 合并区间 | Medium | 排序 |
| 57. 插入区间 | Hard | 排序 |
| 58. 最后一个单词的长度 | Easy | 字符串 |
| 60. 第k个排列 | Medium | 回溯+剪枝 |
| 61. 旋转链表 | Medium | 链表 |
| 62. 不同路径 | Medium | 动态规划 |
| 63. 不同路径 II | Medium | 动态规划 |
| 64. 最小路径和 | Medium | 动态规划 |
| 65. 有效数字 | Hard | 确定有限状态自动机 |
| 66. 加一 | Easy | 加法进位 |
| 67. 二进制求和 | Easy | 加法进位 |
| 69. x 的平方根 | Easy | 二分法 |
| 70. 爬楼梯 | Easy | 动态规划 |
| 71. 简化路径 | Medium | 栈/字符串 |
| 74. 搜索二维矩阵 | Medium | 二分 |
| 75. 颜色分类 | Medium | 排序 |
| 77. 组合 | Medium | 回溯+剪枝 |
| 78. 子集 | Medium | 位运算 |
| 79. 单词搜索 | Medium | 回溯 |
| 81. 搜索旋转排序数组 II | Medium | 二分 |
| 82. 删除排序链表中的重复元素 II | Medium | 链表 |
| 83. 删除排序链表中的重复元素 | Easy | 单链表 |
| 86. 分隔链表 | Medium | 链表 |
| 88. 合并两个有序数组 | Easy | 数组合并 |
| 89. 格雷编码 | Medium | 回溯 |
| 90. 子集 II | Medium | 回溯 |
| 91. 解码方法 | Medium | 动态规划 |
| 92. 反转链表 II | Medium | 链表 |
| 93. 复原IP地址 | Medium | 回溯 |
| 94. 二叉树的中序遍历 | Medium | 栈/树 |
| 95. 不同的二叉搜索树 II | Medium | 递归 |
| 96. 不同的二叉搜索树 | Medium | 动态规划 |
| 97. 交错字符串 | Hard | 动态规划 |
| 98. 验证二叉搜索树 | Medium | 二叉搜索树 |
| 99. 恢复二叉搜索树 | Hard | 树 |
| 100. 相同的树 | Easy | 二叉树 |
| 101. 对称二叉树 | Easy | 二叉树 |
| 102. 二叉树的层次遍历 | Medium | 广搜 |
| 103. 二叉树的锯齿形层次遍历 | Medium | 广搜 |
| 104. 二叉树的最大深度 | Easy | 二叉树 |
| 105. 从前序与中序遍历序列构造二叉树 | Medium | 二叉树 |
| 106. 从中序与后序遍历序列构造二叉树 | Medium | 二叉树 |
| 107. 二叉树的层次遍历 II | Easy | 二叉树 |
| 108. 将有序数组转换为二叉搜索 | Easy | 二叉树 |
| 109. 有序链表转换二叉搜索树 | Medium | 平衡二叉树 |
| 110. 平衡二叉树 | Easy | 二叉树 |
| 111. 二叉树的最小深度 | Easy | 二叉树 |
| 112. 路径总和 | Easy | 二叉树 |
| 113. 路径总和 II | Medium | 二叉树 |
| 114. 二叉树展开为链表 | Medium | 二叉树遍历 |
| 116. 填充每个节点的下一个右侧节点指针 | Medium | 层次遍历 |
| 117. 填充每个节点的下一个右侧节点指针 II | Medium | 层次遍历 |
| 118. 杨辉三角 | Easy | 简单模拟 |
| 119. 杨辉三角 II | Easy | 动态规划 |
| 120. 三角形最小路径和 | Medium | 动态规划 |
| 121. 买卖股票的最佳时机 | Easy | 动态规划 |
| 122. 买卖股票的最佳时机 II | Easy | 动态规划 |
| 123. 买卖股票的最佳时机 III | Hard | 动态规划 |
| 125. 验证回文串 | Easy | 字符串 |
| 126. 单词接龙 II | Hard | 双向广搜 |
| 127. 单词接龙 | Medium | 双向广搜 |
| 129. 求根到叶子节点数字之和 | Medium | 二叉树遍历 |
| 130. 被围绕的区域 | Medium | 并查集 |
| 131. 分割回文串 | Medium | 回溯 |
| 132. 分割回文串 II | Hard | 动规 |
| 133. 克隆图 | Medium | BFS+Map |
| 134. 加油站 | Medium | 贪心 |
| 135. 分发糖果 | Hard | 贪心 |
| 136. 只出现一次的数字 | Easy | 逻辑 |
| 139. 单词拆分 | Medium | 动态规划 |
| 140. 单词拆分 II | Hard | DP+回溯 |
| 141. 环形链表 | Easy | 单链表，快慢指针 |
| 142. 环形链表 II | Medium | 链表 |
| 143. 重排链表 | Medium | 链表 |
| 145. 二叉树的后序遍历 | Hard | 树/栈 |
| 146. LRU缓存机制 | Medium | 设计 |
| 147. 对链表进行插入排序 | Medium | 排序 |
| 148. 排序链表 | Medium | 排序 |
| 150. 逆波兰表达式求值 | Medium | 栈/字符串 |
| 152. 乘积最大子序列 | Medium | 动态规划 |
| 153. 寻找旋转排序数组中的最小值 | Medium | 二分 |
| 155. 最小栈 | Easy | 栈 |
| 160. 相交链表 | Easy | 双指针 |
| 162. 寻找峰值 | Medium | 二分查找 |
| 166. 分数到小数 | Medium | 数学/模拟 |
| 167. 两数之和 II - 输入有序数组 | Easy | Hash |
| 168. Excel表列名称 | Easy | 字符串hash |
| 169. 多数元素 | Easy | 逻辑 |
| 170. 两数之和 III - 数据结构设计 | Easy | 设计 |
| 171. Excel表列序号 | Easy | 字符串hash |
| 173. 二叉搜索树迭代器 | Medium | 设计 |
| 174. 地下城游戏 | Hard | 动态规划 |
| 179. 最大数 | Medium | 排序 |
| 187. 重复的DNA序列 | Medium | 位运算 |
| 188. 买卖股票的最佳时机 IV | Hard | 动态规划 |
| 189. 旋转数组 | Easy | 数组移动 |
| 190. 颠倒二进制位 | Easy | 二进制 |
| 191. 位1的个数 | Easy | 二进制 |
| 198. 打家劫舍 | Easy | 动态规划 |
| 199. 二叉树的右视图 | Medium | DFS |
| 200. 岛屿数量 | Medium | 并查集 |
| 201. 数字范围按位与 | Medium | 位运算 |
| 202. 快乐数 | Easy | 快慢指针 |
| 203. 移除链表元素 | Easy | 单链表 |
| 204. 计数质数 | Easy | 素数Euler |
| 205. 同构字符串 | Easy | Hash |
| 206. 反转链表 | Easy | 单链表 |
| 207. 课程表 | Medium | 拓扑排序 |
| 208. 实现 Trie (前缀树) | Medium | 设计 |
| 209. 长度最小的子数组 | Medium | 滑动窗口 |
| 210. 课程表 II | Medium | 拓扑排序 |
| 211. 添加与搜索单词 - 数据结构设计 | Medium | 设计 |
| 213. 打家劫舍 II | Medium | 动态规划 |
| 214. 最短回文串 | Hard | 字符串/KMP |
| 215. 数组中的第K个最大元素 | Medium | 分治 |
| 216. 组合总和 III | Medium | 回溯 |
| 217. 存在重复元素 | Easy | Hash |
| 218. 天际线问题 | Hard | 分治 |
| 219. 存在重复元素 II | Easy | Hash |
| 220. 存在重复元素 III | Medium | 排序 |
| 221. 最大正方形 | Medium | 动态规划 |
| 222. 完全二叉树的节点个数 | Medium | 树 |
| 223. 矩形面积 | Medium | 数学 |
| 225. 用队列实现栈 | Easy | 队列 |
| 226. 翻转二叉树 | Easy | 二叉树 |
| 230. 二叉搜索树中第K小的元素 | Medium | 二分查找 |
| 231. 2的幂 | Easy | 快速幂 |
| 232. 用栈实现队列 | Easy | 设计 |
| 234. 回文链表 | Easy | 链表 |
| 235. 二叉搜索树的最近公共祖先 | Easy | 树 |
| 236. 二叉树的最近公共祖先 | Medium | 树 |
| 237. 删除链表中的节点 | Easy | 链表 |
| 239. 滑动窗口最大值 | Hard | 滑动窗口 |
| 240. 搜索二维矩阵 II | Medium | 数学 |
| 241. 为运算表达式设计优先级 | Medium | 分治 |
| 242. 有效的字母异位词 | Easy | 排序 |
| 256. 粉刷房子 | Easy | 动态规划 |
| 257. 二叉树的所有路径 | Easy | 深搜 |
| 258. 各位相加 | Easy | 数学 |
| 260. 只出现一次的数字 III | Medium | 位运算 |
| 264. 丑数 II | Medium | 动态规划+三指针 |
| 268. 缺失数字 | Medium | 位运算 |
| 270. 最接近的二叉搜索树值 | Easy | 二分查找 |
| 274. H 指数 | Medium | 二分查找 |
| 275. H指数 II | Medium | 二分查找 |
| 276. 栅栏涂色 | Easy | 动态规划 |
| 278. 第一个错误的版本 | Easy | 二分查找 |
| 279. 完全平方数 | Medium | 动态规划 |
| 284. 顶端迭代器 | Medium | 设计 |
| 287. 寻找重复数 | Medium | 二分查找 |
| 292. Nim 游戏 | Easy | 极大极小化 |
| 303. 区域和检索 - 数组不可变 | Easy | 动态规划 |
| 304. 二维区域和检索 - 矩阵不可变 | Medium | 动态规划 |
| 306. 累加数 | Medium | DFS |
| 307. 区域和检索 - 数组可修改 | Medium | 树状数组 |
| 309. 最佳买卖股票时机含冷冻期 | Medium | 动态规划 |
| 310. 最小高度树 | Medium | 拓扑排序变体 |
| 312. 戳气球 | Hard | 动态规划 |
| 313. 超级丑数 | Medium | 数组、DP |
| 315. 计算右侧小于当前元素的个数 | Hard | 树状数组 |
| 316. 去除重复字母 | Medium | 单调栈 |
| 318. 最大单词长度乘积 | Medium | 位运算 |
| 321. 拼接最大数 | Hard | 单调栈 |
| 322. 零钱兑换 | Medium | 动态规划 |
| 324. 摆动排序 II | Medium | 排序 |
| 327. 区间和的个数 | Hard | 树状数组 |
| 328. 奇偶链表 | Medium | 链表 |
| 329. 矩阵中的最长递增路径 | Hard | 深搜/拓扑排序 |
| 331. 验证二叉树的前序序列化 | Medium | 栈/字符串 |
| 332. 重新安排行程 | Medium | 欧拉回路、深搜 |
| 337. 打家劫舍 III | Medium | 树形DP |
| 338. 比特位计数 | Medium | 位运算+动态规划 |
| 341. 扁平化嵌套列表迭代器 | Medium | 设计 |
| 342. 4的幂 | Easy | 位运算 |
| 343. 整数拆分 | Medium | 动态规划/数学 |
| 344. 反转字符串 | Easy | 双指针 |
| 347. 前 K 个高频元素 | Medium | 堆 |
| 349. 两个数组的交集 | Easy | 集合 |
| 350. 两个数组的交集 II | Easy | 排序/哈希表 |
| 354. 俄罗斯套娃信封问题 | Hard | 动规 |
| 355. 设计推特 | Medium | 设计 |
| 357. 计算各个位数不同的数字个数 | Medium | 动态规划 |
| 367. 有效的完全平方数 | Easy | 数学 |
| 368. 最大整除子集 | Medium | 动态规划 |
| 371. 两整数之和 | Easy | 位运算 |
| 372. 超级次方 | Medium | 数学 |
| 374. 猜数字大小 | Easy | 二分查找 |
| 375. 猜数字大小 II | Medium | 动态规划 |
| 376. 摆动序列 | Medium | 动态规划 |
| 377. 组合总和 Ⅳ | Medium | 动态规划 |
| 378. 有序矩阵中第K小的元素 | Medium | 二分查找 |
| 385. 迷你语法分析器 | Medium | 栈/字符串 |
| 389. 找不同 | Easy | 位运算 |
| 392. 判断子序列 | Medium | 动态规划 |
| 393. UTF-8 编码验证 | Medium | 位运算 |
| 394. 字符串解码 | Medium | 栈/字符串 |
| 397. 整数替换 | Medium | 位运算、动态规划 |
| 399. 除法求值 | Medium | 并查集 |
| 400. 第N个数字 | Medium | 数学 |
| 401. 二进制手表 | Easy | 位运算 |
| 402. 移掉K位数字 | Medium | 贪心 |
| 403. 青蛙过河 | Hard | 记忆化搜索/动规 |
| 404. 左叶子之和 | Easy | 树 |
| 405. 数字转换为十六进制数 | Easy | 位运算 |
| 406. 根据身高重建队列 | Medium | 贪心 |
| 410. 分割数组的最大值 | Hard | 动态规划 |
| 415. 字符串相加 | Easy | 字符串/模拟 |
| 416. 分割等和子集 | Medium | 动态规划 |
| 417. 太平洋大西洋水流问题 | Medium | 广搜 |
| 421. 数组中两个数的最大异或值 | Medium | 位运算/字典树 |
| 424. 替换后的最长重复字符 | Medium | 滑动窗口 |
| 429. N叉树的层序遍历 | Medium | 广搜 |
| 430. 扁平化多级双向链表 | Medium | 链表 |
| 435. 无重叠区间 | Medium | 贪心 |
| 436. 寻找右区间 | Medium | 二分查找 |
| 437. 路径总和 III | Medium | 树 |
| 441. 排列硬币 | Easy | 数学 |
| 445. 两数相加 II | Medium | 链表 |
| 446. 等差数列划分 II - 子序列 | Hard | 动态规划 |
| 452. 用最少数量的箭引爆气球 | Medium | 贪心 |
| 454. 四数相加 II | Medium | 二分查找 |
| 455. 分发饼干 | Easy | 贪心 |
| 456. 132模式 | Medium | 栈 |
| 459. 重复的子字符串 | Easy | 字符串 |
| 461. 汉明距离 | Easy | 位运算 |
| 464. 我能赢吗 | Medium | 动态规划 |
| 467. 环绕字符串中唯一的子字符串 | Medium | 动态规划 |
| 474. 一和零 | Medium | 动态规划 |
| 475. 供暖器 | Easy | 二分查找 |
| 476. 数字的补数 | Easy | 位运算 |
| 477. 汉明距离总和 | Medium | 位运算 |
| 478. 在圆内随机生成点 | Medium | 数学 |
| 486. 预测赢家 | Medium | 动态规划 |
| 491. 递增子序列 | Medium | 回溯+剪枝 |
| 493. 翻转对 | Hard | 分治+二分查找+树状数组 |
| 496. 下一个更大元素 I | Easy | 栈 |
| 497. 非重叠矩形中的随机点 | Medium | 二分查找/设计 |
| 501. 二叉搜索树中的众数 | Easy | 树/Morris中序遍历 |
| 503. 下一个更大元素 II | Medium | 栈 |
| 508. 出现次数最多的子树元素和 | Medium | 树 |
| 513. 找树左下角的值 | Medium | 广搜 |
| 514. 自由之路 | Hard | 动态规划 |
| 515. 在每个树行中找最大值 | Medium | 广搜 |
| 516. 最长回文子序列 | Medium | 动态规划 |
| 523. 连续的子数组和 | Medium | 动态规划 |
| 524. 通过删除字母匹配到字典里最长单词 | Medium | 排序 |
| 526. 优美的排列 | Medium | 回溯 |
| 528. 按权重随机选择 | Medium | 二分查找/随机数 |
| 529. 扫雷游戏 | Medium | 广搜 |
| 530. 二叉搜索树的最小绝对差 | Easy | 树 |
| 535. TinyURL 的加密与解密 | Medium | 数学 |
| 537. 复数乘法 | Medium | 数学 |
| 538. 把二叉搜索树转换为累加树 | Easy | 树 |
| 542. 01 矩阵 | Medium | 广搜 |
| 543. 二叉树的直径 | Easy | 树 |
| 546. 移除盒子 | Hard | 动态规划 |
| 547. 朋友圈 | Medium | 并查集 |
| 553. 最优除法 | Medium | 数学 |
| 557. 反转字符串中的单词 III | Easy | 字符串 |
| 559. N叉树的最大深度 | Easy | 广搜 |
| 563. 二叉树的坡度 | Easy | 树 |
| 567. 字符串的排列 | Medium | 滑动窗口 |
| 572. 另一个树的子树 | Easy | 树 |
| 576. 出界的路径数 | Medium | 动态规划 |
| 592. 分数加减运算 | Medium | 数学 |
| 593. 有效的正方形 | Medium | 数学 |
| 598. 范围求和 II | Easy | 数学/短板效应 |
| 617. 合并二叉树 | Easy | 树 |
| 621. 任务调度器 | Medium | 贪心 |
| 622. 设计循环队列 | Medium | 设计 |
| 632. 最小区间 | Hard | 堆 |
| 636. 函数的独占时间 | Medium | 栈 |
| 637. 二叉树的层平均值 | Easy | 树 |
| 638. 大礼包 | Medium | 动态规划 |
| 640. 求解方程 | Medium | 数学 |
| 641. 设计循环双端队列 | Medium | 设计 |
| 645. 错误的集合 | Easy | 数学 |
| 646. 最长数对链 | Medium | 动态规划 |
| 647. 回文子串 | Medium | 动态规划 |
| 648. 单词替换 | Medium | 字典树 |
| 649. Dota2 参议院 | Medium | 模拟+贪心 |
| 650. 只有两个键的键盘 | Medium | 深搜+剪枝/数学 |
| 652. 寻找重复的子树 | Medium | 序列化 |
| 655. 输出二叉树 | Medium | 树 |
| 657. 机器人能否返回原点 | Easy | 字符串 |
| 658. 找到 K 个最接近的元素 | Medium | 二分查找 |
| 659. 分割数组为连续子序列 | Medium | 贪心 |
| 662. 二叉树最大宽度 | Medium | 树 |
| 673. 最长递增子序列的个数 | Medium | 动态规划 |
| 676. 实现一个魔法字典 | Medium | 字典树 |
| 679. 24 点游戏 | Hard | 回溯 |
| 682. 棒球比赛 | Easy | 栈 |
| 684. 冗余连接 | Medium | 并查集 |
| 685. 冗余连接 II | Hard | 并查集 |
| 688. “马”在棋盘上的概率 | Medium | 动态规划 |
| 690. 员工的重要性 | Easy | 广搜 |
| 691. 贴纸拼词 | Hard | 状压DP+BFS |
| 693. 交替位二进制数 | Easy | 位运算 |
| 696. 计数二进制子串 | Easy | 字符串 |
| 698. 划分为k个相等的子集 | Medium | 动态规划 |
| 703. 数据流中的第K大元素 | Easy | 设计 |
| 704. 二分查找 | Easy | 二分查找 |
| 707. 设计链表 | Easy | 设计 |
| 712. 两个字符串的最小ASCII删除和 | Medium | 动态规划 |
| 714. 买卖股票的最佳时机含手续费 | Medium | 动态规划 |
| 718. 最长重复子数组 | Medium | 动态规划 |
| 720. 词典中最长的单词 | Easy | 字典树 |
| 721. 账户合并 | Medium | 并查集+Hash |
| 725. 分隔链表 | Medium | 链表 |
| 733. 图像渲染 | Easy | 深搜 |
| 735. 行星碰撞 | Medium | 栈 |
| 738. 单调递增的数字 | Medium | 贪心 |
| 739. 每日温度 | Medium | 栈 |
| 740. 删除与获得点数 | Medium | 动态规划 |
| 743. 网络延迟时间 | Medium | 最短路径 |
| 744. 寻找比目标字母大的最小字母 | Easy | 二分查找 |
| 746. 使用最小花费爬楼梯 | Easy | 动态规划 |
| 752. 打开转盘锁 | Medium | 广搜 |
| 756. 金字塔转换矩阵 | Medium | 位运算+深搜 |
| 762. 二进制表示中质数个计算置位 | Easy | 位运算 |
| 763. 划分字母区间 | Medium | 贪心 |
| 764. 最大加号标志 | Medium | 动态规划 |
| 767. 重构字符串 | Medium | 贪心+桶排序 |
| 775. 全局倒置与局部倒置 | Medium | 数学/树状数组 |
| 784. 字母大小写全排列 | Easy | 位运算 |
| 785. 判断二分图 | Medium | 广搜、并查集 |
| 787. K 站中转内最便宜的航班 | Medium | 动态规划 |
| 789. 逃脱阻碍者 | Medium | 数学 |
| 790. 多米诺和托米诺平铺 | Medium | 动态规划 |
| 797. 所有可能的路径 | Medium | 回溯 |
| 799. 香槟塔 | Medium | 动态规划 |
| 801. 使序列递增的最小交换次数 | Medium | 动态规划 |
| 808. 分汤 | Medium | 动态规划 |
| 813. 最大平均值和的分组 | Medium | 动态规划 |
| 820. 单词的压缩编码 | Medium | 后缀+字典树 |
| 826. 安排工作以达到最大收益 | Medium | 双指针/二分 |
| 834. 树中距离之和 | Hard | 树形DP |
| 837. 新21点 | Medium | 概率DP |
| 838. 推多米诺 | Medium | 动态规划 |
| 841. 钥匙和房间 | Medium | 深搜 |
| 842. 将数组拆分成斐波那契序列 | Medium | DFS |
| 843. 猜猜这个单词 | Hard | 极大极小化 |
| 844. 比较含退格的字符串 | Easy | 栈 |
| 845. 数组中的最长山脉 | Medium | 动态规划 |
| 851. 喧闹和富有 | Medium | 记忆化搜索/拓扑排序 |
| 852. 山脉数组的峰顶索引 | Easy | 二分查找 |
| 853. 车队 | Medium | 排序+单调栈 |
| 856. 括号的分数 | Medium | 栈 |
| 867. 转置矩阵 | Easy | 数组 |
| 860. 柠檬水找零 | Easy | 贪心 |
| 861. 翻转矩阵后的得分 | Medium | 贪心 |
| 863. 二叉树中所有距离为 K 的结点 | Medium | 坐标化 |
| 868. 二进制间距 | Easy | 数学 |
| 869. 重新排序得到 2 的幂 | Medium | 数学 |
| 870. 优势洗牌 | Medium | 贪心 |
| 873. 最长的斐波那契子序列的长度 | Medium | 动态规划 |
| 874. 模拟行走机器人 | Easy | 贪心 |
| 875. 爱吃香蕉的珂珂 | Medium | 二分查找 |
| 876. 链表的中间结点 | Easy | 链表 |
| 877. 石子游戏 | Medium | 动态规划/记忆化搜索/前缀和 |
| 880. 索引处的解码字符串 | Medium | 字符串 |
| 881. 救生艇 | Medium | 贪心 |
| 885. 螺旋矩阵 III | Medium | 数学/数组 |
| 887. 鸡蛋掉落 | Hard | 动规 |
| 892. 三维形体的表面积 | Easy | 数学 |
| 894. 所有可能的满二叉树 | Medium | 树/递归 |
| 898. 子数组按位或操作 | Medium | 位运算+unordered_set |
| 901. 股票价格跨度 | Medium | 栈 |
| 907. 子数组的最小值之和 | Medium | 栈 |
| 908. 最小差值 I | Easy | 数学 |
| 909. 蛇梯棋 | Medium | 广搜 |
| 910. 最小差值 II | Medium | 贪心 |
| 911. 在线选举 | Medium | 二分查找 |
| 913. 猫和老鼠 | Hard | 极大极小化 |
| 914. 卡牌分组 | Easy | 最大公约数 |
| 919. 完全二叉树插入器 | Medium | 树 |
| 921. 使括号有效的最少添加 | Medium | 贪心 |
| 922. 按奇偶排序数组 II | Easy | 排序 |
| 930. 和相同的二元子数组 | Medium | 前缀和 |
| 931. 下降路径最小和 | Medium | 动态规划 |
| 932. 漂亮数组 | Medium | 分治 |
| 933. 最近的请求次数 | Easy | 队列 |
| 934. 最短的桥 | Medium | 广搜 |
| 935. 骑士拨号器 | Medium | 动态规划 |
| 944. 删列造序 | Easy | 贪心 |
| 946. 验证栈序列 | Medium | 栈 |
| 947. 移除最多的同行或同列石头 | Medium | 并查集+Hash |
| 948. 令牌放置 | Medium | 贪心 |
| 955. 删列造序 II | Medium | 贪心 |
| 956. 最高的广告牌 | Hard | 动态规划 |
| 959. 由斜杠划分区域 | Medium | 并查集 |
| 967. 连续差相同的数字 | Medium | 动态规划 |
| 968. 监控二叉树 | Hard | 树 |
| 969. 煎饼排序 | Medium | 排序 |
| 970. 强整数 | Easy | 数学 |
| 973. 最接近原点的 K 个点 | Medium | 分治 |
| 976. 三角形的最大周长 | Easy | 数学 |
| 978. 最长湍流子数组 | Medium | 动态规划 |
| 979. 在二叉树中分配硬币 | Medium | 树 |
| 980. 不同路径 III | Hard | 回溯 |
| 981. 基于时间的键值存储 | Medium | 设计/二分 |
| 983. 最低票价 | Medium | 动态规划 |
| 984. 不含 AAA 或 BBB 的字符串 | Medium | 贪心 |
| 987. 二叉树的垂序遍历 | Medium | 坐标+排序 |
| 990. 等式方程的可满足性 | Medium | 并查集 |
| 991. 坏了的计算器 | Medium | 贪心 |
| 992. K 个不同整数的子数组 | Hard | 滑窗 |
| 993. 二叉树的堂兄弟节点 | Easy | 坐标化 |
| 994. 腐烂的橘子 | Medium | 广搜 |
| 996. 正方形数组的数目 | Hard | 回溯 |
| 1002. 查找常用字符 | Easy | 字符串/数组 |
| 1003. 检查替换后的词是否有效 | Medium | 栈 |
| 1004. 最大连续1的个数 III | Medium | 滑动窗口 |
| 1005. K 次取反后最大化的数组和 | Easy | 贪心 |
| 1006. 笨阶乘 | Medium | 数学/模拟 |
| 1008. 前序遍历构造二叉搜索树 | Medium | 树 |
| 1009. 十进制整数的反码 | Easy | 数学 |
| 1011. 在 D 天内送达包裹的能力 | Medium | 二分查找 |
| 1015. 可被 K 整除的最小整数 | Medium | 数学 |
| 1017. 负二进制转换 | Medium | 数学 |
| 1019. 链表中的下一个更大节点 | Medium | 单调栈 |
| 1021. 删除最外层的括号 | Easy | 字符串 |
| 1022. 从根到叶的二进制数之和 | Easy | 树 |
| 1023. 驼峰式匹配 | Easy | 字符串 |
| 1024. 视频拼接 | Medium | 动态规划 |
| 1025. 除数博弈 | Easy | 数学/动态规划 |
| 1027. 最长等差数列 | Medium | 动态规划 |
| 1029. 两地调度 | Easy | 贪心 |
| 1030. 距离顺序排列矩阵单元格 | Easy | 排序 |
| 1033. 移动石子直到连续 | Easy | 脑筋急转弯 |
| 1037. 有效的回旋镖 | Easy | 数学 |
| 1039. 多边形三角剖分的最低得分 | Medium | 动态规划 |
| 1040. 移动石子直到连续 II | Medium | 滑动窗口 |
| 1043. 分隔数组以得到最大和 | Medium | 动态规划 |
| 1046. 最后一块石头的重量 | Easy | 贪心 |
| 1047. 删除字符串中的所有相邻重复项 | Easy | 栈 |
| 1048. 最长字符串链 | Medium | 动态规划 |
| 1049. 最后一块石头的重量 II | Medium | 动态规划 |
| 1052. 爱生气的书店老板 | Medium | 滑动窗口 |
| 1053. 交换一次的先前排列 | Medium | 贪心 |
| 1064. 不动点 | Easy | 二分查找 |
| 1079. 活字印刷 | Medium | 回溯+剪枝 |
| 1081. 不同字符的最小子序列 | Medium | 单调栈 |
| 1090. 受标签影响的最大值 | Medium | 贪心 |
| 1091. 二进制矩阵中的最短路径 | Medium | 广搜 |
| 1093. 大样本统计 | Medium | 数学 |
| 1094. 拼车 | Medium | 贪心 |
| 1104. 二叉树寻路 | Medium | 树 |
| 1105. 填充书架 | Medium | 动态规划 |
| 1111. 有效括号的嵌套深度 | Medium | 贪心 |
| 1122. 数组的相对排序 | Easy | 排序 |
| 1124. 表现良好的最长时间段 | Medium | 栈 |
| 1129. 颜色交替的最短路径 | Medium | 广搜 |
| 1130. 叶值的最小代价生成树 | Medium | 动态规划 |
| 1131. 绝对值表达式的最大值 | Medium | 位运算+数学 |
| 1139. 最大的以 1 为边界的正方形 | Medium | 动态规划 |
| 1140. 石子游戏 II | Medium | 动态规划 |
| 1143. 最长公共子序列 | Medium | 动态规划 |
| 1150. 检查一个数是否在数组中占绝大多数 | Easy | 二分查找 |
| 1154. 一年中的第几天 | Easy | 数学 |
| 1155. 掷骰子的N种方法 | Medium | 动态规划 |
| 1171. 从链表中删去总和值为零的连续节点 | Medium | 链表 |
| 1175. 质数排列 | Easy | 数学 |
| 1186. 删除一次得到子数组最大和 | Medium | 动态规划 |
| 1190. 反转每对括号间的子串 | Medium | 栈 |
| 1191. K 次串联后最大子数组之和 | Medium | 动态规划 |
| 1201. 丑数 III | Medium | 数学+容斥原理+二分查找 |
| 1202. 交换字符串中的元素 | Medium | 并查集 |
| 1208. 尽可能使字符串相等 | Medium | 滑动窗口 |
| 1209. 删除字符串中的所有相邻重复项 II | Medium | 栈 |
| 1217. 玩筹码 | Medium | 贪心 |
| 1218. 最长定差子序列 | Medium | 动态规划变体 |
| 1219. 黄金矿工 | Medium | 回溯 |
| 1221. 分割平衡字符串 | Easy | 贪心 |
| 1223. 掷骰子模拟 | Medium | 动态规划 |
| 1227. 飞机座位分配概率 | Medium | 动态规划 |
| 1234. 替换子串得到平衡字符串 | Medium | 滑动窗口 |
| 1237. 找出给定方程的正整数解 | Easy | 数学 |
| 1239. 串联字符串的最大长度 | Medium | 位运算+暴力 |
| 1240. 铺瓷砖 | Hard | 动态规划 |
| 1247. 交换字符使得字符串相同 | Medium | 贪心 |
| 1249. 移除无效的括号 | Medium | 栈 |
| 1253. 重构 2 行二进制矩阵 | Medium | 贪心 |
| 1261. 在受污染的二叉树中查找元素 | Medium | 树 |
| 1262. 可被三整除的最大和 | Medium | 动态规划 |
| 1269. 停在原地的方案数 | Hard | 动规 |
| 1276. 不浪费原料的汉堡制作方案 | Medium | 贪心 |
| 1277. 统计全为 1 的正方形子矩阵 | Medium | 动态规划 |
| 1282. 用户分组 | Medium | 贪心 |
| 1283. 使结果不超过阈值的最小除数 | Medium | 二分查找 |
| 1286. 字母组合迭代器 | Medium | 设计 |
| 1290. 二进制链表转整数 | Easy | 位运算 |
| 1291. 顺次数 | Medium | 枚举 |
| 1292. 元素和小于等于阈值的正方形的最大边长 | Medium | 前缀和+二分 |
| 1296. 划分数组为连续数字的集合 | Medium | 贪心+Hash+模拟 |
| 1297. 子串的最大出现次数 | Medium | 位运算 |
| 1300. 转变数组后最接近目标值的数组和 | Medium | 二分 |
| 1305. 两棵二叉搜索树中的所有元素 | Medium | 排序 |
| 1306. 跳跃游戏 III | Medium | 广搜 |
| 1310. 子数组异或查询 | Medium | 位运算+前缀和 |
| 1311. 获取你好友已观看的视频 | Medium | 广搜 |
| 1314. 矩阵区域和 | Medium | 动态规划 |
| 1317. 将整数转换为两个无零整数的和 | Easy | 数学 |
| 1318. 或运算的最小翻转次数 | Medium | 位运算 |
| 1319. 连通网络的操作次数 | Medium | 并查集 |
| 1329. 将矩阵按对角线排序 | Medium | 排序 |
| 1337. 方阵中战斗力最弱的 K 行 | Easy | 排序 |
| 1338. 数组大小减半 | Medium | 贪心 |
| 1339. 分裂二叉树的最大乘积 | Medium | 动态规划/数学 |
| 1351. 统计有序矩阵中的负数 | Easy | 二分查找 |
| 1353. 最多可以参加的会议数目 | Medium | 贪心 |
| 1356. 根据数字二进制下 1 的数目排序 | Easy | 位运算 |
| 1362. 最接近的因数 | Medium | 数学 |
| 1366. 通过投票对团队排名 | Medium | 排序 |
| 1367. 二叉树中的列表 | Medium | 动态规划/链表/二叉树 |
| 1370. 上升下降字符串 | Easy | 字符串 |
| 1372. 二叉树中的最长交错路径 | Medium | 动态规划/二叉树/深搜 |
| 1381. 设计一个支持增量操作的栈 | Medium | 栈 |
| 1386. 安排电影院座位 | Medium | 贪心 |
| 1387. 将整数按权重排序 | Medium | 排序 |
| 1390. 四因数 | Medium | 数学 |
| 1391. 检查网格中是否存在有效路径 | Medium | 广搜 |
| 1400. 构造 K 个回文字符串 | Medium | 贪心 |
| 1403. 非递增顺序的最小子序列 | Easy | 贪心 |
| 1405. 最长快乐字符串 | Medium | 贪心 |
| 1410. HTML 实体解析器 | Medium | 字符串 |
| 1414. 和为 K 的最少斐波那契数字数目 | Medium | 贪心 |
| 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串 | Medium | 回溯 |
| 1423. 可获得的最大点数 | Medium | 动态规划 |
| 1424. 对角线遍历 II | Medium | 排序 |
| 1433. 检查一个字符串是否可以打破另一个字符串 | Medium | 贪心 |
| 1438. 绝对差不超过限制的最长连续子数组 | Medium | 滑动窗口 |
| 1441. 用栈操作构建数组 | Easy | 栈 |
| 1447. 最简分数 | Medium | 数学 |
| 1452. 收藏清单 | Medium | 排序 |
| 1456. 定长子串中元音的最大数目 | Medium | 滑动窗口 |
| 1471. 数组中的 k 个最强值 | Medium | 排序 |
| 1473. 粉刷房子 III | Hard | 动规 |
| 1477. 找两个和为目标值且不重叠的子数组 | Medium | 动态规划 |
| 1481. 不同整数的最少数目 | Medium | 排序 |
| 1482. 制作 m 束花所需的最少天数 | Medium | 二分查找 |
| 1491. 去掉最低工资和最高工资后的工资平均值 | Easy | 排序 |
| 1498. 满足条件的子序列数目 | Medium | 滑动窗口 |
| 1502. 判断能否形成等差数列 | Easy | 排序 |
| 1504. 统计全 1 子矩形 | Medium | 动态规划 |
| 1508. 子数组和排序后的区间和 | Medium | 排序 |
| 1528. 重新排列字符串 | Easy | 排序 |
| 1530. 好叶子节点对的数量 | Medium | 树 |
| 1544. 整理字符串 | Easy | 栈 |
| 1561. 你可以获得的最大硬币数目 | Medium | 排序 |
| 1621. 大小为 K 的不重叠线段的数目 | Medium | 动态规划 |
| 1626. 无矛盾的最佳球队 | Medium | 动态规划 |
| 1631. 最小体力消耗路径 | Medium | 优先队列+DP |
| 1636. 按照频率将数组升序排序 | Easy | 排序 |
| 1637. 两点之间不包含任何点的最宽垂直面积 | Medium | 排序 |
| 1641. 统计字典序元音字符串的数目 | Medium | 动态规划 |
| 1658. 将 x 减到 0 的最小操作数 | Medium | 哈希表/滑动窗口 |
| 1664. 生成平衡数组的方案数 | Medium | 动态规划/前缀和 |
| 1674. 使数组互补的最少操作次数 | Medium | 差分数组 |
| 1705. 吃苹果的最大数目 | Medium | 优先队列 |
| 1706. 球会落何处 | Medium | 模拟 |
| 1707. 与数组中元素的最大异或值 | Hard | 字典树 |
| 1723. 完成所有工作的最短时间 | Hard | 动规 |
| 5471. 和为目标值的最大数目不重叠非空子数组数目 | Medium | 动态规划 |
| 5520. 拆分字符串使唯一子字符串的数目最大 | Medium | 回溯 |
| 5631. 跳跃游戏 VI | Medium | 动态规划/优先队列/单调队列 |
| 5642. 大餐计数 | Medium | 贪心 |
| 5643. 将数组分成三个子数组的方案数 | Medium | 前缀和+二分 |
| 5644. 得到子序列的最少操作次数 | Hard | 哈希+二分/LCS |
| 面试题 01.05. 一次编辑 | Medium | 字符串 |
| 面试题 02.01. 移除重复节点 | Easy | 链表 |
| 面试题 02.08. 环路检测 | Medium | 链表 |
| 面试题 03.01. 三合一 | Easy | 设计 |
| 面试题 03.02. 栈的最小值 | Easy | |
| 面试题 03.04. 化栈为队 | Easy | 栈 |
| 面试题 03.06. 动物收容所 | Easy | 设计 |
| 面试题 04.03. 特定深度节点链表 | Medium | 广搜+链表 |
| 面试题32 - I. 从上到下打印二叉树 II | Medium | 广搜 |
| 面试题32 - II. 从上到下打印二叉树 II | Easy | 广搜 |
| 面试题32 - III. 从上到下打印二叉树 III | Medium | 广搜 |
| 面试题14- I. 剪绳子 | Medium | 数学 |
| 面试题14- II. 剪绳子 II | Medium | 数学 |
| 面试题 08.01. 三步问题 | Easy | 动态规划 |
| 面试题 08.02. 迷路的机器人 | Medium | 动态规划 |
| 面试题 08.03. 魔术索引 | Easy | 二分查找 |
| 面试题 08.04. 幂集 | Medium | 回溯 |
| 面试题 08.07. 无重复字符串的排列组合 | Medium | 回溯 |
| 面试题 08.08. 有重复字符串的排列组合 | Medium | 回溯 |
| 面试题 08.09. 括号 | Medium | 回溯 |
| 面试题 08.11. 硬币 | Medium | 动态规划 |
| 面试题 08.12. 八皇后 | Hard | 回溯 |
| 面试题 08.14. 布尔运算 | Medium | 动态规划 |
| 面试题 10.03. 搜索旋转数组 | Medium | 二分查找 |
| 面试题 10.05. 稀疏数组搜索 | Easy | 二分查找 |
| 面试题 10.09. 排序矩阵查找 | Medium | 二分查找 |
| 面试题 16.05. 阶乘尾数 | Easy | 数学 |
| 面试题 16.06. 最小差 | Medium | 双指针 |
| 面试题 16.07. 最大数值 | Easy | 数学 |
| 面试题 16.11. 跳水板 | Medium | 数学 |
| 面试题 16.17. 连续数列 | Easy | 动态规划 |
| 面试题 16.19. 水域大小 | Medium | 广搜 |
| 面试题 16.25. LRU缓存 | Medium | 设计 |
| 面试题17. 打印从1到最大的n位数 | Easy | 数学 |
| 面试题 17.06. 2出现的次数 | Medium | 数学 |
| 面试题 17.07. 婴儿名字 | Medium | 并查集 |
| 面试题 17.08. 马戏团人塔 | Medium | 二分/动态规划 |
| 面试题 17.09. 第 k 个数 | Medium | 数学 |
| 面试题 17.10. 主要元素 | Easy | 分治/数组 |
| 面试题 17.11. 单词距离 | Medium | 哈希+双指针 |
| 面试题 17.13. 恢复空格 | Medium | 动态规划+Trie |
| 面试题 17.14. 最小K个数 | Medium | 分治 |
| 面试题 17.16. 按摩师 | Easy | 动态规划 |
| 面试题 17.17. 多次搜索 | Medium | KMP/AC自动机 |
| 面试题 17.18. 最短超串 | Medium | 滑动窗口 |
| 面试题 17.22. 单词转换 | Medium | 双向广搜 |
| 面试题 17.23. 最大黑方阵 | Medium | 动态规划 |
| 面试题20. 表示数值的字符串 | Medium | 数学/确定有限状态自动机 |
| 面试题42. 连续子数组的最大和 | Easy | 动规 |
| 面试题47. 礼物的最大价值 | Medium | 动态规划 |
| 面试题49. 丑数 | Medium | 丑数 |
| 面试题62. 圆圈中最后剩下的数字 | Easy | 数学+迭代 |
| 面试题67. 把字符串转换成整数 | Medium | 数学 |
| 剑指 Offer 09. 用两个栈实现队列 | Easy | 设计/队列/栈 |
| 剑指 Offer 11. 旋转数组的最小数字 | Easy | 二分查找 |
| 剑指 Offer 25. 合并两个排序的链表 | Easy | 分治 |
| 剑指 Offer 30. 包含min函数的栈 | Easy | 栈 |
| 剑指 Offer 36. 二叉搜索树与双向链表 | Medium | 分治 |
| 剑指 Offer 38. 字符串的排列 | Medium | 回溯+剪枝 |
| 剑指 Offer 39. 数组中出现次数超过一半的数字 | Easy | 位运算/分治 |
| 剑指 Offer 40. 最小的k个数 | Easy | 分治 |
| 剑指 Offer 48. 最长不含重复字符的子字符串 | Medium | 滑动窗口 |
| 剑指 Offer 52. 两个链表的第一个公共节点 | Easy | 链表 |
| 剑指 Offer 53 - I. 在排序数组中查找数字 I | Easy | 二分查找 |
| 剑指 Offer 53 - II. 0～n-1中缺失的数字 | Easy | 二分查找 |
| 剑指 Offer 59 - I. 滑动窗口的最大值 | Easy | 滑动窗口 |
| 剑指 Offer 59 - II. 队列的最大值 | Medium | 滑动窗口 |
| 剑指 Offer 63. 股票的最大利润 | Medium | 动态规划 |
| 剑指 Offer 68 - II. 二叉树的最近公共祖先 | Easy | 树 |
| LCP 13. 寻宝 | Hard | 动态规划 |
| LCP 17. 速算机器人 | Easy | 数学 |
| LCP 18. 早餐组合 | Easy | 二分 |
| LCP 19. 秋叶收藏集 | Medium | 动态规划 |
| LCP 22. 黑白方格画 | Easy | 暴力 |
技巧
992. K 个不同整数的子数组
Description
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
Example
示例 1：
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：
输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
提示：
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length
Program
滑窗
错误代码
样例一就有问题[1,2,1,2]中的{2,1,2}无法识别orz。
1 | class Solution { |
详见官方题解
K个不同整数的子数组个数=最多包含K种不同整数的子数组个数-最多包含K-1种不同整数的子数组个数，妙啊！
1 | class Solution { |
LCP
LCP 17. 速算机器人
Description
小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字（记作 x 和 y），请小扣说出计算指令：
“A” 运算：使 x = 2 * x + y；
“B” 运算：使 y = 2 * y + x。
在本次游戏中，店家说出的数字为 x = 1 和 y = 0，小扣说出的计算指令记作仅由大写字母 A、B 组成的字符串 s，字符串中字符的顺序表示计算顺序，请返回最终 x 与 y 的和为多少。
Example
示例 1：
输入：s = “AB”
输出：4
解释：
经过一次 A 运算后，x = 2, y = 0。
再经过一次 B 运算，x = 2, y = 2。
最终 x 与 y 之和为 4。
提示：
0 <= s.length <= 10
s 由 ‘A’ 和 ‘B’ 组成
Program
1 | class Solution { |
LCP 18. 早餐组合
Description
小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
Example
示例 1：
输入：staple = [10,20,5], drinks = [5,5,2], x = 15
输出：6
解释：小扣有 6 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[0] = 10 + 5 = 15；
第 2 种方案：staple[0] + drinks[1] = 10 + 5 = 15；
第 3 种方案：staple[0] + drinks[2] = 10 + 2 = 12；
第 4 种方案：staple[2] + drinks[0] = 5 + 5 = 10；
第 5 种方案：staple[2] + drinks[1] = 5 + 5 = 10；
第 6 种方案：staple[2] + drinks[2] = 5 + 2 = 7。
示例 2：
输入：staple = [2,1,1], drinks = [8,9,5,1], x = 9
输出：8
解释：小扣有 8 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[2] = 2 + 5 = 7；
第 2 种方案：staple[0] + drinks[3] = 2 + 1 = 3；
第 3 种方案：staple[1] + drinks[0] = 1 + 8 = 9；
第 4 种方案：staple[1] + drinks[2] = 1 + 5 = 6；
第 5 种方案：staple[1] + drinks[3] = 1 + 1 = 2；
第 6 种方案：staple[2] + drinks[0] = 1 + 8 = 9；
第 7 种方案：staple[2] + drinks[2] = 1 + 5 = 6；
第 8 种方案：staple[2] + drinks[3] = 1 + 1 = 2；
提示：
1 <= staple.length <= 10^5
1 <= drinks.length <= 10^5
1 <= staple[i],drinks[i] <= 10^5
1 <= x <= 210^5
*Program**
二分
1 | class Solution { |
LCP 19. 秋叶收藏集
Description
小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
Example
示例 1：
输入：leaves = “rrryyyrryyyrr”
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 “rrryyyyyyyyrr”
示例 2：
输入：leaves = “ryr”
输出：0
解释：已符合要求，不需要额外操作
提示：
3 <= leaves.length <= 10^5
leaves 中只包含字符 ‘r’ 和字符 ‘y’
Program
动态规划
（1）DP[0][i]表示从头到尾全变红的最少次数；
（2）DP[1][i]表示从头变红，当前变黄（红黄）的最少次数；
（3）DP[2][i]表示之前是红黄，现在变成红黄红的最少次数；
时间复杂度：$O(n)$
1 | class Solution { |
LCP 22. 黑白方格画
Description
小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色，所选行数、列数均可为 0。
小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。
注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。
Example
示例 1：
输入：n = 2, k = 2
输出：4
解释：一共有四种不同的方案：
第一种方案：涂第一列；
第二种方案：涂第二列；
第三种方案：涂第一行；
第四种方案：涂第二行。
示例 2：
输入：n = 2, k = 1
输出：0
解释：不可行，因为第一次涂色至少会涂两个黑格。
示例 3：
输入：n = 2, k = 4
输出：1
解释：共有 2*2=4 个格子，仅有一种涂色方案。
限制：
1 <= n <= 6
0 <= k <= n * n
Program
暴力
取i行j列，所得黑格数为$i * n + j *(n - i)$，注意i,j从0开始，且$k=n * n$时答案为1！
1 | class Solution { |
单调队列
239. 滑动窗口最大值
Description
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
Example
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
1 | 滑动窗口的位置 最大值 |
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
Program
滑动窗口
一个很自然的思路就是维护一个保有索引的优先队列，然而时间复杂度为$O(n\log{k})$
线性复杂度的做法：
维护一个双端队列window：
（1）变量的最前端（也就是 window.front()）是此次遍历的最大值的下标
（2）当我们遇到新的数时，将新的数和双项队列的末尾（也就是window.back()）比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才停止。
（3）双项队列中的所有值都要在窗口范围内
特点1：队列头尾当前最大元素下标
特点2：队列降序排列，最大值、次大值…下标
例如
1 | [1,3,1,2,0,5] |
[[1,3,1],2,0,5]，队列3,1
[1,[3,1,2],0,5]，队列3,2
[1,3,[1,2,0],5]，剔除3，新进0，队列2,0
[1,3,1,[2,0,5]]，队列5
1 | class Solution { |
传统思路
超时
1 | class Solution { |
1438. 绝对差不超过限制的最长连续子数组
Description
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
Example
示例 1：
输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。
示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
Program
滑动窗口最大值变型题，所不同的是需要维护两个双端队列，分别保存窗口最大值和最小值（其实是窗口最值排序）
1 | class Solution { |
5631. 跳跃游戏 VI
Description
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
Example
示例 1：
输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
示例 2：
输入：nums = [10,-5,-2,4,0,3], k = 3
输出：17
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：
输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出：0
提示：
$1 <= nums.length, k <= 10^5$
$-10^4 <= nums[i] <= 10^4$
Program
设DP[i]=max(DP[j])+nums[i]，其中i-k<=j<i，时间复杂度：$O(n^2)$
优化如下
优先队列
max(DP[j])通过优先队列查找，且窗口外的dp值全部抛出
时间复杂度：$O(n\log{n})$
1 | class Solution { |
单调队列
窗口内的dp值保持单调递减，因为对于i-k<=j1,j2<i来说，如果dp[j1]<dp[j2]，那么j1就应当永久剔除，因为不影响后续结果；
时间复杂度：$O(n)$
1 | class Solution { |
剑指 Offer 59 - I. 滑动窗口的最大值
Description
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
Example
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
1 | 滑动窗口的位置 最大值 |
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
Program
保持双端队列首位为最大值，队列降序排列！
一个窗口中，较小的数在前面可以剔除，因为后续窗口移动过程中，一定不会是它为窗口最大值。
1 | class Solution { |
剑指 Offer 59 - II. 队列的最大值
Description
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
Example
示例 1：
输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]
限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
Program
双端队列保留队列最大值，思路与滑动窗口最大值相同。
1 | class MaxQueue { |
树状数组/差分数组
307. 区域和检索 - 数组可修改
Description
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
Example
示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:
数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
Program
1 | class NumArray { |
327. 区间和的个数
Description
给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
说明:
最直观的算法复杂度是 $O(n^2)$ ，请在此基础上优化你的算法。
Example
示例:
输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。
Program
树状数组
树状数组与线段树基于类似的思想，不过树状数组支持的基本查询为求出 [0, \textit{val}][0,val] 之间的整数数量。为了查询区间 [\textit{preSum}[j]-\textit{upper}, \textit{preSum}[j]-\textit{lower}][preSum[j]−upper,preSum[j]−lower] 内的整数数量，需要执行两次查询，即分别查询 [0, \textit{preSum}[j]-\textit{upper}-1][0,preSum[j]−upper−1] 区间的整数数量 LL 和[0,\textit{preSum}[j]-\textit{lower}][0,preSum[j]−lower]
1 | class Solution { |
1674. 使数组互补的最少操作次数
Description
给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。
如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。
返回使数组 互补 的 最少 操作次数。
Example
示例 1：
输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。
示例 2：
输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。
示例 3：
输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。
提示：
n == nums.length
$2 <= n <= 10^5$
$1 <= nums[i] <= limit <= 10^5$
n 是偶数。
Program
差分数组
假设 res[x] 表示的是，nums[i] + nums[n - 1 - i] 为 x 的时候，需要多少次操作。
我们只需要计算出所有的 x 对应的 res[x], 取最小值就好了。
根据题意，nums[i] + nums[n - 1 - i] 最小是 2，即将两个数都修改为 1；最大是 2 * limit，即将两个数都修改成 limit。
所以，res[x] 中 x 的取值范围是 [2, 2 * limit]。我们用一个 res[2 * limit + 1] 的数组就好。
关键是，如何求出每一个 res[x] 位置的值，即修改后互补的数字和为 x，需要多少操作？
为了叙述方便，假设 nums[i] 为 A；nums[n - 1 - i] 为 B。
显然有：
如果修改后两个数字的和是 A + B，我们使用的操作数是 0 (没有修改));
否则的话，如果修改后两个数字和在 [1 + min(A, B), limit + max(A, B)] 的范围，我们使用的操作数是 1 (只需要修改 A 或者 B 就好);
否则的话，如果修改后两个数字和在 [2, 2 * limit] 的范围，我们使用的操作数是 2(两个数字都要修改));
所以，我们的算法是遍历每一组 nums[i] 和 nums[n - 1 - i]，然后：
先将 [2, 2 * limit] 的范围需要的操作数 + 2；
之后，将 [1 + min(A, B), limit + max(A, B)] 的范围需要的操作数 - 1（即 2 - 1 = 1，操作 1 次）；
之后，将 [A + B] 位置的值再 -1（即 1 - 1 = 0，操作 0 次）。
可以看出，整个过程都是在做区间更新。最后，我们查询每一个位置的值，取最小值就好。
对于这个需求，我们当然可以使用线段树或者树状数组解决，但代码量稍大，且复杂度也是 O(nlogn) 的。
但是仔细观察，我们发现，我们只需要作区间更新，和单点查询。
对于这个需求，有一种非常常规的”数据结构“，叫差分数组，完全满足需求，并且编程极其简单，整体可以在 O(n) 的时间解决。
打上引号，是因为差分数组就是一个数组而已。
简单来说，差分数组 diff[i]，存储的是 res[i] - res[i - 1]；而差分数组 diff[0…i] 的和，就是 res[i] 的值。
大家可以用一个小数据试验一下，很好理解。
如果我们想给 [l, r] 的区间加上一个数字 a, 只需要 diff[l] += a，diff[r + 1] -= a。
这样做，diff[0…i] 的和，就是更新后 res[i] 的值。
1 | class Solution { |
前缀和
技巧：
（1）与和k相关，哈希表记录前缀和；找区间[i + 1, j]的和为k, 即preSum[j] - preSum[i] = k
（2）与倍数k相关，哈希表记录取模后的余数；找区间[i + 1, j]的和为k的倍数，即preSum[j] - preSum[i] = n * k
面试题 17.05. 字母与数字
Description
给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
Example
示例 1:
输入: [“A”,”1”,”B”,”C”,”D”,”2”,”3”,”4”,”E”,”5”,”F”,”G”,”6”,”7”,”H”,”I”,”J”,”K”,”L”,”M”]
输出: [“A”,”1”,”B”,”C”,”D”,”2”,”3”,”4”,”E”,”5”,”F”,”G”,”6”,”7”]
示例 2:
输入: [“A”,”A”]
输出: []
提示：
array.length <= 100000
Program
digitCnt - charCnt = diff
如果哈希表中找到diff说明[m[diff] + 1, i]是一个结果
1 | class Solution { |
1590. 使数组和能被 P 整除
Description
给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
子数组 定义为原数组中连续的一组元素。
Example
示例 1：
输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
示例 2：
输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。
示例 3：
输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。
示例 4：
输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。
示例 5：
输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109
Program
记录同一个余数最后出现的位置，M为整个数组对p取模的余数
前缀数组A的余数为x，前缀数组B(B>A)的余数为y=M+x，那么B-A的子数组为所求
1 | class Solution { |
930. 和相同的二元子数组
Description
在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组。
Example
示例：
输入：A = [1,0,1,0,1], S = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
提示：
A.length <= 30000
0 <= S <= A.length
A[i] 为 0 或 1
Program
记录每个前缀和出现的次数，dp思想求解
1 | class Solution { |
1497. 检查数组对是否可以被 k 整除
Description
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。
Example
示例 1：
输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出：true
解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。
示例 2：
输入：arr = [1,2,3,4,5,6], k = 7
输出：true
解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。
示例 3：
输入：arr = [1,2,3,4,5,6], k = 10
输出：false
解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。
示例 4：
输入：arr = [-10,10], k = 2
输出：true
示例 5：
输入：arr = [-1,1,-2,2,-3,3,-4,4], k = 3
输出：true
提示：
arr.length == n
1 <= n <= 10^5
n 为偶数
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5
Program
1 | class Solution { |
1010. 总持续时间可被 60 整除的歌曲
Description
在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。
Example
示例 1：
输入：[30,20,150,100,40]
输出：3
解释：这三对的总持续时间可被 60 整数：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60
示例 2：
输入：[60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。
提示：
1 <= time.length <= 60000
1 <= time[i] <= 500
Program
同上一题，记录余数，然后统计。
1 | class Solution { |
523. 连续的子数组和
Description
给定一个包含 非负数 的数组和一个目标 整数 k ，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n * k ，其中 n 也是一个整数。
Example
示例 1：
输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：
输入：[23,2,6,4,7], k = 6
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明：
数组的长度不会超过 10,000 。
你可以认为所有数字总和在 32 位有符号整数范围内。
Program
哈希表记录每个位置前缀和模k的结果对应的下标；
如果两个下标对应的模k结果相同，即[0, i]与[0,j]的前缀和模k结果相同，那么[i + 1, j]的和一定为k的倍数！
时间复杂度：$O(n)$
空间复杂度：$O(min(n, k))$
1 | class Solution { |
560. 和为K的子数组
Description
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
Example
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
Program
哈希表记录前缀和出现的次数
preSum[j] - preSum[i] == k说明[i + 1, j]子数组的和为k！
m[preSum]记录同一个前缀和出现的次数；
时间复杂度：$O(n)$
空间复杂度：$O(n)$
1 | class Solution { |
字典树
648. 单词替换
Description
在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子。
Example
示例 1：
输入：dictionary = [“cat”,”bat”,”rat”], sentence = “the cattle was rattled by the battery”
输出：”the cat was rat by the bat”
示例 2：
输入：dictionary = [“a”,”b”,”c”], sentence = “aadsfasf absbs bbab cadsfafs”
输出：”a a b c”
示例 3：
输入：dictionary = [“a”, “aa”, “aaa”, “aaaa”], sentence = “a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa”
输出：”a a a a a a a a bbb baba a”
示例 4：
输入：dictionary = [“catt”,”cat”,”bat”,”rat”], sentence = “the cattle was rattled by the battery”
输出：”the cat was rat by the bat”
示例 5：
输入：dictionary = [“ac”,”ab”], sentence = “it is abnormal that this solution is accepted”
输出：”it is ab that this solution is ac”
提示：
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写字母组成。
1 <= sentence.length <= 10^6
sentence 仅由小写字母和空格组成。
sentence 中单词的总量在范围 [1, 1000] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。
Program
思路
（1）根据字典进行前缀字典树构造，注意判断词根结尾；
（2）对句子中每个单词进行前缀判断即可，详见代码；
时间复杂度：$O(m+n)$，$m、n$分别是字典和句子的字母总数
1 | class Solution { |
676. 实现一个魔法字典
Description
实现一个带有buildDict, 以及 search方法的魔法字典。
对于buildDict方法，你将被给定一串不重复的单词来构建一个字典。
对于search方法，你将被给定一个单词，并且判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
Example
示例 1:
Input: buildDict([“hello”, “leetcode”]), Output: Null
Input: search(“hello”), Output: False
Input: search(“hhllo”), Output: True
Input: search(“hell”), Output: False
Input: search(“leetcoded”), Output: False
注意:
你可以假设所有输入都是小写字母 a-z。
为了便于竞赛，测试所用的数据量很小。你可以在竞赛结束后，考虑更高效的算法。
请记住重置MagicDictionary类中声明的类变量，因为静态/类变量会在多个测试用例中保留。 请参阅这里了解更多详情。
Program
错误思路：直接字典树递归
对于无需任何转换就能走通的搜索单词，将不能得到正确答案。
1 | class MagicDictionary { |
正确思路
对于搜索单词的每个字母进行递归深搜
1 | class MagicDictionary { |
720. 词典中最长的单词
Description
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
若无答案，则返回空字符串。
Example
示例 1：
输入：
words = [“w”,”wo”,”wor”,”worl”, “world”]
输出：”world”
解释：
单词”world”可由”w”, “wo”, “wor”, 和 “worl”添加一个字母组成。
示例 2：
输入：
words = [“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”]
输出：”apple”
解释：
“apply”和”apple”都能由词典中的单词组成。但是”apple”的字典序小于”apply”。
提示：
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
Program
1 | class Solution { |
421. 数组中两个数的最大异或值
Description
给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。
找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。
你能在O(n)的时间解决这个问题吗？
Example
示例:
输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28.
Program
参考大佬们的题解。
异或性质
1 | class Solution { |
前缀字典树
（1）对于数组的每个元素x，进行字典树构造；
（1）对于数组的每个元素x的每个高位bit，找其互补位，如果bit为1，找0，如果不存在找1；
1 | class Solution { |
1707. 与数组中元素的最大异或值
Description
给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
Example
示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
示例 2：
输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]
提示：
1 <= nums.length, queries.length <= 10^5
queries[i].length == 2
0 <= nums[j], xi, mi <= 10^9
Program
思路
0-1字典树优化，取互补操作
1 | class Solution { |
并查集
684. 冗余连接
Description
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
Example
示例 1：
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1 | 1 |
示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
1 | 5 - 1 - 2 |
注意:
输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。
Program
1 | class Solution { |
685. 冗余连接 II
Description
在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。
输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。
返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
Example
示例 1:
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
1
/
v v
2–>3
示例 2:
输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
^ |
| v
4 <- 3
注意:
二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。
Program
并查集
（1）有根树性质：
- 无有向环
- 无入度为2的节点，因为题目是有根树附加另一条边，这条边使得有根树不成立，所以入度最多为2
（2）首先统计入度，判断是否入度为2；
（3）如果入度为2，那么可以发现两条边(u1,v),(u2,v)使得v的入度为2，那么依次删掉这两条边，判断是否构成有根树即可；注意逆序遍历边
（4）如果没有入度为2，那么说明存在有向环，那么只要正序构建并查集，判断是否构成有向环的边即可，找到第一个构成环的边就是答案；
时间复杂度：$O(n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65class Solution {
public:
int n;
vector<int> father;
void init(){
father.resize(n+1, 0);
for(int i=0;i<=n;i++) father[i]=i;
}
int findFather(int x){
if(father[x]!=x){
father[x]=findFather(father[x]);
}
return father[x];
}
void unionSet(int x, int y){ //x为父节点，y为子节点
int fa=findFather(x);
int fb=findFather(y);
if(fa!=fb){
father[fb]=fa;
}
}
bool isSame(int u, int v){
int fa=findFather(u);
int fb=findFather(v);
return fa==fb;
}
//在有向图里找到删除的那条边，使其变成树
vector<int> getRemoveEdge(const vector<vector<int>>& edges){
init(); //初始化并查集
for(int i=0;i<n;i++){ //遍历所有边
if(isSame(edges[i][0], edges[i][1])){ //构成有向环
return edges[i];
}
unionSet(edges[i][0], edges[i][1]);
}
return {}; //无环
}
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deletEdge){
init(); //初始化并查集
for(int i=0;i<n;i++){
if(i==deletEdge) continue;
if(isSame(edges[i][0], edges[i][1])) return false; //构成有向环
unionSet(edges[i][0], edges[i][1]);
}
return true;
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
n=edges.size();
father.resize(n+1, 0);
vector<int> inDegree(n+1, 0);
for(int i=0;i<n;i++){
inDegree[edges[i][1]]++;
}
vector<int> vec;
for(int i=n-1;i>=0;i--){
if(inDegree[edges[i][1]]==2) vec.push_back(i);
}
//如果有入度为2的节点，那么一定是两条边中的一个
if(vec.size()>0){
if(isTreeAfterRemoveEdge(edges, vec[0])) return edges[vec[0]];
else return edges[vec[1]];
}
return getRemoveEdge(edges);
}
};队列
933. 最近的请求次数
Description
写一个 RecentCounter 类来计算最近的请求。
它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。
返回从 3000 毫秒前到现在的 ping 数。
任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。
保证每次对 ping 的调用都使用比之前更大的 t 值。
Example
示例：
输入：inputs = [“RecentCounter”,”ping”,”ping”,”ping”,”ping”], inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3,3]
提示：
每个测试用例最多调用 10000 次 ping。
每个测试用例会使用严格递增的 t 值来调用 ping。
每次调用 ping 都有 1 <= t <= 10^9。
Program
1 | class RecentCounter { |
状态压缩
691. 贴纸拼词
Description
我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。
你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。
如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。
拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。
Example
示例 1：
输入：
[“with”, “example”, “science”], “thehat”
输出：
3
解释：
我们可以使用 2 个 “with” 贴纸，和 1 个 “example” 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。
示例 2：
输入：
[“notice”, “possible”], “basicbasic”
输出：
-1
解释：
我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。
提示：
stickers 长度范围是 [1, 50]。
stickers 由小写英文单词组成（不带撇号）。
target 的长度在 [1, 15] 范围内，由小写字母组成。
在所有的测试案例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选取的，目标是两个随机单词的串联。
时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。
Program
BFS+状态压缩
（1）step[i]表示i(二进制1的位置表示与target的对应匹配)状态下的最少贴纸数量；
（2）BFS从0状态（无一个匹配）搜索，肯定是最短，即step[i]更新了一次，下次搜索到就不用更新了，之后的更新肯定不是最优；
（3）从长的单词开始搜索；
1 | class Solution { |
欧拉回路
332. 重新安排行程
Description
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。
说明:
- 如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
- 所有的机场都用三个大写字母表示（机场代码）。
- 假定所有机票至少存在一种合理的行程。
Example
示例 1:
输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
输出: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]
示例 2:
输入: [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
输出: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
解释: 另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]。但是它自然排序更大更靠后。
Program
1 | class Solution { |
排序
56. 合并区间
Description
给出一个区间的集合，请合并所有重叠的区间。
Example
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
提示：
intervals[i][0] <= intervals[i][1]
program
1 | class Solution { |
57. 插入区间
Description
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
Example
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
Program
1 | class Solution { |
75. 颜色分类
Description
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
Example
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
Program
1 | class Solution { |
147. 对链表进行插入排序
Description
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
Example
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
Progam
- 维护一个标兵节点，便于访问链表头，因为在插入排序的过程中，表头可能变化；
- 维护一个已排序链表尾节点，模拟数组插入排序，这样方便对链表待排序节点前后位置进行连接！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(head==NULL||head->next==NULL) return head;
ListNode* tHead=new ListNode(-1);
tHead->next=head;
ListNode* tail=head;// 已排序的最后一个节点
ListNode* now=head->next; //当前待排序的节点
while(now!=NULL){
ListNode* node=tHead;
while(node->next!=NULL&&node->next->val<now->val) node=node->next;
if(node==tail){
tail=now;
now=now->next;
continue;
}
tail->next=now->next;
now->next=node->next;
node->next=now;
now=tail->next;
}
return tHead->next;
}
};148. 排序链表
Description
在 $O(n\log{n})$ 时间复杂度和常数级空间复杂度下，对链表进行排序。
Example
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
Program
思路
（1）总体为数组版的非递归二路归并；
（2）每次选择两个长度最多为为step(最多：有的时候链表末尾元素不足)的链表进行合并；
（3）cut(p, n)：表示从p开始切除n个元素的链表，并返回后面的头结点，注意切出的链表尾部应当为NULL，注意处理！；merge则表示合并两个链表
时间复杂度：$O(n\log{n})$
空间复杂度：$O(1)$
1 | /** |
179. 最大数
Description
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
Example
示例 1:
输入: [10,2]
输出: 210
示例 2:
输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
Program
思路
首先整数转成字符串，然后按照字典序降序，但是类似于样例2，”34”,”30”,”3”这种情况就不行了，任何两个字符串a,b，如果a+b>b+a，那么a在前面。
1 | class Solution { |
220. 存在重复元素 III
Description
在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
如果存在则返回 true，不存在返回 false。
Example
示例 1:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false
Program
排序+暴力
时间复杂度：$O(n^2)$
1 | class Solution { |
滑动窗口
（1）$|nums[i] - nums[j]| <=t $等价于$nums[j]-t <= nums[i] <= nums[j]+t$
（2）窗口内的数有序，且找到当前窗口内大于等于$nums[j]-t$第一个数nums[i]，如果$nums[i]<=nums[j]+t$成立，那么说明存在；否则不存在。
时间复杂度：$O(n\log{k})$
1 | class Solution { |
242. 有效的字母异位词
Description
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
Example
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
Program
排序
时间复杂度：$O(n\log{n})$
1 | class Solution { |
哈希表
时间复杂度：$O(n)$
1 | class Solution { |
324. 摆动排序 II
Description
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
Example
示例 1:
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明:
你可以假设所有输入都会得到有效的结果。
进阶:
你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
Program
首先，我们可以很容易想到一种简单的解法：将数组进行排序，然后从中间位置进行等分（如果数组长度为奇数，则将中间的元素分到前面），然后将两个数组进行穿插。
例如：
对于数组[1, 5, 2, 4, 3]，我们将其排序，得到[1, 2, 3, 4, 5]，然后将其分割为[1, 2, 3]和[4, 5]，对两个数组进行穿插，得到[1, 4, 2, 5, 3]。
但是这一解法有一个问题，例如，对于数组[1, 2, 2, 3]，按照这种做法求得的结果仍为[1, 2, 2, 3]。如果题目不要求各元素严格大于或小于相邻元素，即，只要求nums[0] <= nums[1] >= nums[2] <= nums[3]…，那么这一解法是符合要求的，但题目要求元素相互严格大于或小于，那么需要稍微做一点改进。
为了方便阅读，我们在下文中定义较小的子数组为数组A，较大的子数组为数组B。显然，出现上述现象是因为nums中存在重复元素。实际上，由于穿插之后，相邻元素必来自不同子数组，所以A或B内部出现重复元素是不会出现上述现象的。所以，出现上述情况其实是因为数组A和数组B出现了相同元素，我们用r来表示这一元素。而且我们可以很容易发现，如果A和B都存在r，那么r一定是A的最大值，B的最小值，这意味着r一定出现在A的尾部，B的头部。其实，如果这一数字的个数较少，不会出现这一现象，只有当这一数字个数达到原数组元素总数的一半，才会在穿插后的出现在相邻位置。以下举几个例子进行形象地说明：
例如，对于数组[1,1,2,2,3,3],分割为[1,1,2]和[2,3,3]，虽然A和B都出现了2，但穿插后为[1,2,1,3,2,3]，满足要求。
而如果2的个数再多一些，即[1,1,2,2,2,3]，分割为[1,1,2]和[2,2,3]，最终结果为[1,2,1,2,2,3]，来自A的2和来自B的2出现在了相邻位置。
出现这一问题是因为重复数在A和B中的位置决定的，因为r在A尾部，B头部，所以如果r个数太多（大于等于(length(nums) + 1)/2），就可能在穿插后相邻。要解决这一问题，我们需要使A的r和B的r在穿插后尽可能分开。一种可行的办法是将A和B反序：
例如，对于数组[1,1,2,2,2,3]，分割为[1,1,2]和[2,2,3]，分别反序后得到[2, 1, 1]和[3, 2, 2]，此时2在A头部，B尾部，穿插后就不会发生相邻了。
当然，这只能解决r的个数等于(length(nums) + 1)/2的情况，如果r的个数大于(length(nums) + 1)/2，还是会出现相邻。但实际上，这种情况是不存在有效解的，也就是说，这种数组对于本题来说是非法的。
此时我们得到了第一个解法，由于需要使用排序，所以时间复杂度为O(NlogN)，由于需要存储A和B，所以空间复杂度为O(N)。
1 | class Solution { |
524. 通过删除字母匹配到字典里最长单词
Description
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
Example
示例 1:
输入:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]
输出:
“apple”
示例 2:
输入:
s = “abpcplea”, d = [“a”,”b”,”c”]
输出:
“a”
说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。
Program
思路
（1）题目意思“给定字符串删除某些字符”能够与字典中的字符串匹配，且要求匹配的字符最长，也就是说字典中匹配的字符串是给定字符串的子序列！且要求子序列尽可能最长！
（2）题目需要字典序小的最长匹配字符串，则需要先排序
（3）字典中每个字符串与给定字符进行比较，保留最长的那个即可
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
1 | class Solution { |
853. 车队
Description
N 辆车沿着一条车道驶向位于 target 英里之外的共同目的地。
每辆车 i 以恒定的速度 speed[i] （英里/小时），从初始位置 position[i] （英里） 沿车道驶向目的地。
一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车以相同的速度紧接着行驶。
此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。
车队 是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。
即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。
会有多少车队到达目的地?
Example
示例：
输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3
解释：
从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。
从 0 处开始的车无法追上其它车，所以它自己就是一个车队。
从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。
请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。
提示：
0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
所有车的初始位置各不相同。
Program
排序+单调栈
（1）首先，根据pos进行排序；
（2）然后计算各自的用时；
（3）从后往前实现单调递增栈：
- 因为后车追上前车时，后车将与前车同行同速，此时直接忽视后车即可；
- 如果后车和前车同样用时，忽略后车；
- 如果后车用时比前车大，则后车永远追不上前车，应当保留；
- 这个过程使用单调递增栈，注意后车追上前车，仅保留前车结果！
时间复杂度：$O(n\log{n})$，排序复杂度$O(n\log{n})$，遍历+栈总体复杂度$O(n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42**排序+单调栈**
（1）首先，根据pos进行排序；
（2）然后计算各自的用时；
（3）从后往前实现单调递增栈：
- 因为后车追上前车时，后车将与前车同行同速，此时直接忽视后车即可；
- 如果后车和前车同样用时，忽略后车；
- 如果后车用时比前车大，则后车永远追不上前车，应当保留；
- 这个过程使用单调递增栈，注意后车追上前车，仅保留前车结果！
时间复杂度：$O(n\log{n})$，排序复杂度$O(n\log{n})$，遍历+栈总体复杂度$O(n)$
```cpp
class Solution {
public:
struct Node{
int pos;
int speed;
Node(){}
Node(int _pos, int _speed):pos(_pos),speed(_speed){}
bool operator<(const Node& other) const{
return pos<other.pos;
}
};
int carFleet(int target, vector<int>& position, vector<int>& speed) {
int n=position.size();
vector<Node> vec;
for(int i=0;i<n;i++){
vec.push_back(Node(position[i], speed[i]));
}
sort(vec.begin(), vec.end()); //按照pos排序
vector<double> times;
for(int i=0;i<n;i++){ //计算各自用时
double time=(target-vec[i].pos)/(double)vec[i].speed;
times.push_back(time);
}
stack<double> stk;
for(int i=n-1;i>=0;i--){ //单调递增栈
if(stk.empty()||stk.top()<times[i]){
stk.push(times[i]);
} //注意后车不可能超过前车，只能与前车同速，故如果后车用时更少，忽略即可
}
return stk.size(); //栈中元素个数即最终答案
}
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35## 922. 按奇偶排序数组 II
**Description**
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
**Example**
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
提示：
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
**Program**
```cpp
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
vector<int> evens, odds;
for(int x:A){
if(x%2==0) evens.push_back(x);
else odds.push_back(x);
}
int p1=0,p2=0;
int n=A.size();
for(int i=0;i<n;i++){
if(i%2==0) A[i]=evens[p1++];
else A[i]=odds[p2++];
}
return A;
}
};969. 煎饼排序
Description
给定数组 A，我们可以对其进行煎饼翻转：我们选择一些正整数 k <= A.length，然后反转 A 的前 k 个元素的顺序。我们要执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 A 的排序。
返回能使 A 排序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * A.length 范围内的有效答案都将被判断为正确。
Example
示例 1：
输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 A = [3, 2, 4, 1]
第一次翻转后 (k=4): A = [1, 4, 2, 3]
第二次翻转后 (k=2): A = [4, 1, 2, 3]
第三次翻转后 (k=4): A = [3, 2, 1, 4]
第四次翻转后 (k=3): A = [1, 2, 3, 4]，此时已完成排序。
示例 2：
输入：[1,2,3]
输出：[]
解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如[3，3]，也将被接受。
提示：
1 <= A.length <= 100
A[i] 是 [1, 2, …, A.length] 的排列
Program
数学
（1）对区间[0,i]，找到最大值下标j：
（2）翻转[0,j]，将最大值移到第一个位置；
（3）翻转[0,i]，将最大值移到最后一个位置；
时间复杂度：$O(n^2)$
1 | class Solution { |
1030. 距离顺序排列矩阵单元格
Description
给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）
Example
示例 1：
输入：R = 1, C = 2, r0 = 0, c0 = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
示例 2：
输入：R = 2, C = 2, r0 = 0, c0 = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
示例 3：
输入：R = 2, C = 3, r0 = 1, c0 = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。
提示：
1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C
Program
1 | class Solution { |
1122. 数组的相对排序
Description
给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
Example
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
Program
1 | class Solution { |
1305. 两棵二叉搜索树中的所有元素
Description
给你 root1 和 root2 这两棵二叉搜索树。
请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.
Example
示例 1：
输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]
示例 2：
输入：root1 = [0,-10,10], root2 = [5,1,7,0,2]
输出：[-10,0,0,1,2,5,7,10]
示例 3：
输入：root1 = [], root2 = [5,1,7,0,2]
输出：[0,1,2,5,7]
示例 4：
输入：root1 = [0,-10,10], root2 = []
输出：[-10,0,10]
示例 5：
输入：root1 = [1,null,8], root2 = [8,1]
输出：[1,1,8,8]
提示：
每棵树最多有 5000 个节点。
每个节点的值在 [-10^5, 10^5] 之间。
Program
1 | /** |
1329. 将矩阵按对角线排序
Description
给你一个 m * n 的整数矩阵 mat ，请你将同一条对角线上的元素（从左上到右下）按升序排序后，返回排好序的矩阵。
Example
示例 1：
输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100
Program
1 | class Solution { |
1366. 通过投票对团队排名
Description
现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
排名规则如下：
参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。
请你返回能表示按排名系统 排序后 的所有团队排名的字符串。
Example
示例 1：
输入：votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”]
输出：”ACB”
解释：A 队获得五票「排位第一」，没有其他队获得「排位第一」，所以 A 队排名第一。
B 队获得两票「排位第二」，三票「排位第三」。
C 队获得三票「排位第二」，两票「排位第三」。
由于 C 队「排位第二」的票数较多，所以 C 队排第二，B 队排第三。
示例 2：
输入：votes = [“WXYZ”,”XYZW”]
输出：”XWYZ”
解释：X 队在并列僵局打破后成为排名第一的团队。X 队和 W 队的「排位第一」票数一样，但是 X 队有一票「排位第二」，而 W 没有获得「排位第二」。
示例 3：
输入：votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]
输出：”ZMNAGUEDSJYLBOPHRQICWFXTVK”
解释：只有一个投票者，所以排名完全按照他的意愿。
示例 4：
输入：votes = [“BCA”,”CAB”,”CBA”,”ABC”,”ACB”,”BAC”]
输出：”ABC”
解释：
A 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
B 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
C 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
完全并列，所以我们需要按照字母升序排名。
示例 5：
输入：votes = [“M”,”M”,”M”,”M”]
输出：”M”
解释：只有 M 队参赛，所以它排名第一。
提示：
1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length
votes[i][j] 是英文 大写 字母
votes[i] 中的所有字母都是唯一的
votes[0] 中出现的所有字母 同样也 出现在 votes[j] 中，其中 1 <= j < votes.length
Program
1 | class Solution { |
1387. 将整数按权重排序
Description
我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：
如果 x 是偶数，那么 x = x / 2
如果 x 是奇数，那么 x = 3 * x + 1
比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1）。
给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。
请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。
注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。
Example
示例 1：
输入：lo = 12, hi = 15, k = 2
输出：13
解释：12 的权重为 9（12 –> 6 –> 3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1）
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。
示例 2：
输入：lo = 1, hi = 1, k = 1
输出：1
示例 3：
输入：lo = 7, hi = 11, k = 4
输出：7
解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。
示例 4：
输入：lo = 10, hi = 20, k = 5
输出：13
示例 5：
输入：lo = 1, hi = 1000, k = 777
输出：570
提示：
1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1
Program
1 | class Solution { |
1424. 对角线遍历 II
Description
给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
Example
示例 1：
输入：nums = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,4,2,7,5,3,8,6,9]
示例 2：
输入：nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
输出：[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
示例 3：
输入：nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
输出：[1,4,2,5,3,8,6,9,7,10,11]
示例 4：
输入：nums = [[1,2,3,4,5,6]]
输出：[1,2,3,4,5,6]
提示：
1 <= nums.length <= 10^5
1 <= nums[i].length <= 10^5
1 <= nums[i][j] <= 10^9
nums 中最多有 10^5 个数字。
Program
1 | class Solution { |
1452. 收藏清单
Description
给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
Example
示例 1：
输入：favoriteCompanies = [[“leetcode”,”google”,”facebook”],[“google”,”microsoft”],[“google”,”facebook”],[“google”],[“amazon”]]
输出：[0,1,4]
解释：
favoriteCompanies[2]=[“google”,”facebook”] 是 favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] 的子集。
favoriteCompanies[3]=[“google”] 是 favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] 和 favoriteCompanies[1]=[“google”,”microsoft”] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。
示例 2：
输入：favoriteCompanies = [[“leetcode”,”google”,”facebook”],[“leetcode”,”amazon”],[“facebook”,”google”]]
输出：[0,1]
解释：favoriteCompanies[2]=[“facebook”,”google”] 是 favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] 的子集，因此，答案为 [0,1] 。
示例 3：
输入：favoriteCompanies = [[“leetcode”],[“google”],[“facebook”],[“amazon”]]
输出：[0,1,2,3]
提示：
1 <= favoriteCompanies.length <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= favoriteCompanies[i][j].length <= 20
favoriteCompanies[i] 中的所有字符串 各不相同 。
用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
所有字符串仅包含小写英文字母。
Program
1 | class Solution { |
1471. 数组中的 k 个最强值
Description
给你一个整数数组 arr 和一个整数 k 。
设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：
1 | |arr[i] - m| > |arr[j] - m| |
请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。
中位数 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于 ((n - 1) / 2) 的元素。
例如 arr = [6, -3, 7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，数组的中间位置为 m = ((5 - 1) / 2) = 2 ，中位数 arr[m] 的值为 6 。
例如 arr = [-7, 22, 17, 3]，n = 4：数组排序后得到 arr = [-7, 3, 17, 22] ，数组的中间位置为 m = ((4 - 1) / 2) = 1 ，中位数 arr[m] 的值为 3 。
Example
示例 1：
输入：arr = [1,2,3,4,5], k = 2
输出：[5,1]
解释：中位数为 3，按从强到弱顺序排序后，数组变为 [5,1,4,2,3]。最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。
注意，尽管 |5 - 3| == |1 - 3| ，但是 5 比 1 更强，因为 5 > 1 。
示例 2：
输入：arr = [1,1,3,5,5], k = 2
输出：[5,5]
解释：中位数为 3, 按从强到弱顺序排序后，数组变为 [5,5,1,1,3]。最强的两个元素是 [5, 5]。
示例 3：
输入：arr = [6,7,11,7,6,8], k = 5
输出：[11,8,6,6,7]
解释：中位数为 7, 按从强到弱顺序排序后，数组变为 [11,8,6,6,7,7]。
[11,8,6,6,7] 的任何排列都是正确答案。
示例 4：
输入：arr = [6,-3,7,2,11], k = 3
输出：[-3,11,2]
示例 5：
输入：arr = [-7,22,17,3], k = 2
输出：[22,17]
提示：
1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length
Program
1 | class Solution { |
1481. 不同整数的最少数目
Description
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
Example
示例 1：
输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
示例 2：
输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
提示：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length
Program
1 | class Solution { |
1491. 去掉最低工资和最高工资后的工资平均值
Description
给你一个整数数组 salary ，数组里每个数都是 唯一 的，其中 salary[i] 是第 i 个员工的工资。
请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。
Example
示例 1：
输入：salary = [4000,3000,1000,2000]
输出：2500.00000
解释：最低工资和最高工资分别是 1000 和 4000 。
去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500
示例 2：
输入：salary = [1000,2000,3000]
输出：2000.00000
解释：最低工资和最高工资分别是 1000 和 3000 。
去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000
示例 3：
输入：salary = [6000,5000,4000,3000,2000,1000]
输出：3500.00000
示例 4：
输入：salary = [8000,9000,2000,3000,6000,1000]
输出：4750.00000
提示：
3 <= salary.length <= 100
10^3 <= salary[i] <= 10^6
salary[i] 是唯一的。
与真实值误差在 10^-5 以内的结果都将视为正确答案。
Program
1 | class Solution { |
1502. 判断能否形成等差数列
Description
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
Example
示例 1：
输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：
输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。
提示：
2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6
Program
1 | class Solution { |
1508. 子数组和排序后的区间和
Description
给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。
请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
Example
示例 1：
输入：nums = [1,2,3,4], n = 4, left = 1, right = 5
输出：13
解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。
示例 2：
输入：nums = [1,2,3,4], n = 4, left = 3, right = 4
输出：6
解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。
示例 3：
输入：nums = [1,2,3,4], n = 4, left = 1, right = 10
输出：50
提示：
1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2
Program
1 | class Solution { |
1528. 重新排列字符串
Description
给你一个字符串 s 和一个 长度相同 的整数数组 indices 。
请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。
返回重新排列后的字符串。
Example
示例 1：
输入：s = “codeleet”, indices = [4,5,6,7,0,2,1,3]
输出：”leetcode”
解释：如图所示，”codeleet” 重新排列后变为 “leetcode” 。
示例 2：
输入：s = “abc”, indices = [0,1,2]
输出：”abc”
解释：重新排列后，每个字符都还留在原来的位置上。
示例 3：
输入：s = “aiohn”, indices = [3,1,4,2,0]
输出：”nihao”
示例 4：
输入：s = “aaiougrt”, indices = [4,0,2,6,7,3,1,5]
输出：”arigatou”
示例 5：
输入：s = “art”, indices = [1,0,2]
输出：”rat”
提示：
s.length == indices.length == n
1 <= n <= 100
s 仅包含小写英文字母。
0 <= indices[i] < n
indices 的所有的值都是唯一的（也就是说，indices 是整数 0 到 n - 1 形成的一组排列）。
Program
1 | class Solution { |
1561. 你可以获得的最大硬币数目
Description
有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
Alice 将会取走硬币数量最多的那一堆。
你将会取走硬币数量第二多的那一堆。
Bob 将会取走最后一堆。
重复这个过程，直到没有更多硬币。
给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
返回你可以获得的最大硬币数目。
Example
示例 1：
输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
示例 2：
输入：piles = [2,4,5]
输出：4
示例 3：
输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18
提示：
3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4
Program
1 | class Solution { |
1636. 按照频率将数组升序排序
Description
给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
请你返回排序后的数组。
Example
示例 1：
输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：’3’ 频率为 1，’1’ 频率为 2，’2’ 频率为 3 。
示例 2：
输入：nums = [2,3,1,3,2]
输出：[1,3,3,2,2]
解释：’2’ 和 ‘3’ 频率都为 2 ，所以它们之间按照数值本身降序排序。
示例 3：
输入：nums = [-1,1,-6,4,5,-6,1,4,1]
输出：[5,-1,4,4,-6,-6,1,1,1]
提示：
1 <= nums.length <= 100
-100 <= nums[i] <= 100
Program
1 | class Solution { |
1637. 两点之间不包含任何点的最宽垂直面积
Description
给你 n 个二维平面上的点 points ，其中 points[i] = [xi, yi] ，请你返回两点之间内部不包含任何点的 最宽垂直面积 的宽度。
垂直面积 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直面积 为宽度最大的一个垂直面积。
请注意，垂直区域 边上 的点 不在 区域内。
Example
示例 1：
输入：points = [[8,7],[9,9],[7,4],[9,7]]
输出：1
解释：红色区域和蓝色区域都是最优区域。
示例 2：
输入：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
输出：3
提示：
$n == points.length$
$2 <= n <= 10^5$
$points[i].length == 2$
$0 <= x_i, y_i <= 10^9$
Program
1 | class Solution { |
深搜
733. 图像渲染
Description
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
Example
示例 1:
输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。
注意:
image 和 image[0] 的长度在范围 [1, 50] 内。
给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。
Program
1 | class Solution { |
841. 钥匙和房间
Description
有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，…，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
最初，除 0 号房间外的其余所有房间都被锁住。
你可以自由地在房间之间来回走动。
如果能进入每个房间返回 true，否则返回 false。
Example
示例 1：
输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
示例 2：
输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
提示：
1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。
Program
1 | class Solution { |
双指针
11. 盛最多水的容器
Description
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
Example
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
Program
思路
（1）双指针left,right分别指向数组头尾；
（2）每次高度更小的索引更新，$min(height[left],height[right])*(right-left)$，因为高度大的肯定面积更小，高度小的更新后才可能出现更大的值；
如下图所示，在一开始，我们考虑相距最远的两个柱子所能容纳水的面积。水的宽度是两根柱子之间的距离 d = 8d=8；水的高度取决于两根柱子之间较短的那个，即左边柱子的高度 h = 3。水的面积就是3×8=24。
- 如果选择固定一根柱子，另外一根变化，水的面积会有什么变化吗？稍加思考可得：
- 当前柱子是最两侧的柱子，水的宽度 dd 为最大，其他的组合，水的宽度都比这个小。
- 左边柱子较短，决定了水的高度为 3。如果移动左边的柱子，新的水面高度不确定，一定不会超过右边的柱子高度 7。
- 如果移动右边的柱子，新的水面高度一定不会超过左边的柱子高度 3，也就是不会超过现在的水面高度。
由此可见，如果固定左边的柱子，移动右边的柱子，那么水的高度一定不会增加，且宽度一定减少，所以水的面积一定减少。这个时候，左边的柱子和任意一个其他柱子的组合，其实都可以排除了。也就是我们可以排除掉左边的柱子了。
这个排除掉左边柱子的操作，就是双指针代码里的 i++。i 和 j 两个指针中间的区域都是还未排除掉的区域。随着不断的排除，i 和 j 都会往中间移动。当 i 和 j 相遇，算法就结束了
1 | class Solution { |
31. 下一个排列
Description
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1 | 1,2,3 → 1,3,2 |
Program
思路
（1）我们希望下一个数比当前数大，因此需要从后面选择一个较大的数跟前面的小数交换；
（2）而我们又希望下一个数增加的幅度尽可能小
（3）从后往前遍历，查找可能的较小大数与前面的小数交换；
算法过程：
（1）从后往前查找第一个相邻升序的元素对(i, j)，满足A[i]<A[j]。
（2）[j,end)从后往前找第一个满足A[i]<A[k]的k，二者交换；
（3）交换后，[j,end]肯定是降序的，所以只需要逆置就可以。
（4）注意已经是最大排列的情况。
1 | class Solution { |
344. 反转字符串
Description
写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
Example
示例 1：
输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：
输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
Program
1 | class Solution { |
面试题 16.06. 最小差
Description
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
Example
示例：
输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出： 3，即数值对(11, 8)
提示：
1 <= a.length, b.length <= 100000
-2147483648 <= a[i], b[i] <= 2147483647
正确结果在区间[-2147483648, 2147483647]内
Program
排序+双指针
详见代码
1 | class Solution { |
面试题 17.11. 单词距离
Description
有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
Example
示例：
输入：words = [“I”,”am”,”a”,”student”,”from”,”a”,”university”,”in”,”a”,”city”], word1 = “a”, word2 = “student”
输出：1
提示：
words.length <= 100000
Program
哈希+双指针
（1）哈希表建立重复单词出现的位置；
（2）双指针查找两个待查单词的索引数组（升序）：
由于索引数组有序，比较两个索引的时候，A[i]<B[j]则i++，反之j++；这是因为要使得abs(A[i]-B[j])绝对值最小，较小的数组指针后移才能缩小。
时间复杂度：$O(m+n)$
1 | class Solution { |
栈/字符串
32. 最长有效括号
Description
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
Example
示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:
输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”
Program
1 | class Solution { |
43. 字符串相乘
Description
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
Example
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
Program
1 | class Solution { |
71. 简化路径
Description
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
Example
示例 1：
输入：”/home/“
输出：”/home”
解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入：”/../“
输出：”/“
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入：”/home//foo/“
输出：”/home/foo”
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入：”/a/./b/../../c/“
输出：”/c”
示例 5：
输入：”/a/../../b/../c//.//“
输出：”/c”
示例 6：
输入：”/a//b////c/d//././/..”
输出：”/a/b/c”
Program
思路
首先，预处理字符串，剔除‘/’，然后通过栈（这里为了方便用双端队列）进行简化操作：
- ①如果遇到’.’，不加入最终路径；
- ②如果遇到’..’，返回上一级目录，即从当前路径中删除最后一级目录（当前路径不是根目录，如果是根目录不变，这里用双端队列dq表示当前路径）；
- ③如果遇到一般的字符串，加入当前路径；
最后通过加入必要的’/‘得到最终简化的路径。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public:
string simplifyPath(string path) {
vector<string> vec;
string str;
int n=path.length();
for(int i=0;i<n;i++){ //处理'/'之间的字符串，用str保存，如果str为空不加入数组vec
if(path[i]=='/'){
if(str!="") vec.push_back(str);
str="";
}else str+=path[i];
}
if(path[n-1]!='/'&&str!="") vec.push_back(str); //最后一个字符串
deque<string> dq;//用双端队列替换栈，方便操作
for(int i=0;i<vec.size();i++){
if(vec[i]==".") continue; //当前目录不加入栈
if(vec[i]=="..") {if(dq.size()>0)dq.pop_back();continue;} //跳至上一目录
dq.push_back(vec[i]); //加入目录
}
str="/";
for(int i=0;i<dq.size();i++){
str+=dq[i];
if(i!=dq.size()-1) str+='/';
}
return str;
}
};150. 逆波兰表达式求值
Description
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
Example
示例 1：
输入: [“2”, “1”, “+”, “3”, “*”]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入: [“4”, “13”, “5”, “/“, “+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入: [“10”, “6”, “9”, “3”, “+”, “-11”, “*”, “/“, “*”, “17”, “+”, “5”, “+”]
输出: 22
解释:
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
Program
1 | class Solution { |
214. 最短回文串
Description
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
Example
示例 1:
输入: “aacecaaa”
输出: “aaacecaaa”
示例 2:
输入: “abcd”
输出: “dcbabcd”
Program
暴力
找前缀为最长回文的位置，然后拼接！
时间复杂度：$O(n^2)$
1 | class Solution { |
KMP的next前后缀求法
首先一个字符串与其逆串拼接肯定是回文串，问题使未必是最小！！
例如：s=abcd与rs=dcba，拼接为dcbaabcd，明显有冗余，冗余的部分为s前缀和rs后缀公共的部分！
那么需要求出这个公共部分最大的部分剔除就是答案了！
那么怎么求呢？
s+rs=abcddcba，要求最大重叠前后缀，与KMP的next数组一致！！！
但是得注意这里直接拼接s+rs会导致可能最长前后缀长度超过原本s的长度，所以中间插入”#”即可，即s+”#”+rs=abcd#dcba，再来求其最长重叠前后缀，就是next数组计算了！
时间复杂度：$O(n)$
1 | class Solution { |
316. 去除重复字母
Description
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
Example
示例 1：
输入：s = “bcabc”
输出：”abc”
示例 2：
输入：s = “cbacdcbc”
输出：”acdb”
提示：
1 <= s.length <= 104
s 由小写英文字母组成
Program
思路
题意需要三个条件：
（1）去重；
（2）相对位置不变；
（3）字典序最小；
由前两个条件只需要维护一个单调栈，遇到更小的字母，前面较大的字母出栈，即可，注意判重；
第三个条件则需要在出栈时检查即将出栈的元素是否后续没有该字母，如果是，不出栈，否则出栈。
1 | class Solution { |
321. 拼接最大数
Description
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
Example
示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]
Program
单调栈
（1）老套路，与但数组下求保留k个数要求序列最大类似，这里为两个数组；
（2）分治：第一个数组保留i个，第二个数组保留k-i个，使得各自满足最大序列；
（3）合并：这里不同于归并排序的直接比较两个数组索引下的单个值，而需要考虑字典序最大！即取字典序较大的数组的头元素！
1 | class Solution { |
331. 验证二叉树的前序序列化
Description
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
1 | _9_ |
例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,,3” 。
Example
示例 1:
输入: “9,3,4,#,#,1,#,#,2,#,6,#,#”
输出: true
示例 2:
输入: “1,#”
输出: false
示例 3:
输入: “9,#,#,1”
输出: false
Program
利用前序的特性，无需考虑数据
一个正确的二查数据结构，空节点数目=非空节点数目+1，其中空节点就是指”#”。
所以考虑前序遍历先跟后左右子树的特性，遇到数字就push，遇到“#”就pop，这一点与前序遍历的非递归栈实现相同（先遍历到左子树最左边的节点，当为空时就pop，这里就相当于遇到“#”就pop掉当前根结点，然后进入当前右子树）。
- 遇到“#”，如果栈为空，return i == n-1，即判断是否是最后一个，是则为正确结构，否则错误；
- 遇到数字，push即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
bool isValidSerialization(string preorder) {
int n=preorder.length();
stack<int> st;
for(int i=0;i<n;i++){
if(preorder[i]=='#'){
if(st.empty()) return i==n-1;
else{
st.pop();
i++;//跳过逗号
}
}else{
while(i<n&&preorder[i]!=',') i++; //需要跳过逗号分隔符
st.push(0);
}
}
return false;
}
};385. 迷你语法分析器
Description
给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。
列表中的每个元素只可能是整数或整数嵌套列表
提示：你可以假定这些字符串都是格式良好的：
- 字符串非空
- 字符串不包含空格
- 字符串只包含数字0-9、[、-、,、]
Example
示例 1：
给定 s = “324”,
你应该返回一个 NestedInteger 对象，其中只包含整数值 324。
示例 2：
给定 s = “[123,[456,[789]]]”,
返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
1 | 1. 一个 integer 包含值 123 |
Program
字符串处理+栈
（1）字符串是纯数字，直接返回NestInteger的单整数版本；
（2）如果遇到“[”，则表示需要嵌套整数，即必须将默认的单整数版本通过add()转成嵌套链表，即使遇到”[]”这种也要转!，然后将其压入栈
（3）每次遇到“,”，判断当前str是否为空，不为空表示就是数字，栈顶嵌套链表add()加入该单整数版本的NestedInteger；
（4）如果遇到“]”：
①如果str非空，需要将其作为NestInteger通过add()加入栈顶嵌套链表；
②如果栈元素个数多余1，则需要将栈顶元素出栈，新的栈顶元素add()昂刚出栈的栈顶元素，完成嵌套链表合并。
因为例如”[123,456,[788,799,833],[[]],10,[]]”，在833后的第一个”]”就需要先合并两个嵌套，使得栈顶元素降维下一层。
1 | /** |
394. 字符串解码
Description
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
Example
示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”
示例 2：
输入：s = “3[a2[c]]”
输出：”accaccacc”
示例 3：
输入：s = “2[abc]3[cd]ef”
输出：”abcabccdcdcdef”
示例 4：
输入：s = “abc3[cd]xyz”
输出：”abccdcdcdxyz”
Program
思路
（1）遍历字符串，遇到数字就开始处理该满足编码规则的字符串：
- 先处理数字；
- 后处理[]内的字符串，这里很容易想到递归处理，因为[]内的字符串也是一个有效的字符串，也需要解码！但是需要注意[]内可能有嵌套！
- 重复k次；
（2）输出结果
时间复杂度：$O(N+n)$，N为解码后的字符串长度，n为原字符串长度。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public:
int sToi(string str){
int ans=0;
for(int i=0;i<str.length();i++){
ans=ans*10+str[i]-'0';
}
return ans;
}
string decodeString(string s) {
int n=s.length();
string res;
for(int i=0;i<n;i++){
if(s[i]>='0'&&s[i]<='9'){
string numStr;
while(s[i]>=0&&s[i]<='9'){ //处理数字
numStr+=s[i];
i++;
}
int start=i; //[坐标
int nBracket=0;
while(i<n){ //处理数字后的第一个[]，这里得注意可能有嵌套[]，故需要类似栈的判断
if(s[i]=='[') nBracket++;
else if(s[i]==']') nBracket--;
if(nBracket==0) break;
i++;
}
string str=decodeString(s.substr(start+1, i-start-1));//递归
int k=sToi(numStr);
for(int j=0;j<k;j++) res+=str;
}else{
res+=s[i];
}
}
return res;
}
};456. 132模式
Description
给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
Example
示例1:
输入: [1, 2, 3, 4]
输出: False
解释: 序列中不存在132模式的子序列。
示例 2:
输入: [3, 1, 4, 2]
输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:
输入: [-1, 3, 2, 0]
输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
Program
单调递减栈
（1）维护一个数组minVec，minVec[i]表示在截止到索引i时的当前最小值，因为需要$a_i<a_k<a_j$，贪心的希望a_i越小越好；
（2）对$i<j<k$，需要$a_i<a_k<a_j$，那么考虑位置$j$，将数组分成左右两部分$[0,j-1],[j+1,n-1]$，由(1)可以找到左边小于nums[j]的值，那么只需要判断右边[j+1,n-1]这部分是否存在满足$a_i<a_k<a_j$的$k$。
（3）从左往右遍历不好操作，那么考虑从右往左遍历；
对于$j$，满足$a_i<a_k<a_j$的nums[i]就是minVec[j]，即需要满足minVec[j]<nums[j]。那么右边也就是先遍历的部分nums[k]需要满足$minVec[j]<nums[k]<nums[j]$，这些nums[k]就是我们需要维护的部分，假设有这么个数据结构存储这一部分，那么只要找到一个就说明存在132模式，直接返回即可！ 否则，即minVec[j]==nums[j]（由于minVec的性质，不可能大于），不可能满足直接跳过。
（4）现在考虑如何维护这一部分。
- ①首先这一部分需要尽可能小，但是要先满足$minVec[j]<nums[k]$，不满足直接丢弃不满足此条件的那些nums[k]；
- ②然后看是否满足$nums[k]<nums[j]$，如果满足直接返回，否则，即$nums[k]>=nums[j]$，那么nums[j]就是上一步我们所说的尽可能小的部分，需要保留，那么原本维护的nums[k]呢？我们知道从右往左遍历，minVec[j]是递增的，那么当前保留的尽可能小的nums[j]只是满足当前的$minVec[j]<nums[j]<=nums[k]$，对于下一个minVec[j-1]就不一定满足$minVec[j]<nums[j]$了！所以也需要保留满足①的那部分nums[k]。
（5）好了，现在我们知道需要维护相对于j的哪一部分nums[k]了，其实已经基本出来了数据结构了——单调递减栈！
时间复杂度：$O(n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
bool find132pattern(vector<int>& nums) {
if(nums.size()==0) return false;
vector<int> minVec;//minVec[i]为截止目前i索引所得最小值
int n=nums.size();
minVec.push_back(nums[0]);
for(int i=1;i<n;i++) minVec.push_back(min(minVec.back(), nums[i]));
stack<int> desSt;//单调递减栈
for(int i=n-1;i>=0;i--){
if(minVec[i]<nums[i]){
while(!desSt.empty()&&minVec[i]>=desSt.top()) desSt.pop();//所有小于等于minVec[i]的都出栈
if(!desSt.empty()&&desSt.top()<nums[i]) return true;
desSt.push(nums[i]);
}
}
return false;
}
};459. 重复的子字符串
Description
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
Example
示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。
示例 2:
输入: “aba”
输出: False
示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)
Program
思路
如果s满足题目要求，那么s至少由其子串重复两次，那么两个s拼接后出去首尾各一个字符，如果该字符串中能够找到s，说明s满足题意。
时间复杂度：$O(mn)$。
- KMP 算法虽然有着良好的理论时间复杂度上限，但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时，我们需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度；
1
2
3
4
5
6
7
8
9class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n=s.length();
string str=s+s;
str=str.substr(1, 2*n-2);
return str.find(s)!=string::npos;
}
};
KMP
1 | class Solution { |
496. 下一个更大元素 I
Description
给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
Example
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。
Program
暴力
时间复杂度：$O(n^2)$
1 | class Solution { |
单调栈
Next Greater Element问题模板。
时间复杂度：$O(m+n)$
1 | class Solution { |
503. 下一个更大元素 II
Description
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
Example
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
Program
1 | class Solution { |
1 | class Solution { |
557. 反转字符串中的单词 III
Description
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
Example
示例：
输入：”Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”
提示：
在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
Program
1 | class Solution { |
636. 函数的独占时间
Description
给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。
每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。
日志是具有以下格式的字符串：function_id：start_or_end：timestamp。例如：”0:start:0” 表示函数 0 从 0 时刻开始运行。”0🔚0” 表示函数 0 在 0 时刻结束。
函数的独占时间定义是在该方法中花费的时间，调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。
Example
示例 1:
输入:
n = 2
logs =
[“0:start:0”,
“1:start:2”,
“1🔚5”,
“0🔚6”]
输出:[3, 4]
说明：
函数 0 在时刻 0 开始，在执行了 2个时间单位结束于时刻 1。
现在函数 0 调用函数 1，函数 1 在时刻 2 开始，执行 4 个时间单位后结束于时刻 5。
函数 0 再次在时刻 6 开始执行，并在时刻 6 结束运行，从而执行了 1 个时间单位。
所以函数 0 总共的执行了 2 +1 =3 个时间单位，函数 1 总共执行了 4 个时间单位。
说明：
输入的日志会根据时间戳排序，而不是根据日志Id排序。
你的输出会根据函数Id排序，也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。
两个函数不会在同时开始或结束。
函数允许被递归调用，直到运行结束。
1 <= n <= 100
Program
栈
（1）首先，整体思路肯定是栈，遇到start就入栈，遇到end就出栈，计算时间；
（2）关键问题在于同一个id的开始结束之中有其他id(可能与自己相同)的函数，且有可能是顺序的也可能是嵌套的;
（3）形象的用括号表示“[[[[], []]],[],[]]”，其中每一对“[]”表示函数调用开始和结束，例如我们计算最外层的函数所学时间，必须记录其中顺序包含的每个子“[]”所独占时间，最终最外层独占时间是其起始结束之差再减去子函数所占时间，同理，每个子函数所独占时间也是这么算的！
（4）除了栈外，我们需要记录子函数占用时间：用一个结构体记录id，起始时间戳，子函数占用时间。同时用数组记录每次一个函数独占时间
（5）算法过程：
①遇到start入栈；
②遇到end出栈：
- 如果栈非空，刚出栈的调用时间加入栈顶元素的substime中，表示栈顶函数调用了刚刚出栈的函数，需要记录其所占时间（非独占）；
- 无论栈空否，刚出栈的函数调用完毕，计算其独占时间：end-start+1-subtime，即自身函数占用时间-其调用子函数调用的时间，将其通过数组进行累加（因为可能会递归调用自身）。
时间复杂度：$O(n)$
1 | class Solution { |
657. 机器人能否返回原点
Description
在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。
Example
示例 1:
输入: “UD”
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。
示例 2:
输入: “LL”
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。
Program
1 | class Solution { |
682. 棒球比赛
Description
你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
2. “+”（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
3. “D”（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. “C”（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
Example
示例 1:
输入: [“5”,”2”,”C”,”D”,”+”]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
示例 2:
输入: [“5”,”-2”,”4”,”C”,”D”,”9”,”+”,”+”]
输出: 27
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到-2分。总数是：3。
第3轮：你可以得到4分。总和是：7。
操作1：第3轮的数据无效。总数是：3。
第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
第5轮：你可以得到9分。总数是：8。
第6轮：你可以得到-4 + 9 = 5分。总数是13。
第7轮：你可以得到9 + 5 = 14分。总数是27。
注意：
输入列表的大小将介于1和1000之间。
列表中的每个整数都将介于-30000和30000之间。
Program
1 | class Solution { |
696. 计数二进制子串
Description
给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。
Example
示例 1 :
输入: “00110011”
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
示例 2 :
输入: “10101”
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
注意：
s.length 在1到50,000之间。
s 只包含“0”或“1”字符。
Program
1 | class Solution { |
735. 行星碰撞
Description
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
Example
示例 1:
输入:
asteroids = [5, 10, -5]
输出: [5, 10]
解释:
10 和 -5 碰撞后只剩下 10。 5 和 10 永远不会发生碰撞。
示例 2:
输入:
asteroids = [8, -8]
输出: []
解释:
8 和 -8 碰撞后，两者都发生爆炸。
示例 3:
输入:
asteroids = [10, 2, -5]
输出: [10]
解释:
2 和 -5 发生碰撞后剩下 -5。10 和 -5 发生碰撞后剩下 10。
示例 4:
输入:
asteroids = [-2, -1, 1, 2]
输出: [-2, -1, 1, 2]
解释:
-2 和 -1 向左移动，而 1 和 2 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
说明:
数组 asteroids 的长度不超过 10000。
每一颗行星的大小都是非零整数，范围是 [-1000, 1000] 。
Program
思路
栈：这里只有左边的球向右移动，右边的球向左移动才会发生碰撞，反之不会发生碰撞。
时间复杂度：$O(n)$，for循环是$O(n)$的，while里在for的整个过程中是$O(n)$的，因为每个元素最多入栈出栈一次。
1 | class Solution { |
739. 每日温度
Description
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
Example
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
Program
1 | class Solution { |
844. 比较含退格的字符串
Description
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
Example
示例 1：
输入：S = “ab#c”, T = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：S = “ab##”, T = “c#d#”
输出：true
解释：S 和 T 都会变成 “”。
示例 3：
输入：S = “a##c”, T = “#a#c”
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：
输入：S = “a#c”, T = “b”
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 ‘#’。
进阶：
你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
Program
思路
从后往前遍历，遇到’#’则计数，遇到普通字符则判断计数是否为0，否则跳过；
时间复杂度：$O(n)$
空间复杂度：$O(1)$
1 | class Solution { |
856. 括号的分数
Description
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
- () 得 1 分。
- AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
- (A) 得 2 * A 分，其中 A 是平衡括号字符串。
Example
示例 1：
输入： “()”
输出： 1
示例 2：
输入： “(())”
输出： 2
示例 3：
输入： “()()”
输出： 2
示例 4：
输入： “(()(()))”
输出： 6
提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50
Program
栈
维护一个栈，栈内元素表示以该对括号内的分数：
（1）遇到左括号，入栈，初试化括号内的分数为0；
（2）遇到右括号，出栈，出栈前的栈顶元素值为当前一对括号包含的所有子括号的分数，判断该score是否为0：
- score==0,表示当前括号内没有嵌套，应当向上将包含该括号的上一级括号的分数st.top()+1——如果栈为空，则直接最终结果ans+=1;
- score>0,表示当前括号内有嵌套的分数为score，更新栈顶元素（包含当前括号的上一级括号分数）st.top()+2score —— 如果栈为空，则直接最终结果ans+=2score；
时间复杂度：$O(n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
int scoreOfParentheses(string S) {
stack<int> st;
int ans=0;
for(int i=0;i<S.length();i++){
if(S[i]=='('){
st.push(0);
}else{
int score=st.top();st.pop();
if(score==0){
if(st.empty()) ans+=1;
else st.top()+=1;
}else{
if(st.empty()) ans+=2*score;
else st.top()+=2*score;
}
}
}
return ans;
}
};880. 索引处的解码字符串
Description
给定一个编码字符串 S。请你找出 解码字符串 并将其写入磁带。解码时，从编码字符串中 每次读取一个字符 ，并采取以下步骤：
- 如果所读的字符是字母，则将该字母写在磁带上。
- 如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。
- 现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。
Example
示例 1：
输入：S = “leet2code3”, K = 10
输出：”o”
解释：
解码后的字符串为 “leetleetcodeleetleetcodeleetleetcode”。
字符串中的第 10 个字母是 “o”。
示例 2：
输入：S = “ha22”, K = 5
输出：”h”
解释：
解码后的字符串为 “hahahaha”。第 5 个字母是 “h”。
示例 3：
输入：S = “a2345678999999999999999”, K = 1
输出：”a”
解释：
解码后的字符串为 “a” 重复 8301530446056247680 次。第 1 个字母是 “a”。
提示：
2 <= S.length <= 100
S 只包含小写字母与数字 2 到 9 。
S 以字母开头。
1 <= K <= 10^9
题目保证 K 小于或等于解码字符串的长度。
解码后的字符串保证少于 2^63 个字母。
Program
暴力
超内存！
1 | class Solution { |
规律处理
（1）如果我们有一个像 appleappleappleappleappleapple 这样的解码字符串和一个像 K=24 这样的索引，那么如果 K=4，答案是相同的。
（2）一般来说，当解码的字符串等于某个长度为 size 的单词重复某些次数（例如 apple 与 size=5 组合重复6次）时，索引 K 的答案与索引 K % size 的答案相同。
（3）首先计算解码后字符串长度为size，然后从后往前遍历，遇到数字就size/=S[i]-‘0’,否则遇到字母size–，然后K%size，判断K==0且S[i]为字母，则说明找到解。
例如样例1：”leet2code3”
size=36,k=10
i=9,size=36/3=12,k=10 mod 12=10;
i=8,size=11,k=10
i=7,size=10,k=0
i=6,return;
1 | class Solution { |
901. 股票价格跨度
Description
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
Example
示例：
输入：[“StockSpanner”,”next”,”next”,”next”,”next”,”next”,”next”,”next”], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
提示：
调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用 10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。
Program
单调栈
乍一看还以为是树状数组题，然后看到最大连续日数。这题还是比较有意思的，没有直接说求左边第一个比当前大的元素！这个转变很关键啊！
这么一看就是求当前到左边比当前大的天数的索引差值！Next Greater Element变成了Pre Greater Element，正向遍历，单调递减栈！时间复杂度：$O(n)$，n为next调用的次数
1 | class StockSpanner { |
907. 子数组的最小值之和
Description
给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。
Example
示例：
输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
提示：
1 <= A <= 30000
1 <= A[i] <= 30000
Program
单调栈
以A[i]为最小值，左右最大辐射范围
left[i]记录左边第一个小于A[i]的下标；
right[i]记录右边第一个小于A[i]的下标；
以A[i]为最小值的区间个数为：$(i-left[i]) * (right[i] - i)$
由于存在重复元素，所以需要左右两边其中一个取小于等于。
1 | class Solution { |
1 | class Solution { |
946. 验证栈序列
Description
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
Example
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
Program
直接判断栈顶元素是否等于出栈元素，是则继续出栈，否则进栈元素进栈。
时间复杂度：$O(n)$
1 | class Solution { |
1 | class Solution { |
1002. 查找常用字符
Description
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
Example
示例 1：
输入：[“bella”,”label”,”roller”]
输出：[“e”,”l”,”l”]
示例 2：
输入：[“cool”,”lock”,”cook”]
输出：[“c”,”o”]
提示：
1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] 是小写字母
Program
思路
（1）对每个字符串的26个字母进行计数；
（2）最终结果仅保留各个字符串中对应字母最小的值；
1 | class Solution { |
1003. 检查替换后的词是否有效
Description
给定有效字符串 “abc”。
对于任何有效的字符串 V，我们可以将 V 分成两个部分 X 和 Y，使得 X + Y（X 与 Y 连接）等于 V。（X 或 Y 可以为空。）那么，X + “abc” + Y 也同样是有效的。
例如，如果 S = “abc”，则有效字符串的示例是：”abc”，”aabcbc”，”abcabc”，”abcabcababcc”。无效字符串的示例是：”abccba”，”ab”，”cababc”，”bac”。
如果给定字符串 S 有效，则返回 true；否则，返回 false。
Example
示例 1：
输入：”aabcbc”
输出：true
解释：
从有效字符串 “abc” 开始。
然后我们可以在 “a” 和 “bc” 之间插入另一个 “abc”，产生 “a” + “abc” + “bc”，即 “aabcbc”。
示例 2：
输入：”abcabcababcc”
输出：true
解释：
“abcabcabc” 是有效的，它可以视作在原串后连续插入 “abc”。
然后我们可以在最后一个字母之前插入 “abc”，产生 “abcabcab” + “abc” + “c”，即 “abcabcababcc”。
示例 3：
输入：”abccba”
输出：false
示例 4：
输入：”cababc”
输出：false
提示：
1 <= S.length <= 20000
S[i] 为 ‘a’、’b’、或 ‘c’
Program
1 | class Solution { |
1019. 链表中的下一个更大节点
Description
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
Example
示例 1：
输入：[2,1,5]
输出：[5,5,0]
示例 2：
输入：[2,7,4,3,5]
输出：[7,0,5,5,0]
示例 3：
输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]
提示：
对于链表中的每个节点，1 <= node.val <= 10^9
给定列表的长度在 [0, 10000] 范围内
Program
单调栈
时间复杂度：$O(n)$
空间复杂度：$O(n)$
1 | /** |
1021. 删除最外层的括号
Description
有效括号字符串为空 (“”)、”(“ + A + “)” 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
Example
示例 1：
输入：”(()())(())”
输出：”()()()”
解释：
输入字符串为 “(()())(())”，原语化分解得到 “(()())” + “(())”，
删除每个部分中的最外层括号后得到 “()()” + “()” = “()()()”。
示例 2：
输入：”(()())(())(()(()))”
输出：”()()()()(())”
解释：
输入字符串为 “(()())(())(()(()))”，原语化分解得到 “(()())” + “(())” + “(()(()))”，
删除每个部分中的最外层括号后得到 “()()” + “()” + “()(())” = “()()()()(())”。
示例 3：
输入：”()()”
输出：””
解释：
输入字符串为 “()()”，原语化分解得到 “()” + “()”，
删除每个部分中的最外层括号后得到 “” + “” = “”。
提示：
S.length <= 10000
S[i] 为 “(“ 或 “)”
S 是一个有效括号字符串
Program
思路
关键在于拆分原语，可以发现左括号与右括号数量相等的时候是一个原语！！
时间复杂度：$O(n)$
1 | class Solution { |
1023. 驼峰式匹配
Description
如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0 个字符。）
给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。
Example
示例 1：
输入：queries = [“FooBar”,”FooBarTest”,”FootBall”,”FrameBuffer”,”ForceFeedBack”], pattern = “FB”
输出：[true,false,true,true,false]
示例：
“FooBar” 可以这样生成：”F” + “oo” + “B” + “ar”。
“FootBall” 可以这样生成：”F” + “oot” + “B” + “all”.
“FrameBuffer” 可以这样生成：”F” + “rame” + “B” + “uffer”.
示例 2：
输入：queries = [“FooBar”,”FooBarTest”,”FootBall”,”FrameBuffer”,”ForceFeedBack”], pattern = “FoBa”
输出：[true,false,true,false,false]
解释：
“FooBar” 可以这样生成：”Fo” + “o” + “Ba” + “r”.
“FootBall” 可以这样生成：”Fo” + “ot” + “Ba” + “ll”.
示例 3：
输出：queries = [“FooBar”,”FooBarTest”,”FootBall”,”FrameBuffer”,”ForceFeedBack”], pattern = “FoBaT”
输入：[false,true,false,false,false]
解释：
“FooBarTest” 可以这样生成：”Fo” + “o” + “Ba” + “r” + “T” + “est”.
提示：
1 <= queries.length <= 100
1 <= queries[i].length <= 100
1 <= pattern.length <= 100
所有字符串都仅由大写和小写英文字母组成。
Program
双指针
如果str[i]与pattern[j]匹配，同时后移；
否则，如果str[i]为大写字母，直接返回false:
否则，i后移；
判断pattern是否匹配完，没匹配完，直接返回false;
最后判断str剩余部分是否存在大写字母，如果有直接返回false；
如果没有，则匹配成功，返回true;
1 | class Solution { |
1047. 删除字符串中的所有相邻重复项
Description
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
Example
示例：
输入：”abbaca”
输出：”ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。
Program
1 | class Solution { |
1081. 不同字符的最小子序列
Description
返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
Example
示例 1：
输入：”cdadabcc”
输出：”adbc”
示例 2：
输入：”abcd”
输出：”abcd”
示例 3：
输入：”ecbacba”
输出：”eacb”
示例 4：
输入：”leetcode”
输出：”letcod”
提示：
1 <= text.length <= 1000
text 由小写英文字母组成
Program
思路
子序列且要求每个字符仅出现一次，子序列要求相对位置不变，可以考虑单调栈，遇到与当前字符大的字符，检查是否可以出栈；
出栈条件：①比当前字符大；②并且该字符在字符串后面还存在
1 | class Solution { |
1124. 表现良好的最长时间段
Description
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
Example
示例 1：
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
提示：
1 <= hours.length <= 10000
0 <= hours[i] <= 16
Program
暴力
首先将hours数组转成1，-1的形式，方便统计，然后计算前缀和，题目要求的就是说要使得[i,j]的和大于0的最长长度。一个直接的思路是暴力枚举，时间复杂度：$O(n^2)$
超时
1 | class Solution { |
单调栈
从暴力的双循环看：
（1）内循环，$i<j_1<j_2$，如果preSum[j_2]>preSum[i]，那么$j_1$无意义，所以从后往前遍历j；
（2）外循环：$i<i_1<j$，如果preSum[i_1]>preSum[i]，那么$i_1$无意义；
详解
1 | class Solution { |
1190. 反转每对括号间的子串
Description
给出一个字符串 s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
Example
示例 1：
输入：s = “(abcd)”
输出：”dcba”
示例 2：
输入：s = “(u(love)i)”
输出：”iloveu”
示例 3：
输入：s = “(ed(et(oc))el)”
输出：”leetcode”
示例 4：
输入：s = “a(bcdefghijkl(mno)p)q”
输出：”apmnolkjihgfedcbq”
提示：
0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的
Program
暴力
时间复杂度：$O(n^2)$
1 | class Solution { |
虫洞法
时间复杂度：$O(n)$
1 | class Solution { |
1209. 删除字符串中的所有相邻重复项 II
Description
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
Example
示例 1：
输入：s = “abcd”, k = 2
输出：”abcd”
解释：没有要删除的内容。
示例 2：
输入：s = “deeedbbcccbdaa”, k = 3
输出：”aa”
解释：
先删除 “eee” 和 “ccc”，得到 “ddbbbdaa”
再删除 “bbb”，得到 “dddaa”
最后删除 “ddd”，得到 “aa”
示例 3：
输入：s = “pbbcggttciiippooaais”, k = 2
输出：”ps”
提示：
1 <= s.length <= 10^5
2 <= k <= 10^4
s 中只含有小写英文字母。
Program
1 | class Solution { |
1249. 移除无效的括号
Description
给你一个由 ‘(‘、’)’ 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 ‘(‘ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
- 空字符串或只包含小写字母的字符串
- 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
- 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
Example
示例 1：
输入：s = “lee(t(c)o)de)”
输出：”lee(t(c)o)de”
解释：”lee(t(co)de)” , “lee(t(c)ode)” 也是一个可行答案。
示例 2：
输入：s = “a)b(c)d”
输出：”ab(c)d”
示例 3：
输入：s = “))((“
输出：””
解释：空字符串也是有效的
示例 4：
输入：s = “(a(b(c)d)”
输出：”a(b(c)d)”
提示：
1 <= s.length <= 10^5
s[i] 可能是 ‘(‘、’)’ 或英文小写字母
Program
时间复杂度：$O(n)$
1 | class Solution { |
1370. 上升下降字符串
Description
给你一个字符串 s ，请你根据下面的算法重新构造字符串：
从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
重复步骤 2 ，直到你没法从 s 中选择字符。
从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
重复步骤 5 ，直到你没法从 s 中选择字符。
重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串 。
Example
示例 1：
输入：s = “aaaabbbbcccc”
输出：”abccbaabccba”
解释：第一轮的步骤 1，2，3 后，结果字符串为 result = “abc”
第一轮的步骤 4，5，6 后，结果字符串为 result = “abccba”
第一轮结束，现在 s = “aabbcc” ，我们再次回到步骤 1
第二轮的步骤 1，2，3 后，结果字符串为 result = “abccbaabc”
第二轮的步骤 4，5，6 后，结果字符串为 result = “abccbaabccba”
示例 2：
输入：s = “rat”
输出：”art”
解释：单词 “rat” 在上述算法重排序以后变成 “art”
示例 3：
输入：s = “leetcode”
输出：”cdelotee”
示例 4：
输入：s = “ggggggg”
输出：”ggggggg”
示例 5：
输入：s = “spo”
输出：”ops”
提示：
1 <= s.length <= 500
s 只包含小写英文字母。
Program
1 | class Solution { |
1381. 设计一个支持增量操作的栈
Description
请你设计一个支持下述操作的栈。
实现自定义栈类 CustomStack ：
CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，栈在增长到 maxSize 之后则不支持 push 操作。
void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。
Example
示例：
输入：
[“CustomStack”,”push”,”push”,”pop”,”push”,”push”,”push”,”increment”,”increment”,”pop”,”pop”,”pop”,”pop”]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出：
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释：
CustomStack customStack = new CustomStack(3); // 栈是空的 []
customStack.push(1); // 栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.pop(); // 返回 2 –> 返回栈顶值 2，栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.push(3); // 栈变为 [1, 2, 3]
customStack.push(4); // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
customStack.increment(5, 100); // 栈变为 [101, 102, 103]
customStack.increment(2, 100); // 栈变为 [201, 202, 103]
customStack.pop(); // 返回 103 –> 返回栈顶值 103，栈变为 [201, 202]
customStack.pop(); // 返回 202 –> 返回栈顶值 202，栈变为 [201]
customStack.pop(); // 返回 201 –> 返回栈顶值 201，栈变为 []
customStack.pop(); // 返回 -1 –> 栈为空，返回 -1
提示：
1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
每种方法 increment，push 以及 pop 分别最多调用 1000 次
Program
1 | class CustomStack { |
1410. HTML 实体解析器
Description
「HTML 实体解析器」 是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。
HTML 里这些特殊字符和它们对应的字符实体包括：
双引号：字符实体为 " ，对应的字符是 “ 。
单引号：字符实体为 ' ，对应的字符是 ‘ 。
与符号：字符实体为 & ，对应对的字符是 & 。
大于号：字符实体为 > ，对应的字符是 > 。
小于号：字符实体为 < ，对应的字符是 < 。
斜线号：字符实体为 ⁄ ，对应的字符是 / 。
给你输入字符串 text ，请你实现一个 HTML 实体解析器，返回解析器解析后的结果。
Example
示例 1：
输入：text = “& is an HTML entity but &ambassador; is not.”
输出：”& is an HTML entity but &ambassador; is not.”
解释：解析器把字符实体 & 用 & 替换
示例 2：
输入：text = “and I quote: "…"”
输出：”and I quote: "…"“
示例 3：
输入：text = “Stay home! Practice on Leetcode :)”
输出：”Stay home! Practice on Leetcode :)”
示例 4：
输入：text = “x > y && x < y is always false”
输出：”x > y && x < y is always false”
示例 5：
输入：text = “leetcode.com⁄problemset⁄all”
输出：”leetcode.com/problemset/all”
提示：
1 <= text.length <= 10^5
字符串可能包含 256 个ASCII 字符中的任意字符。
Program
1 | class Solution { |
1441. 用栈操作构建数组
Description
给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3…, n} 中依序读取一个数字。
请使用下述操作来构建目标数组 target ：
- Push：从 list 中读取一个新元素， 并将其推入数组中。
- Pop：删除数组中的最后一个元素。
- 如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
请返回构建目标数组所用的操作序列。
题目数据保证答案是唯一的。
Example
示例 1：
输入：target = [1,3], n = 3
输出：[“Push”,”Push”,”Pop”,”Push”]
解释：
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组，然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]
示例 2：
输入：target = [1,2,3], n = 3
输出：[“Push”,”Push”,”Push”]
示例 3：
输入：target = [1,2], n = 4
输出：[“Push”,”Push”]
解释：只需要读取前 2 个数字就可以停止。
示例 4：
输入：target = [2,3,4], n = 4
输出：[“Push”,”Pop”,”Push”,”Push”,”Push”]
提示：
1 <= target.length <= 100
1 <= target[i] <= 100
1 <= n <= 100
target 是严格递增的
Program
1 | class Solution { |
1544. 整理字符串
Description
给你一个由大小写英文字母组成的字符串 s 。
一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：
0 <= i <= s.length - 2
s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。
Example
示例 1：
输入：s = “leEeetcode”
输出：”leetcode”
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 “leEeetcode” 缩减为 “leetcode” 。
示例 2：
输入：s = “abBAcC”
输出：””
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
“abBAcC” –> “aAcC” –> “cC” –> “”
“abBAcC” –> “abBA” –> “aA” –> “”
示例 3：
输入：s = “s”
输出：”s”
提示：
1 <= s.length <= 100
s 只包含小写和大写英文字母
Program
1 | class Solution { |
剑指 Offer 30. 包含min函数的栈
Description
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
Example
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.
提示：
各函数的调用总次数不超过 20000 次
Program
1 | class MinStack { |
面试题 03.02. 栈的最小值
Description
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
Example
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.
Program
1 | class MinStack { |
面试题 03.04. 化栈为队
Description
实现一个MyQueue类，该类用两个栈来实现一个队列。
Example
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明：
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
Program
1 | class MyQueue { |
面试题 17.17. 多次搜索
Description
给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。
Example
示例：
输入：
big = “mississippi”
smalls = [“is”,”ppi”,”hi”,”sis”,”i”,”ssippi”]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
提示：
0 <= len(big) <= 1000
0 <= len(smalls[i]) <= 1000
smalls的总字符数不会超过 100000。
你可以认为smalls中没有重复字符串。
所有出现的字符均为英文小写字母。
Program
1 | **1、KMP** |
2、AC自动机
1 | class Solution { |
树
树的序列化
652. 寻找重复的子树
Description
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
Example
示例 1：
1 | 1 |
下面是两个重复的子树：
1 | 2 |
和
4
因此，你需要以列表的形式返回上述重复子树的根结点。
Program
思路
将每个子树序列化后，用哈希表判断是否重复，如果重复，加入结果即可，注意分隔符，否则将不能准确区分不同子树的情况
1 | /** |
树的操作
114. 二叉树展开为链表
Description
给定一个二叉树，原地将它展开为链表。
Example
例如，给定二叉树
1 | 1 |
将其展开为：
1 | 1 |
Program
前序遍历，自顶而下
1 | /** |
后序遍历，自底而上
1 | /** |
前两种时间复杂度$O(n)$,空间复杂度：$O(n)$,栈相关！
现在使用前驱的方法，使得空间复杂度降为$O(1)$.
其中每个节点最多额外访问一次，所以时间复杂度还是$O(n)$
1 | /** |
99. 恢复二叉搜索树
Description
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
Example
示例 1:
输入: [1,3,null,null,2]
1 | 1 |
3
/
1
2
1 | 示例 2: |
3
/
1 4
/
2
1 | 输出: [2,1,4,null,null,3] |
2
/
1 4
/
3
1 | 进阶: |
Mirros遍历
先找到左子树前驱，如果前驱右孩子为空则，置为root，否则置为空，其他与上一个一致
1 | * Definition for a binary tree node. |
98. 验证二叉搜索树
Description
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
Example
示例 1:
输入:
2
/
1 3
输出: true
示例 2:
输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
Program
1 | /** |
105. 从前序与中序遍历序列构造二叉树
Description
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
Example
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
1 | 3 |
Program
1 | /** |
106. 从中序与后序遍历序列构造二叉树
Description
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
Example
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
1 | 3 |
Program
1 | /** |
109. 有序链表转换二叉搜索树
Description
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
Example
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
1 | 0 |
Program
1 | /** |
113. 路径总和 II
Description
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
Example
示例:
给定如下二叉树，以及目标和 sum = 22，
1 | 5 |
返回:
1 | [ |
Program
1 | /** |
116. 填充每个节点的下一个右侧节点指针
Description
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
1 | struct Node { |
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
Example
1 | 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1} |
Program
1 | /* |
117. 填充每个节点的下一个右侧节点指针 II
Description
给定一个二叉树
1 | struct Node { |
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
Example
示例：
Program
1 | /* |
129. 求根到叶子节点数字之和
Description
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
Example
示例 1:
输入: [1,2,3]
1 | 1 |
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:
输入: [4,9,0,5,1]
1 | 4 |
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.
Progam
1 | /** |
133. 克隆图
Description
给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。
Example
示例：
1 | 输入： |
提示：
节点数介于 1 到 100 之间。
无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
必须将给定节点的拷贝作为对克隆图的引用返回。
Program
1 | /* |
199. 二叉树的右视图
Description
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
Example
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 | 1 <--- |
Program
1 | /** |
235. 二叉搜索树的最近公共祖先
Description
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
Example
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
Program
1 | /** |
236. 二叉树的最近公共祖先
Description
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
Example
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
Program
思路
root为p,q的最近公共祖先：
1.p,q分别在root的左右子树上；
2.root=p,q在root的子树上；
3.root=q,p在root的子树上；
后序遍历：
先判断左右子树是否包含p或q，不分别包含p和q的话，比较2,3即可。
1 | /** |
257. 二叉树的所有路径
Description
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
Example
示例:
输入:
1 | 1 |
输出: [“1->2->5”, “1->3”]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
Program
1 | /** |
437. 路径总和 III
Description
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
Example
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
1 | 10 |
返回 3。和等于 8 的路径有:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
Program
思路
（1）pathSum(root, sum)是以root为根的二叉树路径和为sum的个数，则：
pathSum(root, sum)=pathSum(root->left, sum)+pathSum(root->right, sum)？
还漏了一种情况，因为pathSum仅仅以root为根，而路径不一定以root为起点，所以这里漏了以root为起点的路径的情况：
pathSum(root, sum)=pathSum(root->left, sum)+pathSum(root->right, sum)+calPath(root, sum);
其中calPath(root, sum)为以root为起点的路径和为sum的路径数！
（2）所以有两个递归过程，一个是以root作为根的递归，一个是以root作为路径起点的递归；
（3）calPath(root,sum)中找到和为sum时，ans+1，还需要继续向下递归，因为可以类似于[1,2,-1,4],sum=3这种情况，以1位起点可以有两条路径。
1 | /** |
508. 出现次数最多的子树元素和
Description
给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
Example
示例 1：
输入:
1 | 5 |
返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。
示例 2：
输入：
1 | 5 |
返回 [2]，只有 2 出现两次，-5 只出现 1 次。
提示： 假设任意子树元素和均可以用 32 位有符号整数表示。
Program
1 | /** |
572. 另一个树的子树
Description
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
Example
示例 1:
给定的树 s:
1 | 3 |
给定的树 t：
1 | 4 |
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
1 | 3 |
给定的树 t：
1 | 4 |
返回 false。
Program
思路
（1）比较当前root是否一致，一致则判断各自左右子树是否相等；
（2）即isSubtree(s, t) || isSubtree(s->left, t) ||isSubtree(s->right, t)
这里有问题，即每次第一个isSubtree(s, t)不相等的时候，后面都会进行左右子树比较，存在大量重复，解决方法是比较当前root为根的子树与t是否一致，与左右子树比较分开。
1 | /** |
1 | /** |
530. 二叉搜索树的最小绝对差
Description
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
Example
示例：
输入：
1 | 1 |
输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
提示：
树中至少有 2 个节点。
Program
1 | /** |
538. 把二叉搜索树转换为累加树
Description
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
Example
例如：
输入: 原始二叉搜索树:
1 | 5 |
输出: 转换为累加树:
1 | 18 |
Program
1 | /** |
543. 二叉树的直径
Description
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
Example
示例 :
给定二叉树
1 | 1 |
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
Program
1 | /** |
563. 二叉树的坡度
Description
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
Example
示例：
输入：
1 | 1 |
输出：1
解释：
结点 2 的坡度: 0
结点 3 的坡度: 0
结点 1 的坡度: |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
提示：
任何子树的结点的和不会超过 32 位整数的范围。
坡度的值不会超过 32 位整数的范围。
Program
1 | /** |
617. 合并二叉树
Description
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
Example
示例 1:
输入:
1 | Tree 1 Tree 2 |
3
/ \
4 5
/ \ \
5 4 71 | 注意: 合并必须从两个树的根节点开始。 |
655. 输出二叉树
Description
在一个 mn 的二维字符串数组中输出二叉树，并遵守以下规则：
行数 m 应当等于给定二叉树的高度。
列数 n 应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串””。
使用相同的规则输出子树。
*Example**
示例 1:
输入:
1 | 1 |
输出:
[[“”, “1”, “”],
[“2”, “”, “”]]
示例 2:
输入:
1 | 1 |
输出:
[[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“”, “”, “4”, “”, “”, “”, “”]]
示例 3:
输入:
1 | 1 |
输出:
[[“”, “”, “”, “”, “”, “”, “”, “1”, “”, “”, “”, “”, “”, “”, “”]
[“”, “”, “”, “2”, “”, “”, “”, “”, “”, “”, “”, “5”, “”, “”, “”]
[“”, “3”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]
[“4”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]]
注意: 二叉树的高度在范围 [1, 10] 中。
Program
1 | /** |
662. 二叉树最大宽度
Description
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
Example
示例 1:
输入:
1 | 1 |
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:
输入:
1 | 1 |
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:
输入:
1 | 1 |
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:
输入:
1 | 1 |
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。
Program
思路
（1）通过满二叉树的性质，子节点索引分别为$idx_{father}2+1,idx_{father}}2+2$，来对非空节点进行编码；
（2）由于二叉树的层数阅读，编码为2的指数倍，容易越界，故可以考虑同一层同时减去本层最小的索引来进行编码数值的压缩，而不会影响宽度（索引差值）的结果！
时间复杂度：$O(n)$
1 | /** |
894. 所有可能的满二叉树
Description
满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
Example
示例：
输入：7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释：
提示：
1 <= N <= 20
Program
递归
根结点1
左子树节点数为0, 1, 3, 5, i
右子树节点数为N-1-i, 1, 0
1 | /** |
919. 完全二叉树插入器
Description
完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
- CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
- CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
- CBTInserter.get_root() 将返回树的头节点。
Example
示例 1：
输入：inputs = [“CBTInserter”,”insert”,”get_root”], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]
示例 2：
输入：inputs = [“CBTInserter”,”insert”,”insert”,”get_root”], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]
提示：
最初给定的树是完全二叉树，且包含 1 到 1000 个节点。
每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
给定节点或插入节点的每个值都在 0 到 5000 之间。
Program
思路
维护一个双端队列，保存孩子为0或1的节点，插入时，插入队列头结点即可，如果头结点孩子满了，出队，同时注意插入的节点孩子为0，也需要入队。
1 | /** |
968. 监控二叉树
Description
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
Example
示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。
Program
1 | /** |
979. 在二叉树中分配硬币
Description
给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回使每个结点上只有一枚硬币所需的移动次数。
Example
示例 1：
输入：[3,0,0]
输出：2
解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。
示例 2：
输入：[0,3,0]
输出：3
解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。然后，我们把一枚硬币从根结点移到右子结点上。
示例 3：
输入：[1,0,2]
输出：2
示例 4：
输入：[1,0,0,null,3]
输出：4
提示：
1<= N <= 100
0 <= node.val <= N
Program
1 | /** |
987. 二叉树的垂序遍历
Description
给定二叉树，按垂序遍历返回其结点值。
对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。
把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。
如果两个结点位置相同，则首先报告的结点值较小。
按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
Example
示例 1：
输入：[3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)：
然后，值为 9 的结点出现在 (-1, -1)；
值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)；
值为 20 的结点出现在 (1, -1)；
值为 7 的结点出现在 (2, -2)。
示例 2：
输入：[1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。
然而，在报告 “[1,5,6]” 中，结点值 5 排在前面，因为 5 小于 6。
提示：
树的结点数介于 1 和 1000 之间。
每个结点值介于 0 和 1000 之间。
Program
思路
（1）给每个节点坐标化；
（2）先按照x增序排列，在根据y轴降序排列，最后根据val升序排列；
1 | /** |
1008. 前序遍历构造二叉搜索树
Description
返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）
题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。
Example
示例：
输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]
提示：
1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
preorder 中的值互不相同
Program
1 | /** |
1104. 二叉树寻路
Description
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
Example
示例 1：
输入：label = 14
输出：[1,3,4,14]
示例 2：
输入：label = 26
输出：[1,2,6,10,26]
提示：
$1 <= label <= 10^6$
Program
思路
（1）正常顺序下的父节点编码为子节点编码$\frac{label}{2}$；
（2）可以发现规律每层头尾节点的值$left+right=father_label + label/2$
即$father_label = left+right-label/2=2^{h-1}+2^{h}-1-label/2=3 * 2^{h-1}-1-label/2$；
1 | class Solution { |
1261. 在受污染的二叉树中查找元素
Description
给出一个满足下述规则的二叉树：
root.val == 0
如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
请你先还原二叉树，然后实现 FindElements 类：
FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。
Example
示例 1：
输入：
[“FindElements”,”find”,”find”]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True
示例 2：
输入：
[“FindElements”,”find”,”find”,”find”]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：
[null,true,true,false]
解释：
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False
示例 3：
输入：
[“FindElements”,”find”,”find”,”find”,”find”]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True
提示：
TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 $[1, 10^4]$ 之间
调用 find() 的总次数在 $[1, 10^4]$ 之间
$0 <= target <= 10^6$
Program
1 | /** |
1 | /** |
1530. 好叶子节点对的数量
Description
给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
Example
示例 1：
输入：root = [1,2,3,null,4], distance = 3
输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
示例 2：
输入：root = [1,2,3,4,5,6,7], distance = 3
输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。
示例 3：
输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
输出：1
解释：唯一的好叶子节点对是 [2,5] 。
示例 4：
输入：root = [100], distance = 1
输出：0
示例 5：
输入：root = [1,1,1], distance = 2
输出：1
提示：
tree 的节点数在 [1, 2^10] 范围内。
每个节点的值都在 [1, 100] 之间。
1 <= distance <= 10
Program
思路
详见官方题解
（1）一个自然的思路是需要记录叶子结点到以每个节点为根的距离，这里可以简化，因为题目只需要小于等于distance的好节点，所以对于每个节点为根来说，只需要记录距离小于等于distance的叶子结点个数即可，即$dist[i],0<=i<=distance$；
（2）其次，对于以每个节点为根的好节点个数来说，由两部分组成：
一个是leftDist[i]*rightDist[j]，其中i+j+2<=distance;
另一个则是leftCount+rightCount；(leftCount, rightCount分别为以左右孩子为根的好节点对个数)
可以知道这个以节点为根的好节点对个数，即以该节点为最近公共祖先！
1 | /** |
剑指 Offer 68 - II. 二叉树的最近公共祖先
Description
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
Example
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
Program
1 | /** |
树遍历
94. 二叉树的中序遍历
Description
给定一个二叉树，返回它的中序 遍历。
Example
示例:
输入: [1,null,2,3]
1 | 1 |
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
Program
1 | /** |
144. 二叉树的前序遍历
Description
给定一个二叉树，返回它的 前序 遍历。
Example
示例:
输入: [1,null,2,3]
1 | 1 |
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
Program
1 | /** |
1 | /** |
145. 二叉树的后序遍历
Description
给定一个二叉树，返回它的 后序 遍历。
Example
示例:
输入: [1,null,2,3]
1 | 1 |
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
Program
1 | /** |
222. 完全二叉树的节点个数
Description
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
Example
示例:
输入:
1 | 1 |
输出: 6
Program
1 | /** |
501. 二叉搜索树中的众数
Description
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
Example
例如：
给定 BST [1,null,2,2],
1 | 1 |
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
Program
1 | /** |