leetcode200题模式总结

leetcode中有很多算法题，这里对其前200题中的基本模式进行总结。
https://leetcode.cn/problemset/algorithms/?page=45

线性结构 数组或链表

排序 快排，桶排序，计数排序，插入排序，冒泡排序

二分

• 排序后二分
• 不是有序的，想办法在有序的中二分
• 只要能抛弃一半就能二分。

单指针

• 从左向右遍历
• 从右向左
• 枚举中心向两边

双指针

• 滑动窗口从左向右
• 从两端向中间
• 快慢指针
• 快慢指针到终点，互换起点再继续

3指针，4指针

枚举a=0,1,2…n. b,c在[a+1,n]区间内跑双指针

单调栈

动态规划

• dp[i] = dp[i-1]
• dp[i] = dp[i-k]
• dp[i][K] i位置有k中情况
• 逆序DP
• 两两，到33，到44，到55的DP

旋转与翻转

• 旋转问题可以用翻转解决

其他

• 位运算优化
• 打表

线性结构，两个数组或链表

动态规划

• dp[i][j]与dp[i-1][j],dp[i][j-1]
• 滚动数组优化
• 原地复制

线性结构，k个数组或链表

• 归并
• 堆中放每个的表头

矩阵结构

• dp[i][j]=dp[i-1][j],dp[i][j-1],dp[i-1][j-1]
• 位运算优化
• 矩阵上二分查找，按列，按行
• 回溯+剪枝
• 按层遍历外内中
• 选中0行0列为临时存储

树

• 先根遍历
• 后根遍历
• 中根遍历
• Morris 遍历
• DFS
• BFS
• 二叉搜索树
• 中序遍历考虑相邻两个元素
• 上下层遍历
• 栈辅助遍历，考虑栈与树
• 插入虚拟结点，返回时再入入值
• 利用i层计算i+1层
• 动态规划，按层
• 转树转图，一个点变多个点
• 双向广搜

图

• 问题转为图

有难度的算法

• KMP Manacher
• 状态机(DFA,NFA)
• 全排列下一个
• 牛顿迭代
• 矩阵快速幂
• 树的Morris 遍历
• 格雷码
• n &= n - 1;
• 拓扑排序

困难的题目

• 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
• 柱状图中的最大矩形。类似接雨水
• 生成n个数的格雷码
• 前序和中序遍历恢复出二叉树
• 二叉树按先序遍历展开为链表
• 发糖果
• 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
• 环形列表找出环入口
• 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
• 给定一个整数 n ，返回 n! 结果中尾随零的数量。
• 质数：埃氏筛 线性筛
• 重复的DNA序列
• 给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）
• 快乐数
• 同构字符串
• 课程表：选课有依赖，拓扑排序

200题目如下

无序数组中寻找两数相加之和等于K.
1.枚举任意两个数对，看之和是否是K. C(n,2) O(n^2)
2. 枚举一个数a, 在剩下的数中查找k-a. 借助hash表
3. 先排序，转为有序数组中寻找两数相加之和等于K的问题。


有序数组中寻找两数相加之和等于K
左右指针向中间靠近

两个逆序数字单向链表相加 1->2->8 +  1->1->2
对位相加，最后进位        2->3->0->1

字符串s中最长不含重复字母的子串： abcdefa 中是abcdef
1.动态规划
last[c]中记录字母c出现的最大位置
dp[i]:s[i]为结尾的最大长度
dp[i]=i-last[s[i]]
last[s[i]] = max(last[s[i]], i)
2. 滑动窗口
left=0, right从0到n-1遍历。
while: s[right]在set中，set.erase(s[left++]).
set.insert(s[right])


两个正序数组的中位数：注意(m+n)是偶数，要平均值
1.归并排序，但不归并，找(m+n)/2个数的位置
2.两个数组中进行二分：转为找第k小的数, 想办法排除k/2个值。 平常2分是排除(m+n)/2个
A[k/2-1] 比较 B[k/2-1]
12345
12456
3. 划分：长度小的数组中二分k1=m/2, 则长的数组中k2=k-k1, 比较A[k1] B[k2]


最长回文子串：注意长度是奇偶
1.动态规划
p(i,j)表示i到j是否是回文，如果是p(i-1,j+1)就能判断
p(0,0), p(1,1), p(2,2)
2.中心扩展，枚举每个字符为中心
3. Manacher 算法


将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
1.二级矩阵模拟
2.压缩矩阵
3.数学计算，直接构造


32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果，不能用64位，注意溢出
 模10乘10.注意判断当前数字加入是否溢出
 if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
	return 0;
 }
 rev = rev * 10 + digit;


字符串转换成一个 32 位有符号整数： 注意溢出
1.状态机


判断整数x 是一个回文整数：负数不是
/10 *10
反转一半的数字，另一半大于新的一半就要继续


字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
1.动态规划 dp[i][j]表示s的前i个能否与p的前j个字符匹配
2.DFA生成有限状态机. NFA->DFA


最多水的容器A: [1,8,6,2,5,4,8,3,7]选两个柱子，去了其他柱子看能盛最多的水
1.左右双指针


整数转罗马数字
 1.模拟 找小于n的最大逻马数字，减掉继续
 
 
 字符串数组中的最长公共前缀
 从左向右遍历，计算。 纵向计算。  十分计算
 小于最短的
 2分长度，
 
 
 整数的数组nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 找出所有的
  排序
  3指针first =x结点的左边。保持原始相对位置
双指针

字符串s2是不是s1扰乱后的字符串？
s长度为1停止
扰乱：1.s从随机位置分为x+y  x+y可能随机为y+x.
对x,y分别进行上述扰乱

二维动态规划
或者记忆化搜索


合并两个有序数组A,B到A.
倒着归并

生成n个数的格雷码
n个不同的数围城圈，相邻数字只有一个二进制bit不同
每个数字在[0,2^n-1]中

：对称生成
二进制序列转：g(i)=b(i+1)⊕b(i),    0≤i left展开 ->right展开
用栈辅助迭代
具体做法是，对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。



给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
dp[i][j]二维dp


完全二叉树，每个结点中加个next结点，next指向同一层自己右侧结点
BFS每层设置next
先建立第i层的next,再建立i+1层。利用第i层。 p指向第i层最左结点

生成杨辉三角整个三角
模拟数学计算


生成杨辉三角整个三角，只要第i行
滚动数组。只要第两行
一行数组，倒着计算
直接用公式递推计算： row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;


数字三角形从顶层到底层的路径上数字最小和
动态规划dp[i][j]=min(dp[i-1][j],dp[i][j])+A[i][j]
滚动数组优化空间


prices[i]表示第i天股票的价格只买一次卖一次的最大利润
price[i]-minprice(前边最小值)


买卖股票，只能挂有一支。但可买卖多次
dp[i][0]表示手里没股票的最大利润
dp[i][1]表示手里有股票的最大利润
2.贪心，相邻两天a [1, 2, 3, 4]
把每个数放入hash表。然后枚举每个数字k. 在hash表中找k+1,k+2....   可以优化掉已经找的数。找了k，就不要试k+1了
也就是从k，双向找：k-1, k+1


给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间数字。遍历所有路径找到所有数字之和
dfs
bfs


给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
对于每个边界上的O为起点dfs表示。 没标记的换成X。


给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
dp[i][j]表示i到j是不是回文。记忆化搜索
回溯枚举所有切割点。每个点有切还是不切两种情况


给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的 最少分割次数 。
dp[i] 表示字符串的前缀 s[0..i]s[0..i] 的最少分割次数。要想得出 f[i]f[i] 的值，我们可以考虑枚举 s[0..i]s[0..i]



给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
dfs/bfs 用hash表记录结点是不是访问过



加油站。油箱容量无限。能否回来。边上要耗油。 可以任选加油站出发。 gas = [1,2,3,4,5], cost = [3,4,5,1,2]
枚举起点。走过的不能回来的加油站不能当新起点了


发糖果，ratings = [1,0,2]。相邻的分高的糖果得多。至少要多少糖果
两次遍历数组。 记录上长升下降的端点。


给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
异或


给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
hash表
依次确定每一个二进制位。第i位出的1次数是0次还是3次。 要找的数是1个。


复制带随机指针的链表
在每个结点后插入复制的结点，最后再剥离出来。


给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
暴力回溯。
dp[i]表示前s[i]能不能。 dp[i+1] = dp [i+1-j]和dp[0...j]能不能。j=0...i


给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。返回所有的拼发
暴力回溯+记忆化搜索


环形列表判断是否有环
hash表
快慢指针


环形列表找出环入口
双指针


重排列表123456变成162534
寻找链表中点(快慢指针) + 链表逆序 + 合并链表


给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
前序遍历：Morris 遍历，递归，迭代三种方式


二叉树后序遍历
Morris 遍历，递归，迭代三种方式



LRU 缓存


给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
与数组的一样。



给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
自顶向下归并排序：找到中点，二分排序
自底向上归并排序：两两归并


给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
哈希表，记录斜率。分子和分母组成的二元组来代表斜率
加点优化


逆波兰表达式求值tokens = ["2","1","+","3","*"]



给你一个字符串 s ，请你反转字符串中 单词 的顺序。
split再翻转
原地单词翻转
字符串反转，单词再反转


给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组
用 fmax(i) 来表示以第 i 个元素结尾的乘积最大子数组的乘积
最大最小都要都要保存。考虑负数。


寻找旋转排序数组中的最小值



设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
辅助栈，记录最小



给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
哈希集合
使用双指针的方法，可以将空间复杂度降至 O(1)O(1)。
PA,PB同时移动。PA==NULL时从PB开始。  PB==NULL时放到PA. 相交会相遇



给你一个整数数组 nums，找到峰值元素并返回其索引。
二分查找。


给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0
桶排序，计数排序后算差


版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。比较版本号的大小
split再转int再比较
双指针



给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。如果小数部分为循环小数，则将循环的部分括在括号内。如果存在多个答案，只需返回 任意一个 。


给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。
类似进制转换


给定一个整数 n ，返回 n! 结果中尾随零的数量。
计算2，5，10的个数


实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
先遍历好
用栈


给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
排序，两个数a和b可以组合成ab和ba，这两个新数字谁大谁排前面



给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

哈希表 + 滑动窗口 + 位运算



给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
动态规划：
buy[i][j] 表示对于数组 \textit{prices}[0..i]prices[0..i] 中的价格而言，进行恰好 jj 笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用 \textit{sell}[i][j]sell[i][j] 表示恰好进行 jj 笔交易，并且当前手上不持有股票，这种情况下的最大利润。


给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
使用额外的数组
环状替换
数组翻转


颠倒给定的 32 位无符号整数的二进制位。
逐位颠倒
若要翻转一个二进制串，可以将其均分成左右两部分，对每部分递归执行翻转操作，然后将左半部分拼在右半部分的后面，即完成了翻转。
由于左右两部分的计算方式是相似的，利用位掩码和位移运算，我们可以自底向上地完成这一分治流程。


编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数
 n &= n - 1;
 
 数组中选m个数，和最大：[1,2,3,1]。 但是选的数不能相邻
 
 
 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 BFS右侧
 DFS: 中右左，每个深度下最右


给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
联通图数量
dfs,bfs
转成图后，并查集



给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。



编写一个算法来判断一个数 n 是不是快乐数。
方法一：用哈希集合检测循环
方法二：快慢指针法
打表，但出现这些数就有环 cycle_members = {4, 16, 37, 58, 89, 145, 42, 20}


给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。



给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
方法一：枚举
埃氏筛
方法三：线性筛


给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。反转链表








实现 Trie (前缀树)


给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 
滑动窗口


选课，拓扑排序

hash表，但是有通配符.
字典树


打家劫舍 II 数字围成圈，先一些数字，不能相邻，但求最大和
dp[i]: 选还是不选

我们需要在给定的字符串 s 的前面添加字符串 s's得到最短的回文串。这里我们用 s'+s表示得到的回文串。求最小s'
Rabin-Karp 字
KMP 算法




找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：只使用数字1到9每个数字 最多使用一次 
二进制枚举


给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
排序或者hash表


城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。
输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

方法一：扫描线 + 优先队列



给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 
从左向右遍历，f[i], hash[x]. 一般向右一边插入hash表



给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
：滑动窗口 + 有序集合


数组中的第K个最大元素
快排分治

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
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829