-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathnote
More file actions
213 lines (189 loc) · 15.2 KB
/
note
File metadata and controls
213 lines (189 loc) · 15.2 KB
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
已实现的有：共121题
剑指offer第2版：共75题
简单：共41题
中等：共29题
难：共5题
================================================
复刷顺序：
第一类：1) frequency-5
(23) 2) bitmap-5
-----------------------------------------第1天
3) sort-5
4) string-4
5) hash-4
-----------------------------------------第2天
第二类：6) array-18
(60)
-----------------------------------------第3天
7) heap-3
8) stack-7
-----------------------------------------第4天
9) linkedlist-11
-----------------------------------------第5天
10) tree-21
-----------------------------------------第6天
第三类：11) recursion-2
(40) 12) bfs-0
13) dfs-1
14) divide-2
15) greedy-2
-----------------------------------------第7天
16) backtrack-10
-----------------------------------------第8天
17) dynamic-24
-----------------------------------------第9天
==================================================
========================================================================================================================
frequency
7. 整数反转 ***
9. 回文数 ***
48. 旋转图像 ???? 先转置再反转行
146. LRU缓存机制 *** 双向链表 + HashMap
208. 实现 Trie (前缀树)
bitmap 位运算
136. 只出现一次的数字 ***
191. 位1的个数 ***
231. 2的幂 ***
338. 比特位计数 ***
461. 汉明距离 ***
sort
冒泡排序 sort/BubbleSort （n2 稳定） ***
选择排序 sort/ChoiceSort （n2 稳定） ***
插入排序 sort/InsertSort (n2 不稳定) ***
归并排序 sort/MergeSort （nlogn 稳定，非原地排序） ***
快速排序 sort/QuickSort （nlogn 不稳定）**
string
3. 无重复字符的最长子串(返回子串长度) 滑动窗口，Map<Character,Integer>，start = Math.max(start, map.get(c));map.put(c, end+1);res = Math.max(res, end-start+1);
5. 最长回文子串 动态规划 dp[i][j]表示字符串 s 的第 i 到 j 个字母组成的串是否是回文串(x 表示增量，子串长度，)
14. 最长公共前缀 ***
415. 字符串相加
hash
15. 三数之和 *** 排序+双指针
18. 四数之和 ??? 排序+双指针
49. 字母异位词分组 *** 排序+map
242. 有效的字母异位词 *** 迭代,int[] counter = new int[26];counter[s.charAt(i) - 'a']++;counter[t.charAt(i) - 'a']--;if(counter[i] != 0){return false;}
array
剑指 Offer 29. 顺时针打印矩阵 left right top bottom
剑指 Offer 57 - II. 和为s的连续正数序列 滑动窗口法
1. 两数之和
11. 盛最多水的容器 双指针
26. 删除排序数组中的重复项 双指针，return i+1;
27. 移除元素 双指针，return i;
283. 移动零 双指针(方法同27题移除元素)
34. 在排序数组中查找元素的第一个和最后一个位置 二分查找
56. 合并区间 排序
69. x 的平方根 *** 二分法与50题Pow(x, n)相对应
88. 合并两个有序数组 *** p1,p2,p3=p1+p2
238. 除自身以外数组的乘积 先求出左右两边的乘积再相乘
240. 搜索二维矩阵 II 从左下角开始
287. 寻找重复数 排序迭代/快慢指针
448. 找到所有数组中消失的数字 迭代并赋值为-1，最后大于0的既满足（数组中数都大于0）
581. 最短无序连续子数组 排序迭代对比原数组
674. 最长连续递增序列 *** 滑动窗口
704. 二分查找 ***
heap/Heap
堆的基本操作：堆化，大根堆，小根堆，堆排序
215. 数组中的第K个最大元素 *** 优先级队列 PriorityQueue-小根堆，比较元素默认int的自然升序排序
347. 前K个高频元素 *** PriorityQueue-小根堆，自定义比较器比较频次
703. 数据流中的第K大元素 *** 优先级队列 PriorityQueue-小根堆,创建类和两个属性 limit 和 queue，构造函数构造好初始数据
stack/queue
20. 有效的括号 *** 栈+HashMap
155. 最小栈 *** 维护两个栈，增删-合理操作两个栈，获取操作相应栈
225. 用队列实现栈 *** q2入栈，q1出栈（注意入栈逻辑）
232. 用栈实现队列 *** s1入队列，s2出队列（注意出队列逻辑）
227. 基本计算器 II *** 加减直接入栈正数或负数，乘除先取出栈顶元素乘以或除以新元素，将结果入栈
239. 滑动窗口最大值 *** ??? LinkedList双向链表队列，构建递减队列，添加，超过长度删除并写入最大值
496. 下一个更大元素 I *** 单调栈，栈和HashMap配合实现
linkedlist
2. 两数相加 *** 与 415. 数字型字符串相加 有异曲同工之妙
21. 合并两个有序链表 *** while循环比对，并next
19. 删除链表的倒数第N个节点 *** 双指针法、栈、迭代len-n+1，推荐使用快慢双指针法
83. 删除排序链表中的重复元素 *** 同26.删除排序数组中的重复元素
24. 两两交换链表中的节点 *** 画图演示，看图写代码，声明两链表，while next和next.next都不为空
206. 反转链表 ******* 声明双指针pre=null, curr = head;curr.next = pre(链表指针反转)，最后返回pre
92. 反转链表 II 指定长度反转 双指针头插法-删除结点递推，画图演示，想图写代码
25 K 个一组翻转链表 ??? （推荐）链表分区(已翻转，待翻转，未翻转)，pre，end，start=pre.next，nextTemp=end.next指针,pre和end移动指针到翻转后的start位置
160 相交链表 *** 双指针法（a+c+b = b+c+a）a=链表1未相交部分，b=链表2未相交部分，c=两链表相交部分
141 环形链表（判断链表是否有环） 1-哈希表；（推荐）2-双指针法-快慢指针 while(fast != null && fast.next != null)
142 环形链表 II ***(找出入环点) 1-哈希表；（推荐）2-快慢指针
//148. 排序链表
tree
94. 二叉树的中序遍历 递归和迭代都要会，推荐迭代（一个stack实现）Stack<TreeNode> stack = new Stack<>();（两层while循环，内层放左子树）
144. 二叉树的前序遍历 ***** 递归和迭代都要会，推荐迭代（一个stack实现）while(!stack.isEmpty())
145. 后序遍历二叉树 递归和迭代都要会，推荐迭代（两个stack实现）
102. 二叉树的层序遍历 ***** BFS（一个queue实现）Queue<TreeNode> queue = new LinkedList<>(); 写法同107
107. 二叉树的层次遍历 II （自底向上的层次遍历） BFS（一个queue实现）1-使用队列存储每层元素，用栈存储每层的结果集；2-(推荐)使用java的LinkedList的性质，从上到下遍历，将新遍历的层结果集放入linkedlist的头部
103. 二叉树的锯齿形层次遍历 ***** 使用两个stack交替迭代放值
104. 二叉树的最大深度 *** 1-递归；2-（推荐）层次遍历+累加深度（广度优先搜索）
111. 二叉树的最小深度 *** 1-深度优先搜索，即递归；2-层次遍历，相比104题，多加一个判断，判断是否已经到叶子结点，到了直接return depth（if (node.left == null && node.right == null) ）
199. 二叉树的右视图 ***** 1-广度优先搜索，即层次遍历（推荐）将每一层的最后一个节点放入结果列表
543. 二叉树的直径 递归，左子树的深度+右子树的深度 Math.max(ans, leftDepth + rightDepth);return Math.max(leftDepth, rightDepth) + 1;
101. 对称二叉树 ***** 迭代：队列，放左右结点和右左结点
226. 翻转二叉树 ***** 迭代：用queue层次遍历交换处理,循环体内，每次取出一个node
617. 合并二叉树 递归
96. 不同的二叉搜索树 动态规划,i为根，G(i-1)*G(n-i) 求和（1<= i <=n）
98. 验证二叉搜索树??? 中序遍历：遍历后是升序
235. 二叉搜索树的最近公共祖先 ***** while循环判断根的值和另两个参数的大小。while (root != null) {
236. 二叉树的最近公共祖先 *** 递归
538. 把二叉搜索树转换为累加树 递归-反序中序遍历
112. 路径总和 *** 判断是否存在 层次遍历(BFS推荐)
113. 路径之和 II *** 返回所有路径 同112，用map把结点父节点记录下来，最后求路径反转
437. 路径之和 III *** 不需要到叶子结点返回所有路径的数量 两层递归
recursion
汉诺塔问题 HanNuoTa 递归，理解记忆
172. 阶乘后的零 *** (打印阶乘 Recursion) 递归或迭代获取阶乘后结果，再取0的个数
bfs
dfs
22. 括号生成 *** 递归dfs，左右括号剩余数量，left>right剪枝, 左右括号数递减，字符串追加
divide
50. Pow(x, n) *** 迭代，初始条件分类讨论判断，定义res和中间x，while(n>0)
169. 多数元素 *** 1-排序；2-哈希表（推荐）放入hashmap计数，判断数量是否大于len/2
greedy
122. 买卖股票的最佳时机 II *** 贪心-迭代计算只要有收益就累加到max，返回max; 动态规划
55. 跳跃游戏 贪心-倒序遍历，如果n-2下标能到达n-1下标，意味着前面只要有坐标能够到达n-2即可完成跳跃，于是末尾位置更改为n-2，这样构成一个子问题，迭代求解。
backtrack
36. 有效的数独(9X9) 1-哈希数组（占用空间）2-二维数组(推荐)，第一维表示位置，第二维表示1-9数字，出现过对应二维数组值置为1标识起来，下次循环等于1直接return false
39. 组合总和 *** 元素无重复可以取多次(结果都不可重复) 回溯法-先排序，递归然后循环并剪枝，最后回溯dfs（start=i）
40. 组合总和 II ***元素有重复只能取一次(结果都不可重复) 回溯法-先排序，递归然后循环并剪枝，最后回溯dfs（start=i+1）;if (i > start && nums[i - 1] == nums[i])(剪枝)
46. 全排列 *** 给定数组无重复元素(结果都不可重复) 回溯法-depth、boolen[]
47. 全排列II ***给定数组有重复元素(结果都不可重复) 回溯法-先排序depth、boolen[];i > 0 && nums[i] == nums[i - 1] && !used[i - 1](剪枝)
78. 子集 *** 给定数组无重复元素(结果都不可重复) 回溯法-start,dfs(start=i + 1),递归方法先res.add(new ArrayList<>(curList));
90. 子集II***给定数组有重复元素(结果都不可重复) 回溯法-先排序,剪枝
//51. N皇后 *** ??
79. 单词搜索 ???? 回溯法-定义boolean[][] visited;dfs(int index, char[][] board, String word, int x, int y),判断上|下|左|右
0-1背包问题 /backtrack/ZeroOneBag
dynamic
0-1背包问题 /dynamicprogramming/ZeroOndBag3======动态规划优化空间（滚动数组，从后往前）
416. 分割等和子集(0-1背包)数组是否能分割成两个元素和相等的子集 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
474. 一和零(0-1背包)(String[] strs, int m, int n) 返回 strs 的最大子集的长度,dp[i][j][k]=Math.max(dp[i-1][j][k], dp[i-1][j-cnt[0]][k-cnt[1]] + 1);
494. 目标和(0-1背包)(int[] nums, int S)可加减 （同416）dp[i][j] = dp[i-1][j]+dp[i - 1][j-nums[i-1]];
322. 零钱兑换(完全背包)返回所需的最少的硬币个数 Math.min(dp[i], dp[i - coin] + 1);return dp[amount] > amount ? -1 : dp[amount];
518.零钱兑换 II (完全背包)返回所有组合数 dp[x] = dp[x] + dp[x - coin];return dp[amount];
(股票买卖系列 start)===人为规定买入股票算一笔交易,dp[i][j][k]: i 表示第几天（0-n），j表示交易了几次（0,1,2），k表示是否持股（0-不持股,1-持股）
由于当前天只参考了昨天的状态值，因此可以考虑使用「滚动数组」。
121、最多买卖(交易)一次 双指针法，记录最小值和利益最大值
122、最多买卖(交易)多次，不限次 贪心-迭代计算只要有收益就累加到max，返回max;
123、最多买卖(交易)两次 初始化：dp[0][1][1] = -prices[0];dp[0][2][1] = Integer.MIN_VALUE;
188、最多买卖(交易)K次 特判k>=len/2,转122，初始化：第i天交易k次持有股票dp[i][j][1] = Integer.MIN_VALUE;(还没发生的交易)i和j都有1个位置的偏移
309、可以买卖(交易)多次，有冷冻期 dp[i][0]: 手上不持有股票不冷冻，dp[i][1]: 手上持有股票时，dp[i][2]: 手上不持有股票冷冻
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);dp[i][2] = dp[i - 1][1] + prices[i];
714、 可以买卖(交易)多次，一次买卖含一次手续费
(股票买卖系列 end)
70. 爬楼梯 *** 1-迭代，2-动态规划，dp[i] = dp[i - 1] + dp[i - 2];
120. 三角形最小路径和(自底向上) for(int i = n - 1; i >= 0; i--);for(int j = 0; j <= i; j++);dp[j]=Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
64. 最小路径和(方格子自顶向下) 初始化dp[0][0]=grid[0][0];边界初始化第0行和第0列，for(int j=1;j<cols;j++);dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
62. 不同路径(m*n网格) 边界初始化,dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
53. 最大子序和-返回子数组的和 1-动态规划，2-定义pre=nums[0]和res=nums[0]，for{pre = Math.max(pre + nums[i], nums[i]);res = Math.max(res, pre);}
152. 乘积最大子数组-返回子数组的乘积 int[][] dp = new int[len][2];dp[i][0]：以 nums[i] 结尾的连续子数组的最小值,dp[i][1]：以 nums[i] 结尾的连续子数组的最大值
300. 最长上升子序列-返回子序列的长度 for (int i = 1; i < len; i++);for(int j = 0; j < i; j++)两层循环if (nums[j] < nums[i])dp[i] = Math.max(dp[i], dp[j] + 1);
279. 完全平方数-返回需要的完全平方个数 new int[n + 1];内层循环for (int j = 1; i - j * j >= 0; j++){dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}
343. 整数拆分-返回最大乘积 int[] dp=new int[n+1]; dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积
for (int i = 2; i <= n; i++);for(int j = 1; j < i; j++){dp[i]=Math.max(dp[i], Math.max(dp[i-j]*j, (i-j) * j));}
72. 编辑距离 *** 边界初始化，if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}else{
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;}
198. 打家劫舍 *** dp[i] 表示前 i 间房屋能偷窃到的最高总金额。dp[i] = Math.max(dp[i - 2]+nums[i], dp[i-1]);第i间房偷dp[i-2]+nums[i]；第i间房不偷dp[i-1]
213. 打家劫舍II (环形房屋在198题的基础上，选择不偷第一家或不偷最后一家)Math.max(myRob2(Arrays.copyOfRange(nums, 0, len-1)),myRob2(Arrays.copyOfRange(nums,1,len)));
337. 打家劫舍III (二叉树房屋) 1-树的后序遍历；
（dp[0]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点不偷; dp[1]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点偷）
int[] left = dfs(root.left); int[] right = dfs(root.right);int[] res = new int[2];
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);res[1] = root.val + left[0] + right[0];