Skip to content

Commit 5acb54e

Browse files
linwtlinwt
committed
简化代码
1 parent 63ef875 commit 5acb54e

20 files changed

+125
-75
lines changed

‎leetcode_Java/Solution0042.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -79,7 +79,7 @@ public int trap(int[] height) {
7979
for (int i = 1; i < n - 1; i++) {
8080
dpLeft[i] = Math.max(dpLeft[i - 1], height[i - 1]);
8181
}
82-
for (int i = n - 2; i >= 0; i--) {
82+
for (int i = n - 2; i > 0; i--) {
8383
dpRight[i] = Math.max(dpRight[i + 1], height[i + 1]);
8484
}
8585
for (int i = 1; i < n - 1; i++) {

‎leetcode_Java/Solution0047.java

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,10 @@
99
4、定义递归函数
1010
1）终止条件，子结果大小满足条件，存储子结果
1111
2）for循环遍历数组：剪枝条件 → 做选择 → 递归 → 撤销选择，回溯
12-
① 剪枝条件：当前元素使用过则跳过；或者当前元素未使用过，但同一层前面有同样的元素未使用过，该元素在本层可以使用，则需要跳过重复选择
12+
① 剪枝条件：当前元素使用过则跳过；或者当前元素未使用过，但同层前面有同样的元素使用过，则跳过重复选择
13+
去重代码 i > 0 && nums[i] == nums[i - 1] && !used[i - 1]
14+
used[i - 1] = false 表示树层去重，即前一个状态已撤销，为同层。效率更高，避免无效处理。
15+
used[i - 1] = true 表示树枝去重，即前一个状态未撤销，为递归，不同层。
1316
② 做选择：元素只加入子结果，标记当前元素已使用
1417
③ 递归：进入下一层，同样遍历整个数组，通过used标记判断元素是否有效可用
1518
④ 回溯：撤销选择，移除子结果最后一个元素，标记当前元素未使用

‎leetcode_Java/Solution0051.java

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -19,25 +19,27 @@
1919
class Solution {
2020
private List<List<String>> res = new ArrayList<>();
2121
private char[][] chessBoard;
22+
private int n;
2223

2324
public List<List<String>> solveNQueens(int n) {
24-
chessBoard = new char[n][n];
25+
this.n = n;
26+
this.chessBoard = new char[n][n];
2527
for (char[] c : chessBoard) {
2628
Arrays.fill(c, '.');
2729
}
28-
backtrack(n, 0);
30+
backtrack(0);
2931
return res;
3032
}
3133

32-
private void backtrack(int n, int row) {
34+
private void backtrack(int row) {
3335
if (row == n) {
3436
res.add(arrayToList());
3537
return;
3638
}
3739
for (int col = 0; col < n; col++) {
38-
if (isValid(n, row, col)) {
40+
if (isValid(row, col)) {
3941
chessBoard[row][col] = 'Q';
40-
backtrack(n, row + 1);
42+
backtrack(row + 1);
4143
chessBoard[row][col] = '.';
4244
}
4345
}
@@ -53,7 +55,7 @@ private List arrayToList() {
5355
}
5456

5557
// 检查是否有皇后
56-
private boolean isValid(int n, int row, int col) {
58+
private boolean isValid(int row, int col) {
5759
// 检查列
5860
for (int i = 0; i < row; i++) {
5961
if (chessBoard[i][col] == 'Q') {

‎leetcode_Java/Solution0096.java

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,8 +17,7 @@
1717
class Solution {
1818
public int numTrees(int n) {
1919
int[] dp = new int[n + 1];
20-
dp[0] = 1;
21-
dp[1] = 1;
20+
dp[0] = dp[1] = 1;
2221
for (int i = 2; i <= n; i++) {
2322
for (int j = 1; j <= i; j++) {
2423
dp[i] += dp[j - 1] * dp[i - j];

‎leetcode_Java/Solution0098.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ public boolean isValidBST(TreeNode root) {
5959

6060
/*
6161
递归：
62-
1、方法功能：入参是节点、最小值、最大值，判断节点值是否有效，即是否满足 min < val < max，有效效返回true，无效返回false
62+
1、方法功能：入参是节点、最小值、最大值，判断节点值是否有效，即是否满足 min < val < max，有效返回true，无效返回false
6363
2、终止条件：节点为空返回true
6464
3、单节点处理过程和返回结果：判断节点值是否有效，即是否满足 min < val < max，有效效返回true，无效返回false
6565
4、递归调用：左右节点需要同样的操作，因此调用同样的方法处理，获取结果
@@ -75,10 +75,10 @@ private boolean isValid(TreeNode root, TreeNode min, TreeNode max) {
7575
if (root == null) {
7676
return true;
7777
}
78-
if (max != null && root.val >= max.val) {
78+
if (min != null && root.val <= min.val) {
7979
return false;
8080
}
81-
if (min != null && root.val <= min.val) {
81+
if (max != null && root.val >= max.val) {
8282
return false;
8383
}
8484
return isValid(root.left, min, root) && isValid(root.right, root, max);

‎leetcode_Java/Solution0101.java

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -58,9 +58,7 @@ public boolean isSameTree(TreeNode p, TreeNode q) {
5858
return true;
5959
}
6060
if (p != null && q != null && p.val == q.val) {
61-
boolean l = isSameTree(p.left, q.right);
62-
boolean r = isSameTree(p.right, q.left);
63-
return l && r;
61+
return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
6462
}
6563
return false;
6664
}

‎leetcode_Java/Solution0104.java

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -39,9 +39,7 @@ public int maxDepth(TreeNode root) {
3939
if (root == null) {
4040
return 0;
4141
}
42-
int l = maxDepth(root.left);
43-
int r = maxDepth(root.right);
44-
return 1 + Math.max(l, r);
42+
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
4543
}
4644
}
4745

‎leetcode_Java/Solution0110.java

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -84,9 +84,7 @@ private int treeDepth(TreeNode root) {
8484
if (map.get(root) != null) {
8585
return map.get(root);
8686
}
87-
int left = treeDepth(root.left);
88-
int right = treeDepth(root.right);
89-
int depth = 1 + Math.max(left, right);
87+
int depth = 1 + Math.max(treeDepth(root.left), treeDepth(root.right));
9088
map.put(root, depth);
9189
return depth;
9290
}

‎leetcode_Java/Solution0114.java

Lines changed: 43 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@
3434
* 4、遍历逻辑：
3535
* 1）根指针的移动代表着前序遍历的顺序，循环遍历条件是根指针不为空
3636
* 2）如果根节点的左节点不为空，则进行节点连接步骤；如果为空，则将节点值存入列表
37-
* 3）根节点处理完后看，根指针指向右节点，准备下一轮判断
37+
* 3）根节点处理完后，根指针指向右节点，准备下一轮判断
3838
* 5、“144.二叉树的前序遍历”展开为链表的解法
3939
* */
4040
class Solution {
@@ -49,9 +49,8 @@ public List<Integer> flatten(TreeNode root) {
4949
pre.right = root.right;
5050
root.right = root.left;
5151
root.left = null;
52-
} else {
53-
list.add(root.val);
5452
}
53+
list.add(root.val);
5554
root = root.right;
5655
}
5756
return list;
@@ -80,13 +79,52 @@ public List<Integer> flatten(TreeNode root) {
8079
pre.right = root.right;
8180
root.right = root.left;
8281
root.left = null;
83-
} else {
84-
list.add(root.val);
8582
}
83+
list.add(root.val);
8684
if (root.right != null) {
8785
queue.offer(root.right);
8886
}
8987
}
9088
return list;
9189
}
90+
}
91+
92+
93+
// 方法返回空写法。迭代
94+
class Solution {
95+
public void flatten(TreeNode root) {
96+
while (root != null) {
97+
if (root.left != null) {
98+
TreeNode pre = root.left;
99+
while (pre.right != null) {
100+
pre = pre.right;
101+
}
102+
pre.right = root.right;
103+
root.right = root.left;
104+
root.left = null;
105+
}
106+
root = root.right;
107+
}
108+
}
109+
}
110+
111+
112+
// 递归
113+
class Solution {
114+
public void flatten(TreeNode root) {
115+
if (root == null) {
116+
return;
117+
}
118+
if (root.left != null) {
119+
TreeNode pre = root.left;
120+
while (pre.right != null) {
121+
pre = pre.right;
122+
}
123+
pre.right = root.right;
124+
root.right = root.left;
125+
root.left = null;
126+
}
127+
flatten(root.left);
128+
flatten(root.right);
129+
}
92130
}

‎leetcode_Java/Solution0198.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
1）dp[0]=0 表示没有偷窃时金额为0，dp[1]=nums[0] 表示第1号房屋时偷窃最高金额为nums[0]
99
2）因为状态转移方程由前两项推出，所以要先初始化前两项
1010
3、状态转移方程：
11-
1）如果偷窃第i号房屋，那么i-1号房屋不能偷窃，则最高金额为 dp[i-2] + nums[i - 1]
11+
1）如果偷窃第i号房屋，那么i-1号房屋不能偷窃，则最高金额为 dp[i - 2] + nums[i - 1]
1212
2）如果不偷窃第i号房屋，那么最高金额同i-1号房屋一样，即 dp[i - 1]
1313
3）在 偷窃 和 不偷窃 选择最高金额，即 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
1414
4、遍历dp数组填表：从索引2开始遍历，根据状态转移方程填表

‎leetcode_Java/Solution0236.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -68,4 +68,11 @@ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
6868
}
6969
return null;
7070
}
71+
72+
// 再简化
73+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
74+
if (root == null || root == p || root == q) {
75+
return root;
76+
}
77+
}
7178
}

‎leetcode_Java/Solution0297.java

Lines changed: 9 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -77,20 +77,16 @@ public String serialize(TreeNode root) {
7777
return "X,";
7878
}
7979
StringBuilder sb = new StringBuilder();
80-
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
80+
Queue<TreeNode> queue = new LinkedList<>();
8181
queue.add(root);
8282
while (!queue.isEmpty()) {
83-
int size = queue.size();
84-
while (size > 0) {
85-
TreeNode node = queue.poll();
86-
if (node != null) {
87-
sb.append(node.val + ",");
88-
queue.add(node.left);
89-
queue.add(node.right);
90-
} else {
91-
sb.append("X,");
92-
}
93-
size--;
83+
TreeNode node = queue.poll();
84+
if (node != null) {
85+
sb.append(node.val + ",");
86+
queue.add(node.left);
87+
queue.add(node.right);
88+
} else {
89+
sb.append("X,");
9490
}
9591
}
9692
return sb.toString();
@@ -101,7 +97,7 @@ public TreeNode deserialize(String data) {
10197
return null;
10298
}
10399
String[] splits = data.split(",");
104-
Deque<TreeNode> queue = new ArrayDeque<>();
100+
Queue<TreeNode> queue = new LinkedList<>();
105101
TreeNode root = new TreeNode(Integer.parseInt(splits[0]));
106102
queue.add(root);
107103
int i = 1;

‎leetcode_Java/Solution0543.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@
2626
2727
递归 + 最大路径长度成员变量
2828
计算深度递归函数
29-
1、方法功能：入参是一个节，返回节点的深度
29+
1、方法功能：入参是一个节点，返回节点的深度
3030
2、终止条件：节点为空时返回0
3131
3、一个节点处理过程和返回结果：节点不为空时返回1
3232
4、递归调用：左右节点同样需要计算深度，因此调用同样的方法处理，获取结果

‎剑指Offer_Java_新版/JZ14.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,7 @@ public int cutRope (int target) {
6565
/*
6666
1、以上解法通过公式直接计算
6767
2、x表示余数，余1时跟一个3凑成4进行乘积更大，余2时最后乘上即可，余0则刚好等分直接计算
68-
3、y表示有多少段3,
68+
3、y表示有多少段3
6969
*/
7070
public class Solution {
7171
public int cutRope(int target) {

‎剑指Offer_Java_新版/JZ28.java

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -14,9 +14,7 @@ boolean isSameTree(TreeNode p, TreeNode q) {
1414
return true;
1515
}
1616
if (p != null && q != null && p.val == q.val) {
17-
boolean l = isSameTree(p.left, q.right);
18-
boolean r = isSameTree(p.right, q.left);
19-
return l && r;
17+
return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
2018
}
2119
return false;
2220
}

‎剑指Offer_Java_新版/JZ31.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
// 31. 栈的压入、弹出序列
22

33

4+
// 数据入栈，当数据与弹出序列头元素相等时，则数据出栈且序列头元素弹出，重复以上步骤，最终若栈为空则该序列是符合的弹出序列
45
public class Solution {
5-
// 数据入栈，当数据与弹出序列头元素相等时，则数据出栈且序列头元素弹出，重复以上步骤，最终若栈为空则该序列是符合的弹出序列
66
public boolean IsPopOrder(int[] pushA, int[] popA) {
77
if (pushA.length == 0) {
88
return false;

‎剑指Offer_Java_新版/JZ34.java

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
回溯：
66
1、变量作用：
77
1）成员变量 list 保存回溯过程产生的子结果
8-
2）局部变量 pathList 保存递归到当前节点时路径上的节点值
8+
2）成员变量 pathList 保存递归到当前节点时路径上的节点值
99
3）局部变量 target 表示到达当前节点后剩余目标值，当剩余0时表示凑到了期望值
1010
2、递归：
1111
1）函数作用：累减剩余目标值，将当前节点值加入路径列表，判断剩余目标值是否为0 且 是否为叶结点，若是则将路径列表加入全局列表
@@ -14,15 +14,15 @@
1414
4）回溯：返回到上一层前需要将当前层加入的节点值移除，不影响其他路径递归
1515
*/
1616
public class Solution {
17-
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
17+
private ArrayList<ArrayList<Integer>> list = new ArrayList<>();
18+
private ArrayList<Integer> pathList = new ArrayList<>();
1819

1920
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
20-
ArrayList<Integer> pathList = new ArrayList<>();
21-
backtrack(root, expectNumber, pathList);
21+
backtrack(root, expectNumber);
2222
return list;
2323
}
2424

25-
private void backtrack(TreeNode root, int target, ArrayList<Integer> pathList) {
25+
private void backtrack(TreeNode root, int target) {
2626
if (root == null) {
2727
return;
2828
}
@@ -31,8 +31,8 @@ private void backtrack(TreeNode root, int target, ArrayList<Integer> pathList) {
3131
if (target == 0 && root.left == null && root.right == null) {
3232
list.add(new ArrayList<>(pathList));
3333
}
34-
backtrack(root.left, target, pathList);
35-
backtrack(root.right, target, pathList);
34+
backtrack(root.left, target);
35+
backtrack(root.right, target);
3636
pathList.remove(pathList.size() - 1);
3737
}
3838
}

‎剑指Offer_Java_新版/JZ44.java

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,8 @@
44
/*
55
1、变量含义
66
1）digit：每个数字的位数
7-
2）lowLimit：相同位数数字的区间起始值
8-
3）highLimit：相同位数数字的区间终止值
7+
2）low：相同位数数字的区间起始值
8+
3）high：相同位数数字的区间终止值
99
4）count：相同位数数字的区间内数字个数
1010
2、算法过程
1111
1）初始化变量
@@ -23,15 +23,15 @@
2323
public class Solution {
2424
public int findNthDigit (int n) {
2525
int digit = 1;
26-
long lowLimit = 0, highLimit = 10, count = 10;
26+
long low = 0, high = 10, count = 10;
2727
while (n > count) {
2828
n -= count;
29-
lowLimit = highLimit;
30-
highLimit *= 10;
29+
low = high;
30+
high *= 10;
3131
digit++;
32-
count = (highLimit - lowLimit) * digit;
32+
count = (high - low) * digit;
3333
}
34-
int num = lowLimit + n / digit;
34+
int num = low + n / digit;
3535
int offset = n % digit;
3636
return String.valueOf(num).charAt(offset) - '0';
3737
}

0 commit comments

Comments
 (0)