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开始遍历，根据状态转移方程填表

0 commit comments

Comments
 (0)