Skip to content

Commit 5250fd2

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

14 files changed

Lines changed: 522 additions & 12 deletions

‎README.md‎

Lines changed: 43 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -2,15 +2,46 @@
22

33
> Java 实现算法
44
5-
* [查找](docs/search/README.md)
6-
* [线性表的查找](docs/search/linear-list-search.md)
7-
* [哈希表的查找](docs/search/hash-search.md)
8-
* [排序](docs/sort/README.md)
9-
* [冒泡排序](docs/sort/bubble-sort.md)
10-
* [快速排序](docs/sort/quick-sort.md)
11-
* [直接插入排序](docs/sort/insert-sort.md)
12-
* [希尔排序](docs/sort/shell-sort.md)
13-
* [简单选择排序](docs/sort/selection-sort.md)
14-
* [堆排序](docs/sort/heap-sort.md)
15-
* [归并排序](docs/sort/merge-sort.md)
16-
* [基数排序](docs/sort/radix-sort.md)
5+
## 笔记
6+
7+
- [查找](docs/search/README.md)
8+
- [线性表的查找](docs/search/linear-list-search.md)
9+
- [哈希表的查找](docs/search/hash-search.md)
10+
- [排序](docs/sort/README.md)
11+
- [冒泡排序](docs/sort/bubble-sort.md)
12+
- [快速排序](docs/sort/quick-sort.md)
13+
- [直接插入排序](docs/sort/insert-sort.md)
14+
- [希尔排序](docs/sort/shell-sort.md)
15+
- [简单选择排序](docs/sort/selection-sort.md)
16+
- [堆排序](docs/sort/heap-sort.md)
17+
- [归并排序](docs/sort/merge-sort.md)
18+
- [基数排序](docs/sort/radix-sort.md)
19+
20+
## 源码
21+
22+
### 数组
23+
24+
- [寻找数组的中心索引](codes\data-structure\src\main\java\io\github\dunwu\ds\array\FindPivotIndex.java)
25+
- [至少是其他数字两倍的最大数](codes\data-structure\src\main\java\io\github\dunwu\ds\array\LargestNumberAtLeastTwiceOfOthers.java)
26+
- [加一](codes\data-structure\src\main\java\io\github\dunwu\ds\array\PlusOne.java)
27+
- [对角线遍历](codes\data-structure\src\main\java\io\github\dunwu\ds\array\DiagonalTraverse.java)
28+
- [螺旋矩阵](codes\data-structure\src\main\java\io\github\dunwu\ds\array\SpiralMatrix.java)
29+
- [杨辉三角](codes\data-structure\src\main\java\io\github\dunwu\ds\array\PascalsTriangle.java)
30+
- [杨辉三角 II](codes\data-structure\src\main\java\io\github\dunwu\ds\array\PascalsTriangle2.java)
31+
- [数组拆分 I](codes\data-structure\src\main\java\io\github\dunwu\ds\array\ArrayPartition.java)
32+
- [两数之和 II - 输入有序数组](codes\data-structure\src\main\java\io\github\dunwu\ds\array\TwoSum2InputArrayIsSorted.java)
33+
- [移除元素](codes\data-structure\src\main\java\io\github\dunwu\ds\array\RemoveElement.java)
34+
- [最大连续 1 的个数](codes\data-structure\src\main\java\io\github\dunwu\ds\array\MaxConsecutiveOnes.java)
35+
- [长度最小的子数组](codes\data-structure\src\main\java\io\github\dunwu\ds\array\MinimumSizeSubarraySum.java)
36+
- [旋转数组](codes\data-structure\src\main\java\io\github\dunwu\ds\array\RotateArray.java)
37+
- [删除排序数组中的重复项](codes\data-structure\src\main\java\io\github\dunwu\ds\array\RemoveDuplicatesFromSortedArray.java)
38+
- [移动零](codes\data-structure\src\main\java\io\github\dunwu\ds\array\MoveZeros.java)
39+
40+
### 字符串
41+
42+
- [二进制求和](codes\data-structure\src\main\java\io\github\dunwu\ds\str\AddBinary.java)
43+
- [实现 strStr()](codes\data-structure\src\main\java\io\github\dunwu\ds\str\ImplementStrstr.java)
44+
- [最长公共前缀](codes\data-structure\src\main\java\io\github\dunwu\ds\str\LongestCommonPrefix.java)
45+
- [反转字符串](codes\data-structure\src\main\java\io\github\dunwu\ds\str\ReverseString.java)
46+
- [反转字符串中的单词](codes\data-structure\src\main\java\io\github\dunwu\ds\str\ReverseWordsInAString.java)
47+
- [反转字符串中的单词 III ](codes\data-structure\src\main\java\io\github\dunwu\ds\str\ReverseWordsInAString3.java)

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/MoveZeros.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+
// 【移动零】
4+
//
5+
// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
6+
//
7+
// 示例:
8+
//
9+
// 输入: [0,1,0,3,12]
10+
// 输出: [1,3,12,0,0]
11+
// 说明:
12+
//
13+
// 必须在原数组上操作，不能拷贝额外的数组。
14+
// 尽量减少操作次数。
15+
16+
17+
/**
18+
* @author Zhang Peng
19+
* @date 2018-11-05
20+
*/
21+
public class MoveZeros {
22+
private static void move(int[] nums, int pos) {
23+
int temp = nums[pos];
24+
for (int i = pos; i < nums.length - 1; i++) {
25+
nums[i] = nums[i + 1];
26+
}
27+
nums[nums.length - 1] = temp;
28+
}
29+
30+
public static void moveZeroes(int[] nums) {
31+
int i = 0;
32+
int right = nums.length - 1;
33+
while (i <= right) {
34+
if (nums[i] == 0) {
35+
move(nums, i);
36+
right--;
37+
} else {
38+
i++;
39+
}
40+
}
41+
}
42+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/PascalsTriangle2.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+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
// 【杨辉三角 II】
8+
//
9+
// 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
10+
//
11+
// 在杨辉三角中，每个数是它左上方和右上方的数的和。
12+
//
13+
// 示例:
14+
//
15+
// 输入: 3
16+
// 输出: [1,3,3,1]
17+
// 进阶：
18+
//
19+
// 你可以优化你的算法到 O(k) 空间复杂度吗？
20+
21+
22+
/**
23+
* @author Zhang Peng
24+
* @date 2018-11-05
25+
*/
26+
public class PascalsTriangle2 {
27+
public static List<Integer> getRow(int rowIndex) {
28+
List<List<Integer>> result = new ArrayList<>();
29+
30+
int rows = rowIndex + 1;
31+
if (rows <= 0) {
32+
33+
} else if (rows == 1) {
34+
result.add(Arrays.asList(1));
35+
} else if (rows == 2) {
36+
result.add(Arrays.asList(1));
37+
result.add(Arrays.asList(1, 1));
38+
} else {
39+
result.add(Arrays.asList(1));
40+
result.add(Arrays.asList(1, 1));
41+
for (int i = 2; i < rows; i++) {
42+
List<Integer> current = result.get(i - 1);
43+
List<Integer> next = new ArrayList<>();
44+
45+
for (int j = 0; j <= i; j++) {
46+
if (j == 0 || j == i) {
47+
next.add(1);
48+
} else {
49+
int x = current.get(j - 1);
50+
int y = current.get(j);
51+
next.add(x + y);
52+
}
53+
}
54+
55+
result.add(next);
56+
}
57+
}
58+
59+
return result.get(rowIndex);
60+
}
61+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/array/RemoveDuplicatesFromSortedArray.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+
// 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
8+
//
9+
// 示例 1:
10+
//
11+
// 给定数组 nums = [1,1,2],
12+
//
13+
// 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
14+
//
15+
// 你不需要考虑数组中超出新长度后面的元素。
16+
// 示例 2:
17+
//
18+
// 给定 nums = [0,0,1,1,1,2,2,3,3,4],
19+
//
20+
// 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
21+
//
22+
// 你不需要考虑数组中超出新长度后面的元素。
23+
// 说明:
24+
//
25+
// 为什么返回数值是整数，但输出的答案是数组呢?
26+
//
27+
// 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
28+
//
29+
// 你可以想象内部操作如下:
30+
//
31+
// // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
32+
// int len = removeDuplicates(nums);
33+
//
34+
// // 在函数里修改输入数组对于调用者是可见的。
35+
// // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
36+
// for (int i = 0; i < len; i++) {
37+
// print(nums[i]);
38+
// }
39+
40+
41+
/**
42+
* @author Zhang Peng
43+
* @date 2018-11-05
44+
*/
45+
public class RemoveDuplicatesFromSortedArray {
46+
private static void remove(int[] nums, int pos) {
47+
for (int i = pos; i < nums.length - 1; i++) {
48+
nums[i] = nums[i + 1];
49+
}
50+
}
51+
52+
public static int removeDuplicates(int[] nums) {
53+
int left = 0;
54+
int right = nums.length - 1;
55+
56+
while (left <= right) {
57+
for (int i = left + 1; i <= right; i++) {
58+
if (nums[i] == nums[left]) {
59+
remove(nums, i);
60+
right--;
61+
i--;
62+
}
63+
}
64+
left++;
65+
}
66+
67+
return right + 1;
68+
}
69+
}

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

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package io.github.dunwu.ds.array;
2+
3+
// 【旋转数组】
4+
//
5+
// 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
6+
//
7+
// 示例 1:
8+
//
9+
// 输入: [1,2,3,4,5,6,7] 和 k = 3
10+
// 输出: [5,6,7,1,2,3,4]
11+
// 解释:
12+
// 向右旋转 1 步: [7,1,2,3,4,5,6]
13+
// 向右旋转 2 步: [6,7,1,2,3,4,5]
14+
// 向右旋转 3 步: [5,6,7,1,2,3,4]
15+
// 示例 2:
16+
//
17+
// 输入: [-1,-100,3,99] 和 k = 2
18+
// 输出: [3,99,-1,-100]
19+
// 解释:
20+
// 向右旋转 1 步: [99,-1,-100,3]
21+
// 向右旋转 2 步: [3,99,-1,-100]
22+
// 说明:
23+
//
24+
// 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
25+
// 要求使用空间复杂度为 O(1) 的原地算法。
26+
27+
28+
/**
29+
* @author Zhang Peng
30+
* @date 2018-11-05
31+
*/
32+
public class RotateArray {
33+
public static void rotate(int[] nums, int k) {
34+
int i = 0;
35+
while (i < k) {
36+
int j = nums.length - 1;
37+
int temp = nums[nums.length - 1];
38+
while (j > 0) {
39+
nums[j] = nums[j - 1];
40+
j--;
41+
}
42+
nums[0] = temp;
43+
// System.out.println(ArrayUtil.getArrayString(nums, 0, nums.length - 1));
44+
i++;
45+
}
46+
}
47+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/str/ReverseString.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,19 @@
11
package io.github.dunwu.ds.str;
22

3+
// 【反转字符串】
4+
//
5+
// 编写一个函数，其作用是将输入的字符串反转过来。
6+
//
7+
// 示例 1:
8+
//
9+
// 输入: "hello"
10+
// 输出: "olleh"
11+
// 示例 2:
12+
//
13+
// 输入: "A man, a plan, a canal: Panama"
14+
// 输出: "amanaP :lanac a ,nalp a ,nam A"
15+
16+
317
/**
418
* @author Zhang Peng
519
* @date 2018-11-05

‎codes/data-structure/src/main/java/io/github/dunwu/ds/str/ReverseWordsInAString.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package io.github.dunwu.ds.str;
2+
3+
// 【反转字符串中的单词】
4+
//
5+
// 给定一个字符串，逐个翻转字符串中的每个单词。
6+
//
7+
// 示例:
8+
//
9+
// 输入: "the sky is blue",
10+
// 输出: "blue is sky the".
11+
// 说明:
12+
//
13+
// 无空格字符构成一个单词。
14+
// 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
15+
// 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
16+
// 进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。
17+
18+
19+
/**
20+
* @author Zhang Peng
21+
* @date 2018-11-05
22+
*/
23+
public class ReverseWordsInAString {
24+
public static String reverseWords(String s) {
25+
if (s == null) {
26+
return null;
27+
}
28+
29+
char[] a = s.toCharArray();
30+
int n = a.length;
31+
32+
// step 1. reverse the whole string
33+
reverse(a, 0, n - 1);
34+
// step 2. reverse each word
35+
reverseWords(a, n);
36+
// step 3. clean up spaces
37+
return cleanSpaces(a, n);
38+
}
39+
40+
private static void reverseWords(char[] a, int n) {
41+
int i = 0, j = 0;
42+
43+
while (i < n) {
44+
while (i < j || i < n && a[i] == ' ') {
45+
i++; // skip spaces
46+
}
47+
while (j < i || j < n && a[j] != ' ') {
48+
j++; // skip non spaces
49+
}
50+
// reverse the word
51+
reverse(a, i, j - 1);
52+
}
53+
}
54+
55+
// trim leading, trailing and multiple spaces
56+
private static String cleanSpaces(char[] a, int n) {
57+
int i = 0, j = 0;
58+
59+
while (j < n) {
60+
while (j < n && a[j] == ' ') {
61+
j++; // skip spaces
62+
}
63+
while (j < n && a[j] != ' ') {
64+
a[i++] = a[j++]; // keep non spaces
65+
}
66+
while (j < n && a[j] == ' ') {
67+
j++; // skip spaces
68+
}
69+
if (j < n) {
70+
a[i++] = ' '; // keep only one space
71+
}
72+
}
73+
74+
return new String(a).substring(0, i);
75+
}
76+
77+
// reverse a[] from a[i] to a[j]
78+
private static void reverse(char[] a, int i, int j) {
79+
while (i < j) {
80+
char t = a[i];
81+
a[i++] = a[j];
82+
a[j--] = t;
83+
}
84+
}
85+
}

0 commit comments

Comments
 (0)