Skip to content

Commit 69877f9

Browse files
chefyuanchefyuan
committed
Merge branch 'main' of https://github.com/chefyuan/algorithm-base into main
2 parents 1a0aa4c + 5bae992 commit 69877f9

9 files changed

+272
-2
lines changed

‎animation-simulation/前缀和/leetcode1248寻找优美子数组.md

Lines changed: 58 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,8 @@
4343

4444
我们来解析一下哈希表，key 代表的是含有 1 个奇数的前缀区间，value 代表这种子区间的个数，含有两个，也就是nums[0],nums[0,1].后面含义相同，那我们下面直接看代码吧，一下就能读懂。
4545

46+
Java Code:
47+
4648
```java
4749
class Solution {
4850
public int numberOfSubarrays(int[] nums, int k) {
@@ -70,8 +72,40 @@ class Solution {
7072
}
7173
```
7274

75+
C++ Code:
76+
77+
```cpp
78+
class Solution {
79+
public:
80+
int numberOfSubarrays(vector<int>& nums, int k) {
81+
if (nums.size() == 0) {
82+
return 0;
83+
}
84+
map <int, int> m;
85+
//统计奇数个数，相当于我们的 presum
86+
int oddnum = 0;
87+
int count = 0;
88+
m.insert({0,1});
89+
for (int & x : nums) {
90+
// 统计奇数个数
91+
oddnum += x & 1;
92+
// 发现存在，则 count增加
93+
if (m.find(oddnum - k) != m.end()) {
94+
count += m[oddnum - k];
95+
}
96+
//存入
97+
if(m.find(oddnum) != m.end()) m[oddnum]++;
98+
else m[oddnum] = 1;
99+
}
100+
return count;
101+
}
102+
};
103+
```
104+
73105
但是也有一点不同，就是我们是统计奇数的个数，数组中的奇数个数肯定不会超过原数组的长度，所以这个题目中我们可以用数组来模拟 HashMap ，用数组的索引来模拟 HashMap 的 key，用值来模拟哈希表的 value。下面我们直接看代码吧。
74106
107+
Java Code:
108+
75109
```java
76110
class Solution {
77111
public int numberOfSubarrays(int[] nums, int k) {
@@ -93,4 +127,27 @@ class Solution {
93127
}
94128
```
95129

96-
###
130+
C++ Code:
131+
132+
```cpp
133+
class Solution {
134+
public:
135+
int numberOfSubarrays(vector<int>& nums, int k) {
136+
int len = nums.size();
137+
vector <int> map(len + 1, 0);
138+
map[0] = 1;
139+
int oddnum = 0;
140+
int count = 0;
141+
for (int i = 0; i < len; ++i) {
142+
//如果是奇数则加一，偶数加0，相当于没加
143+
oddnum += nums[i] & 1;
144+
if (oddnum - k >= 0) {
145+
count += map[oddnum-k];
146+
}
147+
map[oddnum]++;
148+
}
149+
return count;
150+
}
151+
};
152+
```
153+

‎animation-simulation/前缀和/leetcode523连续的子数组和.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,8 @@
4646

4747
**题目代码**
4848

49+
Java Code:
50+
4951
```java
5052
class Solution {
5153
public boolean checkSubarraySum(int[] nums, int k) {
@@ -71,5 +73,31 @@ class Solution {
7173
}
7274
```
7375

76+
C++ Code:
7477

78+
```cpp
79+
class Solution {
80+
public:
81+
bool checkSubarraySum(vector<int>& nums, int k) {
82+
map <int, int> m;
83+
//细节2
84+
m.insert({0,-1});
85+
int presum = 0;
86+
for (int i = 0; i < nums.size(); ++i) {
87+
presum += nums[i];
88+
//细节1，防止 k 为 0 的情况
89+
int key = k == 0 ? presum : presum % k;
90+
if (m.find(key) != m.end()) {
91+
if (i - m[key] >= 2) {
92+
return true;
93+
}
94+
//因为我们需要保存最小索引，当已经存在时则不用再次存入，不然会更新索引值
95+
continue;
96+
}
97+
m.insert({key, i});
98+
}
99+
return false;
100+
}
101+
};
102+
```
75103

‎animation-simulation/前缀和/leetcode560和为K的子数组.md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,8 @@ class Solution {
122122

123123
**题目代码**
124124

125+
Java Code：
126+
125127
```java
126128
class Solution {
127129
public int subarraySum(int[] nums, int k) {
@@ -150,3 +152,34 @@ class Solution {
150152
}
151153
```
152154

155+
C++ Code：
156+
157+
```cpp
158+
public:
159+
int subarraySum(vector<int>& nums, int k) {
160+
if (nums.size() == 0) {
161+
return 0;
162+
}
163+
map <int, int> m;
164+
//细节，这里需要预存前缀和为 0 的情况，会漏掉前几位就满足的情况
165+
//例如输入[1,1,0]，k = 2 如果没有这行代码，则会返回0,漏掉了1+1=2，和1+1+0=2的情况
166+
//输入：[3,1,1,0] k = 2时则不会漏掉
167+
//因为presum[3] - presum[0]表示前面 3 位的和，所以需要m.insert({0,1}),垫下底
168+
m.insert({0, 1});
169+
int count = 0;
170+
int presum = 0;
171+
for (int x : nums) {
172+
presum += x;
173+
//当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
174+
if (m.find(presum - k) != m.end()) {
175+
count += m[presum - k];//获取presum-k前缀和出现次数
176+
}
177+
//更新
178+
if(m.find(presum) != m.end()) m[presum]++;
179+
else m[presum] = 1;
180+
}
181+
return count;
182+
}
183+
};
184+
```
185+

‎animation-simulation/前缀和/leetcode724寻找数组的中心索引.md

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,6 +61,8 @@
6161

6262
理解了我们前缀和的概念（不知道好像也可以做，这个题太简单了哈哈）。我们可以一下就能把这个题目做出来，先遍历一遍求出数组的和，然后第二次遍历时，直接进行对比左半部分和右半部分是否相同，如果相同则返回 true，不同则继续遍历。
6363

64+
Java Code:
65+
6466
```java
6567
class Solution {
6668
public int pivotIndex(int[] nums) {
@@ -82,4 +84,27 @@ class Solution {
8284
}
8385
```
8486

85-
###
87+
C++ Code:
88+
89+
```cpp
90+
class Solution {
91+
public:
92+
int pivotIndex(vector<int>& nums) {
93+
int presum = 0;
94+
//数组的和
95+
for (int x : nums) {
96+
presum += x;
97+
}
98+
int leftsum = 0;
99+
for (int i = 0; i < nums.size(); ++i) {
100+
//发现相同情况
101+
if (leftsum == presum - nums[i] - leftsum) {
102+
return i;
103+
}
104+
leftsum += nums[i];
105+
}
106+
return -1;
107+
}
108+
};
109+
```
110+

‎animation-simulation/前缀和/leetcode974和可被K整除的子数组.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,8 @@ int key = (presum % K + K) % K;
8787

8888
那么这个题目我们可不可以用数组，代替 map 呢？当然也是可以的，因为此时我们的哈希表存的是余数，余数最大也只不过是 K-1所以我们可以用固定长度 K 的数组来模拟哈希表。
8989

90+
Java Code:
91+
9092
```java
9193
class Solution {
9294
public int subarraysDivByK(int[] A, int K) {
@@ -107,3 +109,26 @@ class Solution {
107109
}
108110
```
109111

112+
C++ Code:
113+
114+
```cpp
115+
class Solution {
116+
public:
117+
int subarraysDivByK(vector<int>& A, int K) {
118+
vector <int> map (K, 0);
119+
int len = A.size();
120+
int count = 0;
121+
int presum = 0;
122+
map[0] = 1;
123+
for (int i = 0; i < len; ++i) {
124+
presum += A[i];
125+
//求key
126+
int key = (presum % K + K) % K;
127+
//count添加次数，并将当前的map[key]++;
128+
count += (map[key]++);
129+
}
130+
return count;
131+
}
132+
};
133+
```
134+

‎animation-simulation/栈和队列/225.用队列实现栈.md

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818

1919
下面我们来看一下题目代码，也是很容易理解。
2020

21+
Java Code:
2122
```java
2223
class MyStack {
2324
//初始化队列
@@ -55,3 +56,34 @@ class MyStack {
5556

5657
```
5758

59+
JS Code:
60+
```javascript
61+
var MyStack = function() {
62+
this.queue = [];
63+
};
64+
65+
MyStack.prototype.push = function(x) {
66+
this.queue.push(x);
67+
if (this.queue.length > 1) {
68+
let i = this.queue.length - 1;
69+
while (i) {
70+
this.queue.push(this.queue.shift());
71+
i--;
72+
}
73+
}
74+
};
75+
76+
MyStack.prototype.pop = function() {
77+
return this.queue.shift();
78+
};
79+
80+
MyStack.prototype.top = function() {
81+
return this.empty() ? null : this.queue[0];
82+
83+
};
84+
85+
MyStack.prototype.empty = function() {
86+
return !this.queue.length;
87+
};
88+
```
89+

‎animation-simulation/栈和队列/剑指Offer09用两个栈实现队列.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,7 @@ class CQueue {
5858

5959
大家可以点击该链接[剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)去实现一下，下面我们看代码。
6060

61+
Java Code:
6162
```java
6263
class CQueue {
6364
//初始化两个栈
@@ -89,3 +90,24 @@ class CQueue {
8990
}
9091
```
9192

93+
JS Code:
94+
```javascript
95+
var CQueue = function() {
96+
this.stack1 = [];
97+
this.stack2 = [];
98+
};
99+
100+
CQueue.prototype.appendTail = function(value) {
101+
this.stack1.push(value);
102+
};
103+
104+
CQueue.prototype.deleteHead = function() {
105+
if (!this.stack2.length) {
106+
while(this.stack1.length) {
107+
this.stack2.push(this.stack1.pop());
108+
}
109+
}
110+
return this.stack2.pop() || -1;
111+
};
112+
```
113+

‎animation-simulation/链表篇/leetcode141环形链表.md

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@
3838

3939
**题目代码**
4040

41+
Java Code:
4142
```java
4243
public class Solution {
4344
public boolean hasCycle(ListNode head) {
@@ -56,3 +57,18 @@ public class Solution {
5657
}
5758
```
5859

60+
JS Code:
61+
```javascript
62+
var hasCycle = function(head) {
63+
let fast = head;
64+
let slow = head;
65+
while (fast && fast.next) {
66+
fast = fast.next.next;
67+
slow = slow.next;
68+
if (fast === slow) {
69+
return true;
70+
}
71+
}
72+
return false;
73+
};
74+
```

‎animation-simulation/链表篇/leetcode206反转链表.md

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,7 @@ low = temp 即可。然后重复执行上诉操作直至最后，这样则完成
3333

3434
我会对每个关键点进行注释，大家可以参考动图理解。
3535

36+
Java Code:
3637
```java
3738
class Solution {
3839
public ListNode reverseList(ListNode head) {
@@ -62,9 +63,27 @@ class Solution {
6263

6364
}
6465
```
66+
JS Code:
67+
```javascript
68+
var reverseList = function(head) {
69+
if(!head || !head.next) {
70+
return head;
71+
}
72+
let low = null;
73+
let pro = head;
74+
while (pro) {
75+
let temp = pro;
76+
pro = pro.next;
77+
temp.next = low;
78+
low = temp;
79+
}
80+
return low;
81+
};
82+
```
6583

6684
上面的迭代写法是不是搞懂啦，现在还有一种递归写法，不是特别容易理解，刚开始刷题的同学，可以只看迭代解法。
6785

86+
Java Code:
6887
```java
6988
class Solution {
7089
public ListNode reverseList(ListNode head) {
@@ -86,3 +105,16 @@ class Solution {
86105

87106
```
88107

108+
JS Code:
109+
```javascript
110+
var reverseList = function(head) {
111+
if (!head || !head.next) {
112+
return head;
113+
}
114+
let pro = reverseList(head.next);
115+
head.next.next = head;
116+
head.next = null;
117+
return pro;
118+
};
119+
```
120+

0 commit comments

Comments
 (0)