Skip to content

Commit 85cb1aa

Browse files
awangdevawangdev
committed
easy clean up
1 parent a0fa9c2 commit 85cb1aa

42 files changed

Lines changed: 4554 additions & 2960 deletions

Some content is hidden

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

‎Java/Fibonacci.java‎

Lines changed: 26 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,15 @@
11
E
2+
1525416805
3+
tags: Math, DP, Memoization
24

3-
方法1: DP array.
5+
#### Memoization
6+
- fib[n] = fibonacci(n - 1) + fibonacci(n - 2);
47

5-
方法1.1: 滚动数组, 简化DP。
8+
#### DP array.
9+
- 滚动数组, 简化DP
610

7-
方法2: recursively calculate fib(n - 1) + fib(n - 2). 公式没问题, 但是时间太长, timeout.
11+
#### recursively calculate
12+
- recursively calculate fib(n - 1) + fib(n - 2). 公式没问题, 但是时间太长, timeout.
813

914

1015
```
@@ -35,6 +40,24 @@
3540
3641
3742
*/
43+
44+
// Memoization
45+
class Solution {
46+
int[] fib = null;
47+
public int fibonacci(int n) {
48+
if (fib == null) {
49+
fib = new int[n + 1];
50+
}
51+
if (n <= 2) {
52+
return n - 1;
53+
}
54+
if (fib[n] != 0) {
55+
return fib[n];
56+
}
57+
return fib[n] = fibonacci(n - 1) + fibonacci(n - 2);
58+
}
59+
}
60+
3861
/*
3962
Recap 3.28.2016.
4063
Rolling array, instead of initiating array.

‎Java/Identical Binary Tree.java‎

Lines changed: 0 additions & 60 deletions
This file was deleted.

‎Java/Implement Stack by Two Queues.java‎

Lines changed: 0 additions & 82 deletions
This file was deleted.

‎Java/Implement Stack using Queues.java‎

Lines changed: 66 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,24 @@
11
E
2+
1525667621
3+
tags: Stack, Design
24

3-
两个Queue,交互倒水
4-
用一个Temp做swap
5+
如题.
56

6-
做法1:
7-
逻辑在top()/pop()里, 每次换水，查看末尾项.
7+
#### Queue, 倒水
8+
- 两个Queue,交互倒水
9+
- 用一个Temp做swap
10+
11+
##### 做法1
12+
- 逻辑在push里面:
13+
- 1. x 放q2。
14+
- 2. q1全部offer/append到q2.
15+
- 3. 用一个Temp做swap q1, q2.
16+
- q1的头，就一直是最后加进去的值.
17+
18+
19+
##### 做法2
20+
- 逻辑在top()/pop()里, 每次换水，查看末尾项.
821

9-
做法2:
10-
逻辑在push里面:
11-
1. x 放q2。
12-
2. q1全部offer/append到q2.
13-
3. 用一个Temp做swap q1, q2.
14-
q1的头，就一直是最后加进去的值.
1522

1623
```
1724
/*
@@ -22,16 +29,61 @@
2229
pop() -- Removes the element on top of the stack.
2330
top() -- Get the top element.
2431
empty() -- Return whether the stack is empty.
32+
2533
Notes:
26-
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
27-
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
28-
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
34+
You must use only standard operations of a queue --
35+
which means only push to back, peek/pop from front, size, and is empty operations are valid.
36+
37+
Depending on your language, queue may not be supported natively.
38+
You may simulate a queue by using a list or deque (double-ended queue),
39+
as long as you use only standard operations of a queue.
40+
41+
You may assume that all operations are valid
42+
(for example, no pop or top operations will be called on an empty stack).
2943
Credits:
3044
Special thanks to @jianchao.li.fighter for adding this problem and all test cases.
3145
*/
46+
47+
class MyStack {
48+
Queue<Integer> queue;
49+
Queue<Integer> tempQueue;
50+
/** Initialize your data structure here. */
51+
public MyStack() {
52+
queue = new LinkedList<>();
53+
tempQueue = new LinkedList<>();
54+
}
55+
56+
/** Push element x onto stack. */
57+
public void push(int x) {
58+
tempQueue = queue;
59+
queue = new LinkedList<>();
60+
queue.offer(x);
61+
while (!tempQueue.isEmpty()) {
62+
queue.offer(tempQueue.poll());
63+
}
64+
}
65+
66+
/** Removes the element on top of the stack and returns that element. */
67+
public int pop() {
68+
return queue.poll();
69+
}
70+
71+
/** Get the top element. */
72+
public int top() {
73+
return queue.peek();
74+
}
75+
76+
/** Returns whether the stack is empty. */
77+
public boolean empty() {
78+
return queue.isEmpty();
79+
}
80+
}
81+
82+
3283
/*
3384
Thoughts:
34-
1. When top()/pop() on the queue, we need to consume all the items on that queue first, then return the last item.
85+
1. When top()/pop() on the queue, we need to consume all the items on that queue first,
86+
then return the last item.
3587
2. Need to save the consumed items back to the queue.
3688
*/
3789
class MyStack {

‎Java/Implement Stack.java‎

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,18 @@
11
E
2+
1525667761
3+
tags: Stack
24

3-
stack 后入先出.
4-
Data Structure: ArrayList
5-
return/remove ArrayList的末尾项。
5+
随便用一个data structure, implement stack.
6+
7+
#### Stack, 先入, 后出
8+
- ArrayList: return/remove ArrayList的末尾项。
9+
- 2 Queues
610

711
```
812
/*
9-
Implement Stack
13+
LintCode
14+
15+
Implement Stack
1016
1117
Implement a stack. You can use any data structure inside a stack except stack itself to implement it.
1218

‎Java/Intersection of Two Linked Lists.java‎

Lines changed: 53 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,14 @@
11
E
2+
tags: Linked List
3+
1525664839
24

3-
长短list，找重合点。
4-
长度不同的话，切掉长的list那个的extra length。 那么起点一样后，重合点就会同时到达。
5+
给两个 linked list, 问从哪个node开始, 两个 linked list 开始有重复?
56

7+
#### Basics
8+
- 长短list，找重合点
9+
- 长度不同的话，切掉长的list那个的extra length
10+
- 那么起点一样后，重合点就会同时到达
11+
- Time O(n) * 2, constant space
612

713
```
814
/*
@@ -28,6 +34,51 @@ Your code should preferably run in O(n) time and use only O(1) memory.
2834
Tags Expand
2935
Linked List
3036
*/
37+
// Count list length for headA, headB
38+
// Shift the longer list and compare
39+
public class Solution {
40+
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
41+
if (headA == null || headB == null) {
42+
return null;
43+
}
44+
int countA = calcListLength(headA);
45+
int countB = calcListLength(headB);
46+
int diff = Math.abs(countA - countB);
47+
48+
if (countA > countB) {
49+
headA = shiftNode(headA, diff);
50+
} else {
51+
headB = shiftNode(headB, diff);
52+
}
53+
54+
while (headA != null && headB != null) {
55+
if (headA == headB) {
56+
return headA;
57+
}
58+
headA = headA.next;
59+
headB = headB.next;
60+
}
61+
62+
return null;
63+
}
64+
65+
private int calcListLength(ListNode node) {
66+
int count = 0;
67+
while (node != null) {
68+
count++;
69+
node = node.next;
70+
}
71+
return count;
72+
}
73+
74+
private ListNode shiftNode(ListNode node, int shift) {
75+
while (shift != 0) {
76+
shift--;
77+
node = node.next;
78+
}
79+
return node;
80+
}
81+
}
3182

3283
/*
3384
Thoughts:

0 commit comments

Comments
 (0)