8000 Merge branch 'master' of https://github.com/youngyangyang04/leetcode · lee4code/leetcode-master@bc5a462 · GitHub
[go: up one dir, main page]
Skip to content

Commit bc5a462

Browse files
youngyangyang04youngyangyang04
committed
2 parents e7f1f7f + 93db5a0 commit bc5a462

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+
class Solution:
237+
"""
238+
使用一维dp数组
239+
"""
240+
241+
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
242+
m, n = len(obstacleGrid), len(obstacleGrid[0])
243+
244+
# 初始化dp数组
245+
# 该数组缓存当前行
246+
curr = [0] * n
247+
for j in range(n):
248+
if obstacleGrid[0][j] == 1:
249+
break
250+
curr[j] = 1
251+
252+
for i in range(1, m): # 从第二行开始
253+
for j in range(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+
var lowestCommonAncestor = function(root, p, q) {
336+
if(root.val > p.val && root.val > q.val)
337+
return lowestCommonAncestor(root.left, p , q);
338+
else if(root.val < p.val && root.val < q.val)
339+
return lowestCommonAncestor(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+
var lowestCommonAncestor = function(root, p, q) {
362+
while(1) {
363+
if(root.val > p.val && root.val > q.val)
364+
root = root.left;
365+
else if(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
class MyQueue {
213214
Deque<Integer> deque = new LinkedList<>();
@@ -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+
class Solution {
272+
public int[] maxSlidingWindow(int[] nums, int k) {
273+
ArrayDeque<Integer> deque = new ArrayDeque<>();
274+
int n = nums.length;
275+
int[] res = new int[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
class Solution:
160160
def reverseString(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
class Solution:
216216
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
217-
people.sort(key=lambda x: (x[0], -x[1]), reverse=True)
217+
people.sort(key=lambda x: (-x[0], x[1]))
218218
que = []
219219
for p in 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+
func mergeTrees(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
JavaScript:

‎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)
10000 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+ 10000
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+
var insertIntoBST = function (root, val) {
380+
if (root === null) {
381+
root = new TreeNode(val);
382+
} else {
383+
let parent = new TreeNode(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 = new TreeNode(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)
0