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

Commite2d8c0a

Browse files
2 parents57326a9 +b078cc2 commite2d8c0a

22 files changed

+628
-156
lines changed

‎problems/0001.两数之和.md

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -187,7 +187,23 @@ var twoSum = function (nums, target) {
187187
};
188188
```
189189

190-
190+
php
191+
192+
```php
193+
function twoSum(array $nums, int $target): array
194+
{
195+
for ($i = 0; $i < count($nums);$i++) {
196+
// 计算剩下的数
197+
$residue = $target - $nums[$i];
198+
// 匹配的index，有则返回index， 无则返回false
199+
$match_index = array_search($residue, $nums);
200+
if ($match_index !== false && $match_index != $i) {
201+
return array($i, $match_index);
202+
}
203+
}
204+
return [];
205+
}
206+
```
191207

192208

193209
-----------------------

‎problems/0015.三数之和.md

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -354,6 +354,47 @@ def is_valid(strs)
354354
end
355355
```
356356

357+
php:
358+
359+
```php
360+
function threeSum(array $nums): array
361+
{
362+
$result = [];
363+
$length = count($nums);
364+
if ($length < 3) {
365+
return [];
366+
}
367+
sort($nums);
368+
for ($i = 0; $i < $length; $i++) {
369+
// 如果大于0结束
370+
if ($nums[$i] > 0) break;
371+
// 去重
372+
if ($i > 0 && $nums[$i] == $nums[$i - 1]) continue;
373+
$left = $i + 1;
374+
$right = $length - 1;
375+
// 比较
376+
while ($left < $right) {
377+
$sum = $nums[$i] + $nums[$left] + $nums[$right];
378+
if ($sum < 0) {
379+
$left++;
380+
} elseif ($sum > 0) {
381+
$right--;
382+
} else {
383+
array_push($result, [$nums[$i], $nums[$left], $nums[$right]]);
384+
while ($left < $right && $nums[$left] == $nums[$left + 1]) $left++;
385+
while ($left < $right && $nums[$right - 1] == $nums[$right]) $right--;
386+
$left++;
387+
$right--;
388+
}
389+
}
390+
}
391+
392+
return $result;
393+
}
394+
```
395+
396+
397+
357398
-----------------------
358399
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
359400
* B站视频：[代码随想录](https://space.bilibili.com/525438321)

‎problems/0062.不同路径.md

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -279,9 +279,7 @@ Python：
279279
```python
280280
classSolution:# 动态规划
281281
defuniquePaths(self,m:int,n:int) ->int:
282-
dp= [[0for iinrange(n)]for jinrange(m)]
283-
for iinrange(m): dp[i][0]=1
284-
for jinrange(n): dp[0][j]=1
282+
dp= [[1for iinrange(n)]for jinrange(m)]
285283
for iinrange(1, m):
286284
for jinrange(1, n):
287285
dp[i][j]= dp[i][j-1]+ dp[i-1][j]

‎problems/0070.爬楼梯.md

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -283,7 +283,18 @@ func climbStairs(n int) int {
283283
return dp[n]
284284
}
285285
```
286-
286+
#"diff-b6f6a1ca5c95b65b71a54b38df224dc5d34a24cfca589c0e4a67d460697b60a5-286-287-0" data-selected="false" role="gridcell" tabindex="-1" valign="top">
287+
```Javascript
288+
varclimbStairs=function(n) {
289+
// dp[i] 为第 i 阶楼梯有多少种方法爬到楼顶
290+
// dp[i] = dp[i - 1] + dp[i - 2]
291+
let dp= [1 ,2]
292+
for(let i=2; i< n; i++) {
293+
dp[i]= dp[i-1]+ dp[i-2]
294+
}
295+
return dp[n-1]
296+
};
297+
```
287298

288299

289300
-----------------------

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

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -376,6 +376,28 @@ func isBST(root *TreeNode, min, max int) bool {
376376
returnisBST(root.Left, min, root.Val) &&isBST(root.Right, root.Val, max)
377377
}
378378
```
379+
```go
380+
// 中序遍历解法
381+
funcisValidBST(root *TreeNode)bool {
382+
// 保存上一个指针
383+
varprev *TreeNode
384+
vartravelfunc(node *TreeNode)bool
385+
travel =func(node *TreeNode)bool {
386+
if node ==nil {
387+
returntrue
388+
}
389+
leftRes:=travel(node.Left)
390+
// 当前值小于等于前一个节点的值，返回false
391+
if prev !=nil && node.Val <= prev.Val {
392+
returnfalse
393+
}
394+
prev = node
395+
rightRes:=travel(node.Right)
396+
return leftRes && rightRes
397+
}
398+
returntravel(root)
399+
}
400+
```
379401

380402
JavaScript版本
381403

‎problems/0226.翻转二叉树.md

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -205,6 +205,7 @@ public:
205205
Java：
206206

207207
```Java
208+
//DFS递归
208209
classSolution {
209210
/**
210211
* 前后序遍历都可以
@@ -226,6 +227,31 @@ class Solution {
226227
root.right= tmp;
227228
}
228229
}
230+
231+
//BFS
232+
classSolution {
233+
publicTreeNodeinvertTree(TreeNoderoot) {
234+
if (root==null) {returnnull;}
235+
ArrayDeque<TreeNode> deque=newArrayDeque<>();
236+
deque.offer(root);
237+
while (!deque.isEmpty()) {
238+
int size= deque.size();
239+
while (size-->0) {
240+
TreeNode node= deque.poll();
241+
swap(node);
242+
if (node.left!=null) {deque.offer(node.left);}
243+
if (node.right!=null) {deque.offer(node.right);}
244+
}
245+
}
246+
return root;
247+
}
248+
249+
publicvoidswap(TreeNoderoot) {
250+
TreeNode temp= root.left;
251+
root.left= root.right;
252+
root.right= temp;
253+
}
254+
}
229255
```
230256

231257
Python：

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

Lines changed: 29 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -313,65 +313,49 @@ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
313313
}
314314
```
315315

316-
317-
JavaScript版本
318-
>递归
319-
316+
JavaScript版本：
317+
1. 使用递归的方法
320318
```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-
*/
335319
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);
320+
// 使用递归的方法
321+
// 1. 使用给定的递归函数lowestCommonAncestor
322+
// 2. 确定递归终止条件
323+
if(root===null) {
324+
return root;
325+
}
326+
if(root.val>p.val&&root.val>q.val) {
327+
// 向左子树查询
328+
let left=lowestCommonAncestor(root.left,p,q);
329+
return left!==null&&left;
330+
}
331+
if(root.val<p.val&&root.val<q.val) {
332+
// 向右子树查询
333+
let right=lowestCommonAncestor(root.right,p,q);
334+
return right!==null&&right;
335+
}
340336
return root;
341337
};
342338
```
343-
344-
>迭代
345-
339+
2. 使用迭代的方法
346340
```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-
*/
361341
varlowestCommonAncestor=function(root,p,q) {
362-
while(1) {
363-
if(root.val>p.val&&root.val>q.val)
342+
// 使用迭代的方法
343+
while(root) {
344+
if(root.val>p.val&&root.val>q.val) {
364345
root=root.left;
365-
elseif(root.val<p.val&&root.val<q.val)
346+
}elseif(root.val<p.val&&root.val<q.val) {
366347
root=root.right;
367-
else
368-
break;
348+
}else {
349+
return root;
350+
}
351+
369352
}
370-
returnroot;
353+
returnnull;
371354
};
372355
```
373356

374357

358+
375359
-----------------------
376360
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
377361
* B站视频：[代码随想录](https://space.bilibili.com/525438321)

‎problems/0236.二叉树的最近公共祖先.md

Lines changed: 23 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -311,35 +311,34 @@ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
311311
}
312312
```
313313

314-
JavaScript版本
315-
314+
JavaScript版本：
316315
```javascript
317-
/**
318-
* Definition for a binary tree node.
319-
* function TreeNode(val) {
320-
* this.val = val;
321-
* this.left = this.right = null;
322-
* }
323-
*/
324-
/**
325-
*@param{TreeNode}root
326-
*@param{TreeNode}p
327-
*@param{TreeNode}q
328-
*@return{TreeNode}
329-
*/
330316
varlowestCommonAncestor=function(root,p,q) {
331-
if(root=== p|| root=== q|| root===null)
332-
return root;
333-
let left=lowestCommonAncestor(root.left, p , q);
334-
let right=lowestCommonAncestor(root.right, p, q);
335-
if(left&& right)
336-
return root;
337-
if(!left)
338-
return right;
339-
return left;
317+
// 使用递归的方法
318+
// 需要从下到上，所以使用后序遍历
319+
// 1. 确定递归的函数
320+
consttravelTree=function(root,p,q) {
321+
// 2. 确定递归终止条件
322+
if(root===null|| root=== p||root=== q) {
323+
return root;
324+
}
325+
// 3. 确定递归单层逻辑
326+
let left=travelTree(root.left,p,q);
327+
let right=travelTree(root.right,p,q);
328+
if(left!==null&&right!==null) {
329+
return root;
330+
}
331+
if(left===null) {
332+
return right;
333+
}
334+
return left;
335+
}
336+
returntravelTree(root,p,q);
340337
};
341338
```
342339

340+
341+
343342
-----------------------
344343
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
345344
* B站视频：[代码随想录](https://space.bilibili.com/525438321)

‎problems/0257.二叉树的所有路径.md

Lines changed: 48 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -283,6 +283,7 @@ public:
283283
Java：
284284

285285
```Java
286+
//解法一
286287
classSolution {
287288
/**
288289
* 递归法
@@ -321,6 +322,52 @@ class Solution {
321322
}
322323
}
323324

325+
//解法二（常规前序遍历，不用回溯），更容易理解
326+
classSolution {
327+
publicList<String>binaryTreePaths(TreeNoderoot) {
328+
List<String> res=newArrayList<>();
329+
helper(root,newStringBuilder(), res);
330+
return res;
331+
}
332+
333+
publicvoidhelper(TreeNoderoot,StringBuildersb,List<String>res) {
334+
if (root==null) {return;}
335+
// 遇到叶子结点就放入当前路径到res集合中
336+
if (root.left==null&& root.right==null) {
337+
sb.append(root.val);
338+
res.add(sb.toString());
339+
// 记得结束当前方法
340+
return;
341+
}
342+
helper(root.left,newStringBuilder(sb).append(root.val+"->"),res);
343+
helper(root.right,newStringBuilder(sb).append(root.val+"->"),res);
344+
}
345+
}
346+
347+
//针对解法二优化，思路本质是一样的
348+
classSolution {
349+
publicList<String>binaryTreePaths(TreeNoderoot) {
350+
List<String> res=newArrayList<>();
351+
helper(root,"", res);
352+
return res;
353+
}
354+
355+
publicvoidhelper(TreeNoderoot,Stringpath,List<String>res) {
356+
if (root==null) {return;}
357+
// 由原始解法二可以知道，root的值肯定会下面某一个条件加入到path中，那么干脆直接在这一步加入即可
358+
StringBuilder sb=newStringBuilder(path);
359+
sb.append(root.val);
360+
if (root.left==null&& root.right==null) {
361+
res.add(sb.toString());
362+
}else{
363+
// 如果是非叶子结点则还需要跟上一个 “->”
364+
sb.append("->");
365+
helper(root.left,sb.toString(),res);
366+
helper(root.right,sb.toString(),res);
367+
}
368+
}
369+
}
370+
324371
```
325372

326373
Python：
@@ -350,7 +397,7 @@ class Solution:
350397

351398
```
352399
Go：
353-
400+
354401
```go
355402
funcbinaryTreePaths(root *TreeNode) []string {
356403
res:=make([]string,0)

0 commit comments

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