10000 Merge branch 'master' into master · lee4code/leetcode-master@90100eb · GitHub
[go: up one dir, main page]
Skip to content

Commit 90100eb

Browse files
youngyangyang04youngyangyang04
authored
Merge branch 'master' into master
2 parents 53ce92f + d6770c0 commit 90100eb

File tree

58 files changed

+1674
-313
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

58 files changed

+1674
-313
lines changed

‎README.md

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
> 1. **介绍**：本项目是一套完整的刷题计划，旨在帮助大家少走弯路，循序渐进学算法，[关注作者](#关于作者)
44
> 2. **PDF版本** ： [「代码随想录」算法精讲 PDF 版本](https://mp.weixin.qq.com/s/RsdcQ9umo09R6cfnwXZlrQ) 。
5+
> 3. **刷题顺序** ： README已经将刷题顺序排好了，按照顺序一道一道刷就可以。
56
> 3. **学习社区** : 一起学习打卡/面试技巧/如何选择offer/大厂内推/职场规则/简历修改/技术分享/程序人生。欢迎加入[「代码随想录」学习社区](https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ) 。
67
> 4. **提交代码**：本项目统一使用C++语言进行讲解，但已经有Java、Python、Go、JavaScript等等多语言版本，感谢[这里的每一位贡献者](https://github.com/youngyangyang04/leetcode-master/graphs/contributors)，如果你也想贡献代码点亮你的头像，[点击这里](https://mp.weixin.qq.com/s/tqCxrMEU-ajQumL1i8im9A)了解提交代码的方式。
78
> 5. **转载须知** ：以下所有文章皆为我（[程序员Carl](https://github.com/youngyangyang04)）的原创。引用本项目文章请注明出处，发现恶意抄袭或搬运，会动用法律武器维护自己的权益。让我们一起维护一个良好的技术创作环境！
@@ -41,7 +42,7 @@
4142

4243
对于刷题，我们都是想用最短的时间**按照循序渐进的难度顺序把经典题目都做一遍**，这样效率才是最高的！
4344

44-
所以我整理了leetcode刷题攻略：一个超级详细的刷题顺序，**每道题目都是我精心筛选，都是经典题目高频面试题**，大家只要按照这个顺序刷就可以了，**你没看错，就是题目顺序都排好了，文章顺序就是刷题顺序！挨个刷就可以，不用自己再去题海里选题了！**
45+
所以我整理了leetcode刷题攻略：一个超级详细的刷题顺序，**每道题目都是我精心筛选，都是经典题目高频面试题**，大家只要按照这个顺序刷就可以了，**你没看错，README已经把题目顺序都排好了，文章顺序就是刷题顺序！挨个刷就可以，不用自己再去题海里选题了！**
4546

4647
而且每道题目我都写了的详细题解（图文并茂，难点配有视频），力扣上我的题解都是排在对应题目的首页，质量是有目共睹的。
4748

@@ -117,14 +118,18 @@
117118

118119
（持续更新中.....）
119120

120-
## 备战秋招
121+
## 知识星球精选
121122

122123
1. [选择方向的时候，我也迷茫了](https://mp.weixin.qq.com/s/ZCzFiAHZHLqHPLJQXNm75g)
123124
2. [刷题就用库函数了，怎么了？](https://mp.weixin.qq.com/s/6K3_OSaudnHGq2Ey8vqYfg)
124125
3. [关于实习，大家可能有点迷茫！](https://mp.weixin.qq.com/s/xcxzi7c78kQGjvZ8hh7taA)
125126
4. [马上秋招了，慌得很！](https://mp.weixin.qq.com/s/7q7W8Cb2-a5U5atZdOnOFA)
126127
5. [Carl看了上百份简历，总结了这些！](https://mp.weixin.qq.com/s/sJa87MZD28piCOVMFkIbwQ)
127128
6. [面试中遇到了发散性问题.....](https://mp.weixin.qq.com/s/SSonDxi2pjkSVwHNzZswng)
129+
7. [英语到底重不重要！](https://mp.weixin.qq.com/s/1PRZiyF_-TVA-ipwDNjdKw)
130+
8. [计算机专业要不要读研！](https://mp.weixin.qq.com/s/c9v1L3IjqiXtkNH7sOMAdg)
131+
9. [秋招和提前批都越来越提前了....](https://mp.weixin.qq.com/s/SNFiRDx8CKyjhTPlys6ywQ)
132+
128133

129134
## 数组
130135

‎problems/0017.电话号码的字母组合.md

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -342,6 +342,46 @@ class Solution:
342342

343343
Go：
344344

345+
346+
> 主要在于递归中传递下一个数字
347+
348+
```go
349+
func letterCombinations(digits string) []string {
350+
lenth:=len(digits)
351+
if lenth==0 ||lenth>4{
352+
return nil
353+
}
354+
digitsMap:= [10]string{
355+
"", // 0
356+
"", // 1
357+
"abc", // 2
358+
"def", // 3
359+
"ghi", // 4
360+
"jkl", // 5
361+
"mno", // 6
362+
"pqrs", // 7
363+
"tuv", // 8
364+
"wxyz", // 9
365+
}
366+
res:=make([]string,0)
367+
recursion("",digits,0,digitsMap,&res)
368+
return res
369+
}
370+
func recursion(tempString ,digits string, Index int,digitsMap [10]string, res *[]string) {//index表示第几个数字
371+
if len(tempString)==len(digits){//终止条件，字符串长度等于digits的长度
372+
*res=append(*res,tempString)
373+
return
374+
}
375+
tmpK:=digits[Index]-'0' // 将index指向的数字转为int（确定下一个数字）
376+
letter:=digitsMap[tmpK]// 取数字对应的字符集
377+
for i:=0;i<len(letter);i++{
378+
tempString=tempString+string(letter[i])//拼接结果
379+
recursion(tempString,digits,Index+1,digitsMap,res)
380+
tempString=tempString[:len(tempString)-1]//回溯
381+
}
382+
}
383+
```
384+
345385
javaScript：
346386
347387
```js

‎problems/0028.实现strStr.md

Lines changed: 13 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ KMP的经典思想就是:**当出现字符串不匹配时，可以记录一部
5959
* 总结
6060

6161

62-
读完本篇可以顺便，把leetcode上28.实现strStr()题目做了。
62+
读完本篇可以顺便把leetcode上28.实现strStr()题目做了。
6363

6464

6565
# 什么是KMP
@@ -126,16 +126,15 @@ next数组就是一个前缀表（prefix table）。
126126

127127
# 最长公共前后缀？
128128

129-
文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
129+
文章中字符串的**前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串**。
130130

131-
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
131+
**后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串**。
132132

133-
**正确理解什么是前缀什么是后缀很重要。**
133+
**正确理解什么是前缀什么是后缀很重要**!
134134

135135
那么网上清一色都说 “kmp 最长公共前后缀” 又是什么回事呢？
136136

137-
138-
我查了一遍 算法导论 和 算法4里KMP的章节，都没有提到 “最长公共前后缀”这个词，也不知道从哪里来了，我理解是用“最长相等前后缀” 准确一些。
137+
我查了一遍 算法导论 和 算法4里KMP的章节，都没有提到 “最长公共前后缀”这个词，也不知道从哪里来了，我理解是用“最长相等前后缀” 更准确一些。
139138

140139
**因为前缀表要求的就是相同前后缀的长度。**
141140

@@ -220,7 +219,7 @@ next数组就可以是前缀表，但是很多实现都是把前缀表统一减
220219

221220
# 使用next数组来匹配
222221

223-
以下我们以前缀表统一减一之后的next数组来做演示。
222+
**以下我们以前缀表统一减一之后的next数组来做演示**。
224223

225224
有了next数组，就可以根据next数组来 匹配文本串s，和模式串t了。
226225

@@ -236,7 +235,7 @@ next数组就可以是前缀表，但是很多实现都是把前缀表统一减
236235

237236
暴力的解法显而易见是O(n * m)，所以**KMP在字符串匹配中极大的提高的搜索的效率。**
238237

239-
为了和[字符串：KMP是时候上场了（一文读懂系列）](https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug)字符串命名统一，方便大家理解，以下文章统称haystack为文本串, needle为模式串。
238+
为了和力扣题目28.实现strStr保持一致，方便大家理解，以下文章统称haystack为文本串, needle为模式串。
240239

241240
都知道使用KMP算法，一定要构造next数组。
242241

@@ -402,7 +401,7 @@ for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
402401
}
403402
```
404403

405-
此时所有逻辑的代码都已经写出来了，本题整体代码如下：
404+
此时所有逻辑的代码都已经写出来了，力扣 28.实现strStr 题目的整体代码如下：
406405

407406
# 前缀表统一减一 C++代码实现
408407

@@ -448,7 +447,9 @@ public:
448447
449448
# 前缀表（不减一）C++实现
450449
451-
那么前缀表就不减一了，也不右移的，到底行不行呢？行！
450+
那么前缀表就不减一了，也不右移的，到底行不行呢？
451+
452+
**行！**
452453
453454
我之前说过，这仅仅是KMP算法实现上的问题，如果就直接使用前缀表可以换一种回退方式，找j=next[j-1] 来进行回退。
454455
@@ -544,7 +545,7 @@ public:
544545

545546
我们介绍了什么是KMP，KMP可以解决什么问题，然后分析KMP算法里的next数组，知道了next数组就是前缀表，再分析为什么要是前缀表而不是什么其他表。
546547

547-
接着从给出的模式串中，我们一步一步的推导出了前缀表，得出前缀表无论是统一减一还是不同意减一得到的next数组仅仅是kmp的实现方式的不同。
548+
接着从给出的模式串中，我们一步一步的推导出了前缀表，得出前缀表无论是统一减一还是不减一得到的next数组仅仅是kmp的实现方式的不同。
548549

549550
其中还分析了KMP算法的时间复杂度，并且和暴力方法做了对比。
550551

@@ -815,4 +816,4 @@ func strStr(haystack string, needle string) int {
815816
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
816817
* B站视频：[代码随想录](https://space.bilibili.com/525438321)
817818
* 知识星球：[代码随想录](https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ)
818-
<div align="center"><img src=../pics/公众号.png width=450 alt=> </img></div>
819+
<div align="center"><img src=../pics/公众号.png width=450 alt=> </img></div>

‎problems/0037.解数独.md

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -321,6 +321,59 @@ class Solution:
321321
backtrack(board)
322322
```
323323

324+
Python3:
325+
326+
```python3
327+
class Solution:
328+
def __init__(self) -> None:
329+
self.board = []
330+
331+
def isValid(self, row: int, col: int, target: int) -> bool:
332+
for idx in range(len(self.board)):
333+
# 同列是否重复
334+
if self.board[idx][col] == str(target):
335+
return False
336+
# 同行是否重复
337+
if self.board[row][idx] == str(target):
338+
return False
339+
# 9宫格里是否重复
340+
box_row, box_col = (row // 3) * 3 + idx // 3, (col // 3) * 3 + idx % 3
341+
if self.board[box_row][box_col] == str(target):
342+
return False
343+
return True
344+
345+
def getPlace(self) -> List[int]:
346+
for row in range(len(self.board)):
347+
for col in range(len(self.board)):
348+
if self.board[row][col] == ".":
349+
return [row, col]
350+
return [-1, -1]
351+
352+
def isSolved(self) -> bool:
353+
row, col = self.getPlace() # 找个空位置
354+
355+
if row == -1 and col == -1: # 没有空位置，棋盘被填满的
356+
return True
357+
358+
for i in range(1, 10):
359+
if self.isValid(row, col, i): # 检查这个空位置放i，是否合适
360+
self.board[row][col] = str(i) # 放i
361+
if self.isSolved(): # 合适，立刻返回, 填下一个空位置。
362+
return True
363+
self.board[row][col] = "." # 不合适，回溯
364+
365+
return False # 空位置没法解决
366+
367+
def solveSudoku(self, board: List[List[str]]) -> None:
368+
"""
369+
Do not return anything, modify board in-place instead.
370+
"""
371+
if board is None or len(board) == 0:
372+
return
373+
self.board = board
374+
self.isSolved()
375+
```
376+
324377
Go：
325378

326379
Javascript:

‎problems/0039.组合总和.md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -286,6 +286,39 @@ class Solution:
286286
```
287287
Go：
288288

289+
290+
> 主要在于递归中传递下一个数字
291+
292+
```go
293+
func combinationSum(candidates []int, target int) [][]int {
294+
var trcak []int
295+
var res [][]int
296+
backtracking(0,0,target,candidates,trcak,&res)
297+
return res
298+
}
299+
func backtracking(startIndex,sum,target int,candidates,trcak []int,res *[][]int){
300+
//终止条件
301+
if sum==target{
302+
tmp:=make([]int,len(trcak))
303+
copy(tmp,trcak)//拷贝
304+
*res=append(*res,tmp)//放入结果集
305+
return
306+
}
307+
if sum>target{return}
308+
//回溯
309+
for i:=startIndex;i<len(candidates);i++{
310+
//更新路径集合和sum
311+
trcak=append(trcak,candidates[i])
312+
sum+=candidates[i]
313+
//递归
314+
backtracking(i,sum,target,candidates,trcak,res)
315+
//回溯
316+
trcak=trcak[:len(trcak)-1]
317+
sum-=candidates[i]
318+
}
319+
320+
}
321+
```
289322
JavaScript：
290323

291324
```js

‎problems/0040.组合总和II.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -314,6 +314,48 @@ class Solution:
314314
```
315315
Go：
316316

317+
318+
> 主要在于如何在回溯中去重
319+
320+
```go
321+
func combinationSum2(candidates []int, target int) [][]int {
322+
var trcak []int
323+
var res [][]int
324+
var history map[int]bool
325+
history=make(map[int]bool)
326+
sort.Ints(candidates)
327+
backtracking(0,0,target,candidates,trcak,&res,history)
328+
return res
329+
}
330+
func backtracking(startIndex,sum,target int,candidates,trcak []int,res *[][]int,history map[int]bool){
331+
//终止条件
332+
if sum==target{
333+
tmp:=make([]int,len(trcak))
334+
copy(tmp,trcak)//拷贝
335+
*res=append(*res,tmp)//放入结果集
336+
return
337+
}
338+
if sum>target{return}
339+
//回溯
340+
// used[i - 1] == true，说明同一树支candidates[i - 1]使用过
341+
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
342+
for i:=startIndex;i<len(candidates);i++{
343+
if i>0&&candidates[i]==candidates[i-1]&&history[i-1]==false{
344+
continue
345+
}
346+
//更新路径集合和sum
347+
trcak=append(trcak,candidates[i])
348+
sum+=candidates[i]
349+
history[i]=true
350+
//递归
351+
backtracking(i+1,sum,target,candidates,trcak,res,history)
352+
//回溯
353+
trcak=trcak[:len(trcak)-1]
354+
sum-=candidates[i]
355+
history[i]=false
356+
}
357+
}
358+
```
317359
javaScript：
318360
319361
```js

‎problems/0046.全排列.md

Lines changed: 22 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -244,31 +244,35 @@ func backtrack(nums,pathNums []int,used []bool){
244244
}
245245
}
246246

247+
```
248+
247249
Javascript:
248250

249-
```javascript
251+
```js
250252

253+
/**
254+
* @param {number[]} nums
255+
* @return {number[][]}
256+
*/
251257
var permute = function(nums) {
252-
let result = []
253-
let path = []
254-
function backtracing(used) {
255-
if(path.length === nums.length) {
256-
result.push(path.slice(0))
257-
return
258+
const res = [], path = [];
259+
backtracking(nums, nums.length, []);
260+
return res;
261+
262+
function backtracking(n, k, used) {
263+
if(path.length === k) {
264+
res.push(Array.from(path));
265+
return;
258266
}
259-
for(let i = 0; i < nums.length; i++) {
260-
if(used[nums[i]]) {
261-
continue
262-
}
263-
used[nums[i]] = true
264-
path.push(nums[i])
265-
backtracing(used)
266-
path.pop()
267-
used[nums[i]] = false
267+
for (let i = 0; i < k; i++ ) {
268+
if(used[i]) continue;
269+
path.push(n[i]);
270+
used[i] = true; // 同支
271+
backtracking(n, k, used);
272+
path.pop();
273+
used[i] = false;
268274
}
269275
}
270-
backtracing([])
271-
return result
272276
};
273277

274278
```

‎problems/0051.N皇后.md

Lines changed: 0 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -353,14 +353,6 @@ class Solution {
353353
}
354354
```
355355

356-
## 其他语言版本
357-
358-
359-
Java：
360-
361-
362-
Python：
363-
364356

365357
Go：
366358
```Go

‎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
class Solution: # 动态规划
281281
def uniquePaths(self, m: int, n: int) -> int:
282-
dp = [[0 for i in range(n)] for j in range(m)]
283-
for i in range(m): dp[i][0] = 1
284-
for j in range(n): dp[0][j] = 1
282+
dp = [[1 for i in range(n)] for j in range(m)]
285283
for i in range(1, m):
286284
for j in range(1, n):
287285
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

0 commit comments

Comments
 (0)
0