Skip to content

Commit aff0a4d

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent 2032c7b commit aff0a4d

32 files changed

+1082
-444
lines changed

‎README.md‎

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

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: 3 additions & 3 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.bsearch;
22

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

@@ -19,12 +19,12 @@ public static int search(int[] nums, int target) {
1919
if (nums == null || nums.length == 0) return -1;
2020
int left = 0, right = nums.length - 1;
2121
while (left <= right) {
22-
int mid = (left + right) / 2;
22+
int mid = left + (right - left) / 2;
2323
if (nums[mid] == target) {
2424
return mid;
2525
} else if (nums[mid] < target) {
2626
left = mid + 1;
27-
} else {
27+
} else if (nums[mid] > target) {
2828
right = mid - 1;
2929
}
3030
}

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: 26 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,21 @@
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
/**
6+
* <a
7+
* href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/">34.在排序数组中查找元素的第一个和最后一个位置</a>
8+
*
69
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
710
* @since 2020-06-05
811
*/
912
public class 在排序数组中查找元素的第一个和最后一个位置 {
1013

1114
public static void main(String[] args) {
12-
Assertions.assertArrayEquals(new int[] { 3, 4 },
13-
searchRange(new int[] { 5, 7, 7, 8, 8, 10 }, 8));
14-
Assertions.assertArrayEquals(new int[] { -1, -1 },
15-
searchRange(new int[] { 5, 7, 7, 8, 8, 10 }, 6));
15+
Assertions.assertArrayEquals(new int[] { 3, 4 }, searchRange(new int[] { 5, 7, 7, 8, 8, 10 }, 8));
16+
Assertions.assertArrayEquals(new int[] { -1, -1 }, searchRange(new int[] { 5, 7, 7, 8, 8, 10 }, 6));
17+
Assertions.assertArrayEquals(new int[] { -1, -1 }, searchRange(new int[] {}, 0));
18+
Assertions.assertArrayEquals(new int[] { 0, 0 }, searchRange(new int[] { 1 }, 1));
1619

1720
Assertions.assertEquals(-1, searchLeft(new int[] { 5, 7, 7, 8, 8, 10 }, 3));
1821
Assertions.assertEquals(0, searchLeft(new int[] { 5, 7, 7, 8, 8, 10 }, 5));
@@ -27,64 +30,50 @@ public static void main(String[] args) {
2730
Assertions.assertEquals(2, searchRight(new int[] { 5, 7, 7, 8, 8, 10 }, 7));
2831
}
2932

30-
/**
31-
* 题目：<a href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/">34.
32-
* 在排序数组中查找元素的第一个和最后一个位置</a>
33-
* <p>
34-
* 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
35-
* <p>
36-
* 如果数组中不存在目标值，返回 [-1, -1]。
37-
*/
3833
public static int[] searchRange(int[] nums, int target) {
39-
final int[] notFoundResult = { -1, -1 };
40-
if (nums == null || nums.length == 0) { return notFoundResult; }
41-
34+
final int[] notFound = { -1, -1 };
35+
if (nums == null || nums.length == 0) {
36+
return notFound;
37+
}
4238
int begin = searchLeft(nums, target);
43-
if (begin == nums.length || nums[begin] != target) { return notFoundResult; }
4439
int end = searchRight(nums, target);
4540
return new int[] { begin, end };
4641
}
4742

48-
public static int searchLeft(int[] nums, int target) {
49-
if (nums == null || nums.length == 0) { return -1; }
50-
43+
static int searchLeft(int[] nums, int target) {
5144
int left = 0, right = nums.length - 1;
5245
while (left <= right) {
5346
int mid = left + (right - left) / 2;
54-
if (nums[mid] < target) {
55-
left = mid + 1;
56-
} else if (nums[mid] > target) {
47+
if (nums[mid] == target) {
5748
right = mid - 1;
58-
} else if (nums[mid] == target) {
49+
} else if (nums[mid] > target) {
5950
right = mid - 1;
51+
} else if (nums[mid] < target) {
52+
left = mid + 1;
6053
}
6154
}
62-
63-
if (left >= nums.length || nums[left] != target) {
55+
if (left < 0 || left >= nums.length) {
6456
return -1;
6557
}
66-
return left;
58+
return nums[left] == target ? left : -1;
6759
}
6860

69-
public static int searchRight(int[] nums, int target) {
70-
if (nums == null || nums.length == 0) { return -1; }
71-
61+
static int searchRight(int[] nums, int target) {
7262
int left = 0, right = nums.length - 1;
7363
while (left <= right) {
7464
int mid = left + (right - left) / 2;
75-
if (nums[mid] > target) {
76-
right = mid - 1;
77-
} else if (nums[mid] < target) {
65+
if (nums[mid] == target) {
7866
left = mid + 1;
79-
} else if (nums[mid] == target) {
67+
} else if (nums[mid] < target) {
8068
left = mid + 1;
69+
} else if (nums[mid] > target) {
70+
right = mid - 1;
8171
}
8272
}
83-
84-
if (right < 0 || nums[right] != target) {
73+
if (right < 0 || right >= nums.length) {
8574
return -1;
8675
}
87-
return right;
76+
return nums[right] == target ? right : -1;
8877
}
8978

9079
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/bsearch/统计目标成绩的出现次数.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
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/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/">LCR 172. 统计目标成绩的出现次数</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @date 2025-10-15
10+
*/
11+
public class 统计目标成绩的出现次数 {
12+
13+
public static void main(String[] args) {
14+
Assertions.assertEquals(3, countTarget(new int[] { 2, 2, 3, 4, 4, 4, 5, 6, 6, 8 }, 4));
15+
Assertions.assertEquals(0, countTarget(new int[] { 1, 2, 3, 5, 7, 9 }, 6));
16+
}
17+
18+
public static int countTarget(int[] scores, int target) {
19+
int result = search(scores, 0, scores.length - 1, target);
20+
return result == -1 ? 0 : result;
21+
}
22+
23+
static int search(int[] scores, int left, int right, int target) {
24+
if (left > right) {
25+
return -1;
26+
}
27+
int mid = left + (right - left) / 2;
28+
if (scores[mid] == target) {
29+
int lcnt = search(scores, left, mid - 1, target);
30+
int rcnt = search(scores, mid + 1, right, target);
31+
int cnt = 1;
32+
if (lcnt > 0) {
33+
cnt += lcnt;
34+
}
35+
if (rcnt > 0) {
36+
cnt += rcnt;
37+
}
38+
return cnt;
39+
} else if (scores[mid] < target) {
40+
return search(scores, mid + 1, right, target);
41+
} else if (scores[mid] > target) {
42+
return search(scores, left, mid - 1, target);
43+
}
44+
return -1;
45+
}
46+
47+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/window/乘积小于K的子数组.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.window;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/subarray-product-less-than-k/">713. 乘积小于 K 的子数组</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @date 2025-10-14
10+
*/
11+
public class 乘积小于K的子数组 {
12+
13+
public static void main(String[] args) {
14+
Assertions.assertEquals(8, numSubarrayProductLessThanK(new int[] { 10, 5, 2, 6 }, 100));
15+
Assertions.assertEquals(0, numSubarrayProductLessThanK(new int[] { 1, 2, 3 }, 0));
16+
}
17+
18+
public static int numSubarrayProductLessThanK(int[] nums, int k) {
19+
if (k <= 1) return 0;
20+
21+
// 窗口游标
22+
int left = 0, right = 0;
23+
// 窗口乘积
24+
int multi = 1;
25+
// 符合要求的结果
26+
int result = 0;
27+
while (right < nums.length) {
28+
// 扩大窗口
29+
multi *= nums[right++];
30+
31+
while (multi >= k && left < right) {
32+
multi = multi / nums[left++];
33+
}
34+
35+
result += right - left;
36+
// System.out.format("left: %d, right: %d\n", left, right);
37+
}
38+
return result;
39+
}
40+
41+
}

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

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package io.github.dunwu.algorithm.array.window;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.HashMap;
6+
7+
/**
8+
* <a href="https://leetcode.cn/problems/permutation-in-string/">567. 字符串的排列</a>
9+
*
10+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
11+
* @since 2025-08-06
12+
*/
13+
public class 字符串的排列 {
14+
15+
public static void main(String[] args) {
16+
Assertions.assertTrue(checkInclusion("ab", "eidbaooo"));
17+
Assertions.assertFalse(checkInclusion("ab", "eidboaoo"));
18+
}
19+
20+
public static boolean checkInclusion(String s1, String s2) {
21+
22+
// 定义 need 和 window
23+
HashMap<Character, Integer> need = new HashMap<>();
24+
HashMap<Character, Integer> window = new HashMap<>();
25+
for (int i = 0; i < s1.length(); i++) {
26+
need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
27+
}
28+
29+
// 符合 need 排列的字符个数
30+
int valid = 0;
31+
// 扫描 s 的窗口游标
32+
int left = 0, right = 0;
33+
// 符合要求的子串窗口信息
34+
int start = 0, len = Integer.MAX_VALUE;
35+
while (right < s2.length()) {
36+
char r = s2.charAt(right);
37+
// 窗口扩展
38+
right++;
39+
// 窗口 window 满足 need 的一系列更新
40+
if (need.containsKey(r)) {
41+
window.put(r, window.getOrDefault(r, 0) + 1);
42+
if (window.get(r).equals(need.get(r))) {
43+
valid++;
44+
}
45+
}
46+
47+
// 判断窗口左边界是否收缩
48+
while (valid == need.size()) {
49+
// 更新最小窗口信息
50+
if (right - left < len) {
51+
start = left;
52+
len = right - left;
53+
System.out.format("窗口：[left: %s, right: %s), 子串：%s\n", left, right,
54+
s2.substring(start, right));
55+
if (len == s1.length()) {
56+
return true;
57+
}
58+
}
59+
60+
// 窗口左边界收缩
61+
char l = s2.charAt(left);
62+
left++;
63+
if (need.containsKey(l)) {
64+
if (window.get(l).equals(need.get(l))) {
65+
valid--;
66+
}
67+
window.put(l, window.get(l) - 1);
68+
}
69+
}
70+
}
71+
72+
return false;
73+
}
74+
75+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/window/存在重复元素.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package io.github.dunwu.algorithm.array.window;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.HashSet;
6+
import java.util.Set;
7+
8+
/**
9+
* <a href="https://leetcode-cn.com/problems/contains-duplicate/">217. 存在重复元素</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @since 2020-06-05
13+
*/
14+
public class 存在重复元素 {
15+
16+
public static void main(String[] args) {
17+
Assertions.assertTrue(containsDuplicate(new int[] { 1, 2, 3, 1 }));
18+
Assertions.assertFalse(containsDuplicate(new int[] { 1, 2, 3, 4 }));
19+
Assertions.assertTrue(containsDuplicate(new int[] { 1, 1, 1, 3, 3, 4, 3, 2, 4, 2 }));
20+
}
21+
22+
public static boolean containsDuplicate(int[] nums) {
23+
if (nums == null || nums.length <= 1) {
24+
return false;
25+
}
26+
Set<Integer> set = new HashSet<>();
27+
for (int num : nums) {
28+
if (!set.add(num)) {
29+
return true;
30+
}
31+
}
32+
return false;
33+
}
34+
35+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/window/存在重复元素II.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.window;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.HashSet;
6+
import java.util.Set;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/contains-duplicate-ii/">219. 存在重复元素 II</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @date 2025-10-15
13+
*/
14+
public class 存在重复元素II {
15+
16+
public static void main(String[] args) {
17+
Assertions.assertTrue(containsNearbyDuplicate(new int[] { 1, 2, 3, 1 }, 3));
18+
Assertions.assertTrue(containsNearbyDuplicate(new int[] { 1, 0, 1, 1 }, 1));
19+
Assertions.assertFalse(containsNearbyDuplicate(new int[] { 1, 2, 3, 1, 2, 3 }, 2));
20+
Assertions.assertTrue(containsNearbyDuplicate(new int[] { 99, 99 }, 2));
21+
}
22+
23+
public static boolean containsNearbyDuplicate(int[] nums, int k) {
24+
if (nums == null || nums.length < 2) return false;
25+
int left = 0, right = 0;
26+
Set<Integer> set = new HashSet<>();
27+
while (right < nums.length) {
28+
if (!set.add(nums[right])) {
29+
return true;
30+
}
31+
right++;
32+
33+
if (right - left > k) {
34+
set.remove(nums[left]);
35+
left++;
36+
}
37+
}
38+
return false;
39+
}
40+
41+
/**
42+
* 效率为 O(N^2)
43+
*/
44+
public static boolean containsNearbyDuplicate2(int[] nums, int k) {
45+
if (nums == null || nums.length < 2) return false;
46+
for (int i = 0; i < nums.length; i++) {
47+
for (int j = i + 1; j < nums.length; j++) {
48+
if (nums[i] == nums[j] && Math.abs(j - i) <= k) {
49+
return true;
50+
}
51+
}
52+
}
53+
return false;
54+
}
55+
56+
}

0 commit comments

Comments
 (0)