Skip to content

Commit d39b288

Browse files
dunwudunwu
committed
update codes and docs
1 parent 72418c3 commit d39b288

39 files changed

+674
-465
lines changed

‎README.md‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -33,9 +33,7 @@
3333
- 查找
3434
- 跳表
3535
- [散列表](docs/hash.md)
36-
- [树](docs/tree/README.md)
37-
- [二叉树](docs/tree/binary-tree.md)
38-
- [红黑树](docs/tree/red-black-tree.md)
36+
- [树](docs/tree.md)
3937
- [图](docs/graph.md)
4038
- [堆](docs/heap.md)
4139
- [字典树](docs/trie.md)

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/判断子序列.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/is-subsequence/">392. 判断子序列</a>
8+
* @since 2020-07-06
9+
*/
10+
public class 判断子序列 {
11+
12+
public static void main(String[] args) {
13+
Assertions.assertTrue(isSubsequence("abc", "ahbgdc"));
14+
Assertions.assertFalse(isSubsequence("axc", "ahbgdc"));
15+
Assertions.assertTrue(isSubsequence("", "ahbgdc"));
16+
Assertions.assertFalse(isSubsequence("aaaaaa", "bbaaaa"));
17+
}
18+
19+
public static boolean isSubsequence(String s, String t) {
20+
if (s == null || s.length() == 0) return true;
21+
if (s.length() > t.length()) return false;
22+
char[] source = s.toCharArray();
23+
char[] target = t.toCharArray();
24+
int i = 0, j = 0;
25+
while (i < source.length && j < target.length) {
26+
if (target[j] != source[i]) {
27+
j++;
28+
} else {
29+
if (i == source.length - 1) {
30+
return true;
31+
}
32+
i++;
33+
j++;
34+
}
35+
}
36+
return false;
37+
}
38+
39+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/最大子序和.java‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/maximum-subarray/">53. 最大子序和</a>
8+
* @since 2020-07-06
9+
*/
10+
public class 最大子序和 {
11+
12+
public static void main(String[] args) {
13+
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
14+
Assertions.assertEquals(6, maxSubArray(nums));
15+
Assertions.assertEquals(-1, maxSubArray(new int[] { -1 }));
16+
}
17+
18+
public static int maxSubArray(int[] nums) {
19+
if (nums == null || nums.length == 0) return 0;
20+
21+
int[] dp = new int[nums.length + 1];
22+
dp[0] = nums[0];
23+
int max = dp[0];
24+
for (int i = 1; i < nums.length; i++) {
25+
dp[i] = dp[i - 1] >= 0 ? dp[i - 1] + nums[i] : nums[i];
26+
}
27+
28+
for (int i = 0; i < nums.length; i++) {
29+
if (max < dp[i]) {
30+
max = dp[i];
31+
}
32+
}
33+
return max;
34+
}
35+
36+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/最长上升子序列.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.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/">300. 最长上升子序列</a>
8+
* @since 2020-07-06
9+
*/
10+
public class 最长上升子序列 {
11+
12+
public static void main(String[] args) {
13+
int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
14+
Assertions.assertEquals(4, lengthOfLIS(nums));
15+
Assertions.assertEquals(1, lengthOfLIS(new int[] { 0 }));
16+
}
17+
18+
public static int lengthOfLIS(int[] nums) {
19+
if (nums == null || nums.length == 0) return 0;
20+
int max = 1;
21+
final int[] dp = new int[nums.length + 1];
22+
for (int i = 0; i < nums.length; i++) dp[i] = 1;
23+
for (int i = 1; i < nums.length; i++) {
24+
for (int j = 0; j < i; j++) {
25+
if (nums[j] < nums[i]) {
26+
dp[i] = Math.max(dp[i], dp[j] + 1);
27+
}
28+
}
29+
max = Math.max(max, dp[i]);
30+
}
31+
return max;
32+
}
33+
34+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/编辑距离.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/maximum-subarray/">72. 编辑距离</a>
8+
* @since 2020-07-06
9+
*/
10+
public class 编辑距离 {
11+
12+
public static void main(String[] args) {
13+
Assertions.assertEquals(3, minDistance("horse", "ros"));
14+
Assertions.assertEquals(5, minDistance("intention", "execution"));
15+
}
16+
17+
public static int minDistance(String word1, String word2) {
18+
int m = word1.length();
19+
int n = word2.length();
20+
int[][] dp = new int[m + 1][n + 1];
21+
for (int i = 0; i < m + 1; i++) dp[i][0] = i;
22+
for (int j = 0; j < n + 1; j++) dp[0][j] = j;
23+
24+
for (int i = 1; i < m + 1; i++) {
25+
for (int j = 1; j < n + 1; j++) {
26+
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
27+
dp[i][j] = dp[i - 1][j - 1];
28+
} else {
29+
int m1 = Math.min(dp[i - 1][j], dp[i][j - 1]);
30+
int m2 = Math.min(m1, dp[i - 1][j - 1]);
31+
dp[i][j] = 1 + m2;
32+
}
33+
}
34+
}
35+
return dp[m][n];
36+
}
37+
38+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/零钱兑换.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/coin-change/">322. 零钱兑换</a>
8+
* @since 2020-07-06
9+
*/
10+
public class 零钱兑换 {
11+
12+
public static void main(String[] args) {
13+
int[] nums = { 1, 2, 5 };
14+
Assertions.assertEquals(3, coinChange(nums, 11));
15+
Assertions.assertEquals(-1, coinChange(new int[] { 2 }, 3));
16+
}
17+
18+
19+
public static int coinChange(int[] coins, int amount) {
20+
return coinChange(coins, amount, 0);
21+
}
22+
23+
public static int coinChange(int[] coins, int amount, int idxCoin) {
24+
if (amount == 0) { return 0; }
25+
if (idxCoin < coins.length && amount > 0) {
26+
int maxVal = amount / coins[idxCoin];
27+
int minCost = Integer.MAX_VALUE;
28+
for (int x = 0; x <= maxVal; x++) {
29+
if (amount >= x * coins[idxCoin]) {
30+
int res = coinChange(coins, amount - x * coins[idxCoin], idxCoin + 1);
31+
if (res != -1) { minCost = Math.min(minCost, res + x); }
32+
}
33+
}
34+
return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
35+
}
36+
return -1;
37+
}
38+
39+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/分隔链表.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package io.github.dunwu.algorithm.list;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.List;
6+
7+
/**
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @see <a href="https://leetcode-cn.com/problems/partition-list/">86. 分隔链表</a>
10+
* @since 2020-07-06
11+
*/
12+
public class 分隔链表 {
13+
14+
public static void main(String[] args) {
15+
ListNode head = ListUtil.buildList(1, 4, 3, 2, 5, 2);
16+
ListNode result = partition(head, 3);
17+
List<Integer> list = ListUtil.toList(result);
18+
Assertions.assertArrayEquals(new Integer[] { 1, 2, 2, 4, 3, 5 }, list.toArray(new Integer[0]));
19+
20+
ListNode head2 = ListUtil.buildList(2, 1);
21+
ListNode result2 = partition(head2, 2);
22+
List<Integer> list2 = ListUtil.toList(result2);
23+
Assertions.assertArrayEquals(new Integer[] { 1, 2 }, list2.toArray(new Integer[0]));
24+
25+
ListNode head3 = ListUtil.buildList(3, 1, 2);
26+
ListNode result3 = partition(head3, 3);
27+
List<Integer> list3 = ListUtil.toList(result3);
28+
Assertions.assertArrayEquals(new Integer[] { 1, 2, 3 }, list3.toArray(new Integer[0]));
29+
}
30+
31+
public static ListNode partition(ListNode head, int x) {
32+
return null;
33+
}
34+
35+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/删除排序链表中的重复元素.java‎

Lines changed: 2 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66

77
/**
88
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @see <a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list">83. 删除排序链表中的重复元素</a>
910
* @since 2020-06-09
1011
*/
1112
public class 删除排序链表中的重复元素 {
@@ -19,29 +20,10 @@ public static void main(String[] args) {
1920
Assertions.assertArrayEquals(new Integer[] { 1, 2 }, list.toArray(new Integer[0]));
2021
}
2122

22-
/**
23-
* <code>83. 删除排序链表中的重复元素</code> 算法实现
24-
* <p>
25-
* 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
26-
* <p>
27-
* 示例 1:
28-
* <pre>
29-
* 输入: 1->1->2
30-
* 输出: 1->2
31-
* </pre>
32-
* <p>
33-
* 示例 2:
34-
* <pre>
35-
* 输入: 1->1->2->3->3
36-
* 输出: 1->2->3
37-
* </pre>
38-
*
39-
* @see <a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list">83. 删除排序链表中的重复元素</a>
40-
*/
4123
public static ListNode deleteDuplicates(ListNode head) {
4224
ListNode node = head;
4325
while (node != null && node.next != null) {
44-
if (node.next.val == node.val) {
26+
if (node.val == node.next.val) {
4527
node.next = node.next.next;
4628
} else {
4729
node = node.next;

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/删除排序链表中的重复元素II.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.list;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.List;
6+
7+
/**
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2020-07-06
10+
*/
11+
public class 删除排序链表中的重复元素II {
12+
13+
public static void main(String[] args) {
14+
ListNode head = ListUtil.buildList(1, 1, 2);
15+
System.out.println(ListUtil.toList(head));
16+
ListNode result = deleteDuplicates(head);
17+
List<Integer> list = ListUtil.toList(result);
18+
System.out.println(list);
19+
Assertions.assertArrayEquals(new Integer[] { 2 }, list.toArray(new Integer[0]));
20+
}
21+
22+
public static ListNode deleteDuplicates(ListNode head) {
23+
if (head == null) return head; // 若head为空则直接返回null
24+
ListNode dummy = new ListNode(-1); // 建立一个虚拟头结点
25+
ListNode tail = dummy; // 定义一个尾巴，用于尾插法。
26+
for (ListNode l = head, r = head; l != null; l = r) {
27+
while (r != null && r.val == l.val) r = r.next; // 只要r不为空并且与l的值相等则一直向后移动
28+
if (l.next == r) { // 若长度为1，则通过尾插法加入。
29+
tail.next = l; // 基本的尾插法
30+
tail = l;
31+
tail.next = null; // 这里记得将尾部的后面置为null，不然可能后面会带着一些其他的节点。
32+
}
33+
}
34+
return dummy.next;
35+
}
36+
37+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/反转链表.java‎

Lines changed: 25 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -3,28 +3,45 @@
33
import org.junit.jupiter.api.Assertions;
44

55
import java.util.List;
6+
import java.util.Stack;
67

78
/**
89
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
10+
* @see <a href="https://leetcode-cn.com/problems/reverse-linked-list/">206. 反转链表</a>
911
* @since 2020-06-09
1012
*/
1113
public class 反转链表 {
1214

1315
public static void main(String[] args) {
14-
ListNode head = ListUtil.buildList(1, 2, 4);
16+
ListNode head = ListUtil.buildList(1, 2, 3, 4);
1517
System.out.println(ListUtil.toList(head));
16-
ListNode result = reverseList(head);
18+
ListNode result = reverseList2(head);
1719
List<Integer> list = ListUtil.toList(result);
1820
System.out.println(list);
19-
Assertions.assertArrayEquals(new Integer[] { 4, 2, 1 }, list.toArray(new Integer[0]));
21+
Assertions.assertArrayEquals(new Integer[] { 4, 3, 2, 1 }, list.toArray(new Integer[0]));
2022
}
2123

22-
/**
23-
* <code>206. 反转链表</code> 算法实现
24-
*
25-
* @see <a href="https://leetcode-cn.com/problems/reverse-linked-list/">206. 反转链表</a>
26-
*/
24+
// 借助栈来实现
2725
public static ListNode reverseList(ListNode head) {
26+
if (head == null) return null;
27+
Stack<ListNode> stack = new Stack<>();
28+
ListNode node = head;
29+
while (node != null) {
30+
stack.push(node);
31+
node = node.next;
32+
}
33+
34+
ListNode dummy = new ListNode(-1);
35+
node = dummy;
36+
while (!stack.isEmpty()) {
37+
node.next = stack.pop();
38+
node.next.next = null;
39+
node = node.next;
40+
}
41+
return dummy.next;
42+
}
43+
44+
public static ListNode reverseList2(ListNode head) {
2845
if (head == null) {
2946
return null;
3047
}

0 commit comments

Comments
 (0)