Skip to content

Commit 3ef0381

Browse files
linwtlinwt
committed
剑指offer新版
1 parent 87a604e commit 3ef0381

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

85 files changed

+2301
-2
lines changed

‎leetcode_Java/Solution0236.java

Lines changed: 24 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,14 +11,36 @@
1111
*/
1212

1313

14+
/*
15+
递归：
16+
1、若root是p,q的最近公共祖先，那么有三种情况，即 p <= root <= q 或 q <= root <= p
17+
1）p、q分别在root的左右子树上
18+
2）p=root，且q在root的左或右子树上
19+
3）q=root，且p在root的左或右子树上
20+
2、函数功能：在节点中找p、q，找不到返回null，找到了返回该节点 不继续往下找了。即第一个if语句就代表函数最基本的功能。
21+
3、递归逻辑：
22+
1）根节点找不到时，要再判断左右节点能否找到，因此调用递归函数得到左右节点寻找结果
23+
2）拿结果做判断，如果左右都能找到，说明p、q在左右两边，当前根节点是最近公共祖先，返回根节点
24+
3）如果左边找到了，右边没找到，说明p、q都在左边，左边的节点是最近公共祖先
25+
如果右边找到了，左边没找到，说明p、q都在右边，右边的节点是最近公共祖先
26+
27+
root p q
28+
/ \ / \ / \
29+
p q x q x p
30+
p q
31+
/ \ / \
32+
q x p x
33+
*/
1434
public class Solution {
1535
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
16-
if (root == null || root == p || root == q)
36+
if (root == null || root == p || root == q) {
1737
return root;
38+
}
1839
TreeNode left = lowestCommonAncestor(root.left, p, q);
1940
TreeNode right = lowestCommonAncestor(root.right, p, q);
20-
if (left != null && right != null)
41+
if (left != null && right != null) {
2142
return root;
43+
}
2244
return left != null ? left : right;
2345
}
2446
}

‎剑指Offer_Java/DoneTitle.txt

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
1. 二维数组中的查找
2+
2. 替换空格
3+
3. 从尾到头打印链表
4+
4. 重建二叉树
5+
5. 用两个栈实现队列
6+
6. 旋转数组的最小数字
7+
7. 斐波那契数列
8+
8. 跳台阶
9+
9. 变态跳台阶
10+
10. 矩形覆盖
11+
11. 二进制中1的个数
12+
12. 数值的整数次方
13+
13. 调整数组顺序使奇数位于偶数前面
14+
14. 链表中倒数第k个结点
15+
15. 反转链表
16+
16. 合并两个排序的链表
17+
17. 树的子结构
18+
18. 二叉树的镜像
19+
19. 顺时针打印矩阵
20+
20. 包含min函数的栈
21+
21. 栈的压入、弹出序列
22+
22. 从上往下打印二叉树
23+
23. 二叉搜索树的后序遍历序列
24+
24. 二叉树中和为某一值的路径
25+
25. 复杂链表的复制
26+
26. 二叉搜索树与双向链表
27+
27. 字符串的排列
28+
28. 数组中出现次数超过一半的数字
29+
29. 最小的K个数
30+
30. 连续子数组的最大和
31+
31. 整数中1出现的次数（从1到n整数中1出现的次数）
32+
32. 把数组排成最小的数
33+
33. 丑数
34+
34. 第一个只出现一次的字符
35+
35. 数组中的逆序对
36+
36. 两个链表的第一个公共结点
37+
37. 数字在排序数组中出现的次数
38+
38. 二叉树的深度
39+
39. 平衡二叉树
40+
40. 数组中只出现一次的数字
41+
41. 和为S的连续正数序列
42+
42. 和为S的两个数字
43+
43. 左旋转字符串
44+
44. 翻转单词顺序列
45+
45. 扑克牌顺子
46+
46. 孩子们的游戏(圆圈中最后剩下的数)
47+
47. 求1+2+3+...+n
48+
48. 不用加减乘除做加法
49+
49. 把字符串转换成整数
50+
50. 数组中重复的数字
51+
51. 构建乘积数组
52+
52. 正则表达式匹配
53+
53. 表示数值的字符串
54+
54. 字符流中第一个不重复的字符
55+
55. 链表中环的入口结点
56+
56. 删除链表中重复的结点
57+
57. 二叉树的下一个结点
58+
58. 对称的二叉树
59+
59. 按之字形顺序打印二叉树
60+
60. 把二叉树打印成多行
61+
61. 序列化二叉树
62+
62. 二叉搜索树的第k个结点
63+
63. 数据流中的中位数
64+
64. 滑动窗口的最大值
65+
65. 矩阵中的路径
66+
66. 机器人的运动范围
67+
67. 剪绳子

‎剑指Offer_Java/Test22.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@ public TreeNode(int val) {
1616
}
1717
*/
1818

19+
// 从上往下打印二叉树
1920
public class Test22 {
2021
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
2122
ArrayList<Integer> list = new ArrayList<>();

‎剑指Offer_新版_java/DoneTitle.txt

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
3. 数组中重复的数字
2+
4. 二维数组中的查找
3+
5. 替换空格
4+
6. 从尾到头打印链表
5+
7. 重建二叉树
6+
8. 二叉树的下一个结点
7+
9. 用两个栈实现队列
8+
10. 斐波那契数列
9+
11. 旋转数组的最小数字
10+
12. 矩阵中的路径
11+
13. 机器人的运动范围
12+
14. 剪绳子
13+
15. 二进制中1的个数
14+
16. 数值的整数次方
15+
17. 打印从1到最大的n位数
16+
18. 删除链表的节点
17+
19. 正则表达式匹配
18+
20. 表示数值的字符串
19+
21. 调整数组顺序使奇数位于偶数前面
20+
22. 链表中倒数第k个结点
21+
23. 链表中环的入口结点
22+
24. 反转链表
23+
25. 合并两个排序的链表
24+
26. 树的子结构
25+
27. 二叉树的镜像
26+
28. 对称的二叉树
27+
29. 顺时针打印矩阵
28+
30. 包含min函数的栈
29+
31. 栈的压入、弹出序列
30+
32. 从上往下打印二叉树
31+
33. 二叉搜索树的后序遍历序列
32+
34. 二叉树中和为某一值的路径(二)
33+
35. 复杂链表的复制
34+
36. 二叉搜索树与双向链表
35+
37. 序列化二叉树
36+
38. 字符串的排列
37+
39. 数组中出现次数超过一半的数字
38+
40. 最小的K个数
39+
41. 数据流中的中位数
40+
42. 连续子数组的最大和
41+
43. 整数中1出现的次数（从1到n整数中1出现的次数）
42+
44. 数字序列中某一位的数字
43+
45. 把数组排成最小的数
44+
46. 把数字翻译成字符串
45+
47. 礼物的最大价值
46+
48. 最长不含重复字符的子字符串
47+
49. 丑数
48+
50. 第一个只出现一次的字符
49+
51. 数组中的逆序对
50+
52. 两个链表的第一个公共结点
51+
53. 数字在排序数组中出现的次数
52+
54. 二叉搜索树的第k个结点
53+
55. 二叉树的深度
54+
56. 数组中只出现一次的两个数字
55+
57. 和为S的两个数字
56+
58. 左旋转字符串
57+
59. 滑动窗口的最大值
58+
61. 扑克牌顺子
59+
62. 孩子们的游戏(圆圈中最后剩下的数)
60+
63. 买卖股票的最好时机(一)
61+
64. 求1+2+3+...+n
62+
65. 不用加减乘除做加法
63+
66. 构建乘积数组
64+
67. 把字符串转换成整数(atoi)
65+
68. 二叉搜索树的最近公共祖先
66+
69. 跳台阶
67+
70. 矩形覆盖
68+
71. 跳台阶扩展问题
69+
73. 翻转单词顺序列
70+
74. 和为S的连续正数序列
71+
75. 字符流中第一个不重复的字符
72+
76. 删除链表中重复的结点
73+
77. 按之字形顺序打印二叉树
74+
78. 把二叉树打印成多行
75+
79. 判断是不是平衡二叉树
76+
81. 调整数组顺序使奇数位于偶数前面(二)
77+
82. 二叉树中和为某一值的路径(一)
78+
83. 剪绳子(进阶版)
79+
84. 二叉树中和为某一值的路径(三)
80+
85. 连续子数组的最大和(二)
81+
86. 在二叉树中找到两个节点的最近公共祖先

‎剑指Offer_新版_java/DoneType.txt

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
分类目录
2+
一、链表
3+
二、树
4+
三、队列、栈
5+
四、搜索算法
6+
五、动态规划
7+
六、回溯
8+
七、排序
9+
八、位运算
10+
九、模拟
11+
十、其他算法
12+
13+
14+
一、链表
15+
6. 从尾到头打印链表（递归，列表）
16+
18. 删除链表的节点
17+
22. 链表中倒数第k个结点
18+
23. 链表中环的入口结点
19+
24. 反转链表
20+
25. 合并两个排序的链表
21+
35. 复杂链表的复制
22+
52. 两个链表的第一个公共结点
23+
76. 删除链表中重复的结点
24+
25+
26+
二、树
27+
7. 重建二叉树
28+
8. 二叉树的下一个结点
29+
26. 树的子结构
30+
27. 二叉树的镜像
31+
28. 对称的二叉树
32+
32. 从上往下打印二叉树
33+
33. 二叉搜索树的后序遍历序列
34+
34. 二叉树中和为某一值的路径(二)
35+
36. 二叉搜索树与双向链表
36+
37. 序列化二叉树
37+
54. 二叉搜索树的第k个结点
38+
55. 二叉树的深度
39+
68. 二叉搜索树的最近公共祖先
40+
77. 按之字形顺序打印二叉树
41+
78. 把二叉树打印成多行
42+
79. 判断是不是平衡二叉树
43+
82. 二叉树中和为某一值的路径(一)
44+
84. 二叉树中和为某一值的路径(三)
45+
86. 在二叉树中找到两个节点的最近公共祖先
46+
47+
48+
三、队列、栈
49+
9. 用两个栈实现队列
50+
30. 包含min函数的栈
51+
31. 栈的压入、弹出序列
52+
59. 滑动窗口的最大值
53+
73. 翻转单词顺序列
54+
55+
56+
四、搜索算法
57+
4. 二维数组中的查找（二分查找）
58+
11. 旋转数组的最小数字
59+
38. 字符串的排列
60+
44.数字序列中某一位的数字
61+
53. 数字在排序数组中出现的次数
62+
63+
64+
五、动态规划
65+
10. 斐波那契数列
66+
19. 正则表达式匹配
67+
42. 连续子数组的最大和
68+
46. 把数字翻译成字符串
69+
47. 礼物的最大价值
70+
48. 最长不含重复字符的子字符串
71+
63. 买卖股票的最好时机(一)
72+
69. 跳台阶
73+
70. 矩形覆盖
74+
71. 跳台阶扩展问题
75+
85. 连续子数组的最大和(二)
76+
77+
78+
六、回溯
79+
12. 矩阵中的路径
80+
13. 机器人的运动范围
81+
82+
83+
七、排序
84+
3. 数组中重复的数字
85+
40. 最小的K个数
86+
41. 数据流中的中位数
87+
51. 数组中的逆序对
88+
89+
90+
八、位运算
91+
15. 二进制中1的个数
92+
16. 数值的整数次方
93+
56. 数组中只出现一次的两个数字
94+
64. 求1+2+3+...+n
95+
65. 不用加减乘除做加法
96+
97+
98+
九、模拟
99+
20. 表示数值的字符串
100+
29. 顺时针打印矩阵
101+
61. 扑克牌顺子
102+
67. 把字符串转换成整数(atoi)
103+
104+
105+
十、其他算法
106+
5. 替换空格（增删、构造、替换）
107+
14. 剪绳子
108+
17. 打印从1到最大的n位数
109+
21. 调整数组顺序使奇数位于偶数前面
110+
39. 数组中出现次数超过一半的数字
111+
43. 整数中1出现的次数（从1到n整数中1出现的次数）
112+
45. 把数组排成最小的数
113+
49. 丑数
114+
50. 第一个只出现一次的字符
115+
57. 和为S的两个数字
116+
58. 左旋转字符串
117+
62. 孩子们的游戏(圆圈中最后剩下的数)
118+
66. 构建乘积数组
119+
74. 和为S的连续正数序列
120+
75. 字符流中第一个不重复的字符
121+
81. 调整数组顺序使奇数位于偶数前面(二)
122+
83. 剪绳子(进阶版)

‎剑指Offer_新版_java/JZ04.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
// 4. 二维数组中的查找
2+
3+
4+
/*
5+
二分查找：从左下角到右上角遍历
6+
*/
7+
public class Solution {
8+
public boolean Find(int target, int[][] array) {
9+
int row = array.length - 1;
10+
int col = 0;
11+
while (row >= 0 && col <= array[0].length - 1) {
12+
if (array[row][col] > target) {
13+
row--;
14+
} else if (array[row][col] < target) {
15+
col++;
16+
} else {
17+
return true;
18+
}
19+
}
20+
return false;
21+
}
22+
}

‎剑指Offer_新版_java/JZ05.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// 5. 替换空格
2+
3+
4+
/*
5+
增删、构造、替换
6+
*/
7+
public class Solution {
8+
// 通过删增来替换字符串
9+
public String replaceSpace(StringBuffer str) {
10+
for (int i = 0; i < str.length(); i++) {
11+
if (str.charAt(i) == ' ') {
12+
str.deleteCharAt(i);
13+
str.insert(i, "%20");
14+
}
15+
}
16+
return str.toString();
17+
}
18+
19+
// 构造新字符串
20+
public String replaceSpace2(StringBuffer str) {
21+
String res = "";
22+
for (int i = 0; i < str.length(); i++) {
23+
char s = str.charAt(i);
24+
if (s == ' ') {
25+
res += "%20";
26+
} else {
27+
res += s;
28+
}
29+
}
30+
return res;
31+
}
32+
33+
// 调用替换字符串方法
34+
public String replaceSpace3(StringBuffer str) {
35+
return str.toString().replaceAll("\\s", "%20");
36+
}
37+
}

0 commit comments

Comments
 (0)