Skip to content

Commit c54b368

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent 8d505ce commit c54b368

17 files changed

+244
-160
lines changed

‎README.md‎

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -130,7 +130,7 @@
130130
| [80. 删除有序数组中的重复项 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/) | 💛 | ✔️ |
131131
| [344. 反转字符串](https://leetcode.cn/problems/reverse-string/) | 💚 | ✔️ |
132132
| [125. 验证回文串](https://leetcode.cn/problems/valid-palindrome/) | 💚 | ✔️ |
133-
| [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) | 💛 | ❗ |
133+
| [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) | 💛 | ✔️ |
134134
| [75. 颜色分类](https://leetcode.cn/problems/sort-colors/) | 💛 | ✔️ |
135135
| [88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/) | 💚 | ✔️ |
136136
| [977. 有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/) | 💚 | ✔️ |
@@ -159,11 +159,11 @@
159159
| [3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/) | 💛 | ✔️ |
160160
| [438. 找到字符串中所有字母异位词](https://leetcode.cn/problems/find-all-anagrams-in-a-string/) | 💛 | ✔️ |
161161
| [567. 字符串的排列](https://leetcode.cn/problems/permutation-in-string/) | 💛 | ✔️ |
162-
| [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/) | ❤️ | ❗ |
163-
| [1658. 将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/) | 💛 | ❌ |
162+
| [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/) | ❤️ | ✔️ |
163+
| [1658. 将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/) | 💛 | ✔️ |
164164
| [713. 乘积小于 K 的子数组](https://leetcode.cn/problems/subarray-product-less-than-k/) | 💛 | ✔️ |
165165
| [1004. 最大连续 1 的个数 III](https://leetcode.cn/problems/max-consecutive-ones-iii/) | 💛 | ✔️ |
166-
| [424. 替换后的最长重复字符](https://leetcode.cn/problems/longest-repeating-character-replacement/) | 💛 | ❗ |
166+
| [424. 替换后的最长重复字符](https://leetcode.cn/problems/longest-repeating-character-replacement/) | 💛 | ✔️ |
167167
| [217. 存在重复元素](https://leetcode.cn/problems/contains-duplicate/) | 💚 | ✔️ |
168168
| [219. 存在重复元素 II](https://leetcode.cn/problems/contains-duplicate-ii/) | 💛 | ✔️ |
169169
| [220. 存在重复元素 III](https://leetcode.cn/problems/contains-duplicate-iii/) | ❤️ | ❌ |
@@ -178,10 +178,9 @@
178178
| [35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/) | 💚 | ✔️ |
179179
| [704. 二分查找](https://leetcode.cn/problems/binary-search/) | 💚 | ✔️ |
180180
| [LCR 172. 统计目标成绩的出现次数](https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/) | 💚 | ✔️ |
181-
| [875. 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/) | 💛 | ❌ |
182-
| [1011. 在 D 天内送达包裹的能力](https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/) | 💛 | ❌ |
183-
| [410. 分割数组的最大值](https://leetcode.cn/problems/split-array-largest-sum/) | 💛 | ❌ |
184-
| [378. 有序矩阵中第 K 小的元素](https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/) | 💛 | ❌ |
181+
| [875. 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/) | 💛 | ❗ |
182+
| [1011. 在 D 天内送达包裹的能力](https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/) | 💛 | ✔️ |
183+
| [410. 分割数组的最大值](https://leetcode.cn/problems/split-array-largest-sum/) | ❤️ | ❌ |
185184

186185
#### 前缀和数组
187186

@@ -196,8 +195,8 @@
196195

197196
| 题目 | 难度 | 掌握度 |
198197
| ----------------------------------------------------------------------------- | ---- | ------ |
199-
| [1094. 拼车](https://leetcode.cn/problems/car-pooling/) | 💛 | ❗ |
200-
| [1109. 航班预订统计](https://leetcode.cn/problems/corporate-flight-bookings/) | 💛 | ❌ |
198+
| [1094. 拼车](https://leetcode.cn/problems/car-pooling/) | 💛 | ✔️ |
199+
| [1109. 航班预订统计](https://leetcode.cn/problems/corporate-flight-bookings/) | 💛 | ✔️ |
201200

202201
### 栈和队列
203202

@@ -212,6 +211,7 @@
212211
| [1670. 设计前中后队列](https://leetcode.cn/problems/design-front-middle-back-queue/) | 💛 | |
213212
| [2073. 买票需要的时间](https://leetcode.cn/problems/time-needed-to-buy-tickets/) | 💚 | ✔️ |
214213
| [373. 查找和最小的 K 对数字](https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/) | 💛 | |
214+
| [378. 有序矩阵中第 K 小的元素](https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/) | 💛 | ❌ |
215215

216216
#### 栈
217217

@@ -343,7 +343,7 @@
343343
| [450. 删除二叉搜索树中的节点](https://leetcode.cn/problems/delete-node-in-a-bst/) | 💛 | ✔️ |
344344
| [700. 二叉搜索树中的搜索](https://leetcode.cn/problems/search-in-a-binary-search-tree/) | 💚 | ✔️ |
345345
| [701. 二叉搜索树中的插入操作](https://leetcode.cn/problems/insert-into-a-binary-search-tree/) | 💛 | ✔️ |
346-
| [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/) | 💛 | ❗ |
346+
| [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/) | 💛 | ✔️ |
347347
| [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/) | 💛 | ❌ |
348348
| [95. 不同的二叉搜索树 II](https://leetcode.cn/problems/unique-binary-search-trees-ii/) | 💛 | ❌ |
349349
| [108. 将有序数组转换为二叉搜索树](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/) | 💚 | ✔️ |

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/bsearch/分割数组的最大值.java‎

Lines changed: 21 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -20,38 +20,40 @@ public static void main(String[] args) {
2020
static class Solution {
2121

2222
public int splitArray(int[] nums, int k) {
23-
int left = 0;
24-
int right = 1;
25-
for (int w : nums) {
26-
left = Math.max(left, w);
27-
right += w;
23+
return shipWithinDays(nums, k);
24+
}
25+
26+
public int shipWithinDays(int[] weights, int days) {
27+
int max = 0, sum = 0;
28+
for (int weight : weights) {
29+
max = Math.max(max, weight);
30+
sum += weight;
2831
}
2932

30-
int res = 0;
33+
int left = max, right = sum;
3134
while (left <= right) {
3235
int mid = left + (right - left) / 2;
33-
if (f(nums, mid) <= k) {
34-
res = mid;
36+
if (f(weights, mid) <= days) {
37+
// 需要让 f(x) 的返回值大一些
3538
right = mid - 1;
36-
} else {
39+
} else if (f(weights, mid) > days) {
40+
// 需要让 f(x) 的返回值小一些
3741
left = mid + 1;
3842
}
3943
}
40-
return res;
44+
return left;
4145
}
4246

43-
public int f(int[] nums, int x) {
44-
int i = 0;
47+
// 定义：当运载能力为 x 时，需要 f(x) 天运完所有货物
48+
// f(x) 随着 x 的增加单调递减
49+
int f(int[] weights, int x) {
4550
int days = 0;
46-
while (i < nums.length) {
51+
for (int i = 0; i < weights.length; ) {
4752
// 尽可能多装货物
4853
int cap = x;
49-
while (i < nums.length) {
50-
if (cap < nums[i]) {
51-
break;
52-
} else {
53-
cap -= nums[i];
54-
}
54+
while (i < weights.length) {
55+
if (cap < weights[i]) break;
56+
else cap -= weights[i];
5557
i++;
5658
}
5759
days++;

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/bsearch/在D天内送达包裹的能力.java‎

Lines changed: 11 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -20,22 +20,18 @@ public static void main(String[] args) {
2020
static class Solution {
2121

2222
public int shipWithinDays(int[] weights, int days) {
23-
int left = 0;
24-
// 注意，right 是开区间，所以额外加一
25-
int right = 1;
26-
for (int w : weights) {
27-
left = Math.max(left, w);
28-
right += w;
23+
int max = 0, sum = 0;
24+
for (int weight : weights) {
25+
max = Math.max(max, weight);
26+
sum += weight;
2927
}
3028

31-
while (left < right) {
29+
int left = max, right = sum;
30+
while (left <= right) {
3231
int mid = left + (right - left) / 2;
33-
if (f(weights, mid) == days) {
34-
// 搜索左侧边界，则需要收缩右侧边界
35-
right = mid;
36-
} else if (f(weights, mid) < days) {
32+
if (f(weights, mid) <= days) {
3733
// 需要让 f(x) 的返回值大一些
38-
right = mid;
34+
right = mid - 1;
3935
} else if (f(weights, mid) > days) {
4036
// 需要让 f(x) 的返回值小一些
4137
left = mid + 1;
@@ -49,13 +45,11 @@ public int shipWithinDays(int[] weights, int days) {
4945
int f(int[] weights, int x) {
5046
int days = 0;
5147
for (int i = 0; i < weights.length; ) {
48+
// 尽可能多装货物
5249
int cap = x;
5350
while (i < weights.length) {
54-
if (cap < weights[i]) {
55-
break;
56-
} else {
57-
cap -= weights[i];
58-
}
51+
if (cap < weights[i]) break;
52+
else cap -= weights[i];
5953
i++;
6054
}
6155
days++;

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/bsearch/爱吃香蕉的珂珂.java‎

Lines changed: 12 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -26,38 +26,28 @@ public static void main(String[] args) {
2626
static class Solution {
2727

2828
public int minEatingSpeed(int[] piles, int h) {
29-
final int rightBound = 1_000_000_001;
30-
int left = 1, right = rightBound;
31-
while (left < right) {
29+
int left = 1, right = 1_000_000_000;
30+
31+
// right 是闭区间，所以这里改成 <=
32+
while (left <= right) {
3233
int mid = left + (right - left) / 2;
33-
if (f(piles, mid) == h) {
34-
// 搜索左侧边界，则需要收缩右侧边界
35-
right = mid ;
36-
} else if (f(piles, mid) < h) {
37-
// 需要让 f(x) 的返回值大一些
38-
right = mid ;
34+
if (f(piles, mid) <= h) {
35+
// right 是闭区间，所以这里用 mid - 1
36+
right = mid - 1;
3937
} else if (f(piles, mid) > h) {
40-
// 需要让 f(x) 的返回值小一些
4138
left = mid + 1;
4239
}
4340
}
44-
if (left < 0 || left > rightBound) { return -1; }
4541
return left;
4642
}
4743

48-
public int f(int[] nums, int x) {
49-
int res = 0;
44+
long f(int[] nums, int x) {
45+
long h = 0;
5046
for (int num : nums) {
51-
if (num <= x) {
52-
res++;
53-
} else {
54-
res += num / x;
55-
if (num % x != 0) {
56-
res++;
57-
}
58-
}
47+
h += num / x;
48+
if (num % x > 0) { h++; }
5949
}
60-
return res;
50+
return h;
6151
}
6252

6353
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/matrix/对角线遍历.java‎

Lines changed: 15 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,6 @@
22

33
import org.junit.jupiter.api.Assertions;
44

5-
import java.util.LinkedList;
6-
import java.util.List;
7-
85
/**
96
* <a href="https://leetcode.cn/problems/diagonal-traverse/">498. 对角线遍历</a>
107
*
@@ -33,31 +30,32 @@ public static void main(String[] args) {
3330

3431
static class Solution {
3532

33+
// 1. 同一对角线上的元素，满足 i + j = k
34+
// 2. k 的大小，满足递增，从 0 到 m + n - 2
35+
// 3. 由于，i + j = k -> i = k - j
36+
// i = m - 1 时最大，j 最小；而 k - (m - 1) 必须大于 0 => minJ = max(0, k - (m - 1))
37+
// i = 0 时最小，j 最大，但不能超过 n - 1 => maxJ = Math.max(k, n -1)
3638
public int[] findDiagonalOrder(int[][] mat) {
3739

3840
// base case
3941
if (mat == null || mat.length == 0) { return new int[0]; }
4042

43+
int idx = 0;
4144
int m = mat.length, n = mat[0].length;
42-
List<Integer> list = new LinkedList<>();
43-
for (int step = 0; step <= m + n - 2; step++) {
44-
int min = Math.max(step - (m - 1), 0);
45-
int max = Math.min(step, n - 1);
46-
if (step % 2 == 0) {
47-
for (int i = max; i >= min; i--) {
48-
list.add(mat[i][step - i]);
45+
int[] res = new int[m * n];
46+
for (int k = 0; k < m + n - 1; k++) {
47+
int minJ = Math.max(k - (m - 1), 0);
48+
int maxJ = Math.min(k, n - 1);
49+
if (k % 2 == 0) {
50+
for (int j = minJ; j <= maxJ; j++) {
51+
res[idx++] = mat[k - j][j];
4952
}
5053
} else {
51-
for (int i = min; i <= max; i++) {
52-
list.add(mat[i][step - i]);
54+
for (int j = maxJ; j >= minJ; j--) {
55+
res[idx++] = mat[k - j][j];
5356
}
5457
}
5558
}
56-
57-
int[] res = new int[list.size()];
58-
for (int k = 0; k < list.size(); k++) {
59-
res[k] = list.get(k);
60-
}
6159
return res;
6260
}
6361

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/range/二维区域和检索_矩阵不可变.java‎

Lines changed: 15 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -19,25 +19,32 @@ public static void main(String[] args) {
1919
{ 1, 0, 3, 0, 5 }
2020
});
2121
Assertions.assertEquals(8, numMatrix.sumRegion(2, 1, 4, 3));
22+
Assertions.assertEquals(11, numMatrix.sumRegion(1, 1, 2, 2));
23+
Assertions.assertEquals(12, numMatrix.sumRegion(1, 2, 2, 4));
2224
}
2325

2426
static class NumMatrix {
2527

28+
// preSum[i][j] 记录矩阵 [0, 0, i-1, j-1] 的元素和
2629
private int[][] preSum;
2730

2831
public NumMatrix(int[][] matrix) {
29-
final int M = matrix.length;
30-
final int N = matrix[0].length;
31-
preSum = new int[M + 1][N + 1];
32-
for (int i = 1; i <= M; i++) {
33-
for (int j = 1; j <= N; j++) {
34-
preSum[i][j] = preSum[i][j - 1] + preSum[i - 1][j] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
32+
int m = matrix.length, n = matrix[0].length;
33+
if (m == 0 || n == 0) return;
34+
// 构造前缀和矩阵
35+
preSum = new int[m + 1][n + 1];
36+
for (int i = 1; i <= m; i++) {
37+
for (int j = 1; j <= n; j++) {
38+
// 计算每个矩阵 [0, 0, i, j] 的元素和
39+
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
3540
}
3641
}
3742
}
3843

39-
public int sumRegion(int row1, int col1, int row2, int col2) {
40-
return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
44+
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
45+
public int sumRegion(int x1, int y1, int x2, int y2) {
46+
// 目标矩阵之和由四个相邻矩阵运算获得
47+
return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
4148
}
4249

4350
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/range/拼车.java‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,8 @@ public static void main(String[] args) {
1616
Assertions.assertFalse(s.carPooling(input, 3));
1717
int[][] input2 = { { 1, 2, 10 }, { 2, 2, 15 } };
1818
Assertions.assertTrue(s.carPooling(input2, 5));
19+
int[][] input3 = { { 2, 1, 5 }, { 3, 5, 7 } };
20+
Assertions.assertTrue(s.carPooling(input3, 3));
1921
}
2022

2123
static class Solution {
@@ -50,10 +52,10 @@ public boolean carPooling(int[][] trips, int capacity) {
5052
}
5153

5254
// 差分数组工具类
53-
static class Difference {
55+
class Difference {
5456

5557
// 差分数组
56-
private final int[] diff;
58+
private int[] diff;
5759

5860
// 输入一个初始数组，区间操作将在这个数组上进行
5961
public Difference(int[] nums) {

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/range/航班预订统计.java‎

Lines changed: 2 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -24,20 +24,12 @@ public static void main(String[] args) {
2424
static class Solution {
2525

2626
public int[] corpFlightBookings(int[][] bookings, int n) {
27-
// nums 初始化为全 0
2827
int[] nums = new int[n];
29-
// 构造差分解法
3028
Difference df = new Difference(nums);
31-
3229
for (int[] booking : bookings) {
33-
// 注意转成数组索引要减一哦
34-
int i = booking[0] - 1;
35-
int j = booking[1] - 1;
36-
int val = booking[2];
37-
// 对区间 nums[i..j] 增加 val
38-
df.increment(i, j, val);
30+
int first = booking[0], last = booking[1], seat = booking[2];
31+
df.increment(first - 1, last - 1, seat);
3932
}
40-
// 返回最终的结果数组
4133
return df.result();
4234
}
4335

0 commit comments

Comments
 (0)