字符串
面试题01.09.字符串轮转
1
2
3
4
5
6
7
8
9
10
11
| + 旋转词
+ 特点
+ 拼接两个相同的词
+ 滑动窗口，每个窗口都包含全部词
+ 判断是否为其子串
+ contains()方法
+ KMP
+ 两个数据结构拼接
+ 旋转
+ 链表相交
...
|
572、另一个树的子树
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
| + 判断一棵树是否是另一棵树的子树
+ 遍历（非层次遍历）
+ 暴力
+ 找到子树
+ 判断是否所有子节点都相等
+ 二叉树序列化
+ 遍历，序列化为字符串
+ 如果序列化后是其子串
+ 则为其子树
+ 序列化
+ 每个节点结束后加！（连在一起位数都无法判断）
+ 空节点值为#（保证构建的二叉树唯一）
+ 只有一个后序遍历无空节点，构建无数棵树
+ 如何反序列化？
+ 实现
+ 两个树序列化
+ 序列化（递归）
+ 结束条件：节点为空，序列化#
+ 序列化当前左子树
+ 序列化右子树
+ 拼接当前子树
+ StringBuilder拼接字符串
+ 判断是否为子串
+ contains()
+ 打印树
+ 测试KMP
+ contains改为KMP
+ 前序遍历bug
+ 解决：最前面再加个符号
+ 二叉树序列化字符串
+ 判断两个树的结构方面的
|
242、有效的字母异位词
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| + 两个字符串，所有字母都一样，字母的顺序不一样
+ 1、map统计字符
+ 统计每个字符的kv
+ 判断map中是否还有值
+ 2、数组统计字符（都是小写）轻量级
+ askii码进行计算
+ arr[26]统计所有字符的数量
+ 实现
+ 扫描数组
+ 一个字符串，进行相加
+ 一个字符串，进行相减
+ 若数量小于0，则直接返回false
+ 最后判断是否数组元素都为0
+ 优化
+ 继续空间换时间
+ charAt()一直在调方法
+ 字符串转为char[]数组
+ 直接用索引进行取值，效率很快
|
151、翻转字符串里的单词
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| + 1、消除字符串中多余空格
+ 双指针
+ 若为字符，赋值到前面
+ 若为空格，且前面为字符，赋值空格
+ flag标记：前一个字符是否为空格
+ 2、获取字符串有效长度
+ 若最后为空格，则为cur的位置-1
+ 若最后为字符，则cur位置
+ 3、方法：翻转指定范围字符串
+ 左右边界为两个指针
+ 循环（指针不重合）
+ 左右交换指针值，指针归中
+ 4、对整个字符串逆序
+ 5、对每个单词进行逆序
+ 扫描数组，记录前一个空格位置pre（哨兵）
+ 发现空格时，结束了一个单词
+ 单词在前一个空格和后一个空格之间
|
3、无重复字符的最长子串
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
| + 类似动态规划
+ 以i结尾的最长无重复串
+ 维护最大值即为结果
+ 扫描字符
+ 求以i结尾的最长不重复串
+ 假设i-1的子串已经求出来（li到i-1不重复）
+ li为i-1子串的起始位置，pi为i字符上一次出现的位置
+ 如果li在pi右边
+ i的子串：li到i
+ 如果li在pi左边
+ i的子串：pi+1到i
+ 如果li==pi
+ i的子串：pi+1到i
+ 记录每个字符上一次出现的位置（map：k-v、arr[]）
+ 实现
+ map
+ 扫描每个字符（从1开始）
+ 如果pi不存在（map中不存在），设置pi为-1，直接li为起始
+ getOrDefault()
+ 如果pi存在
+ li小于或等于pi才改li的值为li+1
+ 其他情况都li不变（li在右边）
+ 维护max记录i到li子串的长度
+ 优化
+ arr[26] + ascii
+ 想出来？
+ 之前有经验！！
+ 经历过，刷题越来越多
+ 扫一眼就知道用什么思路！
|
练习
5、最长回文子串
72、编辑距离
1143、32、1048
总结
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| + 二叉树序列化
+ 序列化反序列化
+ 判断两棵树的的相同结构
+ 字符串查找子串
+ KMP
+ contains()
+ 字符统计
+ map
+ 数组
+ 结构拼接
+ 字符串拼接
+ 判断翻转
+ 链表拼接
+ 查找相交位置
+ 翻转字符串
+ 分割单词
+ 哨兵pre
|
动态规划
面试题47、礼物的最大价值
1
2
3
4
5
6
| + 动态规划
+ 状态定义：dp[i][j]：走到ij的最大价值
+ 初始条件：首行首列，不能放在在循环递推
+ 状态转移方程
+ 一行一行求
+ 依靠上和左的值
|
121、买卖股票的最佳时机
1
2
3
4
5
6
7
8
9
10
11
12
| + 求前面最低买入，和后面最高卖出
+ 从卖的角度思考
+ 每一天都有可能卖，求其最大利润
+ 维护最大利润
+ 扫描一遍 + 双指针
+ 一个指针维护最小值
+ 一个指针遍历
+ 计算与最小值的利润
+ 动态规划
+ 求出相邻两天的价格差
+ 转为：求最大连续子序列和问题
+ dp[i]：以i结尾的最大子序列和
|
72、编辑距离
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
| + 动态规划
+ 状态定义
+ dp i j ：s1 [0,i)转为s2 [0,j)最少操作数
+ s1 的前i个字符转为 s2 前j个字符 最少操作数
+ 初始化
+ [0][j]、[i][0]
+ 最小操作数：i次（全部删除、插入）
+ 状态转移方程
+ 按行推导
+ dp[i][j]
+ 上、左、左上三种情况推得
+ 四种情况
+ dp[i-1][j]转换过来：差一个字符，+ 1
+ aa->bb = aaa -> bb + 1
+ 删除一个字符
+ dp[i][j-1]转换过来：差一个字符，+ 1
+ aa -> b = aa -> bb + 1
+ 插入一个字符
+ dp[i-1][j-1]转换过来：
+ 如果最后一个字符相等：相比之前操作一次，替换一个字符，+1
+ aa -> bb = aaa -> bbb + 1
+ bba -> bbb + 1
+ 换掉一个字符
+ 如果最后一个字符不相等：不操作
+ 最后一个字符不用动，只用操作前面的
+ aa -> bb = aab + bbb
+ 不用操作
+ 遍历，每次求最小转换情况
+ 状态转移方程
+ 考虑所有情况，可以从前面推导来的情况
+ 优化
+ 一维数组
|
5、最长回文子串
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
| + 暴力
+ 双指针遍历所有子串n²
+ 判断回文n
+ 记录最大长度
+ 动态规划
+ 状态定义
+ dp[i][j]：s[i,j]是否为回文串
+ 初始化
+ i = j : T
+ 状态转移方程
+ 子串长度为2，判断元素是否相同
+ 子串长度大于2
+ 如果[i+1,j-1]是回文串，且元素相等，那么是回文串
+ 左右都减去一个元素且为回文串，判断最后元素
+ 遍历方式
+ 无法从左往右
+ 由左下角推导的
+ 实现
+ 准备
+ str转换为char[]
+ dp[i][j]
+ 遍历（从下达到上，从左到右）
+ 最后一个字符必须两个相等 && （长度<=2 或者 子串已经回文）
+ 维护max
+ 优化
+ 一维数组
+ 扩展中心法
+ 以i为中心，向外拓展
+ 以字符间隙为中心，向外拓展
+ 实现
+ 遍历扫描
+ 不管是间隙为中心还是元素为中心，只要给左右元素的位置就行
+ 扫描字符为中心的回文子串
+ 扫描间隙为中心的回文子串
+ 左右扫描回文子串方法
+ 循环，条件（双指针移动且相等）
+ 双指针向外扩散（到边界出退出）
+ 维护最大值
+ 优化
+ 1、减少没必要的扫描
+ 已求得的最长子串长度大于剩下的字符长度
+ 2、中间有很多没必要的扩散
+ 实现
+ l和r左右扩散
+ 找到右边第一个不相等的元素为r
+ 左边相邻元素为l
+ 下一次i跳到r（跳到下一个不相等元素）
+ 中间的元素已经相等，没必要扩散
+ 可能是1个、2个、3个，中间相等的元素（不管多少个）已经构成了回文串
+ 只用从r和l的位置进行扩散就行！！！
+ 原理：
+ 核心：如果元素连续相等，变成一个拓展中心
+ 可以省去间隙的拓展中心
+ 因为每个都找右边第一个不相等的位置
+ 代码
+ 遍历数组
+ 找到右边第一个不相等的位置r
+ while 判断
+ 向左向右扩散
+ i -1、r
+ 循环双指针比较
+ 拓展结束。计算长度，开始索引位置
+ 马拉车算法
+ 原理
+ O(n)
+ 预处理
+ 头尾加特殊字符，元素之间加特殊字符
+ m[i]
+ 以i为拓展中心的最大回文子串的长度（不含#）
+ 以i为拓展中心的最大回文子串的右半部分或左半部分的长度（包含#）
+ 核心
+ l、r、c：前一个回文串，li回文串对称位置，i当前位置
+ 根据前面的回文串，进行对称，获取后面的回文串长度
+ 根据对称性，前面的回文长度等于后面的长度
+ 前提 i + m[i] < r，不能超过对称范围
+ 超过对称范围，外面的元素不一定对称
+ 对称范围内的，若前半部分是回文，则后半部分是回文且相等的
+ 可以保证范围内的都对称，超出的不知道
+ 如果恰好 i + m[i] = r
+ 不一定等于前面的（最少情况），r右边的元素不知，也可能回文
+ 拓展中心法，继续比较
+ 更新c、r、l等
+ 维护max
+ 总结：对称性质
+ 对称范围内的，和对称的回文串长度相等
+ 对称范围外的，需要拓展比较
+ 四种情况
+ i==r，拓展中心法
+ i < r
+ i + m[i] < r，相等
+ i + m[i] = r，最少值，拓展计算
+ i + m[i] > r，最少值，拓展计算
+ 实现
+ 预处理字符
+ 遍历，从第一个元素到最后一个元素
+ i==r
+ i<r，求出根据c求出li（对称）
+ 直接赋值，至少是m[li]
+ 拓展中心法
+ 双指针
+ 更新c、r等
+ 维护max：m[i]
|
暴力
动态规划
拓展中心
拓展中心优化
马拉车
练习
47、72、5优化
1143、53、42、322、面试08.11
300、70、198、213、674、63、122、123、188、714
1235、943、516、376
总结
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| + 三步
+ 状态定义
+ 初始值
+ 状态转移方程
+ 优化
+ 一维——>变量
+ 二维——>变量、数组
+ 注意递推关系
+ 后无效性、前推后
+ 考虑所有情况，可以从前面推导来的情况
+ 拓展中心法
+ 拓展中心法优化
+ 右边第一个不同元素
+ 马拉车算法
+ 回文串对称
|
二叉树
绝大多数题目解决：
递归 + 遍历（前序、中序、后序、层次）
236、二叉树的最近公共祖先
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
| + 两个节点最近的公共祖先
+ 可以为节点本身
+ 递归实现
+ 方法功能：查找以root为根节点的p、q的最近公共祖先
+ 递归
+ 去左子树为根节点找
+ 去右子树为根节点找
+ 结束条件
+ 根节点为空，或者根节点为目标元素
+ 直接返回根节点
+ 错误
+ 如果左子树找到
+ 返回左子树
+ 如果右子树找到
+ 返回右子树
+ 如果左右子树都找不到，说明p、q节点在两个子树
+ root节点即为公共祖先，直接返回root
+ 分析递归方法
+ 如果pq在两边，递归左右子树不能返回null
+ 只有一个节点，应该直接返回该节点
+ 两边同时找到，说明根节点为公共祖先
+ 如果pq都存在，返回公共祖先
+ 正确
+ 左右子树都找到，返回root
+ 左子树或右子树找到，返回找到的节点
+ 都没找到，返回null
+ 原理
+ 向下找到节点就返回节点，找不到就返回null
+ 如果左右都找到，返回root
+ 如果找到一个，说明找到的是节点，继续向上返回
+ 如果为父子节点，父节点返回，其他路没有节点返回，父节点为祖先，符合
|
99、恢复二叉搜索树
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
| + 二叉搜素树
+ 中序遍历升序
+ 错误交换后
+ 中序遍历，找到一个或两个逆序对
+ 实现
+ 递归中序遍历，找到错误节点
+ 退出条件：root为空
+ 递归左子树
+ 比较当前节点和上次遍历节点大小是否逆序
+ 准备两个指针标记错误节点
+ 递归右子树
+ 交换node
+ 交换值
+ 二叉树的Morris遍历
+ 使用前驱节点连线，进行回溯
+ 线索二叉树
+ Morris中序遍历
+ 动态线索二叉树
+ 把原来栈里的指针存放在了node里面
+ 实现
+ 循环（node不为空）
+ 若左子树不为空
+ 找到前驱节点
+ 左子树最右边
+ 判断前驱节点右指针
+ 为空（第一次）
+ 前驱节点指向当前node
+ 移动到左子树
+ 不为空（第二次来）
+ 打印当前节点，清空指针
+ 移动到右子树
+ 若左子树为空
+ 打印当前节点
+ 移动到右子树
+ Morris查找错误节点
+ 把打印改成find
+ Morris前序、中序、后序遍历
+ 空间复杂度O(1)
+ 动态线索树
|
