美文网首页
leetcode

leetcode

作者: winter_sweetie | 来源:发表于2020-01-30 17:21 被阅读0次

简单题

696. 计数二进制子串: 一次遍历字符串2020.08.12

连续子序列 vs 子序列

x 有序 连续 思路
1. 子序列 √ × 贪心？
2. 连续子序列/子串 √ √ 滑窗/dp/单调栈
3. 排列/重排 × √ dfs
  1. 300. 最长上升子序列 | 动态规划 or 贪心+二分 | O(nlog(n))+O(n)
  2. 128. 最长连续序列 | 非常简单的一次遍历 | O(n)+O(1)
  3. 53. 最大子序和 | 一次遍历/分治 | O(n) / O(nlog(n))
  4. 152. 乘积最大子数组 | 双dp | O(n)

快速排序 & 快速选择

题解 说明 完成时间
912. 排序数组 笔记 2020.5.7
215. 数组中的第K个最大元素 同上 2020.5.7

分治法

先区分一下概念

  • 二分查找：分
  • 合并两个有序数组：治
  • 对无序数组进行排序：分治

归并排序就是“分治法”的一种，尽管名字中只体现了“治”。

题解 说明 完成时间
912. 排序数组 归并排序 2020.4.25
面试题51. 数组中的逆序对 有返回值的归并排序 2020.4.25
53. 最大子序和 动态规划/有返回值不排序 2020.5.3

单调栈

滑窗法

滑窗，是一种同向双指针技巧。
labuladong滑窗法

题解 说明 完成时间
239. 滑动窗口最大值 labuladong单调队列 2020.4.26
1425. 带限制的子序列和 动态规划+单调队列 2020.4.26
3. 无重复字符的最长子串 hashset 2019.8
76. 最小覆盖子串 hashmap 2020.5.2
5402. 绝对差不超过限制的最长连续子数组 滑窗+单调队列 2020.5.3
632. 最小区间 滑窗+字典/列表 2020.8.8

动态规划

题解 算法 完成时间
62. 不同路径 组合/二维动态规划/一维动态规划 2020/4/27
887. 鸡蛋掉落 二维动态规划/记忆化搜索 2020/5/2
983. 最低票价 一维动态规划 2020/5/6
1434. 每个人戴不同帽子的方案数 动态规划+状态压缩 2020/5/6

链表

索引 题解 最优算法 替代算法 备注 完成时间
0 206. 反转链表 1.迭代 2.递归 所有节点 20.1.27
1 92. 反转链表 II 1.迭代 2.递归 0的进阶版：从m到n的节点 20.1.27
2 24. 两两交换链表中的节点 1.迭代 2.递归 20.1.27
3 114. 二叉树展开为链表 递归 20.1.27
4 234. 回文链表 反转 1.stack 2.half stack 3.递归 20.1.27
5 25. K 个一组翻转链表 尾插法 1.递归 2.堆栈 2的普适版 1的递归版 20.1.28
6 138. 复制带随机指针的链表 影子法 dfs/bfs+hash 算法新颖 20.1.28
7 141. 环形链表 快慢双指针 20.1.28
8 142. 环形链表 II 快慢双指针+数学推导 结论记住 20.1.28
9 86. 分隔链表 双指针 20.1.28
10 143. 重排链表 反转后半 stack 跟4相像 20.1.28
11 160. 相交链表 1.尾部对齐 2.链表拼接 visited hash 可转化为8 20.1.29
12 61. 旋转链表 取模+移动head 20.1.29
13 21. 合并两个有序链表 1.迭代 2.递归 20.1.30
14 23. 合并K个排序链表 1.最小堆 2.分治 13的进阶版 20.1.30
15 203. 移除链表元素 线性遍历 easy 20.1.31
16 83. 删除排序链表中的重复元素 线性遍历 官方题解用循环不变式验证算法正确性 20.1.31
17 82. 删除排序链表中的重复元素 II 线性遍历 20.1.31

树

题解 题目 算法 3种语言 完成时间
104. 二叉树的最大深度 - dfs yep 2020.01
111. 二叉树的最小深度 - dfs yep 2020.01
112. 路径总和 bool dfs yep 2020.01
113. 路径总和 II 返回list[list] dfs+回溯 yep 2020.4.22
437. 路径总和 III int dfs+前缀和 yep 2020.5.13
199. 二叉树的右视图 返回list bfs dfs yep 2020.4.22
236. 二叉树的最近公共祖先(leetcode) - - - -
88. 最近公共祖先(lintcode) 返回节点 dfs yep 2020.4.22
117. 填充每个节点的下一个右侧节点指针 II 添加指针 迭代 层序 nope 2020.5.13
124. 二叉树中的最大路径和 路径和 dfs nope 2020.5.13
99. 恢复二叉搜索树 中序遍历 dfs morris nope 2020.5.13

堆/优先级队列

题解 算法 原数据结构 任务 备注 完成时间
632. 最小区间 最小堆/滑窗法 k个数组 List[List[int]] 计算区间 最小值靠堆，最大值靠比较 2020.1.21
23. 合并K个排序链表 最小堆 k个链表List[ListNode] 合并 每步只需找最小值 2020.1.30
264. 丑数 II 最小堆/三指针 从1开始 第n个 经典 2020.5.3
1439. 有序矩阵中的第 k 个最小数组和 暴力解法/最小堆/二分法 矩阵mat: List[List[int]] 第k个 堆中[curr_sum, pointers] 跟丑数很像 2020.5.3
378. 有序矩阵中第K小的元素 最小堆/二分 矩阵mat: List[List[int]] 第k个 堆中[row, col, val] 跟丑数很像 2020.5.3
295. 数据流的中位数 两个堆 - 动态查询中位数 可用multiset 2020.5.6

二分查找

甜姨的二分查找模板

索引 题解 有序 有重复元素 旋转数组 目标任务 备注 完成时间
0 704. 二分查找 √ x x 查找 20.1.29
1 35. 搜索插入位置 √ x x 查找和插入 0的进阶版 20.1.29
2 34. 在排序数组中查找元素的第一个和最后一个位置 √ √ × 查找区间 0的进阶版 20.1.29
3 153. 寻找旋转排序数组中的最小值 √ × √ 找最小值 20.1.29
4 154. 寻找旋转排序数组中的最小值 II √ √ √ 找最小值 3的进阶版 20.1.29
5 33. 搜索旋转排序数组 √ × √ 查找 20.1.30
6 81. 搜索旋转排序数组 II √ √ √ 查找 5的进阶版 20.1.30
7 222. 完全二叉树的节点个数 节点个数 20.1.30
8 300. 最长上升子序列 √ × 覆盖 二分法是其中一步 19.7.x

p.s. 若要加深对旋转数组的理解，请戳189.旋转数组。

对值的二分

题解 方法 时间
378. 有序矩阵中第K小的元素 最小堆/二分法 2020.5.3
1439. 有序矩阵中的第 k 个最小数组和 暴力解法/最小堆/二分法 2020.5.6
410. 分割数组的最大值 二分法 2020.5.6
LCP 12. 小张刷题计划 二分法 2020.5.6

数组

题解 时间
189.旋转数组 20.1.30

双指针

题解 数据结构 指针类型 时间
27. 移除元素(官方) 数组 同向双指针 2020.04.20
26. 删除排序数组中的重复项 数组 同向双指针 2020.04.20
80. 删除排序数组中的重复项 II 数组 同向双指针 2020.04.20
575. 分糖果 数组 同向双指针 2020.04.20
42. 接雨水 数组 相向双指针 2020.02
11. 盛最多水的容器 数组 相向双指针 2020.02
15. 三数之和 数组 相向双指针 2020.04.20
16. 最接近的三数之和 数组 相向双指针 2020.04.20
75. 颜色分类 数组 边界双指针+遍历指针 2020.04.20
202. 快乐数 公式 快慢双指针 找环 2020.04.30

回溯/dfs

powcai

  • 回溯是dfs的特殊情况。
    • list做参数时会回溯
    • 无list做参数时，只dfs无回溯，还能考虑dp解法。
题解 思路 补充 时间
46. 全排列 swap used数组 liweiwei labuladong 2020.04.20
47. 全排列 II used数组 - 2020.04.20
78. 子集 dfs 两种递归树 liweiwei 2020.4.25
90. 子集 II 排序+dfs+剪枝 - 2020.4.25
51. N皇后 backtrack + isValid labuladong 2020.3
52. N皇后 II backtrack + isValid 位运算 2020.3
37. 解数独 backtrack + isValid 三种语言 2020.4.29
39. 组合总和 backtrack 笔记 2020.4.30
40. 组合总和 II backtrack 同上 2020.4.30
216. 组合总和 III backtrack 同上 2020.4.30
377. 组合总和 Ⅳ dfs / dp 同上 2020.4.30
518. 零钱兑换 II dfs / dp 同上 2020.4.30
77. 组合 backtrack 同上 2020.4.30
17. 电话号码的字母组合 backtrack 同上 2020.4.30

特殊方法

题解 思路 时间
300. 最长上升子序列 覆盖法+二分法 19.7.x
169. 多数元素 哈希表 排序法 随机化 分治法 投票法 位运算 20.3.13
229. 求众数 II 投票法 20.3.16

位运算

题解 思路 时间
169. 多数元素 哈希表 排序法 随机化 分治法 投票法 位运算 20.3.13

二维有序矩阵

题解 思路 时间
74. 搜索二维矩阵 二分/区间缩减 2020.5.2
240. 搜索二维矩阵 II 区间缩减 题解见上 2020.5.2
378. 有序矩阵中第K小的元素 最小堆/二分法 2020.5.3

N数之和

题解 思路 时间
15. 三数之和 排序+相向双指针 2020.04.20
16. 最接近的三数之和 排序+相向双指针 2020.04.20

接雨水

题解 思路 时间
42. 接雨水 双指针 2020.02
11. 盛最多水的容器 动态规划 双指针 2020.02

岛屿

题解 思路 时间
200. 岛屿数量 bfs dfs 并查集 19.6.x
434. 岛屿的个数II（lintcode） 并查集 2020.4.18
695. 岛屿的最大面积 bfs dfs 20.3.15
1254. 统计封闭岛屿的数目 bfs dfs 20.3.16

其他的图问题

题解 思路 时间
133. 克隆图 bfs dfs 2020.8.12

股票问题

题解 题目 思路 时间
121. Best Time to Buy and Sell Stock 最多一次交易 贪心法 2019.8
122. Best Time to Buy and Sell Stock II 无限次交易 贪心法 2019.8
123. Best Time to Buy and Sell Stock III 最多两次交易 二分贪心/动态规划 2019.8
188. Best Time to Buy and Sell Stock IV 最多k次交易 动态规划（二维背包） 2020.4.19

跳跃游戏

题解 题目 思路 时间
55. 跳跃游戏 单向 能不能跳到最后 贪心 2020.02
45. 跳跃游戏 II 单向 最少步数 贪心 2020.02
1306. 跳跃游戏 III 双向 能不能跳到某处 bfs 2020.02
1340. 跳跃游戏 V 双向 最多访问多少 动态规划 2020.02

爬楼梯

题解 题目 思路 时间
70. 爬楼梯 多少种方法 排列问题 动态规划 空间可优化到O（1） 2019/07
746. 使用最小花费爬楼梯 最小花费 动态规划 空间可优化到O（1） 2020/04/19

零钱兑换

题解 题目 思路 时间
322. 零钱兑换 最小硬币个数 1d动态规划/ dfs+贪心 2020/4/19
518. 零钱兑换 II 有多少硬币组合 组合问题 1d动态规划 2020/4/19

山脉数组

题解 思路 时间
852. 山脉数组的峰顶索引 二分查找 2020.4.29
941. 有效的山脉数组 线性扫描 2020.4.29
845. 数组中的最长山脉 状态机 2020.4.29
1095. 山脉数组中查找目标值 3次二分查找 2020.4.29

第181场周赛 2020/3/22

比赛链接
1391. 检查网格中是否存在有效路径 | dfs（看提交记录） | 2020.5.7
1392. 最长快乐前缀 | 字符串hash kmp的第一步（看提交记录）| 2020.5.7

第182场周赛 2020/3/29

比赛链接
1397. 找到所有好字符串 | 数位dp+kmp | forget it...

第183场周赛 2020/4/5

比赛链接
1405. 最长快乐字符串 | 贪心 | 2020.4.5
1406. 石子游戏 III | 博弈dp | 2020.4.5

LCP春季编程大赛 个人赛 2020/4/18

比赛链接

24场双周赛 2020/4/18

周赛链接
和为 K 的最少斐波那契数字数目 | 2020.4.18

第 185 场周赛 字节跳动 2020/4/19

周赛链接
5390. 数青蛙 | 2020.4.19
5391. 生成数组 | 2020.4.19

第 186 场周赛 2020/4/26

周赛链接
5394. 对角线遍历 II | 2020.4.26
5180. 带限制的子序列和 | 2020.4.26

LCP春季编程大赛 战队赛 2020/4/26

比赛链接

第 25 场双周赛 2020/5/2

周赛链接
1432. 改变一个整数能得到的最大差值 | 精心/暴力 |2020/5/2
1434. 每个人戴不同帽子的方案数 |动态规划+状态压缩 | 2020/5/6

第 187 场周赛 2020/5/3

周赛链接
5402. 绝对差不超过限制的最长连续子数组 | 滑窗+单调队列 | 2020.5.3
1439. 有序矩阵中的第 k 个最小数组和 | 暴力解法/最小堆/二分法 |2020.5.3

第 188 场周赛 图森未来 2020/5/10

5405. 形成两个异或相等数组的三元组数目 | 位运算 | 2020.5.10
5406. 收集树上所有苹果的最少时间 | dfs | 2020.5.10
5407. 切披萨的方案数 | dp | 2020.5.10

第 188 场周赛 2020/5/17

比赛链接

  1. 数位成本和为目标值的最大数字 dfs超时 dp通过

第 188 场周赛 2020/5/17

比赛链接
最后一题我服了 这周的两场比赛表现都不好qwq
5415. 圆形靶内的最大飞镖数量

第 188 场周赛 2020/5/17

第 32 场双周赛 2020/8/8

比赛链接
5468. 第 k 个缺失的正整数：这道题可以对比268. 缺失数字(位运算)和字节的面试题41. 缺失的第一个正数(列表/位运算，最优时间复杂度为O(n)，不是O(max(arr))

剑指 Offer 29. 顺时针打印矩阵 / 54. 螺旋矩阵：这种设定四个边界的方法更加清晰。

相关文章

网友评论

      本文标题：leetcode

      本文链接：https://www.haomeiwen.com/subject/kknithtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|leetcode|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！