Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit81f74d8

Browse files
2 parents3957e95 +7625216 commit81f74d8

9 files changed

+224
-9
lines changed

‎problems/0047.全排列II.md

Lines changed: 39 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -296,7 +296,45 @@ var permuteUnique = function (nums) {
296296
};
297297

298298
```
299-
299+
Go：
300+
回溯+本层去重+下层去重
301+
```golang
302+
funcpermuteUnique(nums []int) [][]int {
303+
varsubRes []int
304+
varres [][]int
305+
sort.Ints(nums)
306+
used:=make([]bool,len(nums))
307+
backTring(nums,subRes,&res,used)
308+
return res
309+
}
310+
funcbackTring(nums,subRes []int,res *[][]int,used []bool){
311+
iflen(subRes)==len(nums){
312+
tmp:=make([]int,len(nums))
313+
copy(tmp,subRes)
314+
*res=append(*res,tmp)
315+
return
316+
}
317+
// used[i - 1] == true，说明同一树支candidates[i - 1]使用过
318+
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
319+
fori:=0;i<len(nums);i++{
320+
if i>0&&nums[i]==nums[i-1]&&used[i-1]==false{//当本层元素相同且前一个被使用过，则继续向后找（本层去重）
321+
continue
322+
}
323+
//到达这里有两种情况：1.该层前后元素不同；2.该层前后元素相同但该层没有使用过
324+
//所以只能对该层没有被使用过的抽取
325+
if used[i]==false{
326+
//首先将该元素置为使用过（即同一树枝使用过），下一层的元素就不能选择重复使用过的元素（下层去重）
327+
used[i]=true
328+
subRes=append(subRes,nums[i])
329+
backTring(nums,subRes,res,used)
330+
//回溯
331+
//回溯回来，将该元素置为false，表示该元素在该层使用过
332+
used[i]=false
333+
subRes=subRes[:len(subRes)-1]
334+
}
335+
}
336+
}
337+
```
300338

301339

302340

‎problems/0112.路径总和.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,8 +13,8 @@
1313

1414
接下来我通过详细讲解如下两道题，来回答这个问题：
1515

16-
*112.路径总和
17-
*113.路径总和II
16+
* 112.路径总和
17+
* 113.路径总和II
1818

1919
##112. 路径总和
2020

‎problems/0122.买卖股票的最佳时机II（动态规划）.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -201,6 +201,29 @@ class Solution:
201201

202202
Go：
203203

204+
Javascript：
205+
```javascript
206+
constmaxProfit= (prices)=> {
207+
let dp=Array.from(Array(prices.length), ()=>Array(2).fill(0));
208+
// dp[i][0] 表示第i天持有股票所得现金。
209+
// dp[i][1] 表示第i天不持有股票所得最多现金
210+
dp[0][0]=0- prices[0];
211+
dp[0][1]=0;
212+
for(let i=1; i<prices.length; i++) {
213+
// 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
214+
// 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
215+
// 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
216+
dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]- prices[i]);
217+
218+
// 在来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来
219+
// 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
220+
// 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]
221+
dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]+ prices[i]);
222+
}
223+
224+
return dp[prices.length-1][0];
225+
};
226+
```
204227

205228

206229

‎problems/0188.买卖股票的最佳时机IV.md

Lines changed: 40 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -224,7 +224,7 @@ class Solution {
224224

225225

226226
Python：
227-
227+
版本一
228228
```python
229229
classSolution:
230230
defmaxProfit(self,k:int,prices: List[int]) ->int:
@@ -239,11 +239,49 @@ class Solution:
239239
dp[i][j+2]=max(dp[i-1][j+2], dp[i-1][j+1]+ prices[i])
240240
return dp[-1][2*k]
241241
```
242-
242+
版本二
243+
```python3
244+
classSolution:
245+
defmaxProfit(self,k:int,prices: List[int]) ->int:
246+
iflen(prices)==0:return0
247+
dp= [0]* (2*k+1)
248+
for iinrange(1,2*k,2):
249+
dp[i]=-prices[0]
250+
for iinrange(1,len(prices)):
251+
for jinrange(1,2*k+1):
252+
if j%2:
253+
dp[j]=max(dp[j],dp[j-1]-prices[i])
254+
else:
255+
dp[j]=max(dp[j],dp[j-1]+prices[i])
256+
return dp[2*k]
257+
```
243258
Go：
244259

245260

261+
Javascript：
262+
263+
```javascript
264+
constmaxProfit= (k,prices)=> {
265+
if (prices==null||prices.length<2|| k==0) {
266+
return0;
267+
}
268+
269+
let dp=Array.from(Array(prices.length), ()=>Array(2*k+1).fill(0));
246270

271+
for (let j=1; j<2* k; j+=2) {
272+
dp[0][j]=0- prices[0];
273+
}
274+
275+
for(let i=1; i<prices.length; i++) {
276+
for (let j=0; j<2* k; j+=2) {
277+
dp[i][j+1]=Math.max(dp[i-1][j+1], dp[i-1][j]- prices[i]);
278+
dp[i][j+2]=Math.max(dp[i-1][j+2], dp[i-1][j+1]+ prices[i]);
279+
}
280+
}
281+
282+
return dp[prices.length-1][2* k];
283+
};
284+
```
247285

248286
-----------------------
249287
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)

‎problems/0309.最佳买卖股票时机含冷冻期.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -207,7 +207,29 @@ class Solution:
207207

208208
Go：
209209

210+
#"diff-d1e1c7e4fc58f53970a9f6b4e35b09b459c925cf7db5c143be2c2a8f33580298-209-211-0" data-selected="false" role="gridcell" tabindex="-1" valign="top">
211+
212+
```javascript
213+
constmaxProfit= (prices)=> {
214+
if(prices.length<2) {
215+
return0
216+
}elseif(prices.length<3) {
217+
returnMath.max(0, prices[1]- prices[0]);
218+
}
219+
220+
let dp=Array.from(Array(prices.length), ()=>Array(4).fill(0));
221+
dp[0][0]=0- prices[0];
222+
223+
for(i=1; i<prices.length; i++) {
224+
dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][1], dp[i-1][3])- prices[i]);
225+
dp[i][1]=Math.max(dp[i-1][1], dp[i-1][3]);
226+
dp[i][2]= dp[i-1][0]+ prices[i];
227+
dp[i][3]= dp[i-1][2];
228+
}
210229

230+
returnMath.max(dp[prices.length-1][1], dp[prices.length-1][2], dp[prices.length-1][3]);
231+
};
232+
```
211233

212234

213235
-----------------------

‎problems/0501.二叉搜索树中的众数.md

Lines changed: 61 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -435,7 +435,7 @@ Python：
435435
# self.val = val
436436
# self.left = left
437437
# self.right = right
438-
//递归法
438+
#递归法
439439
classSolution:
440440
deffindMode(self,root: TreeNode) -> List[int]:
441441
ifnot root:return
@@ -460,6 +460,66 @@ class Solution:
460460
return
461461
findNumber(root)
462462
returnself.res
463+
464+
465+
# 迭代法-中序遍历-使用额外空间map的方法：
466+
classSolution:
467+
deffindMode(self,root: TreeNode) -> List[int]:
468+
stack= []
469+
cur= root
470+
pre=None
471+
dist= {}
472+
while curor stack:
473+
if cur:# 指针来访问节点，访问到最底层
474+
stack.append(cur)
475+
cur= cur.left
476+
else:# 逐一处理节点
477+
cur= stack.pop()
478+
if cur.valin dist:
479+
dist[cur.val]+=1
480+
else:
481+
dist[cur.val]=1
482+
pre= cur
483+
cur= cur.right
484+
485+
# 找出字典中最大的key
486+
res= []
487+
for key, valuein dist.items():
488+
if (value==max(dist.values())):
489+
res.append(key)
490+
return res
491+
492+
# 迭代法-中序遍历-不使用额外空间，利用二叉搜索树特性：
493+
classSolution:
494+
deffindMode(self,root: TreeNode) -> List[int]:
495+
stack= []
496+
cur= root
497+
pre=None
498+
maxCount, count=0,0
499+
res= []
500+
while curor stack:
501+
if cur:# 指针来访问节点，访问到最底层
502+
stack.append(cur)
503+
cur= cur.left
504+
else:# 逐一处理节点
505+
cur= stack.pop()
506+
if pre==None:# 第一个节点
507+
count=1
508+
elif pre.val== cur.val:# 与前一个节点数值相同
509+
count+=1
510+
else:
511+
count=1
512+
if count== maxCount:
513+
res.append(cur.val)
514+
if count> maxCount:
515+
maxCount= count
516+
res.clear()
517+
res.append(cur.val)
518+
519+
pre= cur
520+
cur= cur.right
521+
return res
522+
463523
```
464524
Go：
465525
暴力法（非BSL）

‎problems/0714.买卖股票的最佳时机含手续费（动态规划）.md

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -153,7 +153,18 @@ class Solution:
153153

154154
Go：
155155

156-
156+
Javascript：
157+
```javascript
158+
constmaxProfit= (prices,fee)=> {
159+
let dp=Array.from(Array(prices.length), ()=>Array(2).fill(0));
160+
dp[0][0]=0- prices[0];
161+
for (let i=1; i<prices.length; i++) {
162+
dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]- prices[i]);
163+
dp[i][1]=Math.max(dp[i-1][0]+ prices[i]- fee, dp[i-1][1]);
164+
}
165+
returnMath.max(dp[prices.length-1][0], dp[prices.length-1][1]);
166+
}
167+
```
157168

158169

159170
-----------------------

‎problems/0718.最长重复子数组.md

Lines changed: 23 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@ B: [3,2,1,4,7]
2020
输出：3
2121
解释：
2222
长度最长的公共子数组是[3, 2, 1] 。
23-
 
23+
2424
提示：
2525

2626
* 1 <= len(A), len(B) <= 1000
@@ -155,6 +155,7 @@ public:
155155

156156
Java：
157157
```java
158+
// 版本一
158159
classSolution {
159160
publicintfindLength(int[]nums1,int[]nums2) {
160161
int result=0;
@@ -164,14 +165,34 @@ class Solution {
164165
for (int j=1; j< nums2.length+1; j++) {
165166
if (nums1[i-1]== nums2[j-1]) {
166167
dp[i][j]= dp[i-1][j-1]+1;
167-
max=Math.max(max, dp[i][j]);
168+
result=Math.max(result, dp[i][j]);
168169
}
169170
}
170171
}
171172

172173
return result;
173174
}
174175
}
176+
177+
// 版本二: 滚动数组
178+
classSolution {
179+
publicintfindLength(int[]nums1,int[]nums2) {
180+
int[] dp=newint[nums2.length+1];
181+
int result=0;
182+
183+
for (int i=1; i<= nums1.length; i++) {
184+
for (int j= nums2.length; j>0; j--) {
185+
if (nums1[i-1]== nums2[j-1]) {
186+
dp[j]= dp[j-1]+1;
187+
}else {
188+
dp[j]=0;
189+
}
190+
result=Math.max(result, dp[j]);
191+
}
192+
}
193+
return result;
194+
}
195+
}
175196
```
176197

177198
Python：

‎problems/1035.不相交的线.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@
88

99
##1035.不相交的线
1010

11+
题目链接:https://leetcode-cn.com/problems/uncrossed-lines/
12+
1113
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
1214

1315
现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp