Skip to content

Commit 6b81cf6

Browse files
dunwudunwu
committed
update codes
1 parent 31d6f02 commit 6b81cf6

File tree

9 files changed

+483
-10
lines changed

9 files changed

+483
-10
lines changed

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

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package io.github.dunwu.ds.array;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @since 2020-01-20
8+
*/
9+
public class ArrayDemo {
10+
11+
public static int maxSubArray(int[] nums) {
12+
int len = nums.length;
13+
14+
int maxSum = nums[0];
15+
for (int i = 1; i < len; i++) {
16+
if (nums[i - 1] > 0) nums[i] += nums[i - 1];
17+
maxSum = Math.max(nums[i], maxSum);
18+
}
19+
return maxSum;
20+
}
21+
22+
public static void main(String[] args) {
23+
int max = maxSubArray(new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 });
24+
System.out.println("max = " + max);
25+
}
26+
27+
}

‎codes/data-structure/src/main/java/io/github/dunwu/ds/list/LeetcodeListDemo.java‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -184,6 +184,94 @@ public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
184184
return resultHead.next;
185185
}
186186

187+
/**
188+
* <code>排序链表</code> 算法实现
189+
* <p>
190+
* 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
191+
* <p>
192+
* 示例 1:
193+
*
194+
* <pre>
195+
* 输入: 4->2->1->3
196+
* 输出: 1->2->3->4
197+
* </pre>
198+
* <p>
199+
* 示例 2:
200+
*
201+
* <pre>
202+
* 输入: -1->5->3->4->0
203+
* 输出: -1->0->3->4->5
204+
* </pre>
205+
*
206+
* @see <a href="https://leetcode-cn.com/explore/featured/card/bytedance/244/linked-list-and-tree/1040/">排序链表</a>
207+
*/
208+
public static ListNode sortList(ListNode head) {
209+
if (head == null) {return head;}
210+
return mergeSort(head);
211+
}
212+
213+
public static ListNode mergeSort(ListNode head) {
214+
//回归条件
215+
if (head.next == null) {
216+
return head;
217+
}
218+
//快指针,考虑到链表为2时的情况，fast比slow早一格
219+
ListNode fast = head.next;
220+
//慢指针
221+
ListNode slow = head;
222+
//快慢指针开跑
223+
while (fast != null && fast.next != null) {
224+
fast = fast.next.next;
225+
slow = slow.next;
226+
}
227+
//找到右子链表头元素，复用fast引用
228+
fast = slow.next;
229+
//将中点后续置空，切割为两个子链表
230+
slow.next = null;
231+
//递归分解左子链表,得到新链表起点
232+
head = mergeSort(head);
233+
//递归分解右子链表,得到新链表起点
234+
fast = mergeSort(fast);
235+
//并归两个子链表
236+
ListNode newHead = merge(head, fast);
237+
return newHead;
238+
}
239+
240+
public static ListNode merge(ListNode left, ListNode right) {
241+
//维护临时序列的头元素
242+
ListNode head;
243+
if (left.val <= right.val) {
244+
head = left;
245+
left = left.next;
246+
} else {
247+
head = right;
248+
right = right.next;
249+
}
250+
//两个子链表均存在剩余元素
251+
ListNode temp = head;
252+
while (left != null && right != null) {
253+
//将较小的元素加入临时序列
254+
if (left.val <= right.val) {
255+
temp.next = left;
256+
left = left.next;
257+
temp = temp.next;
258+
} else {
259+
temp.next = right;
260+
right = right.next;
261+
temp = temp.next;
262+
}
263+
}
264+
//左子序列用完将右子序列余下元素加入临时序列
265+
if (left == null) {
266+
temp.next = right;
267+
}
268+
//右子序列用完将左子序列余下元素加入临时序列
269+
if (right == null) {
270+
temp.next = left;
271+
}
272+
return head;
273+
}
274+
187275
public static List<Integer> getValues(ListNode listNode) {
188276
List<Integer> list = new ArrayList<>();
189277
ListNode item = listNode;

‎codes/data-structure/src/main/java/io/github/dunwu/ds/stack/MinStack.java‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -10,10 +10,10 @@
1010
public class MinStack {
1111

1212
// 数据栈
13-
private Queue<Integer> data;
13+
private LinkedList<Integer> data;
1414

1515
// 辅助栈
16-
private Queue<Integer> helper;
16+
private LinkedList<Integer> helper;
1717

1818
/**
1919
* initialize your data structure here.
@@ -26,19 +26,19 @@ public MinStack() {
2626
// 思路 1：数据栈和辅助栈在任何时候都同步
2727
public void push(int x) {
2828
// 数据栈和辅助栈一定会增加元素
29-
data.add(x);
29+
data.push(x);
3030
if (helper.isEmpty() || helper.peek() >= x) {
31-
helper.add(x);
31+
helper.push(x);
3232
} else {
33-
helper.add(helper.peek());
33+
helper.push(helper.peek());
3434
}
3535
}
3636

3737
public void pop() {
3838
// 两个栈都得 pop
3939
if (!data.isEmpty()) {
40-
helper.poll();
41-
data.poll();
40+
helper.pop();
41+
data.pop();
4242
}
4343
}
4444

‎codes/data-structure/src/main/java/io/github/dunwu/ds/tree/BTreeDemo.java‎

Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
package io.github.dunwu.ds.tree;
2+
3+
import java.util.LinkedList;
4+
import java.util.List;
5+
import java.util.Queue;
6+
import java.util.Stack;
7+
8+
/**
9+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
10+
* @since 2020-01-20
11+
*/
12+
public class BTreeDemo {
13+
14+
/**
15+
* 前序遍历递归方法
16+
*
17+
* @param root {@link TreeNode}
18+
*/
19+
public static void preOrder(TreeNode root) {
20+
TreeNode node = root;
21+
if (node != null) {
22+
System.out.print(node.val + " ");
23+
preOrder(node.left);
24+
preOrder(node.right);
25+
}
26+
}
27+
28+
/**
29+
* 前序遍历非递归方法
30+
*
31+
* @param root {@link TreeNode}
32+
*/
33+
public static void preOrder2(TreeNode root) {
34+
if (root == null) return;
35+
Stack<TreeNode> stack = new Stack<>();
36+
while (!stack.isEmpty() || root != null) {
37+
while (root != null) {
38+
System.out.print(root.val + " ");
39+
stack.push(root);
40+
root = root.left;
41+
}
42+
if (!stack.isEmpty()) {
43+
TreeNode t = stack.pop();
44+
root = t.right;
45+
}
46+
}
47+
}
48+
49+
/**
50+
* 中序遍历递归方法
51+
*
52+
* @param root {@link TreeNode}
53+
*/
54+
public static void inOrder(TreeNode root) {
55+
if (root != null) {
56+
preOrder(root.left);
57+
System.out.print(root.val + " ");
58+
preOrder(root.right);
59+
}
60+
}
61+
62+
/**
63+
* 中序遍历非递归方法
64+
*
65+
* @param root {@link TreeNode}
66+
*/
67+
public static void inOrder2(TreeNode root) {
68+
if (root == null) {
69+
return;
70+
}
71+
72+
Stack<TreeNode> stack = new Stack<>();
73+
while (!stack.isEmpty() || root != null) {
74+
while (root != null) {
75+
stack.push(root);
76+
root = root.left;
77+
}
78+
if (!stack.isEmpty()) {
79+
TreeNode t = stack.pop();
80+
System.out.print(t.val + " ");
81+
root = t.right;
82+
}
83+
}
84+
}
85+
86+
public static void postOrder(TreeNode root) {
87+
if (root != null) {
88+
postOrder(root.left);
89+
postOrder(root.right);
90+
System.out.print(root.val + " ");
91+
}
92+
}
93+
94+
/**
95+
* 中序遍历非递归方法
96+
*
97+
* @param root {@link TreeNode}
98+
*/
99+
public static void postOrder2(TreeNode root) {
100+
if (root == null) {
101+
return;
102+
}
103+
104+
Stack<TreeNode> stack = new Stack<>();
105+
while (!stack.isEmpty() || root != null) {
106+
while (root != null) {
107+
stack.push(root);
108+
root = root.left;
109+
}
110+
if (!stack.isEmpty()) {
111+
TreeNode t = stack.pop();
112+
System.out.print(t.val + " ");
113+
root = t.left;
114+
}
115+
}
116+
}
117+
118+
public static void levelTraverse(TreeNode root) {
119+
if (root == null) {
120+
return;
121+
}
122+
Queue<TreeNode> queue = new LinkedList<>();
123+
queue.add(root);
124+
while (!queue.isEmpty()) {
125+
TreeNode node = queue.poll();
126+
System.out.print(node.val + " ");
127+
if (node.left != null) queue.add(node.left);
128+
if (node.right != null) queue.add(node.right);
129+
}
130+
}
131+
132+
public static void depthOrderTraverse(TreeNode root) {
133+
if (root == null) {
134+
return;
135+
}
136+
LinkedList<TreeNode> stack = new LinkedList<>();
137+
stack.push(root);
138+
while (!stack.isEmpty()) {
139+
TreeNode node = stack.pop();
140+
System.out.print(node.val + " ");
141+
if (node.left != null) stack.push(node.left);
142+
if (node.right != null) stack.push(node.right);
143+
}
144+
}
145+
146+
public static class TreeNode {
147+
148+
int val;
149+
150+
BTreeDemo.TreeNode left;
151+
152+
BTreeDemo.TreeNode right;
153+
154+
public TreeNode(int val) { this.val = val; }
155+
156+
}
157+
158+
}

0 commit comments

Comments
 (0)