Skip to content

Commit 538fa27

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent aff0a4d commit 538fa27

105 files changed

Lines changed: 1936 additions & 1473 deletions

File tree

Some content is hidden

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

‎README.md‎

Lines changed: 68 additions & 45 deletions
Large diffs are not rendered by default.

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

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package io.github.dunwu.algorithm.array.bsearch;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/split-array-largest-sum/">410. 分割数组的最大值</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @date 2025-10-16
10+
*/
11+
public class 分割数组的最大值 {
12+
13+
public static void main(String[] args) {
14+
Assertions.assertEquals(18, splitArray(new int[] { 7, 2, 5, 10, 8 }, 2));
15+
Assertions.assertEquals(9, splitArray(new int[] { 1, 2, 3, 4, 5 }, 2));
16+
Assertions.assertEquals(4, splitArray(new int[] { 1, 4, 4 }, 3));
17+
}
18+
19+
public static int splitArray(int[] nums, int k) {
20+
int left = 0;
21+
int right = 0;
22+
for (int w : nums) {
23+
left = Math.max(left, w);
24+
right += w;
25+
}
26+
27+
while (left <= right) {
28+
int mid = left + (right - left) / 2;
29+
if (f(nums, mid) == k) {
30+
right = mid - 1;
31+
} else if (f(nums, mid) < k) {
32+
right = mid - 1;
33+
} else if (f(nums, mid) > k) {
34+
left = mid + 1;
35+
}
36+
}
37+
return left;
38+
}
39+
40+
public static int f(int[] weights, int x) {
41+
int days = 0;
42+
for (int i = 0; i < weights.length; ) {
43+
int cap = x;
44+
while (i < weights.length) {
45+
if (cap < weights[i]) {
46+
break;
47+
} else {
48+
cap -= weights[i];
49+
}
50+
i++;
51+
}
52+
days++;
53+
}
54+
return days;
55+
}
56+
57+
}

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

Lines changed: 18 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
1-
package io.github.dunwu.algorithm.array;
1+
package io.github.dunwu.algorithm.array.bsearch;
22

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

55
import java.lang.reflect.InvocationTargetException;
6+
import java.util.Arrays;
67

78
/**
89
* <a href="https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/">1011. 在 D 天内送达包裹的能力</a>
@@ -13,31 +14,39 @@
1314
public class 在D天内送达包裹的能力 {
1415

1516
public static void main(String[] args) throws InvocationTargetException, IllegalAccessException {
17+
18+
// Assertions.assertEquals(5, f(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 15));
19+
// Assertions.assertEquals(3, f(new int[] { 3, 2, 2, 4, 1, 4 }, 6));
20+
// Assertions.assertEquals(4, f(new int[] { 1, 2, 3, 1, 1 }, 3));
21+
1622
Assertions.assertEquals(15, shipWithinDays(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 5));
1723
Assertions.assertEquals(6, shipWithinDays(new int[] { 3, 2, 2, 4, 1, 4 }, 3));
1824
Assertions.assertEquals(3, shipWithinDays(new int[] { 1, 2, 3, 1, 1 }, 4));
1925
}
2026

2127
public static int shipWithinDays(int[] weights, int days) {
22-
int left = 0, right = 1;
28+
int left = 0;
29+
int right = 0;
30+
for (int w : weights) {
31+
left = Math.max(left, w);
32+
right += w;
33+
}
34+
2335
while (left <= right) {
2436
int mid = left + (right - left) / 2;
2537
if (f(weights, mid) == days) {
26-
// 搜索左侧边界，则需要收缩右侧边界
27-
right = mid;
38+
right = mid - 1;
2839
} else if (f(weights, mid) < days) {
29-
// 需要让 f(x) 的返回值大一些
30-
right = mid;
40+
right = mid - 1;
3141
} else if (f(weights, mid) > days) {
32-
// 需要让 f(x) 的返回值小一些
3342
left = mid + 1;
3443
}
3544
}
3645
return left;
3746
}
3847

39-
public static long f(int[] weights, int x) {
40-
long days = 0;
48+
public static int f(int[] weights, int x) {
49+
int days = 0;
4150
for (int i = 0; i < weights.length; ) {
4251
int cap = x;
4352
while (i < weights.length) {

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

Lines changed: 19 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
1-
package io.github.dunwu.algorithm.array;
1+
package io.github.dunwu.algorithm.array.bsearch;
22

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

55
import java.lang.reflect.InvocationTargetException;
6+
import java.util.Arrays;
67

78
/**
89
* <a href="https://leetcode.cn/problems/koko-eating-bananas/">875. 爱吃香蕉的珂珂</a>
@@ -20,31 +21,32 @@ public static void main(String[] args) throws InvocationTargetException, Illegal
2021

2122
public static int minEatingSpeed(int[] piles, int h) {
2223
int left = 1, right = 1000000000 + 1;
23-
while (left < right) {
24+
while (left <= right) {
2425
int mid = left + (right - left) / 2;
25-
if (f(piles, mid) == h) {
26-
// 搜索左侧边界，则需要收缩右侧边界
27-
right = mid;
28-
} else if (f(piles, mid) < h) {
29-
// 需要让 f(x) 的返回值大一些
30-
right = mid;
31-
} else if (f(piles, mid) > h) {
32-
// 需要让 f(x) 的返回值小一些
26+
if (fun(piles, mid) == h) {
27+
right = mid - 1;
28+
} else if (fun(piles, mid) < h) {
29+
right = mid - 1;
30+
} else if (fun(piles, mid) > h) {
3331
left = mid + 1;
3432
}
3533
}
3634
return left;
3735
}
3836

39-
public static long f(int[] arr, int x) {
40-
long hours = 0;
41-
for (int j : arr) {
42-
hours += j / x;
43-
if (j % x > 0) {
44-
hours++;
37+
public static long fun(int[] piles, int speed) {
38+
long hour = 0L;
39+
for (int pile : piles) {
40+
if (pile <= speed) {
41+
hour++;
42+
} else {
43+
hour += pile / speed;
44+
if (pile % speed != 0) {
45+
hour++;
46+
}
4547
}
4648
}
47-
return hours;
49+
return hour;
4850
}
4951

5052
}

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

Lines changed: 12 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package io.github.dunwu.algorithm.array;
1+
package io.github.dunwu.algorithm.array.range;
22

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

@@ -12,7 +12,11 @@ public class 二维区域和检索_矩阵不可变 {
1212

1313
public static void main(String[] args) {
1414
NumMatrix numMatrix = new NumMatrix(new int[][] {
15-
{ 3, 0, 1, 4, 2 }, { 5, 6, 3, 2, 1 }, { 1, 2, 0, 1, 5 }, { 4, 1, 0, 1, 7 }, { 1, 0, 3, 0, 5 }
15+
{ 3, 0, 1, 4, 2 },
16+
{ 5, 6, 3, 2, 1 },
17+
{ 1, 2, 0, 1, 5 },
18+
{ 4, 1, 0, 1, 7 },
19+
{ 1, 0, 3, 0, 5 }
1620
});
1721
Assertions.assertEquals(8, numMatrix.sumRegion(2, 1, 4, 3));
1822
}
@@ -22,12 +26,12 @@ static class NumMatrix {
2226
private int[][] preSum;
2327

2428
public NumMatrix(int[][] matrix) {
25-
int row = matrix.length;
26-
int col = matrix[0].length;
27-
preSum = new int[row + 1][col + 1];
28-
for (int i = 1; i <= row; i++) {
29-
for (int j = 1; j <= col; j++) {
30-
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
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];
3135
}
3236
}
3337
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/range/前缀和数组代码模板.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package io.github.dunwu.algorithm.array.range;
2+
3+
/**
4+
* 前缀和数组代码模板
5+
*
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @date 2025-10-20
8+
*/
9+
public class 前缀和数组代码模板 {
10+
11+
/**
12+
* 一维前缀和
13+
*/
14+
static class NumArray {
15+
16+
// 前缀和数组
17+
private int[] preSum;
18+
19+
// 输入一个数组，构造前缀和
20+
public NumArray(int[] nums) {
21+
// preSum[0] = 0，便于计算累加和
22+
preSum = new int[nums.length + 1];
23+
// 计算 nums 的累加和
24+
for (int i = 1; i < preSum.length; i++) {
25+
preSum[i] = preSum[i - 1] + nums[i - 1];
26+
}
27+
}
28+
29+
// 查询闭区间 [left, right] 的累加和
30+
public int sumRange(int left, int right) {
31+
return preSum[right + 1] - preSum[left];
32+
}
33+
34+
}
35+
36+
/**
37+
* 二维前缀和
38+
*/
39+
static class NumMatrix {
40+
41+
// preSum[i][j] 记录矩阵 [0, 0, i-1, j-1] 的元素和
42+
private int[][] preSum;
43+
44+
public NumMatrix(int[][] matrix) {
45+
int m = matrix.length, n = matrix[0].length;
46+
if (m == 0 || n == 0) return;
47+
// 构造前缀和矩阵
48+
preSum = new int[m + 1][n + 1];
49+
for (int i = 1; i <= m; i++) {
50+
for (int j = 1; j <= n; j++) {
51+
// 计算每个矩阵 [0, 0, i, j] 的元素和
52+
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
53+
}
54+
}
55+
}
56+
57+
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
58+
public int sumRegion(int x1, int y1, int x2, int y2) {
59+
// 目标矩阵之和由四个相邻矩阵运算获得
60+
return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
61+
}
62+
63+
}
64+
65+
}

codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/区域和检索_数组不可变.java renamed to codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/range/区域和检索_数组不可变.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package io.github.dunwu.algorithm.array;
1+
package io.github.dunwu.algorithm.array.range;
22

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

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/range/差分数组代码模板.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package io.github.dunwu.algorithm.array.range;
2+
3+
/**
4+
* 差分数组代码模板
5+
*
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @date 2025-10-20
8+
*/
9+
public class 差分数组代码模板 {
10+
11+
// 差分数组工具类
12+
static class Difference {
13+
14+
// 差分数组
15+
private int[] diff;
16+
17+
// 输入一个初始数组，区间操作将在这个数组上进行
18+
public Difference(int[] nums) {
19+
assert nums.length > 0;
20+
diff = new int[nums.length];
21+
// 根据初始数组构造差分数组
22+
diff[0] = nums[0];
23+
for (int i = 1; i < nums.length; i++) {
24+
diff[i] = nums[i] - nums[i - 1];
25+
}
26+
}
27+
28+
// 给闭区间 [i, j] 增加 val（可以是负数）
29+
public void increment(int i, int j, int val) {
30+
diff[i] += val;
31+
if (j + 1 < diff.length) {
32+
diff[j + 1] -= val;
33+
}
34+
}
35+
36+
// 返回结果数组
37+
public int[] result() {
38+
int[] res = new int[diff.length];
39+
// 根据差分数组构造结果数组
40+
res[0] = diff[0];
41+
for (int i = 1; i < diff.length; i++) {
42+
res[i] = res[i - 1] + diff[i];
43+
}
44+
return res;
45+
}
46+
47+
}
48+
49+
}

0 commit comments

Comments
 (0)