Skip to content

Commit 8d505ce

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

File tree

63 files changed

+1994
-1525
lines changed

Some content is hidden

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

63 files changed

+1994
-1525
lines changed

‎README.md‎

Lines changed: 82 additions & 37 deletions
Large diffs are not rendered by default.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/ArrayDemo.java‎

Lines changed: 0 additions & 25 deletions
This file was deleted.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/base/最大连续1的个数.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.base;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/max-consecutive-ones/">485. 最大连续 1 的个数</a>
7+
*
8+
* @author Zhang Peng
9+
* @since 2018-11-05
10+
*/
11+
public class 最大连续1的个数 {
12+
13+
public static void main(String[] args) {
14+
Solution s = new Solution();
15+
Assertions.assertEquals(3, s.findMaxConsecutiveOnes(new int[] { 1, 1, 0, 1, 1, 1 }));
16+
Assertions.assertEquals(2, s.findMaxConsecutiveOnes(new int[] { 1, 0, 1, 1, 0, 1 }));
17+
}
18+
19+
static class Solution {
20+
21+
public int findMaxConsecutiveOnes(int[] nums) {
22+
int max = 0;
23+
int cnt = 0;
24+
for (int num : nums) {
25+
if (num == 1) {
26+
cnt++;
27+
max = Math.max(max, cnt);
28+
} else {
29+
cnt = 0;
30+
}
31+
}
32+
return max;
33+
}
34+
35+
}
36+
37+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/base/至少是其他数字两倍的最大数.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.base;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/largest-number-at-least-twice-of-others/">747. 至少是其他数字两倍的最大数</a>
7+
*
8+
* @author Zhang Peng
9+
* @since 2018-11-04
10+
*/
11+
public class 至少是其他数字两倍的最大数 {
12+
13+
public static void main(String[] args) {
14+
Solution s = new Solution();
15+
Assertions.assertEquals(1, s.dominantIndex(new int[] { 3, 6, 1, 0 }));
16+
Assertions.assertEquals(-1, s.dominantIndex(new int[] { 1, 2, 3, 4 }));
17+
Assertions.assertEquals(0, s.dominantIndex(new int[] { 1, 0 }));
18+
}
19+
20+
static class Solution {
21+
22+
public int dominantIndex(int[] nums) {
23+
int second = -1, max = 0;
24+
for (int i = 1; i < nums.length; i++) {
25+
if (nums[i] > nums[max]) {
26+
second = max;
27+
max = i;
28+
} else if (second == -1 || nums[i] > nums[second]) {
29+
second = i;
30+
}
31+
}
32+
return nums[max] >= 2 * nums[second] ? max : -1;
33+
}
34+
35+
}
36+
37+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/bsearch/搜索插入位置.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.bsearch;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode-cn.com/problems/search-insert-position/">35. 搜索插入位置</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2020-07-29
10+
*/
11+
public class 搜索插入位置 {
12+
13+
public static void main(String[] args) {
14+
Solution s = new Solution();
15+
Assertions.assertEquals(0, s.searchInsert(new int[] { 1 }, 1));
16+
Assertions.assertEquals(2, s.searchInsert(new int[] { 1, 3, 5, 6 }, 5));
17+
Assertions.assertEquals(1, s.searchInsert(new int[] { 1, 3, 5, 6 }, 2));
18+
Assertions.assertEquals(4, s.searchInsert(new int[] { 1, 3, 5, 6 }, 7));
19+
Assertions.assertEquals(0, s.searchInsert(new int[] { 1, 3, 5, 6 }, 0));
20+
}
21+
22+
static class Solution {
23+
24+
public int searchInsert(int[] nums, int target) {
25+
int left = 0, right = nums.length - 1;
26+
while (left <= right) {
27+
int mid = left + (right - left) / 2;
28+
if (nums[mid] == target) {
29+
return mid;
30+
} else if (nums[mid] < target) {
31+
left = mid + 1;
32+
} else if (nums[mid] > target) {
33+
right = mid - 1;
34+
}
35+
}
36+
return left;
37+
}
38+
39+
}
40+
41+
}

codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/模拟ArrayList1.java renamed to codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/demo/模拟ArrayList1.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.demo;
22

33
import java.util.Arrays;
44

codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/模拟ArrayList2.java renamed to codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/demo/模拟ArrayList2.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.demo;
22

33
public class 模拟ArrayList2<T> {
44

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/matrix/反转字符串中的单词.java‎

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

2828
public String reverseWords(String s) {
29-
String[] strs = s.split(" ");
29+
String[] arr = s.trim().split(" ");
3030
StringBuilder sb = new StringBuilder();
31-
for (int i = strs.length - 1; i >= 0; i--) {
32-
if (strs[i].equals("")) {
31+
for (int i = arr.length - 1; i >= 0; i--) {
32+
if (arr[i].equals("")) {
3333
continue;
3434
}
35-
sb.append(strs[i]).append(" ");
35+
sb.append(arr[i]).append(" ");
3636
}
37-
if (sb.lastIndexOf(" ") == sb.length() - 1) {
38-
return sb.substring(0, sb.length() - 1);
39-
}
40-
return sb.toString();
37+
return sb.toString().trim();
4138
}
4239

4340
}
@@ -48,19 +45,18 @@ static class Solution2 {
4845
public String reverseWords(String s) {
4946
// 删除首尾空格
5047
s = s.trim();
51-
int i = s.length() - 1, j = i;
48+
int l = s.length() - 1, r = l;
5249
StringBuilder res = new StringBuilder();
53-
while (i >= 0) {
54-
// 搜索首个空格
55-
while (i >= 0 && s.charAt(i) != ' ') { i--; }
50+
while (l >= 0) {
51+
// 左指针偏移，直到遇到空格
52+
while (l >= 0 && s.charAt(l) != ' ') { l--; }
5653
// 添加单词
57-
res.append(s.substring(i + 1, j + 1)).append(" ");
58-
// 跳过单词间空格
59-
while (i >= 0 && s.charAt(i) == ' ') { i--; }
60-
// j 指向下个单词的尾字符
61-
j = i;
54+
res.append(s.substring(l + 1, r + 1)).append(' ');
55+
// 左指针偏移，直到遇到非空格
56+
while (l >= 0 && s.charAt(l) == ' ') { l--; }
57+
// 右指针对齐左指针
58+
r = l;
6259
}
63-
// 转化为字符串并返回
6460
return res.toString().trim();
6561
}
6662

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

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package io.github.dunwu.algorithm.array.matrix;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/diagonal-traverse/">498. 对角线遍历</a>
10+
*
11+
* @author Zhang Peng
12+
* @since 2018-11-04
13+
*/
14+
public class 对角线遍历 {
15+
16+
public static void main(String[] args) {
17+
18+
Solution s = new Solution();
19+
20+
int[][] input = { { 1, 2 }, { 3, 4 } };
21+
int[] expect = { 1, 2, 3, 4 };
22+
23+
int[][] input2 = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
24+
int[] expect2 = { 1, 2, 4, 7, 5, 3, 6, 8, 9 };
25+
26+
int[][] input3 = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };
27+
int[] expect3 = { 1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16 };
28+
29+
Assertions.assertArrayEquals(expect, s.findDiagonalOrder(input));
30+
Assertions.assertArrayEquals(expect2, s.findDiagonalOrder(input2));
31+
Assertions.assertArrayEquals(expect3, s.findDiagonalOrder(input3));
32+
}
33+
34+
static class Solution {
35+
36+
public int[] findDiagonalOrder(int[][] mat) {
37+
38+
// base case
39+
if (mat == null || mat.length == 0) { return new int[0]; }
40+
41+
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]);
49+
}
50+
} else {
51+
for (int i = min; i <= max; i++) {
52+
list.add(mat[i][step - i]);
53+
}
54+
}
55+
}
56+
57+
int[] res = new int[list.size()];
58+
for (int k = 0; k < list.size(); k++) {
59+
res[k] = list.get(k);
60+
}
61+
return res;
62+
}
63+
64+
}
65+
66+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/matrix/螺旋矩阵.java‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -29,8 +29,7 @@ public List<Integer> spiralOrder(int[][] matrix) {
2929
}
3030

3131
int m = matrix.length, n = matrix[0].length;
32-
int up = 0, down = m - 1;
33-
int left = 0, right = n - 1;
32+
int up = 0, down = m - 1, left = 0, right = n - 1;
3433
List<Integer> res = new LinkedList<>();
3534
while (res.size() < m * n) {
3635
// 向右

0 commit comments

Comments
 (0)