三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvpj16/
来源：力扣（LeetCode）
说实话我一开始的思路只有三重循环去做，感觉这个做法真的太暴力，就看了别人的题解。
是用排序加双指针来做
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
if(nums.empty() || nums.back() < 0 || nums.front() > 0 || nums.size() < 3) return {};
for(int i = 0; i < nums.size() - 2; ++i)
{
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int target = 0 - nums[i], j = i + 1, k = nums.size() - 1;
while(j < k)
{
if(nums[j] + nums[k] == target)
{
res.push_back({nums[i], nums[j], nums[k]});
++j;
--k;
while(j < k && nums[j] == nums[j-1])
{
++j;
}
while(j < k && nums[k] == nums[k+1])
{
--k;
}
}
else if(nums[j] + nums[k] > target)
{
--k;
while(j < k && nums[k] == nums[k + 1])
{
--k;
}
}
else
{
++j;
while(j < k && nums[j] == nums[j-1])
{
++j;
}
}
}
}
return res;
}
|
矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
O(mn)的方法是直接开辟一个数组，记录零的位置，最后操作原矩阵。
O(m + n)的方法是用一维数组记录出现0的行和列，之后再操作原矩阵。
常数空间的方法一开始没有想到，现在记录一下：
是用每行和每列的第一个元素记录该行/列否出现了0，并且用额外的一个2个元素的数组记录，第一行和第一列是否出现了0，置0的时候要注意，先不要将第一行/列置0。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvpj16/
来源：力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int firstRowCol[2] = {0};
int m = matrix.size();
int n = matrix[0].size();
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(matrix[i][j] == 0)
{
if(i == 0 && j == 0)
{
firstRowCol[0] = 1;
firstRowCol[1] = 1;
}
else if(j == 0)
{
firstRowCol[1] = 1;
matrix[i][0] = 0;
}
else if(i == 0)
{
firstRowCol[0] = 1;
matrix[0][j] = 0;
}
else
{
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
}
for(int i = 1; i < n; ++i)
{
if(matrix[0][i] == 0)
{
for(int j = 0; j < m; ++j)
{
matrix[j][i] = 0;
}
}
}
for(int i = 1; i < m; ++i)
{
if(matrix[i][0] == 0)
{
for(int j = 0; j < n; ++j)
{
matrix[i][j] = 0;
}
}
}
if(firstRowCol[0])
{
for(int i = 0; i < n; ++i)
{
matrix[0][i] = 0;
}
}
if(firstRowCol[1])
{
for(int i = 0; i < m; ++i)
{
matrix[i][0] = 0;
}
}
}
};
|
字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
这道题一开始也没有思路(我真的太菜了)，只知道与hash有关，这道题目的关键是构建映射，可以是单词到下标(排序后单词字母顺序一样，下标是用来返回的二维数组的下标)，可以是排序后单词到字母异位词的单词的映射(这里使用的key很关键，用质数相乘做key真的厉害，开拓了思路，不同质数相乘，结果唯一)。
第一种方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, int> word2idx;
string tmp;
int maxIdx = 0;
for(string str: strs)
{
tmp = str;
sort(tmp.begin(), tmp.end());
if(word2idx.count(tmp))
{
res[word2idx[tmp]].push_back(str);
}
else
{
word2idx[tmp] = maxIdx++;
vector<string> tmpV(1, str);
res.push_back(tmpV);
}
}
return res;
}
};
|
第二种方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map <double,vector<string> > m;
double a[26]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
for(string& s : strs)
{
double t = 1;
for(char c : s)
t *= a[c - 'a'];
m[t].push_back(s);
}
for(auto& n : m)
res.push_back(n.second);
return res;
}
};
|
组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
典型的回溯问题，这里给出一个回溯模板(我觉得这个很6)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| backtracking() {
if (终止条件) {
存放结果;
}
for (选择：选择列表（可以想成树中节点孩子的数量）) {
递归，处理节点;
backtracking();
回溯，撤销处理结果
}
}
作者：carlsun-2
链接：https:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> path;
backTrace(n, k, 1, path, res);
return res;
}
void backTrace(int n, int k, int start, vector<int> & path, vector<vector<int>> & res)
{
if(path.size() == k)
{
res.push_back(path);
return ;
}
else
{
for(int i = start; i <= n; ++i)
{
path.push_back(i);
backTrace(n, k, i + 1, path, res);
path.pop_back();
}
}
}
};
|
还做了一道二叉树的层次遍历II，很简单，不赘述。
无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv2kgi/
来源：力扣（LeetCode）
这道题目思路是滑动窗口，记录字符出现的最后位置，剔除重复字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() < 1)
return 0;
if(s.size() == 1)
return 1;
int idx[128] = {0};
int res = 0;
for(int i = 0, j = 0; j < s.size(); ++j)
{
i = max(i, idx[s[j]]);
if(j - i + 1 > res)
res = j - i + 1;
idx[s[j]] = j + 1;
}
return res;
}
};
|
最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvn3ke/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这道题只会这标准的dp解法，扩展解法有待补充。
写一下dp的公式吧：用dp[i][j]的bool值来表示i到j是否是回文串。
可以得出边界条件：dp[i][i] = true, if(s[i] == s[i+1]) dp[i][i+1] = true
状态转移：if(dp[i+1][j-1] = true && s[i] == s[j]) dp[i][j] = true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public:
string longestPalindrome(string s) {
if(s.size() == 0) return {};
if(s.size() == 1) return s;
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int beg;
int length = 0;
for(int i = 0; i < n - 1; ++i)
{
dp[i][i] = true;
if(length == 0)
{
beg = i;
length = 1;
}
if(s[i] == s[i+1])
{
dp[i][i+1] = true;
beg = i;
length = 2;
}
}
for(int len = 3; len <= n; ++len)
{
for(int i = 0; i < n + 1 - len; ++i)
{
int j = i + len - 1;
if(dp[i+1][j-1] && s[i] == s[j])
{
dp[i][j] = true;
beg = i;
length = len;
}
}
}
return s.substr(beg, length);
}
};
|
递增的三元子序列
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。
示例 1:
输入: [1,2,3,4,5]
输出: true
示例 2:
输入: [5,4,3,2,1]
输出: false
C++
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvvuqg/
来源：力扣（LeetCode）
也是类似于动态规划的思想，用两个int保存i之前的 两个元素的最小递增子序列。 即用p1和p2,会用3种情况，如果num[i]小于p1，更新p1的值，如果num[i]大于p1且小于p2，更新p2的值。若出现大于p2的值，证明有符合条件的序列，直接返回为true，若直到遍历完成所有数组，则返回false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int p1 = INT_MAX, p2 = INT_MAX;
for(int i = 0; i < nums.size(); ++i)
{
if(p1 > nums[i])
{
p1 = nums[i];
}
else if(nums[i] > p1 && nums[i] < p2)
{
p2 = nums[i];
}
else if(nums[i] > p2)
{
return true;
}
}
return false;
}
};
|
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
回溯的题目，只要去掉重复的解，组合中的数字可以重复取用，很简单可以防止出现重复解，先对输入进行排序，然后后面选择的时候只以上一层选择的元素为起点，进行选择。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> tmp;
int tmpSum = 0;
sort(candidates.begin(), candidates.end());
if(candidates.size() == 0 || target < candidates[0]) return {};
backTrace(0, target, tmpSum, tmp, res, candidates);
return res;
}
void backTrace(int start, int target, int tmpSum, vector<int> & tmp, vector<vector<int>> & res, const vector<int> & candidates)
{
if(tmpSum == target)
{
res.push_back(tmp);
return;
}
else if(tmpSum > target)
{
return;
}
else
{
for(int i = start; i < candidates.size(); ++i)
{
tmpSum += candidates[i];
tmp.push_back(candidates[i]);
if(tmpSum > target)
{
tmp.pop_back();
tmpSum -= candidates[i];
break;
}
backTrace(i, target, tmpSum, tmp, res, candidates);
tmp.pop_back();
tmpSum -= candidates[i];
}
}
}
};
|
组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
和上一道题类似，但是这道题每个数字只能选择一次，会有相同的数字，剪枝时的关键是在同一层中不能选择相同的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> tmp;
int tmpSum = 0;
sort(candidates.begin(), candidates.end());
if(candidates.size() == 0 || target < candidates[0]) return {};
backTrace(0, target, tmpSum, tmp, res, candidates);
return res;
}
void backTrace(int start, int target, int tmpSum, vector<int> & tmp, vector<vector<int>> & res, const vector<int> & candidates)
{
if(tmpSum == target)
{
res.push_back(tmp);
return;
}
else
{
for(int i = start; i < candidates.size(); ++i)
{
if(i > start && candidates[i] == candidates[i-1]) continue;
tmpSum += candidates[i];
tmp.push_back(candidates[i]);
if(tmpSum > target)
{
tmp.pop_back();
tmpSum -= candidates[i];
break;
}
backTrace(i + 1, target, tmpSum, tmp, res, candidates);
tmp.pop_back();
tmpSum -= candidates[i];
}
}
}
};
|
组合总和III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii
输入变成 1到 9 此时剪枝，两个条件，深度超过k， 和大于n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> path;
backTrace(1, n, k, 0, path);
return res;
}
void backTrace(int start, int target, int k, int tmpSum, vector<int> & path)
{
if(tmpSum == target && path.size() == k)
{
res.push_back(path);
return;
}
else
{
for(int i = start; i <= 9; ++i)
{
tmpSum += i;
if(tmpSum > target) break;
path.push_back(i);
if(path.size() > k)
{
path.pop_back();
break;
}
backTrace(i+1, target, k, tmpSum, path);
path.pop_back();
tmpSum -= i;
}
}
}
};
|
