Skip to content

Commit df8f2c5

Browse files
DreamCatsDreamCats
committed
📝 update alg
1 parent c10b1c8 commit df8f2c5

9 files changed

Lines changed: 598 additions & 1 deletion

‎Java/.DS_Store‎

0 Bytes
Binary file not shown.

‎Java/alg/.DS_Store‎

0 Bytes
Binary file not shown.

‎Java/alg/README.md‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,4 +33,10 @@
3333
- [121.买卖股票的最佳时机](lc/121.买卖股票的最佳时机.md)
3434
- [122.买卖股票的最佳时机2](lc/122.买卖股票的最佳时机2.md)
3535
- [125.验证回文串](lc/125.验证回文串.md)
36-
- [136.只出现一次的数字](lc/136.只出现一次的数字.md)
36+
- [136.只出现一次的数字](lc/136.只出现一次的数字.md)
37+
- [141.环形链表](lc/141.环形链表.md)
38+
- [155.最小栈](lc/155.最小栈.md)
39+
- [160.相交链表](lc/160.相交链表.md)
40+
- [167.两数之和2-输入有序数组](lc/167.两数之和2-输入有序数组.md)
41+
- [172.阶乘后的零](lc/172.阶乘后的零.md)
42+
- [191.位1的个数](lc/191.位1的个数.md)

‎Java/alg/lc/141.环形链表.md‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
# 141. 环形链表
2+
3+
[url](https://leetcode-cn.com/problems/linked-list-cycle/)
4+
5+
6+
## 题目
7+
8+
给定一个链表，判断链表中是否有环。
9+
10+
如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 -1，则在该链表中没有环。注意：`pos` 不作为参数进行传递，仅仅是为了标识链表的实际情况。
11+
12+
如果链表中存在环，则返回 `true` 。 否则，返回 `false` 。
13+
14+
你能用 O(1)（即，常量）内存解决此问题吗？
15+
16+
![circularlinkedlist-lc-q9kmLK](https://cdn.jsdelivr.net/gh/DreamCats/imgs@main/uPic/circularlinkedlist-lc-q9kmLK.png)
17+
```
18+
输入：head = [3,2,0,-4], pos = 1
19+
输出：true
20+
解释：链表中有一个环，其尾部连接到第二个节点。
21+
```
22+
23+
![circularlinkedlist_test2-lc-i5Xwi1](https://cdn.jsdelivr.net/gh/DreamCats/imgs@main/uPic/circularlinkedlist_test2-lc-i5Xwi1.png)
24+
```
25+
输入：head = [1,2], pos = 0
26+
输出：true
27+
解释：链表中有一个环，其尾部连接到第一个节点。
28+
```
29+
30+
## 方法
31+
32+
33+
挺简单的：快慢指针
34+
35+
## code
36+
37+
### js
38+
39+
```js
40+
let hasCycle = head => {
41+
if (head === null) return false;
42+
let l1 = head, l2 = head.next;
43+
while (l2 !== null && l2.next !== null) {
44+
if (l1 === l2)
45+
return true;
46+
l1 = l1.next;
47+
l2 = l2.next.next;
48+
}
49+
return false;
50+
}
51+
```
52+
53+
### go
54+
55+
```go
56+
func hasCycle(head *ListNode) bool {
57+
if head == nil {
58+
return false
59+
}
60+
l1, l2 := head, head.Next
61+
for l2 != nil && l2.Next != nil {
62+
if l1 == l2 {
63+
return true
64+
}
65+
l1 = l1.Next
66+
l2 = l2.Next.Next
67+
}
68+
return false;
69+
}
70+
```
71+
72+
### java
73+
74+
```java
75+
public class Solution {
76+
public boolean hasCycle(ListNode head) {
77+
if (head == null) {
78+
return false;
79+
}
80+
ListNode l1 = head, l2 = head.next;
81+
while (l1 != null && l2 != null && l2.next != null) {
82+
if (l1 == l2) {
83+
return true;
84+
}
85+
l1 = l1.next;
86+
l2 = l2.next.next;
87+
}
88+
return false;
89+
}
90+
}
91+
```
92+

‎Java/alg/lc/155.最小栈.md‎

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
# 155. 最小栈
2+
3+
[url](https://leetcode-cn.com/problems/min-stack/)
4+
5+
6+
## 题目
7+
8+
设计一个支持 `push` `，pop` `，top` 操作，并能在常数时间内检索到最小元素的栈。
9+
10+
`push(x)` —— 将元素 x 推入栈中。
11+
`pop()` —— 删除栈顶的元素。
12+
`top()` —— 获取栈顶元素。
13+
`getMin()` —— 检索栈中的最小元素。
14+
15+
16+
```
17+
输入：
18+
["MinStack","push","push","push","getMin","pop","top","getMin"]
19+
[[],[-2],[0],[-3],[],[],[],[]]
20+
输出：
21+
[null,null,null,null,-3,null,0,-2]
22+
解释：
23+
MinStack minStack = new MinStack();
24+
minStack.push(-2);
25+
minStack.push(0);
26+
minStack.push(-3);
27+
minStack.getMin(); --> 返回 -3.
28+
minStack.pop();
29+
minStack.top(); --> 返回 0.
30+
minStack.getMin(); --> 返回 -2.
31+
```
32+
33+
## 方法
34+
35+
36+
双栈即可
37+
- 数据栈与最小栈
38+
39+
## code
40+
41+
### js
42+
43+
```js
44+
let MinStack = function() {
45+
this.dataStack = [];
46+
this.minStack = [];
47+
this.min = Infinity;
48+
}
49+
MinStack.prototype.push = function(x) {
50+
this.dataStack.push(x);
51+
this.min = Math.min(this.min, x);
52+
this.minStack.push(this.min);
53+
}
54+
MinStack.prototype.pop = function() {
55+
this.dataStack.pop();
56+
this.minStack.pop();
57+
this.min = this.minStack.length === 0 ? Infinity : this.minStack[this.minStack.length - 1];
58+
}
59+
MinStack.prototype.top = function() {
60+
return this.dataStack[this.dataStack.length - 1];
61+
}
62+
MinStack.prototype.getMin = function() {
63+
return this.min;
64+
}
65+
var test = new MinStack();
66+
test.push(2);
67+
test.push(1);
68+
test.push(3);
69+
// test.pop();
70+
console.log(test.getMin());
71+
console.log(test.top());
72+
```
73+
74+
### go
75+
76+
```go
77+
const (
78+
INT_MAX = int(^uint((0)) >> 1)
79+
INT_MIN = ^INT_MAX
80+
)
81+
var min = INT_MAX
82+
var s1 = []int{}
83+
var s2 = []int{}
84+
func push(x int) {
85+
s1 = append(s1, x)
86+
min = Min(min, x)
87+
s2 = append(s2, min)
88+
}
89+
func pop() {
90+
s1 = s1[:len(s1) - 1]
91+
s2 = s2[:len(s2) - 1]
92+
if len(s2) == 0 {
93+
min = INT_MAX
94+
} else {
95+
min = s2[len(s2) - 1]
96+
}
97+
}
98+
func top() int {
99+
return s1[len(s1) - 1]
100+
}
101+
func getMin() int {
102+
return min
103+
}
104+
```
105+
106+
### java
107+
108+
```java
109+
class MinStack {
110+
private Stack<Integer> dataStack;
111+
private Stack<Integer> minStack;
112+
private int min;
113+
/** initialize your data structure here. */
114+
public MinStack() {
115+
dataStack = new Stack<>();
116+
minStack = new Stack<>();
117+
min = Integer.MAX_VALUE;
118+
}
119+
public void push(int x) {
120+
dataStack.push(x);
121+
min = Math.min(min, x);
122+
minStack.push(min);
123+
}
124+
public void pop() {
125+
dataStack.pop();
126+
minStack.pop();
127+
min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
128+
}
129+
public int top() {
130+
return dataStack.peek();
131+
}
132+
public int getMin() {
133+
return min;
134+
}
135+
}
136+
/**
137+
* Your MinStack object will be instantiated and called as such:
138+
* MinStack obj = new MinStack();
139+
* obj.push(x);
140+
* obj.pop();
141+
* int param_3 = obj.top();
142+
* int param_4 = obj.getMin();
143+
*/
144+
```
145+

‎Java/alg/lc/160.相交链表.md‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
# 160. 相交链表
2+
3+
[url](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
4+
5+
6+
## 题目
7+
8+
编写一个程序，找到两个单链表相交的起始节点。
9+
10+
如下面的两个链表：
11+
![160_statement-lc-j1QVOw](https://cdn.jsdelivr.net/gh/DreamCats/imgs@main/uPic/160_statement-lc-j1QVOw.png)
12+
13+
在节点 c1 开始相交。
14+
15+
![160_example_1-lc-bAOm3q](https://cdn.jsdelivr.net/gh/DreamCats/imgs@main/uPic/160_example_1-lc-bAOm3q.png)
16+
17+
```
18+
输入：
19+
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
20+
输出：Reference of the node with value = 8
21+
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
22+
```
23+
![160_example_2-lc-iqzSva](https://cdn.jsdelivr.net/gh/DreamCats/imgs@main/uPic/160_example_2-lc-iqzSva.png)
24+
25+
```
26+
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
27+
输出：Reference of the node with value = 2
28+
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
29+
```
30+
31+
![160_example_3-lc-RNgABI](https://cdn.jsdelivr.net/gh/DreamCats/imgs@main/uPic/160_example_3-lc-RNgABI.png)
32+
33+
```
34+
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
35+
输出：null
36+
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
37+
解释：这两个链表不相交，因此返回 null。
38+
39+
注意：
40+
- 如果两个链表没有交点，返回 `null`.
41+
- 在返回结果后，两个链表仍须保持原有的结构。
42+
- 可假定整个链表结构中没有循环。
43+
- 程序尽量满足 `O(n) `时间复杂度，且仅用 `O(1) `内存。
44+
45+
```
46+
47+
## 方法
48+
49+
双指针
50+
- 分别走A、B两圈，如果相等，则退出循环
51+
52+
## code
53+
54+
### js
55+
56+
```js
57+
let getIntersectionNode = (headA, headB) => {
58+
let l1 = headA, l2 = headB;
59+
while (l1 !== l2) {
60+
l1 = l1 === null ? headB : l1.next;
61+
l2 = l2 === null ? headA: l2.next;
62+
}
63+
return l1;
64+
}
65+
```
66+
67+
### go
68+
69+
```go
70+
func getIntersectionNode(headA, headB *ListNode) *ListNode {
71+
l1, l2 := headA, headB
72+
for l1 != l2 {
73+
if l1 == nil {
74+
l1 = headB
75+
} else {
76+
l1 = l1.Next
77+
}
78+
if l2 == nil {
79+
l2 = headA
80+
} else {
81+
l2 = l2.Next
82+
}
83+
}
84+
return l1
85+
}
86+
```
87+
88+
### java
89+
90+
```java
91+
public class Solution {
92+
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
93+
ListNode l1 = headA, l2 = headB;
94+
while (l1 != l2) {
95+
l1 = l1 == null ? headB : l1.next;
96+
l2 = l2 == null ? headA : l2.next;
97+
}
98+
return l1;
99+
}
100+
}
101+
```
102+

0 commit comments

Comments
 (0)