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

Commit0597ad9

Browse files
2 parents11feb33 +34dba19 commit0597ad9

15 files changed

+381
-53
lines changed

‎problems/0047.全排列II.md

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
<ahref="https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ"><imgsrc="https://img.shields.io/badge/知识星球-代码随想录-blue"alt=""></a>
66
</p>
77
<palign="center"><strong>欢迎大家<ahref="https://mp.weixin.qq.com/s/tqCxrMEU-ajQumL1i8im9A">参与本项目</a>，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！</strong></p>
8+
89
#排列问题（二）
910

1011
##47.全排列 II
@@ -222,6 +223,43 @@ class Solution:
222223
return res
223224
```
224225

226+
Go：
227+
228+
```go
229+
varres [][]int
230+
funcpermute(nums []int) [][]int {
231+
res = [][]int{}
232+
sort.Ints(nums)
233+
dfs(nums,make([]int,0),make([]bool,len(nums)))
234+
return res
235+
}
236+
237+
funcdfs(nums,path []int,used []bool) {
238+
iflen(path) ==len(nums) {
239+
res =append(res,append([]int{}, path...))
240+
return
241+
}
242+
243+
m:=make(map[int]bool)
244+
fori:=0; i <len(nums); i++ {
245+
// used 从剩余 nums 中选
246+
if used[i] {
247+
continue
248+
}
249+
// m 集合间去重
250+
if_,ok:= m[nums[i]]; ok {
251+
continue
252+
}
253+
m[nums[i]] =true
254+
path =append(path, nums[i])
255+
used[i] =true
256+
dfs(nums, path, used)
257+
used[i] =false
258+
path = path[:len(path)-1]
259+
}
260+
}
261+
```
262+
225263
#"diff-98e87b7d9aad7293c047830f7f0b1d93c21da32c2a368695215739f2e3fe5c15-226-264-0" data-selected="false" role="gridcell" tabindex="-1" valign="top">226
264

227265
```javascript

‎problems/0098.验证二叉搜索树.md

Lines changed: 30 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -344,7 +344,7 @@ Python：
344344
# self.val = val
345345
# self.left = left
346346
# self.right = right
347-
//递归法
347+
#递归法
348348
classSolution:
349349
defisValidBST(self,root: TreeNode) ->bool:
350350
res= []//把二叉搜索树按中序遍历写成list
@@ -356,6 +356,35 @@ class Solution:
356356
return res
357357
buildalist(root)
358358
return res==sorted(res)andlen(set(res))==len(res)//检查list里的数有没有重复元素，以及是否按从小到大排列
359+
360+
# 简单递归法
361+
classSolution:
362+
defisValidBST(self,root: TreeNode) ->bool:
363+
defisBST(root,min_val,max_val):
364+
ifnot root:returnTrue
365+
if root.val>= max_valor root.val<= min_val:
366+
returnFalse
367+
return isBST(root.left, min_val, root.val)and isBST(root.right, root.val, max_val)
368+
return isBST(root,float("-inf"),float("inf"))
369+
370+
# 迭代-中序遍历
371+
classSolution:
372+
defisValidBST(self,root: TreeNode) ->bool:
373+
stack= []
374+
cur= root
375+
pre=None
376+
while curor stack:
377+
if cur:# 指针来访问节点，访问到最底层
378+
stack.append(cur)
379+
cur= cur.left
380+
else:# 逐一处理节点
381+
cur= stack.pop()
382+
if preand cur.val<= pre.val:# 比较当前节点和前节点的值的大小
383+
returnFalse
384+
pre= cur
385+
cur= cur.right
386+
returnTrue
387+
359388
```
360389
Go：
361390
```Go

‎problems/0123.买卖股票的最佳时机III.md

Lines changed: 39 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -193,35 +193,49 @@ dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1]，即保持买入股
193193
Java：
194194

195195
```java
196-
classSolution {// 动态规划
196+
// 版本一
197+
classSolution {
197198
publicintmaxProfit(int[]prices) {
198-
// 可交易次数
199-
int k=2;
200-
201-
// [天数][交易次数][是否持有股票]
202-
int[][][] dp=newint[prices.length][k+1][2];
203-
204-
// badcase
205-
dp[0][0][0]=0;
206-
dp[0][0][1]=Integer.MIN_VALUE;
207-
dp[0][1][0]=0;
208-
dp[0][1][1]=-prices[0];
209-
dp[0][2][0]=0;
210-
dp[0][2][1]=Integer.MIN_VALUE;
211-
212-
for (int i=1; i< prices.length; i++) {
213-
for (int j=2; j>=1; j--) {
214-
// dp公式
215-
dp[i][j][0]=Math.max(dp[i-1][j][0], dp[i-1][j][1]+ prices[i]);
216-
dp[i][j][1]=Math.max(dp[i-1][j][1], dp[i-1][j-1][0]- prices[i]);
217-
}
199+
int len= prices.length;
200+
// 边界判断, 题目中 length >= 1, 所以可省去
201+
if (prices.length==0)return0;
202+
203+
/*
204+
* 定义 5 种状态:
205+
* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
206+
*/
207+
int[][] dp=newint[len][5];
208+
dp[0][1]=-prices[0];
209+
// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
210+
dp[0][3]=-prices[0];
211+
212+
for (int i=1; i< len; i++) {
213+
dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
214+
dp[i][2]=Math.max(dp[i-1][2], dp[i][1]+ prices[i]);
215+
dp[i][3]=Math.max(dp[i-1][3], dp[i][2]- prices[i]);
216+
dp[i][4]=Math.max(dp[i-1][4], dp[i][3]+ prices[i]);
218217
}
219218

220-
int res=0;
221-
for (int i=1; i<3; i++) {
222-
res=Math.max(res, dp[prices.length-1][i][0]);
219+
return dp[len-1][4];
220+
}
221+
}
222+
223+
// 版本二: 空间优化
224+
classSolution {
225+
publicintmaxProfit(int[]prices) {
226+
int len= prices.length;
227+
int[] dp=newint[5];
228+
dp[1]=-prices[0];
229+
dp[3]=-prices[0];
230+
231+
for (int i=1; i< len; i++) {
232+
dp[1]=Math.max(dp[1], dp[0]- prices[i]);
233+
dp[2]=Math.max(dp[2], dp[1]+ prices[i]);
234+
dp[3]=Math.max(dp[3], dp[2]- prices[i]);
235+
dp[4]=Math.max(dp[4], dp[3]+ prices[i]);
223236
}
224-
return res;
237+
238+
return dp[4];
225239
}
226240
}
227241
```

‎problems/0139.单词拆分.md

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -291,6 +291,27 @@ func wordBreak(s string,wordDict []string) bool {
291291
}
292292
```
293293

294+
Javascript：
295+
```javascript
296+
constwordBreak= (s,wordDict)=> {
297+
298+
let dp=Array(s.length+1).fill(false);
299+
dp[0]=true;
300+
301+
for(let i=0; i<=s.length; i++){
302+
for(let j=0; j<wordDict.length; j++) {
303+
if(i>= wordDict[j].length) {
304+
if(s.slice(i- wordDict[j].length, i)=== wordDict[j]&& dp[i- wordDict[j].length]) {
305+
dp[i]=true
306+
}
307+
}
308+
}
309+
}
310+
311+
return dp[s.length];
312+
}
313+
```
314+
294315

295316

296317
-----------------------

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

Lines changed: 38 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -170,41 +170,54 @@ public:
170170
Java：
171171

172172
```java
173-
classSolution {//动态规划
173+
// 版本一: 三维 dp数组
174+
classSolution {
174175
publicintmaxProfit(intk,int[]prices) {
175-
if (prices==null|| prices.length<2|| k==0) {
176-
return0;
177-
}
178-
179-
// [天数][交易次数][是否持有股票]
180-
int[][][] dp=newint[prices.length][k+1][2];
181-
182-
// bad case
183-
dp[0][0][0]=0;
184-
dp[0][0][1]=Integer.MIN_VALUE;
185-
dp[0][1][0]=0;
186-
dp[0][1][1]=-prices[0];
187-
// dp[0][j][0] 都均为0
188-
// dp[0][j][1] 异常值都取Integer.MIN_VALUE;
189-
for (int i=2; i< k+1; i++) {
190-
dp[0][i][0]=0;
191-
dp[0][i][1]=Integer.MIN_VALUE;
176+
if (prices.length==0)return0;
177+
178+
// [天数][交易次数][是否持有股票]
179+
int len= prices.length;
180+
int[][][] dp=newint[len][k+1][2];
181+
182+
// dp数组初始化
183+
// 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润
184+
for (int i=0; i<= k; i++) {
185+
dp[0][i][1]=-prices[0];
192186
}
193187

194-
for (int i=1; i<prices.length; i++) {
195-
for (int j=k; j>=1; j--) {
196-
//dp公式
188+
for (int i=1; i<len; i++) {
189+
for (int j=1; j<= k; j++) {
190+
//dp方程, 0表示不持有/卖出, 1表示持有/买入
197191
dp[i][j][0]=Math.max(dp[i-1][j][0], dp[i-1][j][1]+ prices[i]);
198192
dp[i][j][1]=Math.max(dp[i-1][j][1], dp[i-1][j-1][0]- prices[i]);
199193
}
200194
}
195+
return dp[len-1][k][0];
196+
}
197+
}
201198

202-
int res=0;
203-
for (int i=1; i< k+1; i++) {
204-
res=Math.max(res, dp[prices.length-1][i][0]);
199+
// 版本二: 空间优化
200+
classSolution {
201+
publicintmaxProfit(intk,int[]prices) {
202+
if (prices.length==0)return0;
203+
204+
// [天数][股票状态]
205+
// 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
206+
int len= prices.length;
207+
int[][] dp=newint[len][k*2+1];
208+
209+
// dp数组的初始化, 与版本一同理
210+
for (int i=1; i< k*2; i+=2) {
211+
dp[0][i]=-prices[0];
205212
}
206213

207-
return res;
214+
for (int i=1; i< len; i++) {
215+
for (int j=0; j< k*2-1; j+=2) {
216+
dp[i][j+1]=Math.max(dp[i-1][j+1], dp[i-1][j]- prices[i]);
217+
dp[i][j+2]=Math.max(dp[i-1][j+2], dp[i-1][j+1]+ prices[i]);
218+
}
219+
}
220+
return dp[len-1][k*2];
208221
}
209222
}
210223
```

‎problems/0322.零钱兑换.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -304,6 +304,26 @@ func min(a, b int) int {
304304

305305
```
306306

307+
Javascript：
308+
```javascript
309+
constcoinChange= (coins,amount)=> {
310+
if(!amount) {
311+
return0;
312+
}
313+
314+
let dp=Array(amount+1).fill(Infinity);
315+
dp[0]=0;
316+
317+
for(let i=0; i<coins.length; i++) {
318+
for(let j= coins[i]; j<= amount; j++) {
319+
dp[j]=Math.min(dp[j- coins[i]]+1, dp[j]);
320+
}
321+
}
322+
323+
return dp[amount]===Infinity?-1: dp[amount];
324+
}
325+
```
326+
307327

308328

309329
-----------------------

‎problems/0377.组合总和Ⅳ.md

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -201,6 +201,25 @@ func combinationSum4(nums []int, target int) int {
201201
}
202202
```
203203

204+
Javascript：
205+
```javascript
206+
constcombinationSum4= (nums,target)=> {
207+
208+
let dp=Array(target+1).fill(0);
209+
dp[0]=1;
210+
211+
for(let i=0; i<= target; i++) {
212+
for(let j=0; j<nums.length; j++) {
213+
if (i>= nums[j]) {
214+
dp[i]+= dp[i- nums[j]];
215+
}
216+
}
217+
}
218+
219+
return dp[target];
220+
};
221+
```
222+
204223

205224

206225
-----------------------

‎problems/0474.一和零.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -244,6 +244,35 @@ func max(a,b int) int {
244244
}
245245
```
246246

247+
Javascript：
248+
```javascript
249+
constfindMaxForm= (strs,m,n)=> {
250+
constdp=Array.from(Array(m+1), ()=>Array(n+1).fill(0));
251+
let numOfZeros, numOfOnes;
252+
253+
for(let strof strs) {
254+
numOfZeros=0;
255+
numOfOnes=0;
256+
257+
for(let cof str) {
258+
if (c==='0') {
259+
numOfZeros++;
260+
}else {
261+
numOfOnes++;
262+
}
263+
}
264+
265+
for(let i= m; i>= numOfZeros; i--) {
266+
for(let j= n; j>= numOfOnes; j--) {
267+
dp[i][j]=Math.max(dp[i][j], dp[i- numOfZeros][j- numOfOnes]+1);
268+
}
269+
}
270+
}
271+
272+
return dp[m][n];
273+
};
274+
```
275+
247276

248277

249278
-----------------------

0 commit comments

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