# 力扣100热题
# 第一题 两数之和
1. 两数之和 - 力扣（LeetCode） (opens new window)
一种方法是直接使用暴力，这里就不在赘述了
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
{
if(nums[i]+nums[j] == target)
return {i,j};
}
return {};
}
2
3
4
5
6
7
8
9
10
显然对于这题来说用哈希来做更加的合适，用暴力来解决时间复杂度围殴O(n^2^),而使用哈希来做时间复杂度仅为O(n)。
该题用了unordered_map而不是map，这样可以加快速度。如果这题用哈希需要转变思路点是target - nums[i]。用减出的答案去反套回去寻找答案。find函数定义在unordered_map中，用来寻找unordered_map中的元素。若找到则返回答案。题中还需要注意的一点是向unordered_map存入数据的契机。从题目中可以了解到数组中同一个元素在答案里不能重复出现。所以m[nums[i]] = i;操作必须在判断之后，不然会将自己本身加入到判断中，不满足题目的条件。
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> m;
int n = nums.size();
for(int i = 0; i < n; i++)
{
auto t = m.find(target - nums[i]);
if(t != m.end())
{
return {i,t->second};
}
m[nums[i]] = i;
}
return {};
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# 第二题 字母异位词分组
49. 字母异位词分组 - 力扣（LeetCode） (opens new window)
题目中字母异位词这个概念讲述的可能不是那么的清楚，简单来说就是一个单词中的字母的不同组合。比如：”eat”的字母异位词有“ate”、“eta”、“tea”、“tae”、“ate”。
解决该题，我是使用了排序的思想来解决。单独拿出给出的单词，然后对单词进行排序，接着将排完序的单词加入到关系无序容器unordered_map中。若不存在则在unordered_map自动创建一个新的键值对，值为一个空的 vector。完成该操作后将unordered_map中的元素添加到创立的散列表中，接着输出答案
需要注意的是题目用到了unordered_map而不是map，其主要的原因是为了加快速度，unordered_map的底层是哈希，map的底层是红黑树，所以对于查找、添加、删除等操作应当使用unordered_map来加快速度。题目中同样加快速度的操作是在for循环是用来&引用来进行传值，这一行为避免了不必要的拷贝操作，从而加快了效率。
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> m;
//for(auto s : strs)
//{
// string ss = s;
// sort(ss.begin(), ss.end());
// m[ss].emplace_back(s);
//}
for(auto &s : strs)
{
string ss = s;
sort(ss.begin(), ss.end());
m[ss].emplace_back(s);
}
vector<vector<string>> ans;
for(auto i = m.begin(); i != m.end(); i++)
{
ans.emplace_back(i->second);
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 第三题 最长连续序列
128. 最长连续序列 (opens new window)
这题一开始没做出来，没有想到用set（最主要的作用是去重），前两题都用了map下意识的就用map来解。也想过用排序来解，但是题目中要求是O(n)，排序就能直接排除了，常见排序的最快也需要O(nlog)。所以就能直接排除掉排序了。
那么直接来看题目。题目需要我们在一个乱序的vector容器中寻找最长的连续序列。题解中用到了很妙的方法：寻找每个数的前一个数，要是前一个数在set容器中（前提是已经将vector中的元素复制到了set中）则说明这个数不是连续序列的首位，那就跳过这个数（这部操作对应的是!s.count(n-1)，也是解题的关键）。若说set中没有这个数，则说明是连续序列的首位，就是去寻找这个数的下一个数，若下一个数存在set中则计数器加一。最后选出最大的那个序列数作为答案。
下面这个题解中用了
auto来代替官方题解中const int&，这是为了写题的方便。若是平时在使用时尽量使用官方题解的形式
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s;
for(auto i: nums)// 将vector中的数据输入到unordered_set中，完成对数据的去重
{
s.insert(i);
}
int ans = 0;// 答案变量
for(auto n : s)
{
if(!s.count(n-1))// 关键步骤：判断数是不是序列的开头
{
int ans_max = 1;
while(s.count(n+1))// 寻找数的下一个数
{
ans_max += 1;//计数器加一
n += 1;
}
ans = max(ans,ans_max);
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 第四题 移动零
这题相对来说就比较简单了，我是看到用了vector容器，所以用删除0元素，并计数。完成操作后再将删掉的0元素添加到容器尾部。
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int num = 0;
for(int i = 0; i < n; i++)
{
if(nums[i] == 0)
{
num++;
nums.erase(nums.begin()+i);
n--;
i--;
}
}
for(int i = 0; i < num; i++)
{
nums.push_back(0);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
官方题解是使用了快慢指针，时间复杂度会更加低一点。而且不用改变vector的大小。
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while (right < n) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
2
3
4
5
6
7
8
9
10
11
# 第五题 盛最多水的容器
11. 盛最多水的容器 (opens new window)
先提供暴力解法，即两次遍历vector容器计算出容器中所有数之间能形成的面积，取其中的最大值（超时）
int maxArea(vector<int>& height) {
int ans = 0;
int s = 0;
for(int i = 0; i < height.size(); i++)
{
for(int j = i; j < height.size(); j++)
{
s = min(height[j],height[i]) * (j-i);
ans = max(s,ans);
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
不超时是解法是使用双指针，将一个指针指向容器的最前端，另一个指针指向容器的最后端。根据短板效应，能装最多水的最高高度是两数中较短的那个数。所以当我们移动指针，比较指针指向的两个数，固定较高的那个数对应的指针，让较小的数的指针进行移动，记录下所围成的面积，选出其中的最大值。
int maxArea(vector<int>& height) {
int q = 0;
int p = height.size() - 1;
int s = 0;
int ans = 0;
while(p != q)
{
if(height[q] < height[p])
{
s = (p-q) * height[q];
q += 1;
ans = max(ans,s);
}else{
s = (p-q) * height[p];
p -= 1;
ans = max(ans,s);
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 第六题 三数之和
第一次做没做出来看了题解才做出来，这道题不是难在寻找出三个数，而是怎么想办法去重。这道题的去重用到的方法是排序后跳过重复的元素做到去重。
虽然这道题是双指针的用法，但实际上有点三指针的味道。通过三个指针来循环访问整个vector容器就能完成三数之和为0的数字。for循环中的i作为三数中的一个元素，定义一个首指针first_p和尾指针last_p。对三个数进行相加得到sum，若是sum>0则说明sum太大，那么使last_p--，反之first_p++。
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;// 答案容器
sort(nums.begin(),nums.end());// 排序容器，方便去重
int num = nums.size();
for(int i = 0; i < num - 2; i++)
{
int first_p = i+1;
int last_p = num-1;
if (i > 0 && nums[i] == nums[i - 1]) continue; //避免重复解
while(first_p < last_p)
{
int sum = nums[i] + nums[first_p] + nums[last_p];
if(sum == 0)
{
ans.push_back({nums[i], nums[first_p], nums[last_p]});
while (first_p < last_p && nums[first_p] == nums[first_p + 1])
first_p++;//避免重复解
first_p++;
while (first_p < last_p && nums[last_p] == nums[last_p - 1])
last_p--;//避免重复解
last_p--;
}
else if (sum < 0)
first_p++;
else if (sum > 0)
last_p--;
}
}
return ans;
}
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
# 第七题 接雨水
虽然说力扣给这道题标的困难，但是如果用双指针来解这道题我认为比上一题要简单，毕竟不用考虑额外情况。当然如果用其他的方法来解这道题可以会麻烦一点，第一次做这题时用的单调栈来解，不多细说（ 上次做的时候不知道时什么时候忘过程了（-__-) )
int trap(vector<int>& height) {
stack<int> st;
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
while (!st.empty() && height[i] > height[st.top()]) {
int mid = st.top();
st.pop();
if (!st.empty()) {
int h = min(height[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1;
sum += h * w;
}
}
st.push(i);
}
return sum;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
接下来就是双指针了，对于双指针来解这道题十分的简单。能不能接住水的关键是在水的两边是否有比水高的墙。我们用一个m_l来表示右侧相对最高的墙，所谓的相对是因为是对于r来说，因为只需要知道在r的右边有比它高的墙就行了。反之亦然。通过时时更新m_l(m_r)可以判断出哪出需要装水，哪处不需要。
int trap(vector<int>& height) {
int l = 0;
int r = height.size()-1;
int ans = 0;
int m_l=0;
int m_r=0;
while(l < r){
m_l = max(m_l,height[l]);
m_r = max(m_r,height[r]);
if(height[l]<height[r])
{
ans += m_l-height[l];
l++;
}else{
ans += m_r-height[r];
r--;
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 第八题 无重复字符的最长子串
3. 无重复字符的最长子串 (opens new window)
这道题用滑动窗口解决，官方题解中用到了set，我使用的方法并没有用到set采用了最原始的每次读入一个元素就对之前的字串进行扫描，寻找是否存在重复的字符，若是存在则保存当前字串的长度并重新计数（ 从重复的字符开始算起）。
int lengthOfLongestSubstring(string s) {
int l = 0;
int r = 0;
int ans = 0;
int count = 0;
int n = s.size();
while(r < n)
{
for(int j = l; j < r; j++)
{
if(s[j] == s[r])
{
l = r;
count = 0;
break;
}
}
count++;
r++;
ans = max(ans,count);
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 第九题 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词 (opens new window)
字母异位词是经常能用到滑动窗口的一道题目，这道字母异位题就比较的经典，虽然说力扣给的数据很宽，但是对于这种题还是有限制的。比如这道字母异位词题，题目都说了是字母异位词，如果在解题的时候还对字母进行排序，那么必然是超时的，所以拿到题对题目的分析还是尤为重要的。
现在回到题目的本身，这题我们先创立连个数组a和b（ 这种命名方式我非常的不推荐，只是个人比较懒，用了这种简易命名 ），用来分别储存目标字符串p，以及滑动窗口字符串。先对两个数组进行初始化。注意在对b数组初始化时就要进行一次判断（ 当然你可以在后面进行判断 ，比较函数equal不再多说十分的简单）。接着用一个指针i指向滑动窗口的头部（ 要舍弃的元素），另一个指针指向滑动窗口尾部的下一个元素（ 要加入的元素）。移动窗口，每次移动进行一次判断。
这道题中有个小技巧，就是用到了ASCII值。小写字母a-z的ASCII值是从97-122，这样做可以更加方便的定位到具体的下标。
vector<int> findAnagrams(string s, string p) {
int a[26] = {0}; // 存放p
int b[26] = {0}; // 滑动窗口
int num_p = p.size();
int num_s = s.size();
vector<int> ans;
if(num_p > num_s)// 排除特殊情况
return {};
for(int k : p)// 初始化目标数组
{
a[k-97]++;
}
int j = 0; // 对滑动窗口进行初始化
while(j < num_p)
{
int k = s[j];
b[k-97]++;
j++;
}
bool f = equal(a,b);
if(f == true)
ans.push_back(0);
j = num_p;
for(int i = 0; i < num_s-num_p; i++)
{
int k = s[i];
b[k-97]--;
k = s[j++];
b[k-97]++;
bool f = equal(a,b);
if(f == true)
ans.push_back(i+1);
}
return ans;
}
bool equal(int a[],int b[])// 对比两个数组
{
for(int i = 0; i < 26; i++)
{
if(a[i] != b[i])
{
return false;
}
}
return true;
}
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
# 第十题 和为k的数组
560. 和为 K 的子数组 (opens new window)
暴力枚举可以解这题，即把所有的情况都枚举出来，确定一个i接着通过循环来遍历i到vector最后的元素，若存在则把ans++。这种时间复杂度为O(n^2^)会超时，不推荐。
第二种方法是前缀和+哈希求和的方法，这种方法的时间复杂度为O(n)。先创立一个保存前缀和的变量pre。由于存储用哈希的方式存储，所有用变量来暂时存放前缀和即可。由题意可知，我们有一个目标变量k，我们通过前求得前n项和存放在哈希表中，我们假设存放的位置进行到i，在i之前的所有前缀和都存放进了哈希表中，那么我们就要从哈希表中寻找到pre - k（此时pre算的前缀和是i处的前缀和）。若存在一个数满足条件，则说明在vector中存在一个连续非空序列相加等于k。
能使用第二种方法有一个很重要的前提，也就是题目种所说的子数组是数组中元素的连续非空序列。如果没这一条件就无法使用第二种方法。也是因为这个原因使得做题的时候很容易用滑动窗口来解答，但是这题无法使用滑动窗口来解决，主要的原因是在nums中存在负数。一般来说滑动窗口前端和后端只向一个方向移动，所以当数组中出现负数的时滑动窗口很难处理。
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> map;
map[0] = 1;
int ans = 0;
int pre = 0;
for(auto n : nums)
{
pre = pre + n;
int x = pre - k;
if(map.find(x) != map.end())
{
ans += map[x];
}
map[pre]++;
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 第十一题 滑动窗口的最大值
239. 滑动窗口最大值 (opens new window)
暴力
暴力的解法时间复杂度是O(n^2^),即每次滑动窗口滑动进行数据的插入时，对滑动窗口进行遍历，寻找到滑动窗中的最大值。下面给出的暴力解法进行了一些优化。只有当滑动窗口中既存的最大值消失时才会对窗口进行最大值寻找的操作，不过可惜的是任然不能完全通过测试样例
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
int mymax = nums[0];
int l = 0;
int r = k-1;
mymax = findMax(nums,l,r);
ans.push_back(mymax);
for(int i = k; i < nums.size(); i++)
{
if(r+1 != nums.size() && nums[++r] > mymax)
{
mymax = nums[r];
}
if(nums[l++] == mymax)
{
mymax = findMax(nums,l,r);
}
ans.push_back(mymax);
}
return ans;
}
int findMax(vector<int>& nums, int l, int r)
{
int mymax = nums[l];
for(int i = r; i >= l; i--)
{
mymax = max(mymax,nums[i]);
}
return mymax;
}
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
单调队列
单调队列是这题的正解之一，时间复杂度可以降低到O(n)。我们用一个双端队列来实现单调队列，队列中严格按照递减的规则来实现。我们在队列的开头存放的是滑动窗口的最大值，当读取到有比队列开头大的数时，替换掉开头的数。当遇到小于开头的数时，我们将进行判断，这个数是否应该存储存放入队列中，条件为该数是否比队尾元素大，若比队尾元素大则删除掉队尾元素（ 注意这里是一个循环操作 ），接着存放进入数从而来保证队列中的严格单调递减。值得关注的是队列中存放的是nums的下标，而不是具体的值。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
deque<int> q;
for (int i = 0; i < nums.size(); i++)
{
while(!q.empty() && nums[q.back()] <= nums[i])// 维持队列的单调递减
{
q.pop_back();
}
q.push_back(i);
if (i - q.front() >= k) // 防止超过滑动窗口上线
{
q.pop_front();
}
if(i >= k-1)// 作用于初始化的操作
{
ans.push_back(nums[q.front()]);
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 第十二题 最小覆盖字串
灵茶山艾府最小覆盖字串题解 (opens new window)
这题看了灵神的题解，用到了一个比较独特的方法——覆盖。覆盖我们可以简单的理解为待处理数组中的目标元素一定大于等于目标数组才满足条件。s 的子串 BANC 中每个字母的出现次数，都大于等于 t=ABC 中每个字母的出现次数。具体解法移步灵神的题解，下面粘上灵神的代码
bool is_covered(int cnt_s[], int cnt_t[]) {
for (int i = 'A'; i <= 'Z'; i++) {
if (cnt_s[i] < cnt_t[i]) {
return false;
}
}
for (int i = 'a'; i <= 'z'; i++) {
if (cnt_s[i] < cnt_t[i]) {
return false;
}
}
return true;
}
string minWindow(string s, string t) {
int m = s.length();
int ans_left = -1, ans_right = m, left = 0;
int cnt_s[128]{}, cnt_t[128]{};
for (char c : t) {
cnt_t[c]++;
}
for (int right = 0; right < m; right++) {
cnt_s[s[right]]++;
while (is_covered(cnt_s, cnt_t)) {
if (right - left < ans_right - ans_left) {
ans_left = left;
ans_right = right;
}
cnt_s[s[left++]]--;
}
}
return ans_left < 0 ? "" : s.substr(ans_left, ans_right - ans_left + 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
# 第十三题 最大子数组和
这题是动态规划，pre是用来储存区间和的，我们可以很轻松的理解到在pre = max(x,pre + x);中若是前区间中相加的值不如x，那么就可以直接舍弃前个区间，并创立新的区间。
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int pre = 0;
for(auto& x : nums)
{
pre = max(x,pre + x);
ans = max(pre,ans);
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
# 第十四题 合并区间
这题就是一题简单的模拟题，需要注意的是我们先要对数组进行排序处理。我们可以理解到的是，如果两个区间能合并则必须满足前一个区间arr[i][1]必须大于后一个区间arr[i+1][0],接着我们挑取较大值作为答案数组ans[i][1]。
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() == 0)
{
return {};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for(int i = 0 ; i < intervals.size(); i++)
{
if(!ans.empty() && ans.back()[1] >= intervals[i][0])
{
ans.back()[1] = max(ans.back()[1],intervals[i][1]);
}
else{
ans.push_back(intervals[i]);
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 第十五题 轮转数组
这道题虽然力扣把它分到中等题里，但是其实就是一道简单题，先说空间复杂度为O(n)的方法，换句话来说就是新创立一个数组，然后有题所给出的`k`，寻找到数组中`nums.size()-k`的位置，需要注意的是`k`有可能大于`nums.size()`，所以要对`k`进行取余操作（这道题唯一的思考点），寻找到位置后直接存放到另一个数组中即可。
void rotate(vector<int>& nums, int k) {
int n = k % nums.size();
vector<int> ans;
for(int i = nums.size()-n; i < nums.size(); i++)
{
ans.push_back(nums[i]);
}
for(int i = 0; i < nums.size()-n; i++)
{
ans.push_back(nums[i]);
}
nums.assign(ans.begin(),ans.end());
}
2
3
4
5
6
7
8
9
10
11
12
13
空间复杂度为O(1)的做法，我用到了reverse()，这个函数能翻转元素，找到 k % nums.size()后，先将整个数组反转，再分别反转k % nums.size()前后的区间得到答案。
void rotate(vector<int>& nums, int k) {
int n = k % nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + n);
reverse(nums.begin() + n, nums.end());
}
2
3
4
5
6
# 第十六题 除自身以外数组的乘积
238. 除自身以外数组的乘积 (opens new window)
这题的难点在于不能使用除法，那么就只能用前后缀的方法。我们先创立一个答案数组answer，先把每个答案的前缀存在数组里，再把每个数组的后缀乘上它的前缀得到答案。
vector<int> productExceptSelf(vector<int>& nums) {
int num = nums.size();
vector<int> answer(num);
answer[0] = 1;
for(int i = 1; i < num; i++)
{
answer[i] = answer[i-1] * nums[i-1];
}
int n = 1;
for(int i = num-1; i >= 0; i--)
{
answer[i] = answer[i] * n;
n *= nums[i];
}
return answer;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 第十七题 缺失的第一个正数
41. 缺失的第一个正数 (opens new window)
这题是困难题中较为简单的一题，力扣的中等题和困难有些题划分就很鬼畜。这题的难点是在于题目给的限制条件：时间复杂度为 O(n) 并且只使用常数级别额外空间.这题的条件就是这个限制条件提起来的，通过更改数据量来提高题目难度，是力扣常用的一种方法。当然这个就是研究算法的目的，不就是为了更快处理更大的数据，所以来研究的算法嘛，毕竟理论上来说所有的题目都能使用暴力来解决。
回到题目本身，我用到的是官方题解中的第二种方法——置换法。简单点来说，我们假设nums[2] = 4;
那么我们将nums[4]与nums[2]进行交换，也就是将nums[i]对应的值去到应该去到的地方。然后再进行遍历若是对应位置不为对应的值，则输出这个值+1，否则输出nums.size()+1。
int firstMissingPositive(vector<int>& nums) {
int num = nums.size();
for(int i = 0 ; i < num; i++)
{
int x = nums[i];
while (nums[i] > 0 && nums[i] <= num && nums[x-1] != nums[i])
{
swap(nums[x-1], nums[i]);
x = nums[i];
}
}
for(int i = 0 ; i < num; i++)
{
if(nums[i] != i + 1)
{
return i+1;
}
}
return num+1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 第十八题 矩阵置零
力扣这种题我觉得是挺没意思的，题目加的限制完全就是为了出题而出题，现在的计算机硬件背景下，为了一点空间来换取代码可读性的减弱，我认为是没有太大意义的，我们应当把目光更多聚焦到时间复杂度上。
这里讲一下空间复杂度为O(1)的做法。用到的技巧是用数组matrix的第0行和第0列作为整一行和列是否存在0的标志。由于第一行和列可能存在0，所以要首先检查第一行或列是否存在0 。
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int col = false;
int row = false;
for (int i = 0; i < m; i++)
{
if (matrix[i][0] == 0)
{
col = true;
}
}
for (int i = 0; i < n; i++)
{
if (matrix[0][i] == 0)
{
row = true;
}
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
if (matrix[i][j] == 0)
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
if (!matrix[i][0] || !matrix[0][j])
{
matrix[i][j] = 0;
}
}
}
if (col)
{
for (int i = 0; i < m; i++)
{
matrix[i][0] = 0;
}
}
if (row) {
for (int i = 0; i < n; i++)
{
matrix[0][i] = 0;
}
}
}
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
# 第十九题 螺旋矩阵
这题是最经典的矩阵题之一，模拟是这题比较清晰的解法。从题目中可以看到，最后输出的结果就是螺旋遍历矩阵的结果。而在同一个方向上，运动方向相同。所以我们可以使用四个变量来存储运动碰壁时运动空间的变化情况。
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector<int> ans;
int left = 0;
int right = col - 1;
int top = 0;
int bottom = row - 1;
while (left <= right && top <= bottom)
{
// 从左到右
for (int i = left; i <= right; i++)
{
ans.push_back(matrix[top][i]);
}
top++;
// 从上到下
for (int i = top; i <= bottom; i++)
{
ans.push_back(matrix[i][right]);
}
right--;
// 从右到左
if (top <= bottom)
{
for (int i = right; i >= left; i--)
{
ans.push_back(matrix[bottom][i]);
}
}
bottom--;
// 从下到上
if (left <= right)
{
for (int i = bottom; i >= top; i--)
{
ans.push_back(matrix[i][left]);
}
}
left++;
}
return ans;
}
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
# 第二十题 旋转图像
这题参考了题解，下面附上矩阵旋转的所有情况
上下对称：matrix[i][j] -> matrix[n-i-1][j]，（列不变）
左右对称：matrix[i][j] -> matrix[i][n-j-1]，（行不变）
主对角线对称：matrix[i][j] -> matrix[j][i]，（行列互换）
副对角线对称：matrix[i][j] -> matrix[n-j-1][n-i-1] （行列均变，且互换）
2
3
4
顺时针 90° 旋转
上下对称 + 主对角线对称 or 主对角线对称 + 左右对称
顺时针180°旋转
顺时针 90° + 顺时针 90°
= 上下对称 + 主对角线对称 + 主对角线对称 + 左右对称
= 上下对称 + 左右对称 （主对角线对称抵消）
2
3
逆时针90°旋转
左右对称 + 主对角线对称 or 主对角线对称 + 上下对称
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
n = matrix.size();
// 上下对称 + 主对角线对称
upDownSymmetry(matrix);
mainDiagSymmetry(matrix);
// 主对角线对称 + 左右对称
// mainDiagSymmetry(matrix);
// leftRightSymmetry(matrix);
// 左右对称 + 副对角线对称
// leftRightSymmetry(matrix);
// subdiagSymmetry(matrix);
// 副对角线对称 + 上下对称
// subdiagSymmetry(matrix);
// upDownSymmetry(matrix);
}
private:
int n;
// 上下对称
void upDownSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n/2; ++i) {
for (int j = 0; j < n; ++j) {
swap(matrix[i][j], matrix[n-i-1][j]);
}
}
}
// 左右对称
void leftRightSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n/2; ++j) {
swap(matrix[i][j], matrix[i][n-j-1]);
}
}
}
// 主对角线对称
void mainDiagSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n-1; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
// 副对角线对称
void subdiagSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < n-i-1; ++j) {
swap(matrix[i][j], matrix[n-j-1][n-i-1]);
}
}
}
};
//作者：PennX
//链接：https://leetcode.cn/problems/rotate-image/solutions/1692273/lu-qing-ge-chong-by-pennx-ce3x/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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
回到原题
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n/2; ++i) {
for (int j = 0; j < n; ++j) {
swap(matrix[i][j], matrix[n-i-1][j]);
}
}
for (int i = 0; i < n-1; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 第二十一题 搜索二维矩阵II
240. 搜索二维矩阵 II (opens new window)
这题力扣的数据量给的有点问题，直接暴力搜索也能做。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
bool ans = false;
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
if(matrix[i][j] == target)
ans = true;
}
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
较优解法是用"Z字行查找"，我认为这个叫法也不是很恰当，但是这种方法，大家都这么叫。这种方法简单来说就是找到一个极值。这个极值是行的最大值，是列的最小值（矩阵最右上角的值）。所以当前值比target小时，将加大当前值，即往下移动。反之若当前值比target大时，就减少当前值，即往左移动。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
int x = 0;
int y = col-1;
while(x < row && y >= 0)
{
if(matrix[x][y] == target)
return true;
if(matrix[x][y] > target)
y--;
else
x++;
}
return false;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 第二十二题 相交链表
这题的题目描述很垃圾。这边简单点说，所谓的相交链表不是节点内的值相交，而是节点地址相交。如果这么理解那么这道题就是名副其实的简单题了，顺嘴一提，这是12年的考研编程题。
回到题目本身，我们先统计出来两个链表的长度，然后我们减去较长链表的长度使两个链表的长度相同，然后用指针遍历，若地址相同则返回结果，否则为空。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *head1 = headA;
ListNode *head2 = headB;
int len1 = 0;
int len2 = 0;
while(head1->next != NULL)
{
head1 = head1->next;
len1++;
}
while(head2->next != NULL)
{
head2 = head2->next;
len2++;
}
while(len1 - len2 > 0)
{
headA = headA->next;
len1--;
}
while(len2 - len1 > 0)
{
headB = headB->next;
len2--;
}
while (headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
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
# 第二十三题 反转链表
这一题直接看题中的解释吧，一看就懂了。（ 看不懂可以用笔在纸上画一画就懂了 )。
ListNode* reverseList(ListNode* head) {
ListNode* p = nullptr;
ListNode* q = head;
while (q != nullptr) {
ListNode* n = q->next; // 暂存下一个节点
q->next = p; // 反转当前节点的指向
p = q; // 移动p到当前节点
q = n; // 移动q到下一个节点
}
return p; // p将是新的头节点
}
2
3
4
5
6
7
8
9
10
11
12
13
# 第二十四题 回文链表
先将链表中的数放入到数组然后对数组进行是否为回文的判断。
bool isPalindrome(ListNode* head) {
vector<int> vec;
// 将链表元素存入数组
while(head != nullptr) {
vec.push_back(head->val);
head = head->next;
}
// 比较数组中的元素，检查是否是回文
int left = 0;
int right = vec.size() - 1;
while(left < right) {
if(vec[left] != vec[right])
return false;
left++;
right--;
}
return true;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 第二十五题 环形链表
遇到环形链表的题一般会使用的方法就是快慢指针，即一个指针走的快，一个指针走的慢，如果存在环形链表，那么这两个指针在某一时刻一定会相遇。需要注意的是，要判断一下特殊的情况，如输入的指针为空或者只有一个节点时，这些特殊情况要特殊处理。
bool hasCycle(ListNode *head) {
if(head == NULL || head->next == NULL)
return false;
ListNode *fast = head->next;
ListNode *slow = head;
while(slow != fast)
{
if(fast == NULL || fast->next == NULL)
return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
还有一种简单的处理方法是使用哈希表，由于set的性质——不允许重复。那么当出现重复说明出现了环。
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> set;
while (head != nullptr) {
if (set.count(head)) {
return true;
}
set.insert(head);
head = head->next;
}
return false;
}
2
3
4
5
6
7
8
9
10
11
12
# 第二十六题 环形链表II
142. 环形链表 II (opens new window)
使用快慢指针来解决这题，需要进行一定的数学推理。这边附上灵神的代码。具体详解可以去看他的视频。（ 关键是我也不是很能理解 >_<||| ）
环形链表II【基础算法精讲 07】_哔哩哔哩_bilibili (opens new window)
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
while (slow != head) {
slow = slow->next;
head = head->next;
}
return slow;
}
}
return nullptr;
}
//作者：灵茶山艾府
//链接：https://leetcode.cn/problems/linked-list-cycle-ii/solutions/1999271/mei-xiang-ming-bai-yi-ge-shi-pin-jiang-t-nvsq/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
使用哈希表同样很简单和上一题几乎相同，只需要改变return的值即可。
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> set;
while (head != nullptr) {
if (set.count(head)) {
return head;
}
set.insert(head);
head = head->next;
}
return NULL;
}
2
3
4
5
6
7
8
9
10
11
# 第二十七题 合并两个有序链表
21. 合并两个有序链表 (opens new window)
迭代是比较朴实的枪口情况。先处理特殊情况，两个链表有一个为空时，或两个都为空时输出结果。接着比较两个链表节点中的val值，较小的加入到答案链表中，接着将多余的链表拼接到答案链表中。
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 1.处理特殊情况
if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;
// 2.比较两个链表节点中的val值
ListNode* listHead = new ListNode(-1);
ListNode* list = listHead;
while(list1 != NULL && list2 != NULL)
{
if(list1->val <= list2->val)
{
list->next = list1;
list1 = list1->next;
}else{
list->next = list2;
list2 = list2->next;
}
list = list->next;
}
// 3.凭借剩余列表
if(list1 != NULL) {
list->next = list1;
} else {
list->next = list2;
}
return listHead->next;
}
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
# 第二十八题 两数相加
一开始我并没有意识到题目给我们进行了简化，用了逆序，所有本来的想法但是反转链表然后转化为两个数相加，然后再创造新的链表，显然这样过于麻烦。
题目给的逆序可以帮助我们直接相加。但是需要注意的时进位，我们需要一个专门的变量来标志是否进位。接着我们通过提取节点的val值来加入到我们的节点中。最终得出结果时，还是要注意进位，若需要进位要专名创造一个节点来存储（ 这一步我直接放到了循环中，便于代码的可读性，可以单独判断 ）。
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* anshead = new ListNode(0);
ListNode* ans = anshead;
int carry = 0; // 标志进位
while (l1 != nullptr || l2 != nullptr || carry) {
int sum = carry;
if (l1 != nullptr) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != nullptr) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10; // 计算进位
ans->next = new ListNode(sum % 10); // 创建新节点并连接到结果链表
ans = ans->next;
}
return anshead->next;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 第二十九题 删除链表的倒数第N个节点
19. 删除链表的倒数第 N 个结点 (opens new window)
这题我的这种解法算是比较常规的做法。先用一个指针right走n步，接着让另一个指针left和right一起走，直到right走到链表的末尾。由于right先走了n步，那么当right走到末尾时，left->next对应的位置就是我们需要删除的位置。
ListNode *newHead = preHead->next;
delete preHead;
return newHead;
2
3
需要注意最后这里，不是返回head，而是新建了一个节点来表示头节点，为了防止传进来的头节点被删除，当然也可以提前处理这种特殊情况。
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *preHead = new ListNode(-1);
preHead->next = head;
ListNode *left = preHead;
ListNode *right = preHead;
for(int i = 0; i <= n; i++)
{
if (right == nullptr)
return head;
right = right->next;
}
while(right != NULL)
{
right = right->next;
left = left ->next;
}
ListNode *node = left->next;
if (node != nullptr) {
left->next = node->next;
delete node;
}
ListNode *newHead = preHead->next;
delete preHead;
return newHead;
}
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
# 第三十题 两两交换链表中的节点
24. 两两交换链表中的节点 (opens new window)
这题我用的是迭代，用到了四个指针。用head和prev来移动，用first和second两个临时指针来做节点的交换，具体看代码在纸上画一下就能出来，使用迭代的方法至少需要3个指针，如果只有两个指针很难做到。因为在交换时，后面的节点会影响到前面的节点。
ListNode* swapPairs(ListNode* head) {
ListNode *preHead = new ListNode(-1);
preHead->next = head;
ListNode *prev = preHead;
while (head != nullptr && head->next != nullptr) {
ListNode *first = head;
ListNode *second = head->next;
// 交换两节点
first->next = second->next;
second->next = first;
prev->next = second;
// 移动指针以处理下一对节点
prev = first;
head = first->next;
}
ListNode *newHead = preHead->next;
delete preHead;
return newHead;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 第三十一题 k个一组翻转链表
25. K 个一组翻转链表 (opens new window)
hard题中的链表题是相对来说较为简单的，是普通人能看懂的、能够上手做出来的。但是链表的题就是比较绕，容易把自己绕进去。我这边使用的是一种比较笨的方法（ 之前就把自己绕进去了 ）。先把特殊情况处理了，然后进行节点数量的统计。这么做的原因是：防止后面在做节点交换时，指针异常的情况。接着通过以K个为一组进行翻转。
ListNode* reverseKGroup(ListNode* head, int k) {、
// 判断特殊情况
if (!head || k == 1) return head;
ListNode *preHead = new ListNode(-1);
preHead->next = head;
ListNode *prev = preHead;
ListNode *curr = head;
ListNode *next = nullptr;
// 计算节点数量
int num = 0;
while (curr) {
curr = curr->next;
num++;
}
// 反复反转以K为单位的链表
while (num >= k) {
curr = prev->next;
next = curr->next;
for (int i = 1; i < k; ++i) {
curr->next = next->next;
next->next = prev->next;
prev->next = next;
next = curr->next;
}
prev = curr;
num -= k;
}
ListNode *newHead = preHead->next;
delete preHead;
return newHead;
}
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
# 第三十二题 随机链表的复制
138. 随机链表的复制 (opens new window)
这题的题目描述就像便秘一样，表达能力堪忧，当然也有可能是我的阅读能力堪忧。题目简单点来说就是根据它给出的链表，来建立一个一模一样的链表。链表中包含val、next、random三个内容，这些东西需要你完全复制下来。
使用哈希存储是这题比较朴素的方法。用了哈希存储链表，使链表有了像顺序表的特点。如果这题能想到使用哈希来做就十分的简单了。我们先依托map创立所有的链表节点。然后再将链表的节点全部连接。
Node* copyRandomList(Node* head) {
map<Node*,Node*> mp;
Node* cur = head;
int num = 0;// 计数
// 创造链表节点
while(cur != NULL)
{
mp[cur] = new Node(cur->val);
cur = cur->next;
num++;
}
cur = head;
// 连接链表的next和random
for(int i = 0; i < num; i++)
{
mp[cur]->next = mp[cur->next];
mp[cur]->random = mp[cur->random];
cur = cur->next;
}
return mp[head];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 第三十三题 排序链表
链表题有一个很恶心的做法，就是将链表存储到数组中，然后用数组的方式进行处理，接着再拼接起来，这样做虽然能通过，但是失去了题目本身的目的，这一题限制了空间复杂度为O(1)，所以就永不了上述的方法。
这题用的是归并排序，下面展示递归版本。转载
https://leetcode.cn/problems/sort-list/solutions/2400774/ge-chong-pai-xu-suan-fa-jie-jue-mou-pao-9dwmt
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* mid = findMid(head);
ListNode* newHead = mid->next;
mid->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(newHead);
return merge(left, right);
}
ListNode* findMid(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val <= l2->val) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
//作者：smd
//链接：https://leetcode.cn/problems/sort-list/solutions/2400774/ge-chong-pai-xu-suan-fa-jie-jue-mou-pao-9dwmt/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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
# 第三十四题 合并K个升序链表
23. 合并 K 个升序链表 (opens new window)
解答这一题就用到了STL中的优先队列，其实和上一题说的用数组有点像。题目给出的是升序的链表，所以我们只要先存入每个链表的头节点就行了。接在后来每次链表的节点被使用了，就将后续的节点存入到优先队列中去。
在定义优先队列的排列顺序时，用了自定义的比较，在自定义时用c++11中的lamdba表达式来方便书写。
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 自定义比较
auto cmp = [](ListNode *a, ListNode *b){
return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
// 将每个链表的首节点存入到优先队列中去
for (auto& n: lists) {
if (n) {
pq.push(n);
}
}
// 创造一个头节点
ListNode* head = new ListNode;
ListNode* cur = head;
// 升序拼接链表
while(!pq.empty()){
cur->next = pq.top();
pq.pop();
cur = cur->next;
if(cur->next != NULL)
pq.push(cur->next);
}
return head->next;
}
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
# 第三十五题 LRU缓存
146. LRU 缓存 (opens new window)
这题据评论所说是互联网公司面试的时候十分喜欢考察的题。首先我们需要知道的是由于题目的限制时间复杂度要在O(1)这一条件内，所以我们要选择哈希表来处理，又由于是LRU的性质。我们使用双向链表来处理。
首先我们定义一个节点结构体。由于我们要使用哈希表来存储，且链表中的值需要使用，所以我们选择key和value来作为node节点的数据域。又由于是双向链表，所以我们使用next后继和prev前驱来作为指针域。接着我们对节点做一些初始化的操作，用来方便后面节点的创立。
在初始化时我们定义了头尾节点，并且对LRUCache内节点数量上限进行了规定。
在写get函数时，我们先要理解题目中get函数的意思。get函数的目的是得到节点的值，且将节点移动到最前面。理解了这一层意思，那么我们在写这个函数的时候压力就会小很多了。我们先对哈希表进行搜索确定该元素是否存在（ 注意这边使用的是count而非find，因为我们只需要确定是否存在该元素即可）。若是存在该元素那么我们就进行移动节点的操作，并输出节点中的value值。（ 双向链表节点的删除、插入和增加是数据结构中的基础内容 ）
在put函数中，同样我们需要确定的是哈希表中是否存在这个值，若存在则对于该节点的value进行更改。需要注意的是我们在更改完值后，要进行类似get的操作，要将更改完值的节点放到首位。若是不存在则在首位插入节点。插入完成后要对LRUCache中的节点数量进行检查，若数量超过最大值，则要移除末尾的节点。
struct node {
int key;
int value;
node* next;
node* prev;
node() : key(0), value(0), prev(NULL), next(NULL) {}
node(int _key, int _value) : key(_key), value(_value), prev(NULL), next(NULL) {}
};
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = new node();
tail = new node();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!mp.count(key)) {
return -1;
}
node* newNode = mp[key];
moveToHead(newNode);
return newNode->value;
}
void put(int key, int value) {
if (!mp.count(key)) {
node* newNode = new node(key, value);
mp[key] = newNode;
addNode(newNode);
size++;
if (size > capacity) {
removeNode();
size--;
}
} else {
node* oldNode = mp[key];
oldNode->value = value;
moveToHead(oldNode);
}
}
private:
std::unordered_map<int, node*> mp;
node* head;
node* tail;
int size = 0;
int capacity = 0;
void addNode(node* newNode) {
newNode->next = head->next;
newNode->prev = head;
head->next->prev = newNode;
head->next = newNode;
}
void removeNode() {
node* oldNode = tail->prev;
oldNode->prev->next = oldNode->next;
oldNode->next->prev = oldNode->prev;
mp.erase(oldNode->key);
delete oldNode;
}
void moveToHead(node* oldNode) {
oldNode->prev->next = oldNode->next;
oldNode->next->prev = oldNode->prev;
addNode(oldNode);
}
};
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
# 第三十六题 二叉树的中序遍历
94. 二叉树的中序遍历 (opens new window)
1.递归法
不多做解释，是数据结构中的基础知识，若是基础知识不牢固，可以移步数据结构。
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
treeTraversal(root,ans);
return ans;
}
void treeTraversal(TreeNode* root, vector<int>& ans)
{
if(root == NULL)
return;
treeTraversal(root->left, ans);
ans.push_back(root->val);
treeTraversal(root->right, ans);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
2.迭代法
迭代法用到栈来辅助。我们先定义一个指针指向根节点。然后进行循环判断，若是指针指向的非空，或者是栈非空。接着我们就遍历到左子树上，然后将路径上的节点存入到栈中，接着重复上述操作来中序遍历整个二叉树。
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
TreeNode* p = root;
while(p != NULL || !st.empty())
{
while (p != NULL) {
st.push(p);
p = p->left;
}
p = st.top();
st.pop();
ans.push_back(p->val);
p = p->right;
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 第三十七题 二叉树的最大深度
104. 二叉树的最大深度 (opens new window)
递归来完成对树的遍历，很简单的题。唯一要注意点的就是每次递归的时候要比较深度的大小。
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;
if(root->left == NULL && root->right == NULL)
return 1;
return max((1+maxDepth(root->left)),(1+maxDepth(root->right)));
}
2
3
4
5
6
7
# 第三十八题 翻转二叉树
依然是使用递归来解题。递归的出口是当指针为空，若不为空则进行交换操作（ 就算它的左右子树有空也无所谓，直接交换即可，也符合题意 ）。
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
return root;
TreeNode* x = root->left;
root->left = root->right;
root->right = x;
invertTree(root->right);
invertTree(root->left);
return root;
}
2
3
4
5
6
7
8
9
10
# 第三十九题 对称二叉树
这题的递归相对于前三题是要难一点的。将根节点的左右子树传入到递归中，随着递归的进行若左右子树其中一个为空，则比较左右子树是否都为空。若不为空则比较两个值是否相等。
bool isSymmetric(TreeNode *root) {
return isMirror(root->right,root->left);
}
bool isMirror(TreeNode* p, TreeNode* q) {
if(p == NULL || q == NULL)
return p == q;
if(p->val != q->val)
return false;
if(!isMirror(q->left,p->right))
return false;
if(!isMirror(q->right,p->left))
return false;
return true;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 第四十题 二叉树的直径
543. 二叉树的直径 (opens new window)
这题简单的树形DP，但是可能会踩坑。题目中提到的这条路径可能经过也可能不经过根节点 root 。这句就奠定了这是一题DP。我们需要对每个点作为拐点进行计算直径。
递归的出口是当节点为空时，返回-1。返回-1的原因是该节点是空节点，所有减去进入该层递归加上的那个1，然后对ans进行答案的更新
int ans = 0;
int diameterOfBinaryTree(TreeNode* root) {
ans = dfs(root);
return ans;
}
int dfs(TreeNode * p)
{
if(p == NULL)
return -1;
int l_len = dfs(p->left) + 1;
int r_len = dfs(p->right) + 1;
ans = max(ans,l_len+r_len);
return max(l_len,r_len);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 第四十一题 二叉树的层次遍历
102. 二叉树的层序遍历 (opens new window)
层次遍历是dfs。递归出口是节点指向空。由于是层次遍历，所以我们在递归时还需要一个参数，这个参数用来表示在当前遍历在第几层。当第一层二维数组少于层数时，就要增加一层二维数组。其余就是对树的左右子树的遍历。
vector<vector<int>> ans;
vector<vector<int>> levelOrder(TreeNode* root) {
bfs(root,0);
return ans;
}
void bfs(TreeNode* q,int n)
{
if(q == NULL)
return;
if (n >= ans.size()) {
ans.push_back(vector<int>());
}
ans[n].push_back(q->val);
bfs(q->left,n+1);
bfs(q->right,n+1);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 第四十二题 将有序数组转化为二叉搜索树
108. 将有序数组转换为二叉搜索树 (opens new window)
这道题需要注意的是这棵树是平衡二叉树。
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);//给helper中的形参left和right赋值
}
TreeNode* helper(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;//给定一个递归回溯的条件
}
// 总是选择中间位置右边的数字作为根节点
int mid = (left + right + 1) / 2;
TreeNode* root = new TreeNode(nums[mid]);//创建一个新的节点
//递归开始，先创立根节点左孩子部分的节点全部
//随着递归的进行将right不断的减少直到right==left返回空开始左孩子部分的递归回溯
root->left = helper(nums, left, mid - 1);
//当回溯到根节点后开始创立根节点右孩子部分的全部
//随着递归的进行left不断增减直到right==left返回空开始后孩子部分的递归回溯
root->right = helper(nums, mid + 1, right);
return root;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 第四十三题 验证二叉搜素树
98. 验证二叉搜索树 (opens new window)
二叉树搜索树的特点就是中序遍历出来的数据是升序的。我们就用这个特性进行二叉树中序遍历。将节点值存入数组中，然后对数组进行判断是否是升序。
vector<int> arr;
bool isValidBST(TreeNode* root) {
LDR(root);
for(int i = 0; i < arr.size()-1; i++)
{
if(arr[i] >= arr[i+1])
return false;
}
return true;
}
TreeNode* LDR(TreeNode* node)
{
if(node == NULL)
return NULL;
LDR(node->left);
arr.push_back(node->val);
LDR(node->right);
return NULL;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 第四十四题 二叉搜索树中第K小的元素
230. 二叉搜索树中第K小的元素 (opens new window)
这题和上一题相同，也是利用中序遍历存入到数组中，然后就直接通过下标就能找到元素。
vector<int> arr;
int kthSmallest(TreeNode* root, int k) {
LDR(root);
return arr[k-1];
}
TreeNode* LDR(TreeNode* node)
{
if(node == NULL)
return NULL;
LDR(node->left);
arr.push_back(node->val);
LDR(node->right);
return NULL;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# 第四十五题 二叉树的右视图
199. 二叉树的右视图 (opens new window)
这道题的描述很变态，用人话来说就是要展示层次遍历的每一层的最右的元素。
做法的话就是一直遍历最有子树，但是由于存在这一层的最右元素有可能是在左子树上，所以当右子树遍历不下去了就遍历左子树。分辨是不是新的左子树的方法是通过判断n是不是新的值。
vector<int> ans;
vector<int> rightSideView(TreeNode* root) {
dfs(root,0);
return ans;
}
void dfs(TreeNode* q,int n)
{
if(q == NULL)
return;
if (n == ans.size()) {
ans.push_back(q->val);
}
dfs(q->right,n+1);
dfs(q->left,n+1);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 第四十六题 二叉树的展开为链表
114. 二叉树展开为链表 (opens new window)
这题是二叉树的先序遍历的反向遍历（ 可以理解为右左根 ）。接着用一个辅助指针指向连接节点，便于连接。
TreeNode* pre = NULL;
void flatten(TreeNode* root) {
if(root == NULL)
return;
flatten(root->right);
flatten(root->left);
root->left = NULL;
root->right = pre;
pre = root;
}
2
3
4
5
6
7
8
9
10
# 第四十七题 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 (opens new window)
这题参考了灵神的题解。和树的大多数题目一样，这题使用了递归。前序遍历的特点是能很好的找到根。找到的根可以帮助在中序遍历中分割左右子树。在新的左右子树中又可以找到左右子树，从而形成了递归。
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) { // 空节点
return NULL;
}
int x = ranges::find(inorder,preorder[0]) - inorder.begin();
vector<int> p_1(preorder.begin() + 1,preorder.begin() + 1 + x);
vector<int> p_2(preorder.begin() + 1 + x, preorder.end());
vector<int> i_1(inorder.begin(), inorder.begin() + x);
vector<int> i_2(inorder.begin() + 1 + x, inorder.end());
TreeNode *left = buildTree(p_1, i_1);
TreeNode *right = buildTree(p_2, i_2);
return new TreeNode(preorder[0], left, right);
}
2
3
4
5
6
7
8
9
10
11
12
13
# 第四十八题 路径总和
437. 路径总和 III (opens new window)
这一题和 第十题 和为k的数组 很像。都是利用了前缀和加哈希表的组合。具体的操作方式可以看那一题。
这一题新增加的东西就是将数组与树相结合。依然通过递归进行先序遍历来访问所有的节点。和第十题不一样的是这里要考虑状态恢复。由于路径只能从上而下，所以不存在路径拐弯的情况，所以要当遍历回溯时都要进行状态恢复，否则当我们递归完左子树，要递归右子树时，pre 中还保存着左子树的数据。
int ans = 0;
int pathSum(TreeNode* root, int targetSum) {
unordered_map<long long, int> mp;
mp[0] = 1;
dfs(root, 0,targetSum, mp);
return ans;
}
void dfs(TreeNode* node, long long pre, int targetSum, unordered_map<long long, int>& mp){
if(node == NULL)
return;
pre += node->val;
long long x = pre - targetSum;
if(mp.find(x) != mp.end())
{
ans += mp[x];
}
mp[pre]++;
dfs(node->left, pre,targetSum, mp);
dfs(node->right, pre,targetSum, mp);
mp[pre]--;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 第四十九题 二叉树的最近祖先
236. 二叉树的最近公共祖先 (opens new window)
查看下列链接的题解，有详细的画图演示过程。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || root == p || root == q) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left == nullptr) return right;
if(right == nullptr) return left;
return root;
}
//作者：Krahets
//链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solutions/240096/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2
3
4
5
6
7
8
9
10
11
12
13
# 第五十题 二叉树中的最大路径和
124. 二叉树中的最大路径和 (opens new window)
这题和第四十题很像，需要枚举每个节点其左右子树的节点值的最大和。我们在每次递归的时候需要拿到每个节点的左右子树的最大路径和。返回答案时要与0做比较，要是小于0就不要将这条路径的值加进来。
int ans = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* node){
if(node == NULL)
return 0;
int left_val = dfs(node->left);
int right_val = dfs(node->right);
ans = max(left_val + right_val + node->val , ans);
return max(0,max(left_val,right_val) + node->val);
}
2
3
4
5
6
7
8
9
10
11
12
13
# 第五十一题 岛屿数量
一道简单的深度优先搜索整个图。先遍历每个点，若该点为'1'则进行搜索。
递归的出口是当触碰到边界或者是'0'时进行回溯。向上下左右四个方向进行搜索。若是为'1'，则将该点的值改变为'0'。
int ans = 0;
int numIslands(vector<vector<char>>& grid) {
for(int i = 0; i < grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == '1')
{
dfs(i,j,grid);
ans++;
}
}
}
return ans;
}
void dfs(int i, int j, vector<vector<char>>& grid)
{
// 检查是否越界
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
// 向四个方向进行深度优先搜索
dfs(i - 1, j, grid);
dfs(i + 1, j, grid);
dfs(i, j - 1, grid);
dfs(i, j + 1, grid);
}
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
# 第五十二题 腐烂的橘子
这题和五十一题相对应。这题使用的广度优先搜索，借助队列来完成。首先统计新鲜的橘子和腐烂的橘子，将其存放在两个集合。题目的目的就是将新鲜的橘子集合中的所有元素全部转化到腐烂的橘子的集合中。
接着继续宁广度优先遍历，如果队列非空则进行循环，在循环中先要统计此时队列中的元素的数量。因为这要将队列中所有元素周围的所有橘子都感染一遍。做了一个表示k是为了看是否真正进行了感染，若进行则要将时间+1；
最后要判断新鲜的橘子集合中是否还有残留，若有残留则将返回-1。
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int orangesRotting(vector<vector<int>>& grid) {
int ans = 0;
int fresh = 0;
queue<pair<int,int>> q;
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[0].size(); j++)
if(grid[i][j] == 1)
fresh++;
else if(grid[i][j] == 2)
q.push({i, j});
}
while(!q.empty())
{
int len = q.size();
int k = 0;// 标记是否进行腐烂的蔓延
for(int i = 0; i < len; i++)
{
auto n = q.front();
q.pop();
for(auto& dir : dir)
{
int x = n.first + dir[0];
int y = n.second + dir[1];
if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1) {
grid[x][y] = 2;
q.push({x,y});
fresh--;
k = 1;
}
}
}
if(k == 1)
ans++;
}
return fresh == 0 ? ans : -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
# 第五十三题 课程表
这题就是拓扑排序的简化版本，完全使用拓扑的思想就能解决。先用map来统计每个点的入度接着就是用拓扑排序的思想来解决，具体实现方法可以移步数据结构板块。这边是用的队列来存储入度为0的元素，数据结构那边用的是栈，都可。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,int> mp;
for(int i = 0; i < numCourses; i++)
{
mp[i] = 0;
}
for(int i = 0; i < prerequisites.size(); i++)
{
int x = prerequisites[i][1];
mp[x]++;
}
queue<int> q;
int m = 0;
if(prerequisites.size() == 0)
return true;
for(int i = 0; i < numCourses; i++)
{
if(mp[i] == 0)
{
q.push(i);
}
}
while(!q.empty())
{
int n = q.front();
q.pop();
m++;
for(int i = 0; i < prerequisites.size(); i++)
{
if(prerequisites[i][0] == n)
{
int x = prerequisites[i][1];
mp[x]--;
if(mp[x] == 0)
q.push(prerequisites[i][1]);
}
}
}
return m == numCourses ? true : false;
}
};
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
# 第五十四题 实现Trie（前缀树）
208. 实现 Trie (前缀树) (opens new window)
class Trie {
private:
bool isEnd;
Trie* next[26];
public:
Trie() {
isEnd = false;
memset(next, 0, sizeof(next));
}
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (node->next[c-'a'] == NULL) {
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
bool search(string word) {
Trie* node = this;
for (char c : word) {
node = node->next[c - 'a'];
if (node == NULL) {
return false;
}
}
return node->isEnd;
}
bool startsWith(string prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c-'a'];
if (node == NULL) {
return false;
}
}
return true;
}
};
//作者：路漫漫我不畏
//链接：https://leetcode.cn/problems/implement-trie-prefix-tree/solutions/98390/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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
# 第五十五题 全排列
全排列的模板做法。全排列是回溯中的一部分内容。先定义两个数组，path用来存放已选择的元素，is_path用来表示是否这个数是否已经被选择。由于是全排列，所以要进行现场的恢复。
vector<vector<int>> ans;
int num = 0;
vector<vector<int>> permute(vector<int>& nums) {
num = nums.size();
vector<int> path(num);
vector<int> is_path(num);
dfs(0,path,is_path,nums);
return ans;
}
void dfs(int i,vector<int>& path,vector<int>& is_path,vector<int>& nums)
{
if(i == num)
ans.push_back(path);
for(int j = 0; j < num; j++)
{
if(is_path[j] == 0)
{
path[i] = nums[j];
is_path[j] = 1;
dfs(i + 1,path,is_path,nums);
is_path[j] = 0;// 恢复现场
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
偷鸡做法，在C++11的标准库中有一个用来全排列的函数，可以直接使用next_permutation来进行全排列。
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
// 确保输入序列为升序
sort(nums.begin(), nums.end());
do {
ans.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
# 第五十六题 子集
这题和上一题基本相同，都是回溯类型的经典题目。这题比上一题唯一多的一点是要考虑每个元素选或者不选的情况。上一题是全都要选，这一题就要考虑当前的元素是否要进行选择。
vector<vector<int>> ans;
int num = 0;
vector<vector<int>> subsets(vector<int>& nums) {
num = nums.size();
vector<int> path;
dfs(0,path,nums);
return ans;
}
void dfs(int i, vector<int>& path, vector<int>& nums)
{
if(i == num)
{
ans.push_back(path);
return;
}
// 不选
dfs(i+1,path,nums);
// 选
path.push_back(nums[i]);
dfs(i+1,path,nums);
path.pop_back();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 第五十七题 电话号码的组合
17. 电话号码的字母组合 (opens new window)
和前两题的做法相同，但是在恢复现场部分需要继续微调。这道题目使用的是直接将后输入的值覆盖之前的值，能这样做得益于这题输出的path的长度都是固定的。
string buttons[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
int num = 0;
vector<string> ans;
vector<string> letterCombinations(string digits) {
num = digits.size();
if (num == 0) return {};
string path(num, 0);
dfs(digits,path,0);
return ans;
}
void dfs(string digits,string path,int i)
{
if(i == num)
{
ans.push_back(path);
return;
}
for(char x : buttons[digits[i]-'0'])
{
path[i] = x;
dfs(digits,path,i+1);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 第五十八题 组合总和
这一题和 [第五十六题 子集](##第五十六题 子集)做法相同，都考虑选或是不选。唯一的区别点是可以重复选择同一个元素，那么只需要在选择选时不去增加i值即可。
vector<vector<int>> ans;
int num = 0;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> path;
num = candidates.size();
dfs(0, target, path, candidates);
return ans;
}
void dfs(int i, int target, vector<int>& path, vector<int>& candidates)
{
if(target == 0)
{
ans.push_back(path);
return;
}
if(i == num || target < 0)
return;
// 不选
dfs(i+1, target, path, candidates);
// 选
path.push_back(candidates[i]);
dfs(i, target - candidates[i], path, candidates);
path.pop_back();// 恢复现场
}
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
# 第五十九题 括号生成
这题在回溯的基础上加上了括号的判断，必须是需要左右括号两两配对。所以在回溯条件中要加上判断多少个左括号就要加上多少个右括号。
vector<string> ans;
int num = 0;
vector<string> generateParenthesis(int n) {
num = n*2;
string path(num,0);
dfs(0,0,path,n);
return ans;
}
void dfs(int open,int i, string path, int n)
{
if(i == num)
{
ans.push_back(path);
return;
}
if(open < n)
{
path[i] = '(';
dfs(open+1,i+1,path,n);
}
if(i-open < open)
{
path[i] = ')';
dfs(open,i+1,path,n);
}
}
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
# 第六十题 单词搜索
就是简单的dfs当匹配到对应单词时就上下左右的去寻找能够匹配的词，再用一个标记数组来标记走过的路径防止出现死循环。当然标记数组要进行恢复。
bool ans = false;
int n = 0;
bool exist(vector<vector<char>>& board, string word) {
n = word.size();
vector<vector<int>> memo(board.size(), vector<int>(board[0].size(), 0));
for(int i = 0; i < board.size(); i++)
{
for(int j = 0; j < board[0].size();j++)
{
if(board[i][j] == word[0])
{
dfs(i,j,0,board,word,memo);
}
}
}
return ans;
}
void dfs(int i, int j, int k, vector<vector<char>>& board, string word,vector<vector<int>>& memo)
{
if(k == n)
{
ans = true;
return;
}
if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
return;
if(memo[i][j] == 1)
return;
if(board[i][j] != word[k])
return;
memo[i][j] = 1;
dfs(i-1,j,k+1,board,word,memo);
dfs(i+1,j,k+1,board,word,memo);
dfs(i,j-1,k+1,board,word,memo);
dfs(i,j+1,k+1,board,word,memo);
memo[i][j] = 0;
}
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
# 第六十一题 分割字符串
假设每对相邻字符之间有个逗号，那么就看每个逗号是选还是不选。这题用dp做更加好，但是只要有前面那句话的转化就是可以用回溯来写。该问题和 [第五十六题 子集](##第五十六题 子集)问题想用，选或是不选。需要注意i==num-1一定要选，因为单个字符一定是回文字符串。
class Solution {
public:
vector<vector<string>> ans;
int num = 0;
vector<vector<string>> partition(string s) {
num = s.size();
vector<string> path;
dfs(0,0,path,s);
return ans;
}
void dfs(int i, int start, vector<string> path, string s)
{
if(i == num)
{
ans.push_back(path);
return;
}
if(i < num-1)// 不选
dfs(i+1,start,path,s);
if(isPalindrome(s,start,i))// 选
{
path.push_back(s.substr(start,i-start+1));
dfs(i+1,i+1,path,s);
path.pop_back();
}
}
bool isPalindrome(string s, int left, int right)
{
while (left < right)
if (s[left++] != s[right--])
return false;
return true;
}
};
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
# 第六十二题 N皇后
皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。r行c列来算，同一斜线上，右上方向r + c是一个定制，左下方向r - c是一个定值。
vector<vector<string>> ans;
vector<vector<string>> solveNQueens(int n) {
vector<int> col(n), on_path(n), diag1(n * 2 - 1), diag2(n * 2 - 1);
dfs(0,n,col,on_path,diag1,diag2);
return ans;
}
void dfs(int i, int n, vector<int> col, vector<int> on_path, vector<int> diag1,vector<int> diag2)
{
if (i == n) {
vector<string> board(n);
for (int j = 0; j < n; j++)
board[j] = string(col[j], '.') + 'Q' + string(n - 1 - col[j], '.');
ans.emplace_back(board);
return;
}
for(int j = 0; j < n; j++)
{
int ij = i - j + n - 1;
if (!on_path[j] && !diag1[i + j] && !diag2[ij])
{
col[i] = j;
on_path[j] = diag1[i + j] = diag2[ij] = true;
dfs(i+1,n,col,on_path,diag1,diag2);
on_path[j] = diag1[i + j] = diag2[ij] = false; // 恢复现场
}
}
}
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
# 第六十三题 二分查找
二分查找模板题。
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left <= right)
{
int mid = (left+right)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
{
right = mid -1;
}else{
left = mid + 1;
}
}
return left;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 第六十四题 搜索二维矩阵
对于行列分别进行二分查找，可以在进行二分之前进行判断目标数是否小于二维矩阵的最小值或者大于二维矩阵的最大值，可以减少不必要的搜索，也可以避免超出数组阈值。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size() - 1;
int n = matrix[0].size() - 1;
int left = 0;
int right = m;
if (matrix[0][0] > target || matrix[m][n] < target)
return false;
while(left <= right)
{
int mid = (left+right)/2;
if(matrix[mid][0] == target)
return true;
else if(matrix[mid][0] > target)
{
right = mid -1;
}else{
left = mid + 1;
}
}
int k = right;
left = 0;
right = n;
while(left <= right)
{
int mid = (left+right)/2;
if(matrix[k][mid] == target)
return true;
else if(matrix[k][mid] > target)
{
right = mid -1;
}else{
left = mid + 1;
}
}
return false;
}
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
# 第六十五题 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)
题目要求了时间复杂度，所以要使用折半查找的方法。折半查找到目标元素，对其左右进行搜索寻找元素出现的第一个位置和最后一个位置。
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(right >= left)
{
int mid = (left+right)/2;
if(nums[mid] == target)
{
int i = mid;
int j = mid;
while(i >= 0 && nums[i] == target)
{
i--;
}
while(j <= nums.size()-1 && nums[j] == target)
{
j++;
}
return {++i,--j};
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return {-1,-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
# 第六十六题 搜索旋转排序数组
先通过第 [第六十七题 寻找旋转排序数组中的最小值](# 第六十七题 寻找旋转排序数组中的最小值)找到旋转点（ 旋转点就是数组中最小值 ），然后再通过判断目标是与数组尾部的值谁大，确定在哪个区间，然后对区间内进行查找。
int search(vector<int>& nums, int target) {
int n = nums.size()-1;
int left = 0;
int right = n;
while(left <= right)
{
int mid = (left+right)/2;
if(nums[mid] <= nums.back())
{
right = mid - 1;
}else{
left = mid + 1;
}
}
if(nums[left] == target)
return left;
if(target > nums.back())
{
return binarySearch(nums,target,0,left);
}else{
return binarySearch(nums,target,left,n);
}
return -1;
}
int binarySearch(vector<int>& nums, int target, int left,int right){
while(left <= right)
{
int mid = (left+right)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
{
right = mid -1;
}else{
left = mid + 1;
}
}
return -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
# 第六十七题 寻找旋转排序数组中的最小值
通过二分查找找到数组中最小值。
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
while(left <= right)
{
int mid = (left+right)/2;
if(nums[mid] <= nums.back())
{
right = mid - 1;
}else{
left = mid + 1;
}
}
return nums[left];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 第六十八题 寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数 (opens new window)
CV题，伟大无需多言。
class Solution {
public:
int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
*/
int m = nums1.size();
int n = nums2.size();
int index1 = 0, index2 = 0;
while (true) {
// 边界情况
if (index1 == m) {
return nums2[index2 + k - 1];
}
if (index2 == n) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}
// 正常情况
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int totalLength = nums1.size() + nums2.size();
if (totalLength % 2 == 1) {
return getKthElement(nums1, nums2, (totalLength + 1) / 2);
}
else {
return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
}
}
};
//作者：力扣官方题解
//链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/258842/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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