Skip to content

Commit 3f7893a

Browse files
dunwudunwu
committed
数据结构算法
1 parent 9528373 commit 3f7893a

10 files changed

Lines changed: 777 additions & 0 deletions

File tree

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

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【对角线遍历】
4+
//
5+
// 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
6+
//
7+
// 示例:
8+
//
9+
// 输入:
10+
// [
11+
// [ 1, 2, 3 ],
12+
// [ 4, 5, 6 ],
13+
// [ 7, 8, 9 ]
14+
// ]
15+
//
16+
// 输出: [1,2,4,7,5,3,6,8,9]
17+
//
18+
// 说明:
19+
//
20+
// 给定矩阵中的元素总数不会超过 100000 。
21+
22+
23+
/**
24+
* @author Zhang Peng
25+
* @date 2018-11-04
26+
*/
27+
public class DiagonalTraverse {
28+
29+
private static int[] findDiagonalOrder(int[][] matrix) {
30+
if (matrix.length == 0) {
31+
return new int[0];
32+
}
33+
34+
int x = 0, y = 0;
35+
final int M = matrix.length;
36+
final int N = matrix[0].length;
37+
int[] arr = new int[M * N];
38+
for (int i = 0; i < arr.length; i++) {
39+
arr[i] = matrix[x][y];
40+
if ((x + y) % 2 == 0) {
41+
if (y == N - 1) {
42+
x++;
43+
} else if (x == 0) {
44+
y++;
45+
} else {
46+
x--;
47+
y++;
48+
}
49+
} else {
50+
if (x == M - 1) {
51+
y++;
52+
} else if (y == 0) {
53+
x++;
54+
} else {
55+
x++;
56+
y--;
57+
}
58+
}
59+
}
60+
return arr;
61+
}
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+
}
67+
}

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

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【寻找数组的中心索引】
4+
//
5+
// 给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。
6+
//
7+
// 我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
8+
//
9+
// 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
10+
//
11+
// 示例 1:
12+
//
13+
// 输入:
14+
// nums = [1, 7, 3, 6, 5, 6]
15+
// 输出: 3
16+
// 解释:
17+
// 索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。
18+
// 同时, 3 也是第一个符合要求的中心索引。
19+
// 示例 2:
20+
//
21+
// 输入:
22+
// nums = [1, 2, 3]
23+
// 输出: -1
24+
// 解释:
25+
// 数组中不存在满足此条件的中心索引。
26+
// 说明:
27+
//
28+
// nums 的长度范围为 [0, 10000]。
29+
// 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
30+
31+
32+
/**
33+
* @author Zhang Peng
34+
* @date 2018-11-04
35+
*/
36+
public class FindPivotIndex {
37+
public int pivotIndex(int[] nums) {
38+
int result = 0;
39+
for (int i = 0; i < nums.length; i++) {
40+
int sum1 = 0;
41+
int sum2 = 0;
42+
for (int a = 0; a < result; a++) {
43+
sum1 += nums[a];
44+
}
45+
46+
for (int b = result + 1; b < nums.length; b++) {
47+
sum2 += nums[b];
48+
}
49+
50+
if (sum1 == sum2) {
51+
return result;
52+
}
53+
54+
result++;
55+
}
56+
return -1;
57+
}
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+
}
66+
}

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

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【至少是其他数字两倍的最大数】
4+
//
5+
// 在一个给定的数组nums中，总是存在一个最大元素 。
6+
//
7+
// 查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
8+
//
9+
// 如果是，则返回最大元素的索引，否则返回-1。
10+
//
11+
// 示例 1:
12+
//
13+
// 输入: nums = [3, 6, 1, 0]
14+
// 输出: 1
15+
// 解释: 6是最大的整数, 对于数组中的其他整数,
16+
// 6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.
17+
//
18+
//
19+
// 示例 2:
20+
//
21+
// 输入: nums = [1, 2, 3, 4]
22+
// 输出: -1
23+
// 解释: 4没有超过3的两倍大, 所以我们返回 -1.
24+
//
25+
//
26+
// 提示:
27+
//
28+
// nums 的长度范围在[1, 50].
29+
// 每个 nums[i] 的整数范围在 [0, 99].
30+
31+
32+
/**
33+
* @author Zhang Peng
34+
* @date 2018-11-04
35+
*/
36+
public class LargestNumberAtLeastTwiceOfOthers {
37+
private static int dominantIndex(int[] nums) {
38+
int index = 0;
39+
while (index < nums.length) {
40+
boolean isMatch = true;
41+
int max = nums[index];
42+
for (int i = 0; i < nums.length; i++) {
43+
if (index != i && max < nums[i] * 2) {
44+
isMatch = false;
45+
break;
46+
}
47+
}
48+
if (isMatch) {
49+
return index;
50+
} else {
51+
index++;
52+
}
53+
}
54+
return -1;
55+
}
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+
}
64+
}

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

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package io.github.dunwu.ds.array;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
8+
// 【杨辉三角】
9+
//
10+
// 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
11+
//
12+
// 在杨辉三角中，每个数是它左上方和右上方的数的和。
13+
//
14+
// 示例:
15+
//
16+
// 输入: 5
17+
// 输出:
18+
// [
19+
// [1],
20+
// [1,1],
21+
// [1,2,1],
22+
// [1,3,3,1],
23+
// [1,4,6,4,1]
24+
// ]
25+
26+
27+
/**
28+
* @author Zhang Peng
29+
* @date 2018-11-04
30+
*/
31+
public class PascalsTriangle {
32+
33+
private static List<List<Integer>> generate(int numRows) {
34+
List<List<Integer>> result = new ArrayList<>();
35+
36+
if (numRows <= 0) {
37+
38+
} else if (numRows == 1) {
39+
result.add(Arrays.asList(1));
40+
} else if (numRows == 2) {
41+
result.add(Arrays.asList(1));
42+
result.add(Arrays.asList(1, 1));
43+
} else {
44+
result.add(Arrays.asList(1));
45+
result.add(Arrays.asList(1, 1));
46+
for (int i = 2; i < numRows; i++) {
47+
List<Integer> current = result.get(i - 1);
48+
List<Integer> next = new ArrayList<>();
49+
50+
for (int j = 0; j <= i; j++) {
51+
if (j == 0 || j == i) {
52+
next.add(1);
53+
} else {
54+
int x = current.get(j - 1);
55+
int y = current.get(j);
56+
next.add(x + y);
57+
}
58+
}
59+
60+
result.add(next);
61+
}
62+
}
63+
64+
return result;
65+
}
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+
}
84+
}

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

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【加一】
4+
//
5+
// 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
6+
//
7+
// 最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
8+
//
9+
// 你可以假设除了整数 0 之外，这个整数不会以零开头。
10+
//
11+
// 示例 1:
12+
//
13+
// 输入: [1,2,3]
14+
// 输出: [1,2,4]
15+
// 解释: 输入数组表示数字 123。
16+
// 示例 2:
17+
//
18+
// 输入: [4,3,2,1]
19+
// 输出: [4,3,2,2]
20+
// 解释: 输入数组表示数字 4321。
21+
22+
23+
import io.github.dunwu.ds.util.ArrayUtil;
24+
25+
/**
26+
* @author Zhang Peng
27+
* @date 2018-11-04
28+
*/
29+
public class PlusOne {
30+
private static int[] plusOne(int[] digits) {
31+
int n = digits.length;
32+
for (int i = n - 1; i >= 0; i--) {
33+
if (digits[i] < 9) {
34+
digits[i]++;
35+
return digits;
36+
}
37+
38+
digits[i] = 0;
39+
}
40+
41+
int[] newNumber = new int[n + 1];
42+
newNumber[0] = 1;
43+
44+
return newNumber;
45+
}
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+
}
69+
}

0 commit comments

Comments
 (0)