二叉树
333、最大BST子树
1
2
3
4
5
6
7
8
9
10
11
12
| + 找到最大二叉搜索树子树
+ 自顶向下（递归实现）
+ 如果根节点不是BST
+ 方法：判断root树是否为BST
+ 方法：节点计数
+ 递归左子树、右子树，返回max
+ 递归重要的是想清楚方法的功能
+ 自底向上（后序遍历）
+ 如果下面子树不是BST
+ 则所有父节点都不是BST
+ 父节点的另一子树不一定
+ 结合info信息
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| + 自底向上：从底部开始向上，记录收集信息
+ 原理（向上递推）
+ 左子树是BST，右子树也是BST，root符合条件
+ root也是BST
+ 利用子树的信息，向上递推
+ 准备
+ info类
+ 最大BST子树的：根节点、节点数量、node的最大最小值
+ 实现
+ 返回根节点的info信息（递归）
+ 结束条件：root为null
+ 递归查找左子树info
+ 递归查找右子树info
+ 左右子树的info，四种情况
+ 1、左右最大BST为本身，root大于左最大，root小于右最小
+ 整棵树为BST
+ 2、左子树为空，右子树最大BST为本身，root小于右最小
+ 3、左子树最大BST为本身，右子树为空，root大于左最大
+ 4、左右都为空，root为BST
+ 5、左右不为空（有BST子树），取size最大值
+ li判断、赋值
+ ri判断、赋值
|
练习
94、98、230、101、108、102、104
105、106、297、449
DFS
深度优先搜索：
解决排列组合问题
17、电话号码的字母组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| + 扫描字符
+ DFS：回溯、剪枝
+ 画树状图，从上到下
+ 实现
+ dfs（递归）
+ 枚举这一层可以做的选择
+ 根据参数，获取每一层
+ 遍历所有选择
+ 保存当前选择到字符数组char[]（记录结果）
+ 选择当前值进入下一层
+ 结束条件：层数达到最底层，char[]结果加入list
+ 递归天然特性，自动回溯
+ 栈
+ 原理
+ 遍历 + 递归 + 回溯
+ 优化
+ 成员变量改为参数
|
46、全排列
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
| + dfs
+ 结束条件：到达最后一层
+ 放入数组到list中
+ 遍历（枚举当前一层的选择：boolean数组标识是否被选择）
+ 存储当前选择到数组中
+ 标记为已选择
+ 递归到下一层
+ 回溯回来-还原
+ 设置为未标记
+ 原理
+ 遍历选择
+ 判断是否使用
+ 记录结果
+ 往下递归
+ 设置未使用
+ 结束：递归到最后一层，添加结果
+ 优化
+ 用list存储结果，省略boolean[]
+ 判断是否能用的选择？
+ 查找是否list中contains这个元素：O(n)
+ 回溯时，删除最后一个结果
+ 保证后面的选择继续遍历
+ 最理想做法
+ 一个num[]数组即可，不需要result[]，不需要boolean[]
+ 0、1、2分别放123层的选择
+ 循环
+ 让0号位置与0、1、2进行交换
+ 进入下一层，1号位置分别与1、2交换
+ 进入下一层，2号位置与2交换
+ 最后的num[]数组即为结果，装入list
+ 回溯到上一层
+ 天然解决，不重复问题
+ 后面的不能交换前面的，只能跟后面的交换
+ 实现
+ 循环（起始：层数）
+ 交换：当前层数与后面每一位i
+ 基于原数组，非交换后的数组
+ 递归到下一层
+ 回溯，恢复现场
+ 再交换回来，恢复原数组！！！（恢复上层，以便上层下次交换）
|
46、全排列2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| + 序列可重复
+ 全排列，结果不可重复
+ 去重
+ 1、加入结果时，list的contains判断是否存在
+ O(n)
+ 2、位置交换时进行判断（有的交换后多个选择相同）
+ 什么情况下排除？
+ 遍历数组
+ 判断交换位置之间是否存在相同的值
+ 从index开始（index本身也算交换，相同就和后面重复）
+ 若存在相同的值，则说明已经交换过
+ 本位置再次交换，结果相同
+ 不交换，跳过
+ 前面的交换结果不一样，也被排除？
+ 提前剪枝
+ 本质上一样，后面进行排列组合的结果一样
+ 保证index位置值只出现一次
+ 若index一样，后面即使不一样，排列组合也一样
+ 若index头不一样，后面必然不一样
|
22、括号生成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| + 生成指定数量小括号
+ 合法
+ 排列组合
+ 总量：左括号3个，右括号3个
+ 限制：当剩余数量相同（已经匹配完），必须选左括号
+ 实现
+ 特殊情况
+ dfs递归（传入左括号，右括号剩余情况）
+ 结束条件：最后一层，添加结果
+ 情况判断（拆开for循环的选择，分别判断）
+ 左括号大于0
+ 本层选择左括号
+ 递归下一层，左括号-1
+ 右括号大于0，右不等于左
+ 本层选择右括号
+ 递归下一层，右括号-1
+ 回溯，不需要恢复
|
练习
51、52、112、113
39、93
1
2
3
4
5
6
7
8
9
10
11
| + 路径总和2
+ 结束条件
+ 边界条件：达到叶子节点停止
+ 添加结果：路径和是否满足，满足则添加
+ 参数：剩余选择的值总和
+ 组合总和
+ 找出总和为target的组合
+ 元素可以选择多次！！
+ dfs
+ 参数：剩余值
+ 根据剩余值，枚举可选择值
|
总结
DFS：
1、结束条件：边界条件，添加结果
2、每一层，for枚举选择
高频题
283、移动零
1
2
3
4
| + 一趟遍历 + 双指针（保证相对顺序）
+ 遇到非0的挪到前面
+ i和cur交换
+ 同时后移
|
1、两数之和
1
2
3
4
5
6
| + 暴力 n²
+ 枚举全部情况
+ 一次遍历
+ 扫描到每一个数，判断前面有没有target-i的数（O(1)查找）
+ map
+ sort&双指针（头尾）
|
15、三数之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| + 暴力 O(n3)
+ 枚举每个三元组
+ 去重
+ 暴力优化
+ 1、sort排序
+ 2、i遍历每个元素
+ 去重
+ 若i与前面重复，则跳过
+ l和r指针指向后面区间的头尾
+ while循环查找和
+ 偏小
+ 跳过相同元素
+ l++
+ 偏大
+ 跳过相同元素
+ r--
+ 原理
+ 定一值，获取新的target
+ 在剩下区间搜索和为target，双指针法
+ 区间
+ 偏门做法（复杂）
+ 尽可能排除不必要扫描
|
50、pow(x,n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| + 暴力O(n)
+ while循环
+ 快速幂（分治）
+ O(logn)
+ 递归法
+ 结束条件：n为0
+ 递归拆分
+ 结果相乘
+ 递归：复杂度计算
+ 非递归法
+ 循环
+ x——x2——x4——x8——x16
+ 结果相乘，需要的参数为1，不需要的参数为0
+ 根据n的二进制位判断0/1
+ 负数的/2和>>1不同
+ 快速幂补充
+ 不能先算x的y次方再模（可能溢出）
+ 使用公式
+ 每次相乘之前都模z，相乘之后模z
+ 非递归
+ 递归
|
面试题62、圆圈中最后剩下的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| + 约瑟夫环问题
+ 循环数n个数，删除
+ 求最后一个数
+ 环形链表解决
+ 环形链表不好实现
+ 数学公式解决
+ 递归实现（自顶向下）
+ 结束条件：n为1，返回0（需要剩下一个人）
+ 公式递归
+ 非递归实现（自底向上）
+ 遍历人数
+ 使用公式，从小到大递推
+ 公式推导
+ 先杀一个元素
+ 剩下n-1个元素和n个元素，最后的元素相同
+ 开始的索引不同，n-1个相比n偏移了m个位置
+ 防止越界，最后模上长度
+ 编号不从0开始：
+ 正常算出最后元素，加上偏移位置即可
+ 中间删除位置都是相对的
|
54、螺旋矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| + 顺时针列出矩阵元素
+ 思路
+ 标识每一圈
+ while循环每一圈
+ 遍历top行：left到right
+ top++
+ 遍历right列：top到bottom
+ right--
+ 特殊处理：奇数行、偶数列情况
+ top>bottom || left > right
+ 遍历bottom行：right到left
+ bottom--
+ 遍历left列：bottom到top
+ left++
|
146、LRU缓存机制
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
| + LRU：最近最少使用
+ 操作系统页面置换算法，选择LRU的页面淘汰
+ 常用实现方式
+ 哈希表 + 双向链表
+ 实现
+ 准备
+ hashmap(capacity)
+ get()
+ 元素存在
+ 链表插入：
+ 返回元素
+ put()
+ 条件判断
+ 是否已经存在？更新值
+ 容量达到capacity，淘汰算法：
+ List存储最近使用的key
+ 尾插，删除头元素
+ 双向链表
+ put
+ 自己实现双向链表
+ 准备
+ 虚拟头、尾节点
+ node类
+ key、value、双向指针
+ 节点被get、put修改、添加之后：更新优先级
+ 头插法，插入到头结点的后面
+ 删除节点deleteNode
+ 后面的pre指向前面的node
+ 前面的next指向后面的node
+ 添加到头结点后面insertFirst
+ 先指向后面的节点，再连接头节点
+ put新元素，且容量已满：淘汰最后节点
+ 删除最后一个node节点、删除map中的值
+ map remove
+ deleteNode
+ insertFirst
+ 主流原理
+ 哈希表 + 双向链表（自己实现）
+ 哈希表
+ 存储k-v
+ 双向链表
+ 维护元素的使用优先级
+ 新元素插到最前面
+ 淘汰链表的最后一个元素
+ get
+ get时提升优先级（插入到链表最前面）
+ put
+ 修改
+ 提升优先级
+ 添加新元素，未满
+ 直接put到map
+ 提升优先级
+ 添加新元素，已满
+ 淘汰链表末尾元素
+ 提升新元素的优先级
|
7、整数反转
1
2
3
4
5
| + 1、转为字符串 + 双指针
+ 2、取各个位数
+ 循环倒序取出每一位（取模）
+ 正序组合新的数
+ 防止溢出（计算回去判断是否是之前的值），返回0
|
252、会议室
1
2
3
4
| + 判断区间是否重叠
+ 排序sort（开始时间）
+ 判断前后两个区间
+ 前面结束时间和后面开始时间是否符合
|
252、会议室2
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
| + 避免会议冲突，至少需要多少间会议室
+ 贪心算法
+ 1、最小堆（小顶堆：获取最小值O(1)）
+ 思路
+ 排序
+ 结束时间放到堆中
+ 开始时间比较堆顶的结束时间
+ 符合，则移除堆顶，结束时间进入堆
+ 每次拿最小值：越小结束的越先利用
+ 实现
+ 准备：
+ priorityqueue最小堆
+ sort开始时间
+ 添加0号会议结束时间
+ 遍历每个会议
+ 判断i的开始时间是否大于堆顶
+ 堆顶：占用一个会议室的最早会议结束时间
+ 大于
+ 堆顶移除
+ i的结束时间进入堆
+ 小于
+ 再开一间会议室
+ i的结束时间进入堆
+ 原理
+ 排排序开始时间
+ 堆中排序结束时间
+ 2、分开排序（相当于提前排好堆）
+ 分别排序开始、结束时间
+ 扫描会议开始时间
+ 只关心结束时间最短的
+ 小于结束时间最小值，开一个房间
+ 大于结束时间最小值，结束时间后移（堆顶变化）
+ 原理：贪心 + 一次遍历
+ 按照会议（排序好）进行遍历
+ 维护全部会议室最小结束时间
+ 若小于全部会议室结束时间，加会议室
+ 若大于一间的结束时间，可以利用会议室
+ 最小结束时间更新（上一个时间已被使用）
|
11、盛最多水的容器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| + 暴力
+ 枚举任意两根柱子
+ 维护最大值
+ 双指针（首尾） + 一次遍历
+ 小的指针移动
+ 大柱子不动，为了求出最大值
+ 减少不必要、小的组合
+ 实现
+ 循环（左指针小于右指针）
+ 小于移动
+ 求面积
+ 宽度、高度（小的）
+ 优化：跳过不必要组合
+ 维护左右算过的min
+ 小于min直接跳过
|
42、接雨水
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、求每一行能接多少
+ 2、求每根柱子i上接多少水
+ 思路
+ i接的水取决于min（左、右柱子最大值）
+ 左边右边必须有比i大的柱子
+ 接水量：高度减去当前柱子高度
+ 实现
+ 准备
+ 左、右最大柱子数组
+ 求左边最大值数组（一次遍历 or 动态规划）
+ 动态规划dp[i]：i左边的最大值
+ dp[i] = max(high[i],dp[i-1])
+ i-1左边柱子最大值、i-1柱子
+ 一次遍历：max记录最大值
+ 遍历每个值，进行比较，维护max
+ 求右边最大值数组
+ 遍历每个柱子求接水量（第二个到倒数第二个）
+ 获取左右大柱子最小的高度
+ 若大于当前高度
+ 接水：减去当前高度
+ 优化
+ 放到一个循环中
+ 只记录前面的max，省略数组
+ 3、双指针（左右边界） + 一次遍历
+ while循环
+ 取出较小的柱子lower
+ 高度小的往前移动
+ 维护每次较小的柱子的lowerMax
+ 每个柱子能放多少水：lowerMax - lower
+ 原理
+ 往中间移动过程中，若小于外围的（两个柱子中的最小值）的最大值
+ 说明这个柱子可以盛水
+ lowermax一直更新，所以必是外围最大值（两边最小那个）
+ 双指针相比之前
+ 之前：先搞清楚了每个柱子左右最大值是多少
+ 所以直接可以遍历取值计算
+ 一次遍历：边遍历，边维护左边右边最大值
+ 没有必要把每个位置左右都求出来
+ 只需要遍历过程中max记录就行
+ 因为每次都是取左右最小的那个
+ 所以另一边一定大于当前最大值
+ 所以只需要维护当前边的最大值进行计算即可
|
练习
215、315、4、149、200
总结
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
| + 刷题建议
+ 10-15分钟没思路，看答案
+ 读懂答案，照抄一遍（自己思路 + 作者思路）
+ 自己手写一遍
+ 每道题所有解法都看一遍！！
+ 英文版讨论区靠前的代码（全世界大神写的）
+ 优雅、精简
+ 观摩中文、英文打败时间100%的提交代码
+ 面试建议
+ 沟通题目细节
+ 时间、空间复杂度
+ 口述：把能想到的专业术语关键词、解法都可以说出来
+ 每种解法空间、时间复杂度
+ 笔试、机试
+ 写思路比代码更重要
+ 写出空间时间复杂度
+ 联想关键词
+ 数组：
+ 排序、双指针、三指针、扫描方向、一次遍历
+ 链表：
+ 虚拟头结点、双指针、快慢指针、翻转、中间节点
+ 排列组合
+ DFS
+ 最值
+ 贪心、排序、动态优化
+ 对称\顺序
+ 栈\队列
+ 二叉树
+ 递归、遍历
+ 搜索数据要求O(1)时间
+ 哈希表
+ 完结撒花
|
