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

Commitb4d2f98

Browse files
2 parentse86975c +2e10346 commitb4d2f98

9 files changed

+312
-10
lines changed

‎problems/0096.不同的二叉搜索树.md

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -211,6 +211,23 @@ func numTrees(n int)int{
211211
}
212212
```
213213

214+
Javascript：
215+
```Javascript
216+
constnumTrees=(n)=> {
217+
let dp=newArray(n+1).fill(0);
218+
dp[0]=1;
219+
dp[1]=1;
220+
221+
for(let i=2; i<= n; i++) {
222+
for(let j=1; j<= i; j++) {
223+
dp[i]+= dp[j-1]* dp[i-j];
224+
}
225+
}
226+
227+
return dp[n];
228+
};
229+
```
230+
214231

215232

216233
-----------------------

‎problems/0108.将有序数组转换为二叉搜索树.md

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -209,6 +209,8 @@ public:
209209

210210

211211
Java：
212+
213+
递归: 左闭右开[left,right)
212214
```Java
213215
classSolution {
214216
publicTreeNodesortedArrayToBST(int[]nums) {
@@ -232,6 +234,75 @@ class Solution {
232234

233235
```
234236

237+
递归: 左闭右闭[left,right]
238+
```java
239+
classSolution {
240+
publicTreeNodesortedArrayToBST(int[]nums) {
241+
TreeNode root= traversal(nums,0, nums.length-1);
242+
return root;
243+
}
244+
245+
// 左闭右闭区间[left, right)
246+
privateTreeNodetraversal(int[]nums,intleft,intright) {
247+
if (left> right)returnnull;
248+
249+
int mid= left+ ((right- left)>>1);
250+
TreeNode root=newTreeNode(nums[mid]);
251+
root.left= traversal(nums, left, mid-1);
252+
root.right= traversal(nums, mid+1, right);
253+
return root;
254+
}
255+
}
256+
```
257+
迭代: 左闭右闭[left,right]
258+
```java
259+
classSolution {
260+
publicTreeNodesortedArrayToBST(int[]nums) {
261+
if (nums.length==0)returnnull;
262+
263+
//根节点初始化
264+
TreeNode root=newTreeNode(-1);
265+
Queue<TreeNode> nodeQueue=newLinkedList<>();
266+
Queue<Integer> leftQueue=newLinkedList<>();
267+
Queue<Integer> rightQueue=newLinkedList<>();
268+
269+
// 根节点入队列
270+
nodeQueue.offer(root);
271+
// 0为左区间下表初始位置
272+
leftQueue.offer(0);
273+
// nums.size() - 1为右区间下表初始位置
274+
rightQueue.offer(nums.length-1);
275+
276+
while (!nodeQueue.isEmpty()) {
277+
TreeNode currNode= nodeQueue.poll();
278+
int left= leftQueue.poll();
279+
int right= rightQueue.poll();
280+
int mid= left+ ((right- left)>>1);
281+
282+
// 将mid对应的元素给中间节点
283+
currNode.val= nums[mid];
284+
285+
// 处理左区间
286+
if (left<= mid-1) {
287+
currNode.left=newTreeNode(-1);
288+
nodeQueue.offer(currNode.left);
289+
leftQueue.offer(left);
290+
rightQueue.offer(mid-1);
291+
}
292+
293+
// 处理右区间
294+
if (right>= mid+1) {
295+
currNode.right=newTreeNode(-1);
296+
nodeQueue.offer(currNode.right);
297+
leftQueue.offer(mid+1);
298+
rightQueue.offer(right);
299+
}
300+
}
301+
return root;
302+
}
303+
}
304+
```
305+
235306
Python：
236307
```python3
237308
# Definition for a binary tree node.
@@ -279,6 +350,36 @@ func sortedArrayToBST(nums []int) *TreeNode {
279350
}
280351
```
281352
353+
JavaScript版本
354+
355+
```javascript
356+
/**
357+
* Definition for a binary tree node.
358+
* function TreeNode(val, left, right) {
359+
* this.val = (val===undefined ? 0 : val)
360+
* this.left = (left===undefined ? null : left)
361+
* this.right = (right===undefined ? null : right)
362+
* }
363+
*/
364+
/**
365+
* @param {number[]} nums
366+
* @return {TreeNode}
367+
*/
368+
var sortedArrayToBST = function (nums) {
369+
const buildTree = (Arr, left, right) => {
370+
if (left > right)
371+
return null;
372+
373+
let mid = Math.floor(left + (right - left) / 2);
374+
375+
let root = new TreeNode(Arr[mid]);
376+
root.left = buildTree(Arr, left, mid - 1);
377+
root.right = buildTree(Arr, mid + 1, right);
378+
return root;
379+
}
380+
return buildTree(nums, 0, nums.length - 1);
381+
};
382+
```
282383

283384

284385

‎problems/0115.不同的子序列.md

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,40 @@ class Solution:
186186
return dp[-1][-1]
187187
```
188188

189+
Python3:
190+
```python
191+
classSolutionDP2:
192+
"""
193+
既然dp[i]只用到dp[i - 1]的状态，
194+
我们可以通过缓存dp[i - 1]的状态来对dp进行压缩，
195+
减少空间复杂度。
196+
（原理等同同于滚动数组）
197+
"""
198+
199+
defnumDistinct(self,s:str,t:str) ->int:
200+
n1, n2=len(s),len(t)
201+
if n1< n2:
202+
return0
203+
204+
dp= [0for _inrange(n2+1)]
205+
dp[0]=1
206+
207+
for iinrange(1, n1+1):
208+
# 必须深拷贝
209+
# 不然prev[i]和dp[i]是同一个地址的引用
210+
prev= dp.copy()
211+
# 剪枝，保证s的长度大于等于t
212+
# 因为对于任意i，i > n1, dp[i] = 0
213+
# 没必要跟新状态。
214+
end= iif i< n2else n2
215+
for jinrange(1, end+1):
216+
if s[i-1]== t[j-1]:
217+
dp[j]= prev[j-1]+ prev[j]
218+
else:
219+
dp[j]= prev[j]
220+
return dp[-1]
221+
```
222+
189223
Go：
190224

191225

‎problems/0216.组合总和III.md

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -227,6 +227,44 @@ public:
227227

228228

229229
Java：
230+
231+
模板方法
232+
```java
233+
classSolution {
234+
List<List<Integer>> result=newArrayList<>();
235+
LinkedList<Integer> path=newLinkedList<>();
236+
237+
publicList<List<Integer>>combinationSum3(intk,intn) {
238+
backTracking(n, k,1,0);
239+
return result;
240+
}
241+
242+
privatevoidbackTracking(inttargetSum,intk,intstartIndex,intsum) {
243+
// 减枝
244+
if (sum> targetSum) {
245+
return;
246+
}
247+
248+
if (path.size()== k) {
249+
if (sum== targetSum) result.add(newArrayList<>(path));
250+
return;
251+
}
252+
253+
// 减枝 9 - (k - path.size()) + 1
254+
for (int i= startIndex; i<=9- (k- path.size())+1; i++) {
255+
path.add(i);
256+
sum+= i;
257+
backTracking(targetSum, k, i+1, sum);
258+
//回溯
259+
path.removeLast();
260+
//回溯
261+
sum-= i;
262+
}
263+
}
264+
}
265+
```
266+
267+
其他方法
230268
```java
231269
classSolution {
232270
List<List<Integer>> res=newArrayList<>();

‎problems/0494.目标和.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -306,6 +306,36 @@ func findTargetSumWays(nums []int, target int) int {
306306
}
307307
```
308308

309+
Javascript：
310+
```javascript
311+
constfindTargetSumWays= (nums,target)=> {
312+
313+
constsum=nums.reduce((a,b)=> a+b);
314+
315+
if(target> sum) {
316+
return0;
317+
}
318+
319+
if((target+ sum)%2) {
320+
return0;
321+
}
322+
323+
consthalfSum= (target+ sum)/2;
324+
nums.sort((a,b)=> a- b);
325+
326+
let dp=newArray(halfSum+1).fill(0);
327+
dp[0]=1;
328+
329+
for(let i=0; i<nums.length; i++) {
330+
for(let j= halfSum; j>= nums[i]; j--) {
331+
dp[j]+= dp[j- nums[i]];
332+
}
333+
}
334+
335+
return dp[halfSum];
336+
};
337+
```
338+
309339

310340

311341
-----------------------

‎problems/0538.把二叉搜索树转换为累加树.md

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -239,7 +239,70 @@ func RightMLeft(root *TreeNode,sum *int) *TreeNode {
239239
}
240240
```
241241
242+
JavaScript版本
243+
244+
> 递归
245+
246+
```javascript
247+
/**
248+
* Definition for a binary tree node.
249+
* function TreeNode(val, left, right) {
250+
* this.val = (val===undefined ? 0 : val)
251+
* this.left = (left===undefined ? null : left)
252+
* this.right = (right===undefined ? null : right)
253+
* }
254+
*/
255+
/**
256+
* @param {TreeNode} root
257+
* @return {TreeNode}
258+
*/
259+
var convertBST = function(root) {
260+
let pre = 0;
261+
const ReverseInOrder = (cur) => {
262+
if(cur) {
263+
ReverseInOrder(cur.right);
264+
cur.val += pre;
265+
pre = cur.val;
266+
ReverseInOrder(cur.left);
267+
}
268+
}
269+
ReverseInOrder(root);
270+
return root;
271+
};
272+
```
242273

274+
>迭代
275+
276+
```javascript
277+
/**
278+
* Definition for a binary tree node.
279+
* function TreeNode(val, left, right) {
280+
* this.val = (val===undefined ? 0 : val)
281+
* this.left = (left===undefined ? null : left)
282+
* this.right = (right===undefined ? null : right)
283+
* }
284+
*/
285+
/**
286+
*@param{TreeNode}root
287+
*@return{TreeNode}
288+
*/
289+
varconvertBST=function (root) {
290+
let pre=0;
291+
let cur= root;
292+
let stack= [];
293+
while (cur!==null||stack.length!==0) {
294+
while (cur!==null) {
295+
stack.push(cur);
296+
cur=cur.right;
297+
}
298+
cur=stack.pop();
299+
cur.val+= pre;
300+
pre=cur.val;
301+
cur=cur.left;
302+
}
303+
return root;
304+
};
305+
```
243306

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

‎problems/0617.合并二叉树.md

Lines changed: 27 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -319,7 +319,7 @@ Python：
319319
# self.val = val
320320
# self.left = left
321321
# self.right = right
322-
//递归法*前序遍历
322+
#递归法*前序遍历
323323
classSolution:
324324
defmergeTrees(self,root1: TreeNode,root2: TreeNode) -> TreeNode:
325325
ifnot root1:return root2// 如果t1为空，合并之后就应该是t2
@@ -328,6 +328,32 @@ class Solution:
328328
root1.left=self.mergeTrees(root1.left , root2.left)//左
329329
root1.right=self.mergeTrees(root1.right , root2.right)//右
330330
return root1//root1修改了结构和数值
331+
332+
# 迭代法-覆盖原来的树
333+
classSolution:
334+
defmergeTrees(self,root1: TreeNode,root2: TreeNode) -> TreeNode:
335+
ifnot root1:return root2
336+
ifnot root2:return root1
337+
# 迭代,将树2覆盖到树1
338+
queue1= [root1]
339+
queue2= [root2]
340+
root= root1
341+
while queue1and queue2:
342+
root1= queue1.pop(0)
343+
root2= queue2.pop(0)
344+
root1.val+= root2.val
345+
ifnot root1.left:# 如果树1左儿子不存在，则覆盖后树1的左儿子为树2的左儿子
346+
root1.left= root2.left
347+
elif root1.leftand root2.left:
348+
queue1.append(root1.left)
349+
queue2.append(root2.left)
350+
351+
ifnot root1.right:# 同理，处理右儿子
352+
root1.right= root2.right
353+
elif root1.rightand root2.right:
354+
queue1.append(root1.right)
355+
queue2.append(root2.right)
356+
return root
331357
```
332358

333359
Go：

‎problems/动态规划-股票问题总结篇.md

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -375,12 +375,6 @@ p[i][3] = dp[i - 1][2];
375375

376376
综上分析，递推代码如下：
377377

378-
```C++
379-
dp[i][0] = max(dp[i -1][0], max(dp[i -1][3], dp[i -1][1]) - prices[i];
380-
dp[i][1] = max(dp[i -1][1], dp[i -1][3]);
381-
dp[i][2] = dp[i -1][0] + prices[i];
382-
dp[i][3] = dp[i -1][2];
383-
```
384378
```C++
385379
dp[i][0] = max(dp[i -1][0], max(dp[i -1][3]- prices[i], dp[i -1][1]) - prices[i];
386380
dp[i][1] = max(dp[i -1][1], dp[i -1][3]);

0 commit comments

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