Skip to content

Commit 115e3bb

Browse files
dunwudunwu
committed
feat: 刷 leetcode
1 parent e114f19 commit 115e3bb

File tree

53 files changed

+1675
-639
lines changed

Some content is hidden

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

53 files changed

+1675
-639
lines changed

‎README.md‎

Lines changed: 145 additions & 90 deletions
Large diffs are not rendered by default.

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

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/range-sum-query-immutable/">303. 区域和检索 - 数组不可变</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2025-08-06
10+
*/
11+
public class 二维区域和检索_矩阵不可变 {
12+
13+
public static void main(String[] args) {
14+
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 }
16+
});
17+
Assertions.assertEquals(8, numMatrix.sumRegion(2, 1, 4, 3));
18+
}
19+
20+
static class NumMatrix {
21+
22+
private int[][] preSum;
23+
24+
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];
31+
}
32+
}
33+
}
34+
35+
public int sumRegion(int row1, int col1, int row2, int col2) {
36+
return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
37+
}
38+
39+
}
40+
41+
}

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

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/range-sum-query-immutable/">303. 区域和检索 - 数组不可变</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2025-08-06
10+
*/
11+
public class 区域和检索_数组不可变 {
12+
13+
public static void main(String[] args) {
14+
NumArray numArray = new NumArray(new int[] { -2, 0, 3, -5, 2, -1 });
15+
Assertions.assertEquals(1, numArray.sumRange(0, 2));
16+
Assertions.assertEquals(-1, numArray.sumRange(2, 5));
17+
Assertions.assertEquals(-3, numArray.sumRange(0, 5));
18+
}
19+
20+
static class NumArray {
21+
22+
private int[] preSum;
23+
24+
public NumArray(int[] nums) {
25+
preSum = new int[nums.length + 1];
26+
for (int i = 1; i <= nums.length; i++) {
27+
preSum[i] = preSum[i - 1] + nums[i - 1];
28+
}
29+
}
30+
31+
public int sumRange(int left, int right) {
32+
return preSum[right + 1] - preSum[left];
33+
}
34+
35+
}
36+
37+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/合并两个有序数组.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,21 @@ public static void main(String[] args) throws InvocationTargetException, Illegal
3232
}
3333

3434
public static void merge(int[] nums1, int m, int[] nums2, int n) {
35+
int i = m - 1, j = n - 1;
36+
int p = m + n - 1;
37+
while (i >= 0 && j >= 0) {
38+
if (nums1[i] > nums2[j]) {
39+
nums1[p--] = nums1[i--];
40+
} else {
41+
nums1[p--] = nums2[j--];
42+
}
43+
}
44+
while (j >= 0) {
45+
nums1[p--] = nums2[j--];
46+
}
47+
}
48+
49+
public static void merge2(int[] nums1, int m, int[] nums2, int n) {
3550
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);
3651
for (int i = 0; i < m; i++) {
3752
pq.offer(nums1[i]);

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

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.lang.reflect.InvocationTargetException;
6+
7+
/**
8+
* <a href="https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/">1011. 在 D 天内送达包裹的能力</a>
9+
*
10+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
11+
* @since 2025-08-06
12+
*/
13+
public class 在D天内送达包裹的能力 {
14+
15+
public static void main(String[] args) throws InvocationTargetException, IllegalAccessException {
16+
Assertions.assertEquals(15, shipWithinDays(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 5));
17+
Assertions.assertEquals(6, shipWithinDays(new int[] { 3, 2, 2, 4, 1, 4 }, 3));
18+
Assertions.assertEquals(3, shipWithinDays(new int[] { 1, 2, 3, 1, 1 }, 4));
19+
}
20+
21+
public static int shipWithinDays(int[] weights, int days) {
22+
int left = 0, right = 1;
23+
while (left <= right) {
24+
int mid = left + (right - left) / 2;
25+
if (f(weights, mid) == days) {
26+
// 搜索左侧边界，则需要收缩右侧边界
27+
right = mid;
28+
} else if (f(weights, mid) < days) {
29+
// 需要让 f(x) 的返回值大一些
30+
right = mid;
31+
} else if (f(weights, mid) > days) {
32+
// 需要让 f(x) 的返回值小一些
33+
left = mid + 1;
34+
}
35+
}
36+
return left;
37+
}
38+
39+
public static long f(int[] weights, int x) {
40+
long days = 0;
41+
for (int i = 0; i < weights.length; ) {
42+
int cap = x;
43+
while (i < weights.length) {
44+
if (cap < weights[i]) {
45+
break;
46+
} else {
47+
cap -= weights[i];
48+
}
49+
i++;
50+
}
51+
days++;
52+
}
53+
return days;
54+
}
55+
56+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/字符串的排列.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.HashMap;
6+
import java.util.Map;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/permutation-in-string/">567. 字符串的排列</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @since 2025-08-06
13+
*/
14+
public class 字符串的排列 {
15+
16+
public static void main(String[] args) {
17+
Assertions.assertTrue(checkInclusion("ab", "eidbaooo"));
18+
Assertions.assertFalse(checkInclusion("ab", "eidboaoo"));
19+
}
20+
21+
public static boolean checkInclusion(String t, String s) {
22+
23+
// 定义 window, need
24+
Map<Character, Integer> need = new HashMap<>();
25+
Map<Character, Integer> window = new HashMap<>();
26+
for (char c : s.toCharArray()) {
27+
need.put(c, need.getOrDefault(c, 0) + 1);
28+
}
29+
30+
int valid = 0;
31+
int left = 0, right = 0;
32+
while (right < s.length()) {
33+
34+
// 2. right++，窗口右扩，直到满足条件
35+
36+
// 移入窗口的字符
37+
char c = s.charAt(right);
38+
// 扩大窗口
39+
right++;
40+
// 进行窗口内数据的一系列更新
41+
if (need.containsKey(c)) {
42+
window.put(c, window.getOrDefault(c, 0) + 1);
43+
if (window.get(c).equals(need.get(c))) {
44+
valid++;
45+
}
46+
}
47+
48+
49+
}
50+
return false;
51+
}
52+
53+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/将矩阵按对角线排序.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.ArrayList;
6+
import java.util.Collections;
7+
import java.util.HashMap;
8+
import java.util.List;
9+
import java.util.Map;
10+
11+
/**
12+
* <a href="https://leetcode.cn/problems/sort-the-matrix-diagonally/">1329. 将矩阵按对角线排序</a>
13+
*
14+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
15+
* @since 2025-08-06
16+
*/
17+
public class 将矩阵按对角线排序 {
18+
19+
public static void main(String[] args) {
20+
int[][] input1 = { { 3, 3, 1, 1 }, { 2, 2, 1, 2 }, { 1, 1, 1, 2 } };
21+
int[][] expected1 = { { 1, 1, 1, 1 }, { 1, 2, 2, 2 }, { 1, 2, 3, 3 } };
22+
int[][] output1 = diagonalSort(input1);
23+
Assertions.assertArrayEquals(expected1, output1);
24+
25+
int[][] input2 = { { 11, 25, 66, 1, 69, 7 }, { 23, 55, 17, 45, 15, 52 }, { 75, 31, 36, 44, 58, 8 },
26+
{ 22, 27, 33, 25, 68, 4 }, { 84, 28, 14, 11, 5, 50 } };
27+
int[][] expected2 = { { 5, 17, 4, 1, 52, 7 }, { 11, 11, 25, 45, 8, 69 }, { 14, 23, 25, 44, 58, 15 },
28+
{ 22, 27, 31, 36, 50, 66 }, { 84, 28, 75, 33, 55, 68 } };
29+
int[][] output2 = diagonalSort(input2);
30+
Assertions.assertArrayEquals(expected2, output2);
31+
}
32+
33+
public static int[][] diagonalSort(int[][] mat) {
34+
Map<Integer, List<Integer>> map = new HashMap<>();
35+
int m = mat.length;
36+
int n = mat[0].length;
37+
for (int i = 0; i < m; i++) {
38+
for (int j = 0; j < n; j++) {
39+
int diff = i - j;
40+
if (!map.containsKey(diff)) {
41+
map.put(diff, new ArrayList<>());
42+
}
43+
map.get(diff).add(mat[i][j]);
44+
}
45+
}
46+
47+
map.forEach((diff, list) -> {
48+
Collections.sort(list);
49+
});
50+
51+
int[][] result = new int[m][n];
52+
for (int i = 0; i < m; i++) {
53+
for (int j = 0; j < n; j++) {
54+
int diff = i - j;
55+
List<Integer> list = map.get(diff);
56+
result[i][j] = list.remove(0);
57+
}
58+
}
59+
return result;
60+
}
61+
62+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/最长公共前缀.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/longest-common-prefix/">14. 最长公共前缀</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2025-08-06
10+
*/
11+
public class 最长公共前缀 {
12+
13+
public static void main(String[] args) {
14+
String[] input1 = { "flower", "flow", "flight" };
15+
String expect1 = "fl";
16+
String output1 = longestCommonPrefix(input1);
17+
Assertions.assertEquals(expect1, output1);
18+
19+
String[] input2 = { "dog","racecar","car" };
20+
String expect2 = "";
21+
String output2 = longestCommonPrefix(input2);
22+
Assertions.assertEquals(expect2, output2);
23+
}
24+
25+
public static String longestCommonPrefix(String[] strs) {
26+
if (strs == null || strs.length == 0) return "";
27+
int p = 0;
28+
int len = strs.length;
29+
while (true) {
30+
if (strs[0].length() <= p) {
31+
break;
32+
}
33+
char c = strs[0].charAt(p);
34+
int i = 1;
35+
while (i < len && p < strs[i].length() && strs[i].charAt(p) == c) {
36+
i++;
37+
}
38+
if (i < len) {
39+
break;
40+
}
41+
p++;
42+
}
43+
return strs[0].substring(0, p);
44+
}
45+
46+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/有序数组的平方.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/squares-of-a-sorted-array/">977. 有序数组的平方</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2025-08-06
10+
*/
11+
public class 有序数组的平方 {
12+
13+
public static void main(String[] args) {
14+
int[] input1 = { -4, -1, 0, 3, 10 };
15+
int[] expect1 = { 0, 1, 9, 16, 100 };
16+
int[] output1 = sortedSquares(input1);
17+
Assertions.assertArrayEquals(expect1, output1);
18+
19+
int[] input2 = { -7, -3, 2, 3, 11 };
20+
int[] expect2 = { 4, 9, 9, 49, 121 };
21+
int[] output2 = sortedSquares(input2);
22+
Assertions.assertArrayEquals(expect2, output2);
23+
}
24+
25+
public static int[] sortedSquares(int[] nums) {
26+
int len = nums.length;
27+
int left = 0, right = len - 1;
28+
int p = len - 1;
29+
int[] output = new int[len];
30+
while (left <= right) {
31+
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
32+
output[p] = nums[left] * nums[left];
33+
left++;
34+
} else {
35+
output[p] = nums[right] * nums[right];
36+
right--;
37+
}
38+
p--;
39+
}
40+
return output;
41+
}
42+
43+
}

0 commit comments

Comments
 (0)