两数之和

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<int> twoSum(vector<int>& nums, int target) {
       map<int,int> m;
        vector<int> ret;
        for(int i=0;i<nums.size();i++)
        {
	      
            auto it = m.find(target-nums[i]);
            //定义迭代器，如果指向end就是没找到，否则就是找到了，并存下下标
            if(it!=m.end())
            {
                ret.push_back(it->second);
                ret.push_back(i);
                break;
            }
            else
            {
                m.insert({nums[i],i});
            }
        }
        return ret;
    }   
};
//哈希做法

字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//本题依然是哈希的思路，如果两个字串乘积相同就放在一起
class Solution {
public:
    int m[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};
    //质数解决哈希冲突
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> res[strs.size()];
        unordered_map<int, int> map;//<编码值，res下标>
        int cnt = 0, mod = 1e9+7;
        for(const auto &s : strs){//排序
            long v = 1;
            for(const auto &c : s){
                v *= m[c-'a'];
                v %= mod;//取模防止溢出
            }  
            if(!map.count(v)){
                res[cnt].push_back(s);
                map[v] = cnt++;
            }else   res[map[v]].push_back(s);
        }
        return {res, res + cnt};
    }
};

最长连续序列

这实际上是集合的应用了，算是哈希表的一种了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> uset;
        //将数组中的值加入到哈希表中，便于查找，顺带降重，提高查找效率
        for(auto num:nums)
            uset.insert(num);
        //遍历哈希表
        for(auto x:uset){
            //从连续序列的第一个数开始查找
            if(!uset.count(x - 1)){ //如果x前一位数不存在，则说明x是连续序列的第一个数
                int y = x;
                //这里直接在哈希表中查找y+1，当y+1不存在时，说明正好查找到了y
                while(uset.count(y+1)){
                    y++;
                }
                res = max(res,y-x+1);
            }
        }
        return res;
    }
};

移动0

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
//开两个下标，如果数组遍历不等于0，则往前挪，等于0则不操作，最后补齐0即可。
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int index = 0 ;
        int indexNum = 0 ;
        while ( indexNum < nums.size() )
        {
            if ( nums[indexNum] != 0 )
            {
                nums[index] = nums[indexNum] ;
                index ++ ;
            }
            indexNum ++ ;
        }
        //找到不为0，直接记录
        while ( index < nums.size() )
        {
            nums[index] = 0 ;
            index ++ ;
        }
    }
};
//接下来就是填补0的过程

盛最多水的容器

暴力做法

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
class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size()<1)
        {
            return 0;
        }
        
        int chang=0;
        int kuan=height[0];
        int s=0;
        
        for(int i=0;i<height.size();i++)
        {
            for(int j=i+1;j<height.size();j++)
            {
                kuan=min(height[i],height[j]);
                chang++;
                if(s<chang*kuan)
                {
                    s=chang*kuan;
                }
            }
            chang=0;
 
        }
        return s;
    }
};
//两层循环枚举进行，这样实际上必定超时，不然对不起中等

于是采取双指针加贪心的思路进行求解

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:
    int maxArea(vector<int>& height)  {
        if(height.size()<1)
        {
            return 0;
        }
        int left=0;
        int right=height.size()-1;
        int s=0;   
        while(left<right)
        {
            int tmp=min(height[left],height[right]);
            s=max((right-left)*tmp,s);
            if(height[left]>height[right])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return s;
    }
};
//直接从两边没枚举，每次记录答案，如果左边高度高，我们自然想办法保存，于是右边左移，反之则同理

三数之和

暴力做法依然时间不够

三层循环不够的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        set<vector<int>> s;

        sort(nums.begin(), nums.end());
        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len; j++) {
                for (int k = j + 1; k < len; k++)
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        vector<int> v = { nums[i], nums[j], nums[k] };
                        s.insert(v);
                    }
            }
        }

        vector<vector<int>> ans;
        for (const vector<int>& v : s) ans.push_back(v);
        return 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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> ans;

        sort(nums.begin(), nums.end());
        for (int i = 0; i < len; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue; // 跳过i代表的重复数字
            unordered_map<int, int> m;
            for (int j = i + 1; j < len; j++) {
                if (m.count(-nums[i] - nums[j])) {
                    ans.push_back({ nums[i], nums[j], -nums[i] - nums[j] });
                    while (j + 1 < len && nums[j] == nums[j + 1]) j++; // 跳过j代表的重复数字
                }
                else m.insert(pair<int, int>(nums[j], j)); // 我们是在nums[i]后面的数字寻找nums[j]和nums[k]（即-nums[i] - nums[j]），所以这里存储nums[j]
            }
        }
        
        return ans;
    }
};


双指针法：

详细介绍一下，我们枚举一重循环，定义两个指针，一个从i+1开始，一个从len-1开始，如果==0，就记录，并且一个加加，一个减减，进行逼近，如果大于0，明显我们排完序后的话右指针要减减，如果小于0我们左指针要加加。

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> ans;

        sort(nums.begin(), nums.end());
        for (int i = 0; i < len; i++) {
            int left = i + 1, right = len - 1;
            if (i != 0 && nums[i] == nums[i - 1]) continue; // 跳过nums[i]所表示的重复数字
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    ans.push_back({ nums[i], nums[left], nums[right] });
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++; // 跳过左边界重复数字
                    while (left < right && nums[right] == nums[right + 1]) right--; // 跳过右边界重复数字
                }
                else if (nums[i] + nums[left] + nums[right] > 0) right--;
                else left++;
            }
        }   
        return ans;
    }
};

接雨水

本题实际上就是个单调栈，找到左边第一个比他大的，找到右边第一个比他大的，然后求解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
	int trap(vector<int>& height) {
		int ans = 0;
		stack<int> st;
		for (int i = 0; i < height.size(); i++) {
			while (!st.empty() && height[st.top()] < height[i]) {
				int bottom = st.top(); //取底
				st.pop();
                if (st.empty()) //发现没有左边界
                    break;
 
				int left = st.top();
				int right = i;
				int h = min(height[left], height[right]) - height[bottom];
				ans += h * (right - left - 1);
			}
			st.push(i);
		}
 
		return ans;
	}
};

最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度

好像还是哈希表的应用，但要加一个指针的思想罢了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        int res = 0;
        int begin = 0, end = 0;
        set<char> count_ch;
        for(int i = 0; i < s.size(); i++)
        {
            while(count_ch.count(s[i]) != 0)
            {
                count_ch.erase(s[begin++]);
            }
            count_ch.insert(s[i]);
            end++;
            res = max(end - begin, res);
        }
        return res;
    }
};

无重复字符的最长子串C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;   
        if(s.size() < p.size())
            return res;
        int plen = p.size();
        vector<int> vp(26, 0), vtmp(26, 0);//初始化数组长度为26，每个下标值对应小写字母的ASCII码值-'a'
        for (auto x : p)
            vp[x - 'a']++;
        for (int i = 0; i < s.size(); i++)
        {
            if(i >= plen)//超过p的长度开始，i-plen的字符从滑动窗口删除
                vtmp[s[i - plen] - 'a']--;
            vtmp[s[i] - 'a']++;//每次滑动窗口向右滑动一个字符
            if(vtmp == vp)
                res.push_back(i - plen + 1);
        }
        return res;
    }
};

和为k的子数组C++

前缀和加暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> sum(n+1,0);
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+nums[i-1];
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if(sum[j+1]-sum[i]==k) count+=1;
            }
        }
        return count;
    }
};

前缀和加哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n=nums.size();
        int sum=0,res=0;
        unordered_map<int,int> m;
        m[0]=1;
        for(int i=0;i<n;i++){
            sum+=nums[i];
            res+=m[sum-k];
            m[sum]+=1;
        }
        return res;
    }
};

滑动窗口最大值

实际上就是一个单调队列，维护一个单调递减的就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() == 0) return nums;
        vector<int> arr;
        deque<int> dq;
        for(int i = 0; i < nums.size(); i++)
        {
            while(!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();
            if(!dq.empty() && dq.front() <= (i - k)) dq.pop_front();
            dq.push_back(i);
            if(i >= k - 1) arr.push_back(nums[dq.front()]);
        }
        return arr;
    }
};

LeetCode 76. 最小覆盖子串

依然滑动窗口，满足就收缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        for (auto c: t) ht[c] ++ ;

        string res;
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); i ++ ) {
            hs[s[i]] ++ ;
            if (hs[s[i]] <= ht[s[i]]) cnt ++ ;

            while (hs[s[j]] > ht[s[j]]) hs[s[j ++ ]] -- ;
            if (cnt == t.size()) {
                if (res.empty() || i - j + 1 < res.size())
                    res = s.substr(j, i - j + 1);
            }
        }

        return res;
    }
};

最大子数组和

暴力解法自然是不能少

1
2
3
4
5
6
7
8
9
10
11
12
13
int MaxSumOfSub1(){
    int res=-INF;
    for(int i=1;i<=cnt;i++){
        for(int j=i+1;j<=cnt;j++){
            int sum=0;
            for(int k=i;k<=j;k++)
                sum+=nums[k];
            res=max(res,sum);
        }
    }
    return res;
}

前缀和做法

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
    int n = nums.length;
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            res = Math.max(res, sum);
        }
    }
    return res;
}

上面两种应该会被卡，还是康康正解罢

动态规划

如果加上这个数字比这个数字还小，为什么要加呢？（核心）

除此之外就是记录答案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};
。

合并区间

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        //空集
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};
//排序加贪心而已，排序左端点，贪心右端点

轮转数组

第一种方法：暴力做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int temp[n];
        memset(temp,0,sizeof(int)*n);
        k %= n;
        for(int i = 0;i < k;i++){
        	temp[i] = nums[n-k+i];
        }
        for(int i = k;i < n;i++){
        	temp[i] = nums[i-k];
        }
        for(int i = 0;i < n;i++)
        	nums[i] = temp[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
25
26
27
28
29
30
31
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        if(k == 0) 
            return;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    void reverse(vector<int>&nums,int l,int r){
        while (l < r) {
            nums[l] = nums[l] ^ nums[r];
            nums[r] = nums[l] ^ nums[r];
            nums[l] = nums[l] ^ nums[r];
            l++;
            r--;
        }
	}
};
//reverse部分的重写
/*void reverse(vector<int>&nums,int l,int r){
        while (l < r) {
            nums[l] = nums[l] + nums[r];
            nums[r] = nums[l] - nums[r];
            nums[l] = nums[l] - nums[r];
            l++;
            r--;
        }
*/

除自身以外数组的乘积(C++)

前缀和的另一种模式前缀积

？

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
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> answer(length);

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i];//其实就是等到i-1轮的时候用的
        }
        return answer;
    }
};

Leetcode 41：缺失的第一个正数

讲述一下解法，既然不能开空间，就要想办法（好像是废话）

由于我们如果有 1 2 3 4 ，那么我们未尝不可以就是交换1到num[0],2到num[1]，这样使得每一个数在自己的位置，然后遍历完就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;++i)
        {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1])
        {
            swap(nums[i], nums[nums[i] - 1]);
        }
        }
        for(int i=0;i<n;++i)
        {
            if(nums[i]!=i+1)
                return i+1;
        }
        return n+1;
            
}
};

矩阵置0

有点暴力好像是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int i=matrix.size();
        int j=matrix[0].size();
        vector<int> hang(i);
        vector<int> lie(j);
        for(int m=0;m<i;m++){
            for(int n=0;n<j;n++){
                if(!matrix[m][n]){             //找出0元素所在的行和列
                    hang[m]=lie[n]=true;
                }
            }
        }
        for(int m=0;m<i;m++){                 //使对应行和列的元素均设为0
            for(int n=0;n<j;n++){
                if(hang[m] || lie[n])
                matrix[m][n]=0;
            }
        }
 
    }
};

这种就更暴力了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return;
        vector<vector<int>> arr(matrix);                 //将原矩阵进行复制
        const int i = matrix.size(), j = matrix[0].size();  //const保证变量值不被改变
        for (int m = 0; m < i; m++) {
            for (int n = 0; n < j; n++) {
                if (arr[m][n] == 0) {                   //找到0元素所在位置
                    for (int k = 0; k < j; k++) {
                        matrix[m][k] = 0;               //使0所在的一列元素均为0
                    }
                    for (int t = 0; t < i; t++) {
                        matrix[t][n] = 0;               //使0所在的一行元素均为0
                    }
                }
            }
        }
    }
};

螺旋矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector <int> ans;
        if(matrix.empty()) return ans; //若数组为空，直接返回答案
        int u = 0; //赋值上下左右边界
        int d = matrix.size() - 1;
        int l = 0;
        int r = matrix[0].size() - 1;
        while(true)
        {
            for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
            if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
            for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
            if(-- r < l) break; //重新设定有边界
            for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
            if(-- d < u) break; //重新设定下边界
            for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
            if(++ l > r) break; //重新设定左边界
        }
        return ans;
    }
};
//右下左上的一个思路，然后重新设定边界

旋转矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
};
//交换四个值的方法
//可以画一个正方形对角线分成四部分进行理解。

搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

初始值在左下角，大于target向上移动，小于target向右移动。

给我一种双指针的美感

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int xloc = matrix.size() - 1, yloc = 0;
        while (yloc < matrix[0].size() && xloc >= 0){
            if (matrix[xloc][yloc] == target){
                return true;
            }else if(matrix[xloc][yloc] > target){
                xloc--;
            }else{
                yloc++;
            }
        }
        return false;
    }
};

搜索插入位置

二分方法

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:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return 0;
        
        /*如果目标值大于 nums 里的最大值，则将其插入到数组的末尾*/ 
    	if (target > nums[n-1]) return n;
    	
    	/*将在区间 [0, n - 1] 内查找目标索引*/ 
    	int left = 0, right = n - 1; 
    	while (left < right) {
    		int mid = left + (right - left) / 2; 
    		if (target > nums[mid]) { //严格小于 target 的元素一定不是解 
    			//下一轮搜索区间是 [mid + 1, right] 
    			left = mid + 1;
    		} else { //严格大于等于 target 的元素有可能是解
				//下一轮搜索区间是 [left, mid] 
    			right = mid;
    		}
    	}
    	
    	return left;
    }
};

搜索二维矩阵

将二维下标转换为一维下标，相当于在一维数组上做二分查找（推荐）

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 searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

//一次二分的机会
//就是转换

在排序数组中查找元素的第一个和最后一个位置

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans(2, -1);
        ans[0] = getleftposition(nums, target);
        ans[1] = getrightposition(nums, target);
        return ans;
    }

private:
    int getleftposition(vector<int>& nums, int target) {
        //规定：左闭右闭区间 
        int left = 0, right = nums.size() - 1; 
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(target > nums[mid]) {
                //target在mid值右侧，缩小左半区间
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                // target == nums[mid]
                // 缩小右半区间，在左半区间继续寻找是否存在target
                right = mid - 1;
            }
        }

        if(left == nums.size() || nums[left] != target)
            return -1;
        
        return left;
    }   

    int getrightposition(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(target < nums[mid]) {
                right = mid - 1;
            } else if (target == nums[mid]) {
                // 往右边区间继续找是不是最后一个target
                left = mid + 1;
            } else {
                // target > nums[mid]
                left = mid + 1;
            }
        }

        if(right == - 1 || nums[right] != target) {
            return -1;
        }

        return right;
    } 
};

搜索旋转排序数组

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                // left 到 mid 是顺序区间
                (target >= nums[left] && target < nums[mid]) ? right = mid - 1 : left = mid + 1;
            }
            else {
                // mid 到 right 是顺序区间
                (target > nums[mid] && target <= nums[right]) ? left = mid + 1 : right = mid - 1;
            }
        }
        return -1;
    }
};
/*
定理一：只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。

定理二：判断顺序区间还是乱序区间，只需要对比 left 和 right 是否是顺序对即可，left <= right，顺序区间，否则乱序区间。

定理三：每次二分都会至少存在一个顺序区间。

通过不断的用Mid二分，根据定理二，将整个数组划分成顺序区间和乱序区间，然后利用定理一判断target是否在顺序区间，如果在顺序区间，下次循环就直接取顺序区间，如果不在，那么下次循环就取乱序区间。
*/

寻找旋转排序数组的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            }
            else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
};

有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};


最小栈

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 MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

字符串解码C++

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
class Solution
{
public:
    string decodeString(string s)
    {

        stack<int> nums;
        int num = 0;
        stack<string> st;
        string tmp;
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                num = 10 * num + s[i] - '0';
            }
            else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
            {
                tmp.push_back(s[i]);
            }
            else if (s[i] == '[')
            {
                nums.push(num);
                num = 0;
                st.push(tmp);
                tmp.clear();
            }
            else
            {
                int cnt = nums.top();
                nums.pop();
                for (int j = 0; j < cnt; j++)
                {
                    st.top() += tmp;
                }
                tmp = st.top();
                st.pop();
            }
        }

        return tmp;
    }
};

每日温度

一眼单调栈啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {	//循环，如果找到了最近的较高温度，出栈
                int previousIndex = s.top();
                ans[previousIndex] = i - previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};


柱状图中最大的矩形C++

还是单调栈嘛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 版本二
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.push(0);
        int result = 0;
        for (int i = 1; i < heights.size(); i++) {
            while (heights[i] < heights[st.top()]) {
                int mid = st.top();
                st.pop();
                int w = i - st.top() - 1;
                int h = heights[mid];
                result = max(result, w * h);
            }
            st.push(i);
        }
        return result;
    }
};

数组中第k个最大元素

大根堆啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution 
{
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int, vector<int>, less<int>> maxHeap;
        for (int x : nums)
            maxHeap.push(x);
        for (int _ = 0; _ < k - 1; _ ++)
            maxHeap.pop();
        return maxHeap.top();
    }
};


数组中前k个高频元素

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
// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};


只出现一次的数字

异或性质

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;
        return ret;
    }
};


多数元素

第一种哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

第二种哈希

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};


颜色分类

直接开始循环就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                swap(nums[i], nums[ptr]);
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums[i], nums[ptr]);
                ++ptr;
            }
        }
    }
};


下一个排列

不讲武德的方法

1
2
3
4
5
6
class Solution {
public:
   void nextPermutation(vector<int>& nums) {
       next_permutation(nums.begin(), nums.end());
   }
};

讲武德的方法

先找到逆序的

再找到第一个比他大的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};


买卖股票的最佳时机

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = (int)prices.size(), ans = 0;
        for (int i = 0; i < n; ++i){
            for (int j = i + 1; j < n; ++j) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
};

贪心做法

记录历史最低，每次思考从最低开始买

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true; // 只有一个元素，就是能达到
        for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};
//主要是覆盖范围，如果覆盖范围足够就没问题了

跳跃游戏2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0;
        int begin = 0;
        int end  = 0;    
        //[begin, end]
        
        while(end < nums.size()-1){
            int temp = 0;
            for(int i = begin; i <= end; i++){
                temp = max(nums[i]+i, temp);
            }
            begin = end+1;
            end = temp;
            ans++;
        }
        return ans;
    }
};

划分字母区间

找到最远边界的过程，然后放进去即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

动态规划篇

爬楼梯

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:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

//优化后
    // 版本二
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 杨辉三角

如此经典的动态规划

```C++
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            //边界条件
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
                //递推公式挺好
            }
        }
        return ret;
    }
};


打家劫舍

动态规划的的四个解题步骤是：

  • 定义子问题
  • 写出子问题的递推关系
  • 确定 DP 数组的计算顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        vector<int> dp = vector<int>(size, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[size - 1];
    }
};


完全平方数

刚看到是不是有一点小懵逼

实际上想想01背包

不就是装满吗

但又想到样例12=4+4+4

明显是完成背包

因此两重正序循环即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                minn = min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
};

零钱兑换

依然是完全背包的变式

只是最后需要特判一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

最长递增子序列

最长上升子序列

这个还是弱了点

实际上可以二分优化，队列优化

然而这样写就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};


乘积最大子数组

这道题不是那么简单

因为最优解不一定是由前一个最优解转移过来，而可能由最差解转移过来，考虑负数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector <int> maxF(nums), minF(nums);
        for (int i = 1; i < nums.size(); ++i) {
            maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i]));
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

分割等和子集

一眼01背包，acmer太熟悉了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), m = 0;
        for (auto x : nums) m += x;
        if (m & 1) return false;
        m /= 2;
        
        vector<int> f(m + 1);
        for (auto x : nums){
            for (int j = m; j >=x ; j --)
                f[j] = max(f[j], f[j - x] + x);
        }
        return f[m] == m;

    }
};

不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 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
30
31
class Solution {
public:
    // 5. 动态规划：从起始点到终点
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        // 状态定义：dp[i][j] 表示从 [0,0] 到 [i,j] 的最小路径和
        vector<vector<int>> dp(m, vector<int>(n));

        // 状态初始化
        dp[0][0] = grid[0][0];

        // 状态转移
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j != 0) { //第一行
                    dp[i][j] = grid[i][j] + dp[i][j - 1];
                } else if (i != 0 && j == 0) { // 第一列
                    dp[i][j] = grid[i][j] + dp[i - 1][j];
                } else if (i != 0 && j != 0) {
                    dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 返回结果
        return dp[m - 1][n - 1];
    }
};


最长公共子序列

经典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            char c1 = text1.at(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.at(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][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
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        for (int i = 0; i < dp.size(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < dp[0].size(); j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[i].size(); j++) {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp.back().back();
    }
};


全排列

库函数大大滴好

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        do {
            result.emplace_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return result;
    }
};

正经回溯步骤

首先，如果我们需要输出搜素中我们的选择，这时候我们可能需要传入一个表示当前走到哪里的参数，第二个，如果我们需要计算出和最大或者是最小问题，我们可能传入一个参数，用来表示他们的和，第三个参数，也就是我们经常说的步数，我们可能要记录我们走了多少步，所以我们往往需要一个step的参数，来表示我们走了多少步，又或者，我们需要选完这个数后，我们要选比这个数大的数，我们此时也需要记录我们当前的数。

初步谈完了关于参数的传入，我们来谈谈关于终止条件，为什么要有终止条件呢，这是很重要的，不然我们的搜索不会停止，无法得到我们需要的结构，搜说条件往往是我们已经遇到死胡同了，接下来没有路可以走了，或者是说，我们已经收集好我们要的东西了，我们不需要再进行搜素了，这些都是需要我们进行终止的，而往往伴随着终止的是一个更新，我们需要更新我们最大值啊1，或是更新我们的最小值啊，又或者进行输出啊，当然是满足我们终止的条件下进行的啦，然后别忘了，我们在终止完后要return哦，不然你搜完第一次就卡在那里了，哪里能达到我们搜索的目的呢，你说是吧。

再来谈谈我们搜说的核心部分，首先我们要试探一下，试探这个点的下一个点有没有被搜索过，也就是说我们在前面要有一个东西，也就是一个判断的数组，来表示我们的下一个东西有没有被搜索过，如果有，可以continue，如果没有，那就标记下一个点为被搜索的状态，并进行递归调用我们的dfs，传入我们的下一个搜索点，注意参数往往要改变，也许是步数的加一，也许是和的加，也可以是下一个点的值，都要结合题目要求具体分析，然后也是比较重要的一点，我们需要进行清理现场，就是说我们要把我们前面标记的拿掉，让他可选择，这样我们就完成了整个dfs的搜索过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
private:
    vector<vector<int>> res;
    void dfs(vector<int> nums, int x) {
        if (x == nums.size() - 1) {
            res.push_back(nums);      // 添加排列方案
            return;
        }
        for (int i = x; i < nums.size(); i++) {
            swap(nums[i], nums[x]);   // 交换，将 nums[i] 固定在第 x 位
            dfs(nums, x + 1);         // 开启固定第 x + 1 位元素
            swap(nums[i], nums[x]);   // 恢复交换
        }
    }
};

子集

围绕选与不选进行深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    void dfs(int cur, vector<int>& nums) {
        if (cur == nums.size()) {
            ans.push_back(t);
            return;
        }
        t.push_back(nums[cur]);
        dfs(cur + 1, nums);
        t.pop_back();
        dfs(cur + 1, nums);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0, nums);
        return 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
class Solution {
public:
    string path = "";  //利用该字符串记录每次数据
    vector<string> ans; //利用该数组记录每次path保存的数据
    unordered_map<char,string> dic{   //将数字和字母对应
        {'2',"abc"},
        {'3',"def"},
        {'4',"ghi"},
        {'5',"jkl"},
        {'6',"mno"},
        {'7',"pqrs"},
        {'8',"tuv"},
        {'9',"wxyz"}
    };
    void dfs(int index,string digits)
    {
        if(index == digits.length()){  //index代表是digits中第几个数字下标
            ans.push_back(path);
        }
        string str = dic[digits[index]];
        for(int i = 0;i<str.length();i++){  // 回溯算法的递归嵌套
            path += str[i];  //将这层数据保存
            dfs(index+1,digits); //深层进入
            path.pop_back();  // 恢复现场
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.empty()){ //若为空需要进行特殊处理，因为全局变量path初始化为""，若不进行该处理，则最终为空的结果为[""],而不是[]
            return ans;
        }
        dfs(0,digits);
        return 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
class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> combine;
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }
};

括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        dfs("", n, n);
        return res;
    }
private:
    vector<string> res;
    void dfs(const string& str, int left, int right) {
        if (left < 0 || left > right)  // 出现类似 ()) )) 这种格式都是错误的不用再继续了
            return;
        if (left == 0 && right == 0) {
            res.push_back(str);
            return;
        }
        dfs(str + '(', left - 1, right);
        dfs(str + ')', left, right - 1);
    }
};

链表相关题目

下面有关于列表的概要讲述。

有两种常用的列表实现，分别为数组列表和链表。如果我们想在列表中存储值，它们是如何实现的呢？

数组列表底层是使用数组存储值，我们可以通过索引在 O(1)的时间访问列表任何位置的值，这是由基于内存寻址的方式。 链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 O(n)的时间，因为要通过指针获取到下一个位置的节点。

总结一下数组的优缺点：

  • 优点：可以根据偏移实现快速的随机读写。
  • 缺点：扩容，增删元素极慢。

面试问题总结 无法高效获取长度，无法根据偏移快速访问元素，是链表的两个劣势。然而面试的时候经常碰见诸如获取倒数第k个元素，获取中间位置的元素，判断链表是否存在环，判断环的长度等和长度与位置有关的问题。这些问题都可以通过灵活运用双指针来解决。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};
//两个结点指针分别走，根据数学推导实际上只需要走对方的一部分，走两次就可以走到同一个点

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

//需要记录，不然无法进行

回文链表

题解真的是天才，竟然把链表弄成数组，我这个nt还想着反转一次链表逐个比对，乐。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};

环形链表

应该不难想，快慢指针各自移动，有环你两肯定遇上，没有就不好说了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

环形链表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
/*
解题思路：
这类链表题目一般都是使用双指针法解决的，例如寻找距离尾部第 K 个节点、寻找环入口、寻找公共尾部入口等。

在本题的求解过程中，双指针会产生两次“相遇”。

    f=2s （快指针每次2步，路程刚好2倍）

f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb
  从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步 
*/
    class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (true) {
            if (fast == nullptr || fast->next == nullptr) return nullptr;
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

合并两个有序链表·

双指针写法

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:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dum = new ListNode(0);
        ListNode* cur = dum;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            }
            else {
                cur->next = list2;
                list2 = list2->next;
            }
            //找到比较小的接上即可，注意链表要移动
            cur = cur->next;
            //现在这个也需要移动
        }
        cur->next = list1 != nullptr ? list1 : list2;
        //有一个是空的话直接接上就可以了
        return dum->next;
    }
};
//这种方法比较好理解

递归写法

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
/*
，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
我们直接将以上递归过程建模，同时需要考虑边界情况。

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
返回值：每一层调用都返回排序好的链表头
O(m+n)
*/
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
};

两数相加

对齐的方法题解大大的好

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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1=1;//记录l1的长度
        int len2=1;//记录l2的长度
        ListNode* p=l1;
        ListNode* q=l2;
        while(p->next!=NULL)//获取l1的长度
        {
            len1++;
            p=p->next;
        }
        while(q->next!=NULL)//获取l2的长度
        {
            len2++;
            q=q->next;
        }
        if(len1>len2)//l1较长，在l2末尾补零
        {
            for(int i=1;i<=len1-len2;i++)
            {
                q->next=new ListNode(0);
                q=q->next;
            }
        }
        else//l2较长，在l1末尾补零
        {
            for(int i=1;i<=len2-len1;i++)
            {
                p->next=new ListNode(0);
                p=p->next;
            }
        }
        p=l1;
        q=l2;
        bool count=false;//记录进位
        ListNode* l3=new ListNode(-1);//存放结果的链表
        ListNode* w=l3;//l3的移动指针
        int i=0;//记录相加结果
        while(p!=NULL&&q!=NULL)
        {
            i=count+p->val+q->val;
            w->next=new ListNode(i%10);
            count=i>=10?true:false;
            w=w->next;
            p=p->next;
            q=q->next;
        }
        if(count)//若最后还有进位
        {
            w->next=new ListNode(1);
            w=w->next;
        }
        return l3->next; 
    }
};

删除链表的倒数第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
class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return 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
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* temp = dummyHead;
        while (temp->next != nullptr && temp->next->next != nullptr) {
            ListNode* node1 = temp->next;
            ListNode* node2 = temp->next->next;
            //分别赋值node 1,node 2
        
            temp->next = node2;
            //指向node2
            node1->next = node2->next;
            //node 1指向node 2的下一个
            node2->next = node1;
            //这样node 2才能指向node 1
            temp = node1;
            //最后重新更新temp
        }
        ListNode* ans = dummyHead->next;
        delete dummyHead;
        return ans;
    }
};

二叉树世界

一般是递归写法，毕竟树很难离得开递归。

二叉树的中序遍历

按照访问左子树——根节点——右子树的方式遍历这棵树

  • 前序遍历：打印 - 左 - 右
  • 中序遍历：左 - 打印 - 右
  • 后序遍历：左 - 右 - 打印
  • 终止条件：当前节点为空时
  • 函数内：递归的调用左节点，打印当前节点，再递归调用右节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};

二叉树的最大深度

知识前置

3 个树的重要概念：层次、深度、高度。

二叉树的层次是从根节点算起，根节点是第一层，依次往下类推。

二叉树的高度是从叶子节点算起，叶子节点高度是 1，依次往上类推。可以看成是高楼，从下往上看，也就是自底向上看。

通过图，也可以看出，二叉树的深度和层次是完全对应的，最大深度为最大层次数。二叉树的深度和高度正好相反。

(1) 自顶向下

自顶向下，就是从根节点递归到叶子节点，计算这一条路径上的深度，并更新维护最大深度。

这个是正儿八经的求深度。每次先维护根节点的深度，再递归左子树、右子树。

(2) 自底向上

自底向上，从叶子节点开始，一层一层的向上，最终汇集在根节点。

总结：dfs

1
2
3
4
5
6
7
8
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

翻转二叉树

好精美的图，偷了

226_2.gif

交换一下左右节点，然后再递归的交换左节点，右节点

显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root为根节点的整棵子树的翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};


对称二叉树

根据题目的描述，镜像对称，就是左右两边相等，也就是左子树和右子树是相当的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return root == nullptr || recur(root->left, root->right);
    }
private:
    bool recur(TreeNode* L, TreeNode* R) {
        if (L == nullptr && R == nullptr) return true;
        //如果都是空并且都成立就没问题了
        if (L == nullptr || R == nullptr || L->val != R->val) return false;
        //有一个提前为空，或者比较的时候不等于了
        return recur(L->left, R->right) && recur(L->right, R->left);
        //比较左子树的左和右子树的右
        //比较左子树
    }
};

二叉树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int ans;
    int depth(TreeNode* root){
        if (root == NULL) return 0;
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans, L + R + 1);
        return max(L, R) + 1;
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

岛屿数量

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 111，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 111 都会被重新标记为 000。

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
class Solution {
private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();

        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
};

腐烂的橘子

我认为还是一眼Bfs的

把初始时的腐烂橘子加入队列，并计算新鲜橘子的个数。

BFS 将预处理阶段找到的腐烂橘子向四个方向开始腐烂，需要记录队列的初始长度，当长度减少到0时算一轮感染。再进行次轮感染，直到队列为空。

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
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int min = 0, 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});
        }
        vector<pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        while(!q.empty()) {
            int n = q.size();
            bool rotten = false;
            for(int i = 0; i < n; i++) {
                auto x = q.front();
                q.pop();
                for(auto cur: dirs) {
                    int i = x.first + cur.first;
                    int j = x.second + cur.second;
                    if(i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1) {
                        grid[i][j] = 2;
                        q.push({i, j});
                        fresh--;
                        rotten = true;
                    }
                }
            }
            if(rotten) min++;
        } 
        return fresh ? -1 : min;
    }
};

课程表

对于一个有向图中的一个顶点，它的入度是指指向该顶点的边的数量，而出度是指从该顶点出发的边的数量。如果一个顶点的入度为0，则称其为源点；如果一个顶点的出度为0，则称其为汇点。

方法一 拓扑排序

课程之间的关系可以用有向图来表示，能完成课程的依据就是课程组成的有向图中没有环，可以通过拓扑排序来实现。

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //所有课程的入度
        vector<int> ingree(numCourses, 0);
        //保存课程和先修课程之间的关系
        unordered_map<int, vector<int>> preCourse;
        for (int i = 0; i < prerequisites.size(); ++i){
            preCourse[prerequisites[i][0]].push_back(prerequisites[i][1]);
            ingree[prerequisites[i][1]]++;
        }
       
        queue<int> zero_ingree;
        int count = 0;
        for (int i = 0; i < numCourses; ++i) {
            //所有入度为0的课程入队列
            if (!ingree[i]) {
                zero_ingree.push(i);
                ++count;
            } 
        }

        while(!zero_ingree.empty()) {
            int cur_course = zero_ingree.front();
            zero_ingree.pop();
            for (int i = 0; i < preCourse[cur_course].size(); ++i) {
                    //当前入度为0的课程对应的先修课程入度减1
                    --ingree[preCourse[cur_course][i]];
                    if (!ingree[preCourse[cur_course][i]]) {
                        //入度为0的课程入队列
                        zero_ingree.push(preCourse[cur_course][i]);
                        ++count;
                    }
            }
        }
        //所有课程的入度减为0，说明课程可以修完
        if (count == numCourses) return true;
        return false;
    }
};

方法二 深度优先搜索(DFS)

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 {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

public:
    void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            else if (visited[v] == 1) {
                valid = false;
                return;
                /*
                如果 v为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；
                */
            }
        }
        visited[u] = 2;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return valid;
    }
};