Skip to content

Commit 1964a4d

Browse files
dunwudunwu
committed
更新刷题
1 parent dfc0428 commit 1964a4d

26 files changed

+1307
-471
lines changed

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/两数之和.java‎

Lines changed: 21 additions & 75 deletions
Original file line numberDiff line numberDiff line change
@@ -6,105 +6,51 @@
66
import java.util.Map;
77

88
/**
9+
* 题目：<a href="https://leetcode-cn.com/problems/two-sum/">1. 两数之和</a>
10+
*
911
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
1012
* @since 2020-06-05
1113
*/
1214
public class 两数之和 {
1315

1416
public static void main(String[] args) {
15-
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSumInSorted(new int[] { 2, 7, 11, 15 }, 9));
16-
Assertions.assertArrayEquals(new int[] { 1, 3 }, twoSumInSorted(new int[] { 2, 3, 4 }, 6));
17-
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSumInSorted(new int[] { 0, 0, 3, 4 }, 0));
17+
Assertions.assertArrayEquals(new int[] { 0, 1 }, twoSumInSorted(new int[] { 2, 7, 11, 15 }, 9));
18+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSumInSorted(new int[] { 3, 2, 4 }, 6));
19+
Assertions.assertArrayEquals(new int[] { 0, 1 }, twoSumInSorted(new int[] { 3, 3 }, 6));
1820

19-
Assertions.assertArrayEquals(new int[] { 0, 1 },
20-
twoSum_method1(new int[] { 2, 7, 11, 15 }, 9));
21-
Assertions.assertArrayEquals(new int[] { 1, 2 },
22-
twoSum_method1(new int[] { 3, 2, 4 }, 6));
23-
Assertions.assertArrayEquals(new int[] { -1, -1 },
24-
twoSum_method1(new int[] { 3, 2, 4 }, 9));
25-
26-
Assertions.assertArrayEquals(new int[] { 0, 1 },
27-
twoSum_method2(new int[] { 2, 7, 11, 15 }, 9));
28-
Assertions.assertArrayEquals(new int[] { 1, 2 },
29-
twoSum_method2(new int[] { 3, 2, 4 }, 6));
30-
Assertions.assertArrayEquals(new int[] { -1, -1 },
31-
twoSum_method2(new int[] { 3, 2, 4 }, 9));
21+
Assertions.assertArrayEquals(new int[] { 0, 1 }, twoSumInSorted2(new int[] { 2, 7, 11, 15 }, 9));
22+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSumInSorted2(new int[] { 3, 2, 4 }, 6));
23+
Assertions.assertArrayEquals(new int[] { 0, 1 }, twoSumInSorted2(new int[] { 3, 3 }, 6));
3224
}
3325

3426
/**
35-
* 题目：<a href="https://leetcode-cn.com/problems/two-sum/">1. 两数之和</a>
36-
* <p>
37-
* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
38-
* <p>
39-
* 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
27+
* 时间复杂度：O(n^2)
4028
*/
4129
public static int[] twoSumInSorted(int[] nums, int target) {
42-
final int[] notFound = new int[] { -1, -1 };
43-
if (nums == null || nums.length < 2) {
44-
return notFound;
45-
}
46-
47-
int left = 0, right = nums.length - 1;
48-
while (left <= right) {
49-
int v = nums[left] + nums[right];
50-
if (v == target) {
51-
return new int[] { left + 1, right + 1 };
52-
} else if (v > target) {
53-
right--;
54-
} else {
55-
left++;
56-
}
57-
}
58-
return notFound;
59-
}
60-
61-
/**
62-
* 题目：<a href="https://leetcode-cn.com/problems/two-sum/">1. 两数之和</a>
63-
* <p>
64-
* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
65-
* <p>
66-
* 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
67-
*/
68-
public static int[] twoSum_method1(int[] nums, int target) {
69-
final int[] notFound = new int[] { -1, -1 };
70-
if (nums == null || nums.length < 2) {
71-
return notFound;
72-
}
73-
74-
for (int i = 0; i < nums.length; i++) {
75-
for (int j = i + 1; j < nums.length; j++) {
76-
if (nums[i] + nums[j] == target) {
77-
return new int[] { i, j };
30+
for (int left = 0; left < nums.length; left++) {
31+
for (int right = left + 1; right < nums.length; right++) {
32+
if (nums[left] + nums[right] == target) {
33+
return new int[] { left, right };
7834
}
7935
}
8036
}
81-
return notFound;
37+
return new int[] { -1, -1 };
8238
}
8339

8440
/**
85-
* 题目：<a href="https://leetcode-cn.com/problems/two-sum/">1. 两数之和</a>
86-
* <p>
87-
* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
88-
* <p>
89-
* 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
41+
* 时间复杂度：O(n)
9042
*/
91-
public static int[] twoSum_method2(int[] nums, int target) {
92-
final int[] notFound = new int[] { -1, -1 };
93-
if (nums == null || nums.length < 2) {
94-
return notFound;
95-
}
96-
97-
Map<Integer, Integer> map = new HashMap<>();
43+
public static int[] twoSumInSorted2(int[] nums, int target) {
44+
Map<Integer, Integer> map = new HashMap<>(nums.length);
9845
for (int i = 0; i < nums.length; i++) {
99-
int temp = target - nums[i];
100-
if (map.containsKey(temp)) {
101-
return new int[] { map.get(temp), i };
46+
int expectNum = target - nums[i];
47+
if (map.containsKey(expectNum)) {
48+
return new int[] { map.get(expectNum), i };
10249
} else {
10350
map.put(nums[i], i);
10451
}
10552
}
106-
107-
return notFound;
53+
return new int[] { -1, -1 };
10854
}
10955

11056
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/两数之和II.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
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/two-sum-ii-input-array-is-sorted/description/">167. 两数之和 II - 输入有序数组</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @since 2020-06-05
13+
*/
14+
public class 两数之和II {
15+
16+
public static void main(String[] args) {
17+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSum(new int[] { 2, 7, 11, 15 }, 9));
18+
Assertions.assertArrayEquals(new int[] { 1, 3 }, twoSum(new int[] { 2, 3, 4 }, 6));
19+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSum(new int[] { -1, 0 }, -1));
20+
21+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSum2(new int[] { 2, 7, 11, 15 }, 9));
22+
Assertions.assertArrayEquals(new int[] { 1, 3 }, twoSum2(new int[] { 2, 3, 4 }, 6));
23+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSum2(new int[] { -1, 0 }, -1));
24+
25+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSum3(new int[] { 2, 7, 11, 15 }, 9));
26+
Assertions.assertArrayEquals(new int[] { 1, 3 }, twoSum3(new int[] { 2, 3, 4 }, 6));
27+
Assertions.assertArrayEquals(new int[] { 1, 2 }, twoSum3(new int[] { -1, 0 }, -1));
28+
}
29+
30+
/**
31+
* 时间复杂度：O(n^2)
32+
*/
33+
public static int[] twoSum(int[] numbers, int target) {
34+
for (int i = 0; i < numbers.length; i++) {
35+
for (int j = i + 1; j < numbers.length; j++) {
36+
if (numbers[i] + numbers[j] == target) {
37+
return new int[] { i + 1, j + 1 };
38+
}
39+
}
40+
}
41+
return new int[] { -1, -1 };
42+
}
43+
44+
/**
45+
* 时间复杂度：O(n)
46+
*/
47+
public static int[] twoSum2(int[] numbers, int target) {
48+
int len = numbers.length;
49+
Map<Integer, Integer> map = new HashMap<>(len);
50+
for (int i = 0; i < len; i++) {
51+
int num = numbers[i];
52+
int diff = target - num;
53+
if (map.containsKey(diff)) {
54+
return new int[] { map.get(diff) + 1, i + 1 };
55+
}
56+
map.put(num, i);
57+
}
58+
return new int[] { -1, -1 };
59+
}
60+
61+
/**
62+
* 时间复杂度：O(logn)
63+
*/
64+
public static int[] twoSum3(int[] numbers, int target) {
65+
int left = 0, right = numbers.length - 1;
66+
while (left < right) {
67+
int sum = numbers[left] + numbers[right];
68+
if (sum == target) {
69+
return new int[] { left + 1, right + 1 };
70+
} else if (sum < target) {
71+
left++;
72+
} else {
73+
right--;
74+
}
75+
}
76+
return new int[] { -1, -1 };
77+
}
78+
79+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/删除排序数组中的重复项.java‎

Lines changed: 14 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -48,40 +48,31 @@ public class 删除排序数组中的重复项 {
4848

4949
public static void main(String[] args) {
5050
int[] nums1 = { 1, 1, 2 };
51-
Assertions.assertEquals(2, 删除排序数组中的重复项.removeDuplicates(nums1));
51+
Assertions.assertEquals(2, removeDuplicates(nums1));
5252

5353
int[] nums2 = { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };
54-
Assertions.assertEquals(5, 删除排序数组中的重复项.removeDuplicates(nums2));
54+
Assertions.assertEquals(5, removeDuplicates(nums2));
5555

5656
int[] nums3 = { 1, 2 };
57-
Assertions.assertEquals(2, 删除排序数组中的重复项.removeDuplicates(nums3));
57+
Assertions.assertEquals(2, removeDuplicates(nums3));
5858

5959
int[] nums4 = { 2, 2 };
60-
Assertions.assertEquals(1, 删除排序数组中的重复项.removeDuplicates(nums4));
60+
Assertions.assertEquals(1, removeDuplicates(nums4));
6161
}
6262

6363
public static int removeDuplicates(int[] nums) {
64-
int left = 0;
65-
int right = nums.length - 1;
66-
67-
while (left <= right) {
68-
for (int i = left + 1; i <= right; i++) {
69-
if (nums[i] == nums[left]) {
70-
remove(nums, i);
71-
right--;
72-
i--;
73-
}
74-
}
75-
left++;
64+
if (nums.length == 0) {
65+
return 0;
7666
}
77-
78-
return right + 1;
79-
}
80-
81-
private static void remove(int[] nums, int pos) {
82-
for (int i = pos; i < nums.length - 1; i++) {
83-
nums[i] = nums[i + 1];
67+
int slow = 0, fast = 0;
68+
while (fast < nums.length) {
69+
if (nums[slow] != nums[fast]) {
70+
slow++;
71+
nums[slow] = nums[fast];
72+
}
73+
fast++;
8474
}
75+
return slow + 1;
8576
}
8677

8778
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/反转字符串.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* 题目：<a href="https://leetcode.cn/problems/reverse-string/description/">344. 反转字符串</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2020-06-05
10+
*/
11+
public class 反转字符串 {
12+
13+
public static void main(String[] args) {
14+
char[] s1 = new char[] { 'h', 'e', 'l', 'l', 'o' };
15+
reverseString(s1);
16+
Assertions.assertArrayEquals(new char[] { 'o', 'l', 'l', 'e', 'h' }, s1);
17+
18+
char[] s2 = new char[] { 'H', 'a', 'n', 'n', 'a', 'h' };
19+
reverseString(s2);
20+
Assertions.assertArrayEquals(new char[] { 'h', 'a', 'n', 'n', 'a', 'H' }, s2);
21+
}
22+
23+
public static void reverseString(char[] s) {
24+
int left = 0, right = s.length - 1;
25+
while (left < right) {
26+
char temp = s[left];
27+
s[left] = s[right];
28+
s[right] = temp;
29+
left++;
30+
right--;
31+
}
32+
}
33+
34+
}

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

Lines changed: 57 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -28,9 +28,19 @@
2828
public class 对角线遍历 {
2929

3030
public static void main(String[] args) {
31-
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
32-
int[] expected = { 1, 2, 4, 7, 5, 3, 6, 8, 9 };
31+
32+
int[][] matrix = { { 1, 2 }, { 3, 4 } };
33+
int[] expected = { 1, 2, 3, 4 };
34+
35+
int[][] matrix2 = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
36+
int[] expected2 = { 1, 2, 4, 7, 5, 3, 6, 8, 9 };
37+
38+
int[][] matrix3 = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };
39+
int[] expected3 = { 1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16 };
40+
3341
Assertions.assertArrayEquals(expected, 对角线遍历.findDiagonalOrder(matrix));
42+
Assertions.assertArrayEquals(expected2, 对角线遍历.findDiagonalOrder(matrix2));
43+
Assertions.assertArrayEquals(expected3, 对角线遍历.findDiagonalOrder(matrix3));
3444
}
3545

3646
public static int[] findDiagonalOrder(int[][] matrix) {
@@ -67,4 +77,49 @@ public static int[] findDiagonalOrder(int[][] matrix) {
6777
return arr;
6878
}
6979

80+
public static int[] findDiagonalOrder2(int[][] matrix) {
81+
final int UP = 1;
82+
final int DOWN = 2;
83+
final int M = matrix.length;
84+
final int N = matrix[0].length;
85+
int i = 0, j = 0, status = UP;
86+
87+
int[] result = new int[M * N];
88+
// System.out.println("========================================");
89+
// System.out.println(JSONUtil.toJsonStr(matrix));
90+
// System.out.println("========================================");
91+
int index = 0;
92+
while (i < M && j < N) {
93+
result[index] = matrix[i][j];
94+
System.out.println(result[index]);
95+
index++;
96+
if (status == UP) {
97+
if (i == 0 || j == N - 1) {
98+
status = DOWN;
99+
if (j == N - 1) {
100+
i++;
101+
} else {
102+
j++;
103+
}
104+
} else {
105+
i--;
106+
j++;
107+
}
108+
} else {
109+
if (j == 0 || i == M - 1) {
110+
status = UP;
111+
if (i == M - 1) {
112+
j++;
113+
} else {
114+
i++;
115+
}
116+
} else {
117+
i++;
118+
j--;
119+
}
120+
}
121+
}
122+
return result;
123+
}
124+
70125
}

0 commit comments

Comments
 (0)