Skip to content

Commit 1dbde8a

Browse files
dunwudunwu
committed
update codes and docs
1 parent 59fc909 commit 1dbde8a

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

48 files changed

+1315
-98
lines changed

‎README.md‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -197,15 +197,17 @@
197197
- [The-Art-Of-Programming-By-July](https://github.com/julycoding/The-Art-Of-Programming-By-July)
198198
- [微软面试 100 题](http://blog.csdn.net/column/details/ms100.html)
199199
- [程序员编程艺术](http://blog.csdn.net/v_JULY_v/article/details/6460494)
200-
- 基本算法演示
200+
- **基本算法演示**
201201
- <http://sjjg.js.zwu.edu.cn/SFXX/sf1/sfys.html>
202202
- <http://www.cs.usfca.edu/\~galles/visualization/Algorithms.html>
203-
- 编程网站
203+
- **编程网站**
204204
- [leetcode](http://leetcode-cn.com/)
205205
- [openjudge](http://openjudge.cn/)
206-
- 其它
206+
- **教程**
207207
- [高级数据结构和算法](https://www.coursera.org/learn/gaoji-shuju-jiegou/) 北大教授张铭老师在 coursera 上的课程。完成这门课之时，你将掌握多维数组、广义表、Trie 树、AVL 树、伸展树等高级数据结构，并结合内排序、外排序、检索、索引有关的算法，高效地解决现实生活中一些比较复杂的应用问题。当然 coursera 上也还有很多其它算法方面的视频课程。
208208
- [算法设计与分析 Design and Analysis of Algorithms](https://class.coursera.org/algorithms-001/lecture) 由北大教授 Wanling Qu 在 coursera 讲授的一门算法课程。首先介绍一些与算法有关的基础知识，然后阐述经典的算法设计思想和分析技术，主要涉及的算法设计技术是：分治策略、动态规划、贪心法、回溯与分支限界等。每个视频都配有相应的讲义（pdf 文件）以便阅读和复习。
209+
- [算法面试通关 40 讲](https://time.geekbang.org/course/intro/100019701)
210+
- [数据结构与算法之美](https://time.geekbang.org/column/intro/100017301)
209211

210212
## 🚪 传送
211213

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/合并区间.java‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.Arrays;
6+
7+
/**
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2020-07-29
10+
*/
11+
public class 合并区间 {
12+
13+
public static void main(String[] args) {
14+
int[][] array = new int[][] {
15+
{ 1, 4 }, { 2, 3 }
16+
};
17+
int[][] exprect = new int[][] {
18+
{ 1, 4 }
19+
};
20+
Assertions.assertArrayEquals(exprect, merge(array));
21+
22+
// int[][] array = new int[][] {
23+
// { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 }
24+
// };
25+
// int[][] exprect = new int[][] {
26+
// { 1, 6 }, { 8, 10 }, { 15, 18 }
27+
// };
28+
// Assertions.assertArrayEquals(exprect, merge(array));
29+
30+
int[][] array2 = new int[][] {
31+
{ 1, 4 }, { 4, 5 }
32+
};
33+
int[][] exprect2 = new int[][] {
34+
{ 1, 5 }
35+
};
36+
Assertions.assertArrayEquals(exprect2, merge(array2));
37+
}
38+
39+
public static int[][] merge(int[][] intervals) {
40+
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
41+
42+
int len = intervals.length;
43+
int[][] res = new int[len][2];
44+
int cnt = 0;
45+
for (int[] interval : intervals) {
46+
boolean merged = false;
47+
for (int i = 0; i < cnt; i++) {
48+
if (interval[0] >= res[i][0] && interval[1] <= res[i][1]) {
49+
merged = true;
50+
continue;
51+
}
52+
if (interval[0] <= res[i][1]) {
53+
if (interval[1] >= res[i][1]) {
54+
res[i][1] = interval[1];
55+
merged = true;
56+
continue;
57+
}
58+
}
59+
}
60+
if (!merged) {
61+
res[cnt] = Arrays.copyOf(interval, 2);
62+
cnt++;
63+
}
64+
}
65+
return Arrays.copyOf(res, cnt);
66+
}
67+
68+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/寻找数组的中心索引.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -37,8 +37,8 @@
3737
public class 寻找数组的中心索引 {
3838

3939
public static void main(String[] args) {
40-
Assertions.assertEquals(3, 寻找数组的中心索引.pivotIndex(new int[] { 1, 7, 3, 6, 5, 6 }));
41-
Assertions.assertEquals(-1, 寻找数组的中心索引.pivotIndex(new int[] { 1, 2, 3 }));
40+
Assertions.assertEquals(3, pivotIndex(new int[] { 1, 7, 3, 6, 5, 6 }));
41+
Assertions.assertEquals(-1, pivotIndex(new int[] { 1, 2, 3 }));
4242
}
4343

4444
public static int pivotIndex(int[] nums) {

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/搜索插入位置.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package io.github.dunwu.algorithm.array;
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/search-insert-position/">搜索插入位置</a>
8+
* @since 2020-07-29
9+
*/
10+
public class 搜索插入位置 {
11+
12+
public static void main(String[] args) {
13+
Assertions.assertEquals(0, searchInsert(new int[] { 1 }, 1));
14+
Assertions.assertEquals(2, searchInsert(new int[] { 1, 3, 5, 6 }, 5));
15+
Assertions.assertEquals(1, searchInsert(new int[] { 1, 3, 5, 6 }, 2));
16+
Assertions.assertEquals(4, searchInsert(new int[] { 1, 3, 5, 6 }, 7));
17+
Assertions.assertEquals(0, searchInsert(new int[] { 1, 3, 5, 6 }, 0));
18+
}
19+
20+
public static int searchInsert(int[] nums, int target) {
21+
if (nums == null || nums.length == 0) return 0;
22+
if (nums[0] >= target) return 0;
23+
if (nums[nums.length - 1] < target) return nums.length;
24+
for (int i = 1; i < nums.length; i++) {
25+
if (nums[i] >= target) {
26+
return i;
27+
}
28+
}
29+
return nums.length;
30+
}
31+
32+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/ListNode.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,26 @@
11
package io.github.dunwu.algorithm.list;
22

3+
import java.util.Objects;
4+
35
public final class ListNode {
46

57
int val;
68
ListNode next;
79

810
ListNode(int val) { this.val = val; }
911

12+
@Override
13+
public boolean equals(Object o) {
14+
if (this == o) return true;
15+
if (!(o instanceof ListNode)) return false;
16+
ListNode listNode = (ListNode) o;
17+
return val == listNode.val &&
18+
Objects.equals(next, listNode.next);
19+
}
20+
21+
@Override
22+
public int hashCode() {
23+
return Objects.hash(val, next);
24+
}
25+
1026
}

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,8 @@ public static ListNode reverseList2(ListNode head) {
4646
return null;
4747
}
4848

49+
ListNode dummy = new ListNode(-1);
50+
dummy.next = head;
4951
ListNode prev = null;
5052
ListNode curr = head;
5153
while (curr != null) {

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/回文链表.java‎

Lines changed: 4 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,8 @@
77

88
/**
99
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
10+
* @see <a href="https://leetcode-cn.com/problems/palindrome-linked-list/">234. 回文链表</a>
11+
* @see <a href="https://leetcode-cn.com/problems/palindrome-linked-list-lcci/submissions/">面试题 02.06. 回文链表</a>
1012
* @since 2020-06-09
1113
*/
1214
public class 回文链表 {
@@ -19,14 +21,6 @@ public static void main(String[] args) {
1921
Assertions.assertFalse(isPalindrome(head));
2022
}
2123

22-
/**
23-
* <code>234. 回文链表</code> 算法实现
24-
* <p>
25-
* 判断当前单链表是否有环
26-
*
27-
* @see <a href="https://leetcode-cn.com/problems/palindrome-linked-list/">234. 回文链表</a>
28-
* @see <a href="https://leetcode-cn.com/problems/palindrome-linked-list-lcci/submissions/">面试题 02.06. 回文链表</a>
29-
*/
3024
public static boolean isPalindrome(ListNode head) {
3125
List<Integer> list = new ArrayList<>();
3226
ListNode node = head;
@@ -35,13 +29,11 @@ public static boolean isPalindrome(ListNode head) {
3529
node = node.next;
3630
}
3731

38-
int i = 0, j = list.size() - 1;
39-
while (i <= j) {
32+
// int i = 0, j = list.size() - 1;
33+
for (int i = 0, j = list.size() - 1; i < j; i++, j--) {
4034
if (!list.get(i).equals(list.get(j))) {
4135
return false;
4236
}
43-
i++;
44-
j--;
4537
}
4638
return true;
4739
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/奇偶链表.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.list;
2+
3+
import java.util.Arrays;
4+
import java.util.List;
5+
6+
/**
7+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
8+
* @since 2020-07-08
9+
*/
10+
public class 奇偶链表 {
11+
12+
public static void main(String[] args) {
13+
ListNode head = ListUtil.buildList(1, 2, 3, 4, 5);
14+
List<Integer> list = ListUtil.toList(oddEvenList(head));
15+
System.out.println(list);
16+
// Assertions.assertFalse();
17+
}
18+
19+
public static ListNode oddEvenList(ListNode head) {
20+
if (head == null || head.next == null) return head;
21+
22+
ListNode odd = head, even = head.next, evenHead = even;
23+
24+
while (even != null && even.next != null) {
25+
odd.next = even.next;
26+
odd = odd.next;
27+
even.next = odd.next;
28+
even = even.next;
29+
}
30+
odd.next = evenHead;
31+
return head;
32+
}
33+
34+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/环形链表.java‎

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44

55
/**
66
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/linked-list-cycle/">141. 环形链表</a>
78
* @since 2020-06-09
89
*/
910
public class 环形链表 {
@@ -19,13 +20,6 @@ public static void main(String[] args) {
1920
Assertions.assertTrue(hasCycle(head));
2021
}
2122

22-
/**
23-
* <code>141. 环形链表</code> 算法实现
24-
* <p>
25-
* 判断当前单链表是否有环
26-
*
27-
* @see <a href="https://leetcode-cn.com/problems/linked-list-cycle/">141. 环形链表</a>
28-
*/
2923
public static boolean hasCycle(ListNode head) {
3024
if (head == null || head.next == null) {
3125
return false;

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/环形链表II.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package io.github.dunwu.algorithm.list;
2+
3+
/**
4+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
5+
* @since 2020-07-08
6+
*/
7+
public class 环形链表II {
8+
9+
public static ListNode detectCycle(ListNode head) {
10+
ListNode slow = head;
11+
ListNode fast = head;
12+
while (true) {
13+
if (fast == null || fast.next == null) {
14+
return null;
15+
}
16+
slow = slow.next;
17+
fast = fast.next.next;
18+
if (slow == fast) break;
19+
}
20+
21+
fast = head;
22+
while (slow != fast) {
23+
slow = slow.next;
24+
fast = fast.next;
25+
}
26+
return fast;
27+
}
28+
29+
}

0 commit comments

Comments
 (0)