Skip to content

Commit 71fdb48

Browse files
dunwudunwu
committed
数据结构算法
1 parent c3bf9fb commit 71fdb48

24 files changed

+481
-68
lines changed

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/ArrayPartition.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【数组拆分 I】
4+
//
5+
// 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
6+
//
7+
// 示例 1:
8+
//
9+
// 输入: [1,4,3,2]
10+
//
11+
// 输出: 4
12+
// 解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
13+
// 提示:
14+
//
15+
// n 是正整数,范围在 [1, 10000].
16+
// 数组中的元素范围在 [-10000, 10000].
17+
18+
19+
import java.util.Arrays;
20+
21+
/**
22+
* @author Zhang Peng
23+
* @date 2018-11-05
24+
*/
25+
public class ArrayPartition {
26+
public static int arrayPairSum(int[] nums) {
27+
Arrays.sort(nums);
28+
int result = 0;
29+
for (int i = 0; i < nums.length; i += 2) {
30+
result += nums[i];
31+
}
32+
return result;
33+
}
34+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/DiagonalTraverse.java‎

Lines changed: 1 addition & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@
2626
*/
2727
public class DiagonalTraverse {
2828

29-
private static int[] findDiagonalOrder(int[][] matrix) {
29+
public static int[] findDiagonalOrder(int[][] matrix) {
3030
if (matrix.length == 0) {
3131
return new int[0];
3232
}
@@ -59,9 +59,4 @@ private static int[] findDiagonalOrder(int[][] matrix) {
5959
}
6060
return arr;
6161
}
62-
63-
public static void main(String[] args) {
64-
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
65-
int[] results = findDiagonalOrder(matrix);
66-
}
6762
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/FindPivotIndex.java‎

Lines changed: 1 addition & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@
3434
* @date 2018-11-04
3535
*/
3636
public class FindPivotIndex {
37-
public int pivotIndex(int[] nums) {
37+
public static int pivotIndex(int[] nums) {
3838
int result = 0;
3939
for (int i = 0; i < nums.length; i++) {
4040
int sum1 = 0;
@@ -55,12 +55,4 @@ public int pivotIndex(int[] nums) {
5555
}
5656
return -1;
5757
}
58-
59-
public static void main(String[] args) {
60-
int[] nums = {1, 7, 3, 6, 5, 6};
61-
62-
FindPivotIndex demo = new FindPivotIndex();
63-
int result = demo.pivotIndex(nums);
64-
System.out.println("result = [" + result + "]");
65-
}
6658
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/LargestNumberAtLeastTwiceOfOthers.java‎

Lines changed: 1 addition & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@
3434
* @date 2018-11-04
3535
*/
3636
public class LargestNumberAtLeastTwiceOfOthers {
37-
private static int dominantIndex(int[] nums) {
37+
public static int dominantIndex(int[] nums) {
3838
int index = 0;
3939
while (index < nums.length) {
4040
boolean isMatch = true;
@@ -53,12 +53,4 @@ private static int dominantIndex(int[] nums) {
5353
}
5454
return -1;
5555
}
56-
57-
public static void main(String[] args) {
58-
int[] nums1 = {3, 6, 1, 0};
59-
int[] nums2 = {1, 2, 3, 4};
60-
61-
System.out.println("result1 = [" + dominantIndex(nums1) + "]");
62-
System.out.println("result2 = [" + dominantIndex(nums2) + "]");
63-
}
6456
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/MaxConsecutiveOnes.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【最大连续1的个数】
4+
//
5+
// 给定一个二进制数组， 计算其中最大连续1的个数。
6+
//
7+
// 示例 1:
8+
//
9+
// 输入: [1,1,0,1,1,1]
10+
// 输出: 3
11+
// 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
12+
// 注意：
13+
//
14+
// 输入的数组只包含 0 和1。
15+
// 输入数组的长度是正整数，且不超过 10,000。
16+
17+
18+
/**
19+
* @author Zhang Peng
20+
* @date 2018-11-05
21+
*/
22+
public class MaxConsecutiveOnes {
23+
public static int findMaxConsecutiveOnes(int[] nums) {
24+
int max = 0;
25+
int count = 0;
26+
for (int i = 0; i < nums.length; i++) {
27+
if (nums[i] == 1) {
28+
count++;
29+
} else {
30+
if (count > max) {
31+
max = count;
32+
}
33+
count = 0;
34+
}
35+
}
36+
37+
if (count > max) {
38+
max = count;
39+
}
40+
return max;
41+
}
42+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/MinimumSizeSubarraySum.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【长度最小的子数组】
4+
//
5+
// 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
6+
//
7+
// 示例:
8+
//
9+
// 输入: s = 7, nums = [2,3,1,2,4,3]
10+
// 输出: 2
11+
// 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
12+
// 进阶:
13+
//
14+
// 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
15+
16+
17+
/**
18+
* @author Zhang Peng
19+
* @date 2018-11-05
20+
*/
21+
public class MinimumSizeSubarraySum {
22+
public static int minSubArrayLen(int s, int[] nums) {
23+
if (nums == null || nums.length == 0) {
24+
return 0;
25+
}
26+
27+
int j = 0, i = 0, sum = 0, min = Integer.MAX_VALUE;
28+
29+
while (i < nums.length) {
30+
sum += nums[i++];
31+
32+
while (sum >= s) {
33+
min = Math.min(min, i - j);
34+
sum -= nums[j++];
35+
}
36+
}
37+
38+
return min == Integer.MAX_VALUE ? 0 : min;
39+
}
40+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/PascalsTriangle.java‎

Lines changed: 1 addition & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@
3030
*/
3131
public class PascalsTriangle {
3232

33-
private static List<List<Integer>> generate(int numRows) {
33+
public static List<List<Integer>> generate(int numRows) {
3434
List<List<Integer>> result = new ArrayList<>();
3535

3636
if (numRows <= 0) {
@@ -63,22 +63,4 @@ private static List<List<Integer>> generate(int numRows) {
6363

6464
return result;
6565
}
66-
67-
private static void printPascalsTriangle(int level) {
68-
System.out.printf("【%d层杨辉三角】\n", level);
69-
List<List<Integer>> lists = generate(level);
70-
for (List<Integer> list : lists) {
71-
for (Integer num : list) {
72-
System.out.print(num + "\t");
73-
}
74-
System.out.println();
75-
}
76-
System.out.println();
77-
}
78-
79-
public static void main(String[] args) {
80-
for (int i = 1; i <= 5; i++) {
81-
printPascalsTriangle(i);
82-
}
83-
}
8466
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/PlusOne.java‎

Lines changed: 1 addition & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@
2727
* @date 2018-11-04
2828
*/
2929
public class PlusOne {
30-
private static int[] plusOne(int[] digits) {
30+
public static int[] plusOne(int[] digits) {
3131
int n = digits.length;
3232
for (int i = n - 1; i >= 0; i--) {
3333
if (digits[i] < 9) {
@@ -43,27 +43,4 @@ private static int[] plusOne(int[] digits) {
4343

4444
return newNumber;
4545
}
46-
47-
private static String getArrayString(int[] array) {
48-
StringBuilder sb = new StringBuilder();
49-
for (int i = 0; i < array.length - 1; i++) {
50-
sb.append(array[i] + ", ");
51-
}
52-
sb.append(array[array.length - 1]);
53-
return sb.toString();
54-
}
55-
56-
public static void main(String[] args) {
57-
int[] nums1 = {1, 2, 3};
58-
int[] nums2 = {4, 3, 2, 1};
59-
int[] nums3 = {9, 9, 9, 9};
60-
61-
int[] result1 = plusOne(nums1);
62-
int[] result2 = plusOne(nums2);
63-
int[] result3 = plusOne(nums3);
64-
65-
System.out.println("nums1 = [" + ArrayUtil.getArrayString(result1, 0, result1.length - 1) + "]");
66-
System.out.println("nums2 = [" + ArrayUtil.getArrayString(result2, 0, result2.length - 1) + "]");
67-
System.out.println("nums3 = [" + ArrayUtil.getArrayString(result3, 0, result3.length - 1) + "]");
68-
}
6946
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/RemoveElement.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【移除元素】
4+
//
5+
// 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
6+
//
7+
// 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
8+
//
9+
// 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
10+
//
11+
// 示例 1:
12+
//
13+
// 给定 nums = [3,2,2,3], val = 3,
14+
//
15+
// 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
16+
//
17+
// 你不需要考虑数组中超出新长度后面的元素。
18+
// 示例 2:
19+
//
20+
// 给定 nums = [0,1,2,2,3,0,4,2], val = 2,
21+
//
22+
// 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
23+
//
24+
// 注意这五个元素可为任意顺序。
25+
//
26+
// 你不需要考虑数组中超出新长度后面的元素。
27+
// 说明:
28+
//
29+
// 为什么返回数值是整数，但输出的答案是数组呢?
30+
//
31+
// 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
32+
//
33+
// 你可以想象内部操作如下:
34+
//
35+
// // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
36+
// int len = removeElement(nums, val);
37+
//
38+
// // 在函数里修改输入数组对于调用者是可见的。
39+
// // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
40+
// for (int i = 0; i < len; i++) {
41+
// print(nums[i]);
42+
// }
43+
44+
45+
/**
46+
* @author Zhang Peng
47+
* @date 2018-11-05
48+
*/
49+
public class RemoveElement {
50+
public static int removeElement(int[] nums, int val) {
51+
int end = 0;
52+
final int n = nums.length;
53+
for (int i = 0; i < n; i++) {
54+
if (nums[i] != val) {
55+
nums[end] = nums[i];
56+
end++;
57+
}
58+
}
59+
return end;
60+
}
61+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/SpiralMatrix.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@
3333
* @date 2018-11-04
3434
*/
3535
public class SpiralMatrix {
36-
private static List<Integer> spiralOrder(int[][] matrix) {
36+
public static List<Integer> spiralOrder(int[][] matrix) {
3737
ArrayList<Integer> list = new ArrayList<>();
3838
if (matrix.length == 0) {
3939
return list;

0 commit comments

Comments
 (0)