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

Commit6cc132a

Browse files
Update
1 parent30c8292 commit6cc132a

12 files changed

+263
-12
lines changed

‎README.md‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@
3838
*[哈希表：map等候多时了](https://mp.weixin.qq.com/s/uVAtjOHSeqymV8FeQbliJQ)
3939
*[哈希表：其实需要哈希的地方都能找到map的身影](https://mp.weixin.qq.com/s/Ue8pKKU5hw_m-jPgwlHcbA)
4040
*[哈希表：这道题目我做过？](https://mp.weixin.qq.com/s/sYZIR4dFBrw_lr3eJJnteQ)
41+
*[哈希表：解决了两数之和，那么能解决三数之和么？](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
4142
* 精选链表相关的面试题
4243
* 精选字符串相关的面试题
4344
* 精选栈与队列相关的面试题
@@ -354,11 +355,13 @@ int countNodes(TreeNode* root) {
354355
|[0027.移除元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0027.移除元素.md)|数组|简单|**暴力****双指针/快慢指针/双指针**|
355356
|[0028.实现strStr()](https://github.com/youngyangyang04/leetcode/blob/master/problems/0028.实现strStr().md)|字符串|简单|**KMP**|
356357
|[0035.搜索插入位置](https://github.com/youngyangyang04/leetcode/blob/master/problems/0035.搜索插入位置.md)|数组|简单|**暴力****二分**|
358+
|[0037.解数独](https://github.com/youngyangyang04/leetcode/blob/master/problems/0037.解数独.md)|回溯|困难|**回溯**|
357359
|[0039.组合总和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0039.组合总和.md)|数组/回溯|中等|**回溯**|
358360
|[0040.组合总和II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0040.组合总和II.md)|数组/回溯|中等|**回溯**|
359361
|[0046.全排列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0046.全排列.md)|回溯|中等|**回溯**|
360362
|[0047.全排列II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0047.全排列II.md)|回溯|中等|**回溯**|
361-
|[0051.N皇后](https://github.com/youngyangyang04/leetcode/blob/master/problems/0051.N皇后.md)|回溯|中等|**回溯**|
363+
|[0051.N皇后](https://github.com/youngyangyang04/leetcode/blob/master/problems/0051.N皇后.md)|回溯|困难|**回溯**|
364+
|[0052.N皇后II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0052.N皇后II.md)|回溯|困难|**回溯**|
362365
|[0053.最大子序和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0053.最大子序和.md)|数组|简单|**暴力****贪心** 动态规划 分治|
363366
|[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md)|数组|中等|**模拟**|
364367
|[0077.组合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0077.组合.md)|回溯|中等|**回溯**|
@@ -400,10 +403,11 @@ int countNodes(TreeNode* root) {
400403
|[0349.两个数组的交集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0349.两个数组的交集.md)|哈希表|简单|**哈希**|
401404
|[0350.两个数组的交集II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0350.两个数组的交集II.md)|哈希表|简单|**哈希**|
402405
|[0383.赎金信](https://github.com/youngyangyang04/leetcode/blob/master/problems/0383.赎金信.md)|数组|简单|**暴力****字典计数****哈希**|
403-
|[0450.删除二叉搜索树中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0450.删除二叉搜索树中的节点.md)|树|中等|**递归**|
404406
|[0434.字符串中的单词数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0434.字符串中的单词数.md)|字符串|简单|**模拟**|
407+
|[0450.删除二叉搜索树中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0450.删除二叉搜索树中的节点.md)|树|中等|**递归**|
405408
|[0454.四数相加II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0454.四数相加II.md)|哈希表|中等|**哈希**|
406409
|[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)|字符创|简单|**KMP**|
410+
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯**|
407411
|[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)|字符串|简单|**模拟**|
408412
|[0575.分糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0575.分糖果.md)|哈希表|简单|**哈希**|
409413
|[0617.合并二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0617.合并二叉树.md)|树|简单|**递归****迭代**|
24.2 KB
Loading

‎pics/491. 递增子序列1.jpg‎

2.59 MB
Loading
33.2 KB
Loading
33.6 KB
Loading

‎problems/0018.四数之和.md‎

Lines changed: 38 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,56 @@
1-
2-
##题目地址
1+
#题目地址
32
https://leetcode-cn.com/problems/4sum/
43

5-
##思路
4+
>一样的道理，能解决四数之和
5+
6+
>那么五数之和、六数之和、N数之和呢？
7+
8+
#第18题. 四数之和
9+
10+
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
11+
12+
**注意：**
13+
14+
答案中不可以包含重复的四元组。
15+
16+
示例：
17+
给定数组 nums =[1, 0, -1, 0, -2, 2]，和 target = 0。
18+
满足要求的四元组集合为：
19+
[
20+
[-1, 0, 0, 1],
21+
[-2, -1, 1, 2],
22+
[-2, 0, 0, 2]
23+
]
24+
25+
#思路
26+
27+
四数之和，和[三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)是一个思路，都是使用双指针法, 基本解法就是在[三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A) 的基础上再套一层for循环。
28+
29+
但是有一些细节需要注意，例如： 不要判断`nums[k] > target` 就返回了，三数之和 可以通过`nums[i] > 0` 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。（大家亲自写代码就能感受出来）
30+
31+
[三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下表作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
32+
33+
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下表作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
634

35+
那么一样的道理，五数之和、六数之和等等都采用这种解法。
736

8-
四数之和，和[三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)是一个思路，都是使用双指针法，但是有一些细节需要注意，例如： 不要判断`nums[k] > target` 就返回了，三数之和 可以通过`nums[i] > 0` 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。
37+
对于[三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。
938

10-
三数之和 我们是一层for循环，然后循环内有left和right下表作为指针，四数之和，就可以是两层for循环，依然是循环内有left和right下表作为指针，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
39+
之前我们讲过哈希表的经典题目：[四数相加II](https://mp.weixin.qq.com/s/Ue8pKKU5hw_m-jPgwlHcbA)，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复。
1140

12-
动画如下：
13-
<videosrc='../video/15.三数之和.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
41+
而[四数相加II](https://mp.weixin.qq.com/s/Ue8pKKU5hw_m-jPgwlHcbA)是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！
1442

43+
大家解决一下这两道题目就能感受出来难度的差异。
1544

16-
##C++代码
45+
#C++代码
1746
```
1847
class Solution {
1948
public:
2049
vector<vector<int>> fourSum(vector<int>& nums, int target) {
2150
vector<vector<int>> result;
2251
sort(nums.begin(), nums.end());
2352
for (int k = 0; k < nums.size(); k++) {
24-
//这中剪枝是错误的，这道题目target 是任意值
53+
//这种剪枝是错误的，这道题目target 是任意值
2554
// if (nums[k] > target) {
2655
// return result;
2756
// }

‎problems/0037.解数独.md‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
#题目地址
2+
3+
https://leetcode-cn.com/problems/sudoku-solver/
4+
5+
#思路
6+
7+
这道题目和之前递归的方式都不一样，这里相当于两层递归，之前的都是一层递归
8+
9+
#C++代码
10+
11+
```
12+
class Solution {
13+
private:
14+
bool backtracking(vector<vector<char>>& board) {
15+
for (int i = 0; i < board.size(); i++) {
16+
for (int j = 0; j < board[0].size(); j++) {
17+
if (board[i][j] != '.') continue;
18+
for (char k = '1'; k <= '9'; k++) {
19+
if (isValid(i, j, k, board)) {
20+
board[i][j] = k;
21+
if (backtracking(board)) return true;
22+
board[i][j] = '.';
23+
}
24+
}
25+
return false;
26+
}
27+
}
28+
return true;
29+
30+
}
31+
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
32+
33+
for (int i = 0; i < 9; i++) {
34+
if (board[row][i] == val) {
35+
return false;
36+
}
37+
}
38+
for (int j = 0; j < 9; j++) {
39+
if (board[j][col] == val) {
40+
return false;
41+
}
42+
43+
}
44+
int startRow = (row / 3) * 3;
45+
int startCol = (col / 3) * 3;
46+
for (int i = startRow; i < startRow + 3; i++) {
47+
for (int j = startCol; j < startCol + 3; j++) {
48+
if (board[i][j] == val ) {
49+
return false;
50+
}
51+
}
52+
}
53+
return true;
54+
}
55+
public:
56+
void solveSudoku(vector<vector<char>>& board) {
57+
backtracking(board);
58+
}
59+
};
60+
```

‎problems/0052.N皇后II.md‎

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
#题目链接
2+
https://leetcode-cn.com/problems/n-queens-ii/
3+
4+
#第51题. N皇后
5+
6+
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
7+
8+
上图为 8 皇后问题的一种解法。
9+
![51n皇后](https://img-blog.csdnimg.cn/20200821152118456.png)
10+
11+
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
12+
13+
示例:
14+
15+
输入: 4
16+
输出: 2
17+
解释: 4 皇后问题存在如下两个不同的解法。
18+
[
19+
 [".Q..",  // 解法 1
20+
  "...Q",
21+
  "Q...",
22+
  "..Q."],
23+
24+
 ["..Q.",  // 解法 2
25+
  "Q...",
26+
  "...Q",
27+
  ".Q.."]
28+
]
29+
#思路
30+
31+
这道题目和 51.N皇后 基本没有区别
32+
33+
#C++代码
34+
35+
```
36+
class Solution {
37+
private:
38+
int count = 0;
39+
void backtracking(int n, int row, vector<string>& chessboard, vector<vector<string>>& result) {
40+
if (row == n) {
41+
count++;
42+
return;
43+
}
44+
for (int col = 0; col < n; col++) {
45+
if (isValid(row, col, chessboard, n)) {
46+
chessboard[row][col] = 'Q';
47+
backtracking(n, row + 1, chessboard, result);
48+
chessboard[row][col] = '.';
49+
}
50+
}
51+
}
52+
bool isValid(int row, int col, vector<string>& chessboard, int n) {
53+
int count = 0;
54+
// 检查列
55+
for (int i = 0; i < row; i++) { // 这是一个剪枝
56+
if (chessboard[i][col] == 'Q') {
57+
return false;
58+
}
59+
}
60+
// 检查 45度角是否有皇后
61+
for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
62+
if (chessboard[i][j] == 'Q') {
63+
return false;
64+
}
65+
}
66+
// 检查 135度角是否有皇后
67+
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
68+
if (chessboard[i][j] == 'Q') {
69+
return false;
70+
}
71+
}
72+
return true;
73+
}
74+
75+
public:
76+
int totalNQueens(int n) {
77+
std::vector<std::string> chessboard(n, std::string(n, '.'));
78+
vector<vector<string>> result;
79+
backtracking(n, 0, chessboard, result);
80+
return count;
81+
82+
}
83+
};
84+
```
85+
86+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0053.最大子序和.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -53,5 +53,5 @@ public:
5353
}
5454
};
5555
```
56-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
56+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
5757

‎problems/0459.重复的子字符串.md‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,22 @@ https://leetcode-cn.com/problems/repeated-substring-pattern/
44

55
##思路
66

7+
这是一道标准的KMP的题目。
8+
9+
使用KMP算法，next 数组记录的就是最长公共前后缀， 最后如果 next[len - 1] != -1，说明此时有最长公共前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度），同时如果len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长公共前后缀的长度) 正好可以被 数组的长度整除，说明有重复的子字符串。
10+
11+
**强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法**
12+
13+
如图：
14+
15+
<imgsrc='../pics/459.重复的子字符串_1.png'width=600> </img></div>
16+
17+
此时next[len - 1] = 7，next[len - 1] + 1 = 8，8就是此时 字符串asdfasdfasdf的最长公共前后缀的长度。
18+
19+
20+
(len - (next[len - 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串。
21+
22+
代码如下：
723

824
##C++代码
925

0 commit comments

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