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

Commitbc5a462

Browse files
2 parentse7f1f7f +93db5a0 commitbc5a462

10 files changed

+405
-8
lines changed

‎problems/0063.不同路径II.md

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -232,6 +232,38 @@ class Solution:
232232
return dp[-1][-1]
233233
```
234234

235+
```python
236+
classSolution:
237+
"""
238+
使用一维dp数组
239+
"""
240+
241+
defuniquePathsWithObstacles(self,obstacleGrid: List[List[int]]) ->int:
242+
m, n=len(obstacleGrid),len(obstacleGrid[0])
243+
244+
# 初始化dp数组
245+
# 该数组缓存当前行
246+
curr= [0]* n
247+
for jinrange(n):
248+
if obstacleGrid[0][j]==1:
249+
break
250+
curr[j]=1
251+
252+
for iinrange(1, m):# 从第二行开始
253+
for jinrange(n):# 从第一列开始，因为第一列可能有障碍物
254+
# 有障碍物处无法通行，状态就设成0
255+
if obstacleGrid[i][j]==1:
256+
curr[j]=0
257+
elif j>0:
258+
# 等价于
259+
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
260+
curr[j]= curr[j]+ curr[j-1]
261+
# 隐含的状态更新
262+
# dp[i][0] = dp[i - 1][0]
263+
264+
return curr[n-1]
265+
```
266+
235267

236268
Go：
237269

‎problems/0235.二叉搜索树的最近公共祖先.md

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -314,7 +314,62 @@ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
314314
```
315315

316316

317+
JavaScript版本
318+
>递归
317319
320+
```javascript
321+
/**
322+
* Definition for a binary tree node.
323+
* function TreeNode(val) {
324+
* this.val = val;
325+
* this.left = this.right = null;
326+
* }
327+
*/
328+
329+
/**
330+
*@param{TreeNode}root
331+
*@param{TreeNode}p
332+
*@param{TreeNode}q
333+
*@return{TreeNode}
334+
*/
335+
varlowestCommonAncestor=function(root,p,q) {
336+
if(root.val>p.val&&root.val>q.val)
337+
returnlowestCommonAncestor(root.left, p , q);
338+
elseif(root.val<p.val&&root.val<q.val)
339+
returnlowestCommonAncestor(root.right, p , q);
340+
return root;
341+
};
342+
```
343+
344+
>迭代
345+
346+
```javascript
347+
/**
348+
* Definition for a binary tree node.
349+
* function TreeNode(val) {
350+
* this.val = val;
351+
* this.left = this.right = null;
352+
* }
353+
*/
354+
355+
/**
356+
*@param{TreeNode}root
357+
*@param{TreeNode}p
358+
*@param{TreeNode}q
359+
*@return{TreeNode}
360+
*/
361+
varlowestCommonAncestor=function(root,p,q) {
362+
while(1) {
363+
if(root.val>p.val&&root.val>q.val)
364+
root=root.left;
365+
elseif(root.val<p.val&&root.val<q.val)
366+
root=root.right;
367+
else
368+
break;
369+
}
370+
return root;
371+
};
372+
```
318373

319374

320375
-----------------------

‎problems/0239.滑动窗口最大值.md

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -208,6 +208,7 @@ public:
208208

209209
Java：
210210
```Java
211+
//解法一
211212
//自定义数组
212213
classMyQueue {
213214
Deque<Integer> deque=newLinkedList<>();
@@ -260,6 +261,40 @@ class Solution {
260261
return res;
261262
}
262263
}
264+
265+
//解法二
266+
//利用双端队列手动实现单调队列
267+
/**
268+
* 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
269+
* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
270+
*/
271+
classSolution {
272+
publicint[]maxSlidingWindow(int[]nums,intk) {
273+
ArrayDeque<Integer> deque=newArrayDeque<>();
274+
int n= nums.length;
275+
int[] res=newint[n- k+1];
276+
int idx=0;
277+
for(int i=0; i< n; i++) {
278+
// 根据题意，i为nums下标，是要在[i - k + 1, k] 中选到最大值，只需要保证两点
279+
// 1.队列头结点需要在[i - k + 1, k]范围内，不符合则要弹出
280+
while(!deque.isEmpty()&& deque.peek()< i- k+1){
281+
deque.poll();
282+
}
283+
// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
284+
while(!deque.isEmpty()&& nums[deque.peekLast()]< nums[i]) {
285+
deque.pollLast();
286+
}
287+
288+
deque.offer(i);
289+
290+
// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
291+
if(i>= k-1){
292+
res[idx++]= nums[deque.peek()];
293+
}
294+
}
295+
return res;
296+
}
297+
}
263298
```
264299

265300
Python：

‎problems/0344.反转字符串.md

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -155,7 +155,7 @@ class Solution {
155155
```
156156

157157
Python：
158-
```python3
158+
```python
159159
classSolution:
160160
defreverseString(self,s: List[str]) ->None:
161161
"""
@@ -166,6 +166,17 @@ class Solution:
166166
s[left], s[right]= s[right], s[left]
167167
left+=1
168168
right-=1
169+
170+
# 下面的写法更加简洁，但是都是同样的算法
171+
# class Solution:
172+
# def reverseString(self, s: List[str]) -> None:
173+
# """
174+
# Do not return anything, modify s in-place instead.
175+
# """
176+
# 不需要判别是偶数个还是奇数个序列，因为奇数个的时候，中间那个不需要交换就可
177+
# for i in range(len(s)//2):
178+
# s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i]
179+
# return s
169180
```
170181

171182
Go：

‎problems/0406.根据身高重建队列.md

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -214,13 +214,10 @@ Python：
214214
```python
215215
classSolution:
216216
defreconstructQueue(self,people: List[List[int]]) -> List[List[int]]:
217-
people.sort(key=lambdax: (x[0],-x[1]),reverse=True)
217+
people.sort(key=lambdax: (-x[0], x[1]))
218218
que= []
219219
for pin people:
220-
if p[1]>len(que):
221-
que.append(p)
222-
else:
223-
que.insert(p[1], p)
220+
que.insert(p[1], p)
224221
return que
225222
```
226223

‎problems/0450.删除二叉搜索树中的节点.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -358,6 +358,51 @@ func deleteNode1(root *TreeNode)*TreeNode{
358358
}
359359
```
360360

361+
JavaScript版本
362+
363+
> 递归
364+
365+
```javascript
366+
/**
367+
* Definition for a binary tree node.
368+
* function TreeNode(val, left, right) {
369+
* this.val = (val===undefined ? 0 : val)
370+
* this.left = (left===undefined ? null : left)
371+
* this.right = (right===undefined ? null : right)
372+
* }
373+
*/
374+
/**
375+
* @param {TreeNode} root
376+
* @param {number} key
377+
* @return {TreeNode}
378+
*/
379+
var deleteNode = function (root, key) {
380+
if (root === null)
381+
return root;
382+
if (root.val === key) {
383+
if (!root.left)
384+
return root.right;
385+
else if (!root.right)
386+
return root.left;
387+
else {
388+
let cur = root.right;
389+
while (cur.left) {
390+
cur = cur.left;
391+
}
392+
cur.left = root.left;
393+
let temp = root;
394+
root = root.right;
395+
delete root;
396+
return root;
397+
}
398+
}
399+
if (root.val > key)
400+
root.left = deleteNode(root.left, key);
401+
if (root.val < key)
402+
root.right = deleteNode(root.right, key);
403+
return root;
404+
};
405+
```
361406

362407

363408

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

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -368,6 +368,20 @@ func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
368368
Right:mergeTrees(t1.Right,t2.Right)}
369369
return root
370370
}
371+
372+
// 前序遍历简洁版
373+
funcmergeTrees(root1 *TreeNode,root2 *TreeNode) *TreeNode {
374+
if root1 ==nil {
375+
return root2
376+
}
377+
if root2 ==nil {
378+
return root1
379+
}
380+
root1.Val += root2.Val
381+
root1.Left =mergeTrees(root1.Left, root2.Left)
382+
root1.Right =mergeTrees(root1.Right, root2.Right)
383+
return root1
384+
}
371385
```
372386

373387
#"diff-43d288c323760223a5ce3b933e7f7ee226d58973440dae6255efa381f12e3e61-empty-empty-0" data-selected="false" role="gridcell" tabindex="-1" valign="top" colSpan="4">

‎problems/0701.二叉搜索树中的插入操作.md

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -286,8 +286,118 @@ func insertIntoBST(root *TreeNode, val int) *TreeNode {
286286
}
287287
```
288288

289+
JavaScript版本
290+
291+
> 有返回值的递归写法
292+
293+
```javascript
294+
/**
295+
* Definition for a binary tree node.
296+
* function TreeNode(val, left, right) {
297+
* this.val = (val===undefined ? 0 : val)
298+
* this.left = (left===undefined ? null : left)
299+
* this.right = (right===undefined ? null : right)
300+
* }
301+
*/
302+
/**
303+
* @param {TreeNode} root
304+
* @param {number} val
305+
* @return {TreeNode}
306+
*/
307+
var insertIntoBST = function (root, val) {
308+
const setInOrder = (root, val) => {
309+
if (root === null) {
310+
let node = new TreeNode(val);
311+
return node;
312+
}
313+
if (root.val > val)
314+
root.left = setInOrder(root.left, val);
315+
else if (root.val < val)
316+
root.right = setInOrder(root.right, val);
317+
return root;
318+
}
319+
return setInOrder(root, val);
320+
};
321+
```
289322

323+
> 无返回值的递归
324+
325+
```javascript
326+
/**
327+
* Definition for a binary tree node.
328+
* function TreeNode(val, left, right) {
329+
* this.val = (val===undefined ? 0 : val)
330+
* this.left = (left===undefined ? null : left)
331+
* this.right = (right===undefined ? null : right)
332+
* }
333+
*/
334+
/**
335+
* @param {TreeNode} root
336+
* @param {number} val
337+
* @return {TreeNode}
338+
*/
339+
var insertIntoBST = function (root, val) {
340+
let parent = new TreeNode(0);
341+
const preOrder = (cur, val) => {
342+
if (cur === null) {
343+
let node = new TreeNode(val);
344+
if (parent.val > val)
345+
parent.left = node;
346+
else
347+
parent.right = node;
348+
return;
349+
}
350+
parent = cur;
351+
if (cur.val > val)
352+
preOrder(cur.left, val);
353+
if (cur.val < val)
354+
preOrder(cur.right, val);
355+
}
356+
if (root === null)
357+
root = new TreeNode(val);
358+
preOrder(root, val);
359+
return root;
360+
};
361+
```
290362

363+
>迭代
364+
365+
```javascript
366+
/**
367+
* Definition for a binary tree node.
368+
* function TreeNode(val, left, right) {
369+
* this.val = (val===undefined ? 0 : val)
370+
* this.left = (left===undefined ? null : left)
371+
* this.right = (right===undefined ? null : right)
372+
* }
373+
*/
374+
/**
375+
*@param{TreeNode}root
376+
*@param{number}val
377+
*@return{TreeNode}
378+
*/
379+
varinsertIntoBST=function (root,val) {
380+
if (root===null) {
381+
root=newTreeNode(val);
382+
}else {
383+
let parent=newTreeNode(0);
384+
let cur= root;
385+
while (cur) {
386+
parent= cur;
387+
if (cur.val> val)
388+
cur=cur.left;
389+
else
390+
cur=cur.right;
391+
}
392+
let node=newTreeNode(val);
393+
if (parent.val> val)
394+
parent.left= node;
395+
else
396+
parent.right= node;
397+
}
398+
return root;
399+
};
400+
```
291401

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

0 commit comments

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