力扣hot100二番ak

哈希

两数之和

使用哈希表存储数组中每个数字和它的下标
遍历每个数字，同时在哈希表中遍历target - nums[i]，判断其在哈希表中是否存在
如果存在，则推入vector，并break
返回ans

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        int n = nums.size();
        for(int i = 0; i < n; i ++){
            numMap[nums[i]] = i;
        }
        vector<int> ans;
        for(int i = 0; i < n; i ++){
            if(numMap.count(target - nums[i]) && i != numMap[target - nums[i]]){
                ans.push_back(i);
                ans.push_back(numMap[target - nums[i]]);
                break;
            }
        }

        return ans;
    }
};

最长连续序列

使用的是unordered_set
可以通过numSet.count(i - 1)来判断这个数是否可以继续遍历
- 如果numSet.count(i - 1) == 1，那么这个数一定不是最长序列的开头
需要遍历unordered_set，遍历数组的话会导致时间复杂度异常的大
- 例子：1,1, ... , 2, 3, 5, ...，前一半都是1。如果遍历数组的话，会导致前一半的每个1都会走一个时间复杂度为O(n)的遍历，总的时间复杂度达到了 $O (n^{2})$

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int ans = 0;
        for(auto num: numSet){
            if(numSet.count(num - 1))
                continue;
            int length = 1;
            int t = num;
            while(numSet.count(++ t))
                length ++;
            ans = max(ans, length);
        }

        return ans;
    }
};

双指针

移动零

左指针指向当前遍历到的位置，右指针指向原数组（未插入0时中的元素，避免遍历到0）
当左指针指向的元素为0时，数组push_back(0)，并erase当前左指针指向的元素。right --
直至left >= right，遍历停止

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right){
            if(nums[left] != 0){
                left ++;
            }
            else{
                nums.erase(nums.begin() + left);
                nums.push_back(0);
                right --;
            }
        }
    }
};

盛最多水的容器

左指针和右指针分别指向左右边界，并向中间移动
首先移动两个指针中高度较小的那个，这样才更有机会获得最大值
直至两个指针相遇，遍历停止

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 左右指针同时开始遍历
        // 那个指针的高度低，哪个就移动，这样才更有机会获得最大值
        int left = 0, right = height.size() - 1;
        // int leftMax = left, rightMax = right;
        int ans = 0;
        while(left < right){
            int w = right - left;
            int h = min(height[right], height[left]);
            ans = max(ans, w * h);
            if(height[right] > height[left])
                left ++;
            else
                right --;
        }
        return ans;
    }
};

三数之和

自己写了一个超长代码
时间复杂度是 $O (n^{2})$
转化为两数之和问题
利用双指针查找等于特定和的两个数
为了避免同样的组合被反复查找，设立状态数组记录每个数是否被遍历过
开始时左右指针分别指向左右边界（左边界：主循环遍历到的数i下一个数i + 1，右边界：n - 1）
对于0的处理，如果最大元素和最小元素都是0，直接返回0

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(*min_element(nums.begin(), nums.end()) == 0 && *max_element(nums.begin(), nums.end()) == 0)
        return 0;
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> st(n);
        for(int i = 0; i < n && nums[i] <= 0; i ++){
            bool flag = false;
            vector<int> t;
            t.push_back(nums[i]);
            int l = i + 1, r = n - 1;
            int target = 0 - nums[i];
            while(l < r){
                if(st[l] && st[r])
                    continue;
                if(nums[l] + nums[r] == target){
                    cout << 1 << endl;
                    flag = true;
                    st[l] = 1;
                    st[r] = 1;
                    t.push_back(nums[l]);
                    t.push_back(nums[r]);
                    ans.push_back(t);
                    t.pop_back();
                    t.pop_back();
                    l ++;
                    r --;
                }
                else if(nums[l] + nums[r] < target){
                    l ++;
                }
                else
                    r --;
            }
            // if(flag)
            //     ans.push_back(t);
        }
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        return ans;
    }
};

滑动窗口

滑动窗口必备的三要素：left，right和哈希表
leetcode模版

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}

无重复字符的最长子串

当我们每向后遍历一个字符时，我们发现寻找不重复子串的右指针都是向后或者不动的
因为如果一个序列是不重复的，将左边界右移之后也一定是不重复的
所以我们考虑到可以使用滑动窗口来寻找最长的不重复子串
利用哈希集合来判断滑动窗口中是否有重复的字符
时间复杂度依然为O(N)，因为右指针在左指针移动的时候只会向后或者不懂
unordered_set的插入方式是insert()

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int n = s.size();
        int rk = -1, ans = 0;
        for(int i = 0; i < n ; i ++){
            if(i != 0){
                occ.erase(s[i - 1]);
            }
            while(rk + 1 < n && occ.count(s[rk + 1]) == 0){
                occ.insert(s[rk + 1]);
                rk ++;
            }
            ans = max(ans, rk - i + 1);
        }

        return ans;
    }
};

找到字符串中所有字母异位词

利用哈希表来记录字符串p中的字母种类和数量
动态维护滑动窗口的哈希表，当滑动窗口移动的时候，更新哈希表中字母的数量
- 如果左指针为0，初始化哈希表，在滑动窗口内字母的数量都加一
- 如果左指针不为0，则在哈希表中让左指针前一个字母的数量减一，并将新进入窗口的字母数量加一
利用check()函数来判断当前的i能否进入ans数组中
- check()函数依次判断当前窗口中字符的个数是否都等于字符串p中的每个元素的个数
- 注意哈希表也是可以t.first访问key，t.second访问value的

class Solution {
public:
    unordered_map<char, int> strP, strWd;

    bool check(){
        for(const auto &t: strP){
            if(strWd[t.first] != t.second)
                return false;
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        for(const auto &c: p){
            strP[c] ++;
        }

        for(const auto &t: strP){
            cout << t.first << " " << t.second << endl;
        }
        int n = s.size();
        int wd = p.size();
        int r = -1, l = -1;
        for(int i = 0; i < n - wd + 1; i ++){
            if(i > 0){
                strWd[s[i - 1]] --;
                strWd[s[i + wd - 1]] ++;
            }else{
                for(int j = 0; j < wd; j ++){
                    strWd[s[i + j]] ++;
                }
            }
            if(check())
                ans.push_back(i);
        }

        return ans;
    }
};

子串

和为 K 的子数组

前缀和
哈希表
利用前缀和求区间和，进而判断区间和是否等于k
根据公式可推出，对于遍历到的元素j
只需判断是否有pre[i - 1] = pre[j] - k
所以在遍历过程中，要记录每种和出现的次数
符合条件的对应和出现次数累加起来就是ans

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 前缀和
        // 哈希表
        // 就是[i, j]中间的序列和等不等于k
        // pre[j] - pre[i - 1] = k
        // pre[i - 1] = pre[j] - k
        unordered_map<int, int> mp;
        int pre = 0;
        int ans = 0;
        mp[0] = 1;
        for(const auto &num : nums){
            pre += num;
            if(mp.find(pre - k) != mp.end())
                ans += mp[pre - k];
            mp[pre] ++;
        }

        return ans;
    }
};

滑动窗口最大值

利用一个大根堆维护滑动窗口中的元素，这样堆顶元素一直是最大的
大根堆还要保存元素的下标位置，如果当前堆顶元素的下标已经在滑动窗口外的范围，将其弹出堆
直至找到滑动窗口中的对顶元素
推入ans数组中

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        priority_queue<pair<int, int>> q;
        int n = nums.size();
        for(int i = 0; i < k; i ++){
            q.push({nums[i], i});
        }
        ans.push_back(q.top().first);
        for(int i = k; i < n; i ++){
            q.push({nums[i], i});
            while(q.top().second < i - k + 1)
                q.pop();
            ans.push_back(q.top().first);
        }

        return ans;
    }
};

最小覆盖子串

class Solution {
public:
    // 初始化两个哈希表
    // 一个用来记录字符串t中的每种字母的数量
    // 一个用来记录滑动窗口中的每种字母的数量
    unordered_map <char, int> ori, cnt;

    bool check(){
        // 对于t字符串中每个字母
        // 如果当前窗口中该字母的数量已经大于等于其在t中的数量
        // 那么当前窗口子串即为符合题意
        for(const auto &p: ori){
            if(cnt[p.first] < p.second){
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        for(const auto &c :t){
            ++ ori[c];
        }
        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;
        // 因为s.size()默认返回类型是size_t，为无符号整数
        // 如果不加上int()，在比较过程中，r就会被默认转化为size_t类型
        // 在size_t中，-1会被变成一个非常大的数字，与我们的逻辑是不一样的
        while(r < int(s.size())){
            if(ori.find(s[++r]) != ori.end()){
                cnt[s[r]] ++;
            }
            while(check() && l <= r){
                cout << "check" << endl;
                if(r - l + 1 < len){
                    len = r - l + 1;
                    ansL = l;
                }
                if(ori.find(s[l]) != ori.end()){
                    --cnt[s[l]];
                }
                ++ l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

普通数组

最大子数组和

利用动态规划
集合表示：f[i]表示以第i个数为结尾的最大子数组和
集合性质：最大值
集合计算：
- f[i] = max(f[i - 1] + nums[i], nums[i])
由于f[i]只与f[i - 1]有关，所以我们可以只用一个变量pre来维护对于当前i的f[i - 1]值是什么，并且更新pre的值

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        int ans = INT_MIN, pre = 0;
        for(int i = 0; i < n; i ++){
            pre = max(pre + nums[i], nums[i]);
            ans = max(ans, pre);
        }

        return ans;
    }
};

合并区间

将所有区间按照左边界进行排序
依次遍历每个区间
如果该区间的起始点大于当前重叠区间（由多个区间构成）的结束点
- 将当前的重叠区间加入答案中
- 并将（新）重叠区间的起点更新为该区间的左边界
如果当前起始点小于等于当前重叠区间的结束点
- 并且当前区间的结束点大于当前重叠区间的结束点
- 将当前重叠区间的结束点更新为该区间的结束点
遍历结束之后，将最后一个{start, end}区间放入ans中

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end());
        int start = intervals[0][0], end = intervals[0][1];
        for(const auto &t: intervals){
            if(t[0] > end){
                ans.push_back({start, end});
                start = t[0];
                end = t[1];
            }
            else if(t[1] > end)
                end = t[1];
        }

        ans.push_back({start, end});
        return ans;
    }
};

轮转数组

这道题的进阶写法就是原地进行对数组进行轮转
我们可以发现数组在每次进行轮转后：
- 数组的后k % n个数都转移到数组前列
- 每个数字都向后移动了k % n个单位
所以我们通过以下方法可以实现数组的轮转
- 先将整个数组进行翻转
- 再将数组的第0个元素到第k - 1个元素进行翻转
- 最后将数组的第k个元素到第n - 1个元素进行翻转

class Solution {
public:
    void reverse(vector<int> &nums, int start, int end){
        while(start < end){
            swap(nums[start], nums[end]);
            start ++;
            end --;
        }
    }
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
};

除自身以外数组的乘积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1), post(n, 1);
        for(int i = 1; i < n; i ++){
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        for(int i = n - 2; i >= 0; i --){
            post[i] = post[i + 1] * nums[i + 1];
        }

        vector<int> ans;
        for(int i = 0; i < n; i ++){
            ans.push_back(pre[i] * post[i]);
        }
        return ans;
    }
};

缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // 这道题上来首先想到的就是使用哈希表
        // 遍历数组，将数组中每个数字出现的次数用哈希表存储起来
        // 再从1开始遍历，依次枚举正整数，判断在哈希表中其是否存在
        // 但是这样的做法时间复杂度和空间复杂度都是O(n)
        // 所以我们考虑使用题中给定的数组来代替哈希表
        // 首先考虑题解中的：没有出现的正整数一定出现在[1, N + 1]中，N = nums.size()
        // 如果一个数组的长度为N，全为正整数的最理想情况为数组元素为1 ~ N
        // 此时，没有出现的最小正整数为N + 1
        // 如果不是此种情况，那么没有出现的正整数最小值的范围一定在[1, N]中
        // 因为我们只考虑正整数，不用考虑负数
        // 并且只要出现了一个负数，那么没有出现最小正整数就必不可能是 N + 1
        // 所以对于出现的负数，我们将其赋值为 N + 1
        // 随后，开始遍历数组，对于出现的正整数x，并且范围在1 ~ N中，我们将数组x - 1位的值赋值为负
        // 最后，遍历数组，第一个出现正值的下标idx，返回 idx + 1，即为答案
        int n = nums.size();

        for(int i = 0; i < n; i ++){
            if(nums[i] <= 0)
                nums[i] = n + 1;
        }

        for(int i = 0; i < n; i ++){
            int num = abs(nums[i]);
            if(num <= n)
                nums[num - 1] = -abs(nums[num - 1]);
        }

        for(int i = 0; i < n; i ++){
            if(nums[i] > 0)
                return i + 1;
        }

        return n + 1;
    }
};

矩阵

旋转图像

解法1

给定矩阵的长和宽都为 $n$
根据观察可以发现，对于矩阵中的一个元素matrix[i][j]，旋转后的位于矩阵中的第 $j$ 行第 $n - i - 1$ 列
所以我们可以新初始化一个矩阵，存储移动后的矩阵

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        auto matrix_new = matrix;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                matrix_new[j][n - i - 1] = matrix[i][j];

        matrix = matrix_new;
    }
};

解法2

试着不开辟新的矩阵，在原地进行矩阵的旋转
先将矩阵进行翻转，matrix[i][j]' = matrix[n - 1 - i][j]
然后翻转后的矩阵再沿着对角线进行翻转，matrix[i][j]" = matrix[j][i]'
联立可得matrix[i][j]" = matrix[n - 1 - j][i]

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 先对矩阵进行上下翻转
        // 再对矩阵沿着对角线进行翻转
        int n = matrix.size();
        int m = matrix[0].size();
        for(int i = 0; i < n / 2; i ++)
            for(int j = 0; j < m; j ++)
                swap(matrix[i][j], matrix[n - i - 1][j]);

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < i; j ++)
                swap(matrix[i][j], matrix[j][i]);
    }
};

搜索二维矩阵II

解法1

对矩阵中的每一行执行二分查找
给定数组长度为 $n$ ，数组中每个元素数组的长度为 $m$
时间复杂度为 $Ω (n \log m)$

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        for(int i = 0; i < n; i ++){
            int l = 0, r = matrix[i].size() - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(matrix[i][mid] >= target)
                    r = mid;
                else
                    l = mid + 1;
            }

            if(matrix[i][l] == target)
                return true;
        }

        return false;
    }
};

解法2

可以从矩阵的右上角开始搜索，右上角的坐标为 $(0, n - 1)$
给定一个点 $(x, y)$ ，我们以矩阵的左下角为搜索范围的左下角， $(x, y)$ 为搜索范围的右上角，进行搜索
如果matrix[x][y] > target，则说明 $(x, y)$ 所在的 $y$ 列元素都大于target（矩阵的列是严格递增的），则省略该列
如果matrix[x][y] < target，则说明 $(x, y)$ 所在的 $x$ 行都小于target，则省略该行
如果matrix[x][y] = target，则找到

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();
        int x = 0, y = m - 1;
        while(x < n && y >= 0){
            if(matrix[x][y] == target)
                return true;
            else if(matrix[x][y] > target)
                y --;
            else
                x ++;
        }
        return false;
    }
};

二叉树

二叉搜索树中第 K 小的元素

二叉树的题可以考虑用vector来存遍历到的各个节点
若有明确要访问哪些节点，可以直接在vector中找

class Solution {
public:
    void helper(TreeNode* root, vector<int> &ans){
        if(root == nullptr)
            return ;
        helper(root->left, ans);
        ans.push_back(root->val);
        helper(root->right, ans);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> ans;
        helper(root, ans);
        return ans[k - 1];
    }
};

二叉树的右视图

bfs的实现方式就是依靠队列，初始化时将头结点放入队列中，然后利用队列不空和头结点和后续节点的链接，实现bfs
每层遍历到最右侧的节点就是右视图节点
可以通过哈希表来找到每层最右侧的节点，因为在同一层的节点的深度都是一样的，哈希表通过深度映射右视图节点，而我们又是从左往右遍历节点的，所以哈希表中通过深度映射的节点值就是右视图节点的值

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        // 我想用广度优先遍历
        unordered_map<int, int> rightmostvalueAtDepth;
        int max_depth = -1;
        queue<TreeNode*> nodeQueue;
        queue<int> depthQueue;
        nodeQueue.push(root);
        depthQueue.push(0);

        while(!nodeQueue.empty()){
            TreeNode* t = nodeQueue.front();
            nodeQueue.pop();
            int depth = depthQueue.front();
            depthQueue.pop();


            if(t != nullptr){
                max_depth = max(depth, max_depth);
                // 遍历该层逐个节点，最后一个就是最右边的
                rightmostvalueAtDepth[depth] = t->val;

                nodeQueue.push(t->left);
                nodeQueue.push(t->right);
                depthQueue.push(depth + 1);
                depthQueue.push(depth + 1);
            }
        }

        vector<int> ans;
        for(int i = 0; i <= max_depth; i ++){
            ans.push_back(rightmostvalueAtDepth[i]);
        }

        return ans;
    }
};

二叉树展开为链表

class Solution {
public:
    void helper(TreeNode* root, vector<TreeNode*> &nums){
        if(root != nullptr){
            nums.push_back(root);
            helper(root->left, nums);
            helper(root->right, nums);
        }
    }
    void flatten(TreeNode* root) {
        vector<TreeNode*> nums;
        helper(root, nums);
        int length = nums.size();
        for(int i = 1; i < length; i ++){
            TreeNode *prev = nums[i - 1], *curr = nums[i];
            prev->left = nullptr;
            prev->right = curr;
        }
    }
};

从前序与中序遍历序列构造二叉树

前序遍历一个二叉树，构成序列是这样组成的

[根节点, [左子树], [右子树]]

中序遍历一个二叉树，构成序列是这样的

[[左子树], 根节点, [右子树]]

现在前序遍历序列中找到根节点，然后再中序遍历序列中确定根节点的位置，位置减去0就是左子树的大小，右子树的大小也就确定了
- 可以通过建立哈希表的方式，在 $Ω (n)$ 时间复杂度内获取到根节点在中序遍历序列中的位置
通过preorder_left, preorder_right, inorder_left, inorder_right, inorder_root在两个序列中限制子树的边界
递归调用创建根节点的函数，即可构建

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> index;
public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
        if(preorder_left > preorder_right)
            return nullptr;

        int preorder_root = preorder_left;
        int inorder_root = index[preorder[preorder_root]];

        TreeNode* root = new TreeNode(preorder[preorder_root]);

        int size_left_subtree = inorder_root - inorder_left;
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root);
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i = 0; i < n; i ++){
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

二叉树的最近公共祖先

这道题的关键在于：判断一共有多少种情况
一共有两种情况
- 两个节点分别位于祖先节点的左右子树上
- 一个节点是祖先节点，另一个节点位于该节点的左右子树上
利用反证法：
1. 如果两个节点不是分别位于祖先节点的左右子树上，那么说明它们位于同一颗子树上，符合情况2
2. 如果一个节点p是祖先节点，另一个节点q不在其子树上。那么q可能是p的祖先节点，符合情况2。或者两个节点分别是两颗子树的根节点，那么情况就属于情况1
结合以上的情况，我们的判断一个节点是不是二者的祖先节点的条件就是：$$(lson && rson) ((root->va p->val root->val == q->val) &&(lson rson))$$
要判断子树的情况，就要使用后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == nullptr){
            return false;
        }
        // 后序遍历
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))){
            ans = root;
        }
        return lson || rson || root->val == p->val || root->val == q->val;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

二叉树的最近公共祖先

这道题的关键在于：判断一共有多少种情况
一共有两种情况
- 两个节点分别位于祖先节点的左右子树上
- 一个节点是祖先节点，另一个节点位于该节点的左右子树上
利用反证法：
1. 如果两个节点不是分别位于祖先节点的左右子树上，那么说明它们位于同一颗子树上，符合情况2
2. 如果一个节点p是祖先节点，另一个节点q不在其子树上。那么q可能是p的祖先节点，符合情况2。或者两个节点分别是两颗子树的根节点，那么情况就属于情况1
结合以上的情况，我们的判断一个节点是不是二者的祖先节点的条件就是：$$(lson && rson) ((root->va p->val root->val))$$
要判断子树的情况，就要使用后序遍历

二叉树中的最大路径和

这道题主要重点在于计算每条子树的贡献值
因为路径中不能再有分叉
所以递归函数设计为左子树或者右子树的最大贡献值
使用的后序遍历，在遍历两颗子树后，更新最大路径值为max(最大路径值，左子树 + 右子树 + root->val)
返回值为根节点值+max(左子树最大贡献值，右子树最大贡献值)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxSum = INT_MIN;
    int maxGain(TreeNode* node){
        if(node == nullptr)
            return 0;

        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        int priceNewPath = node->val + leftGain +rightGain;
        maxSum = max(maxSum, priceNewPath);

        return node->val + max(leftGain, rightGain);
    }
    int maxPathSum(TreeNode* root) {
        // 其实就是一条路径上不能有岔路
        maxGain(root);
        return maxSum;
    }
};

链表

反转链表

反转链表的本质就是讲当前节点指向上一个节点
所以我们需要两个节点，一个节点curr用来指向当前节点，一个节点prev用来指向上一个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while(curr){
            ListNode* nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
};

两两交换链表中的节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 利用递归的思想
        // 初始化一个newHead节点，作为新链表的头结点
        // 每次递归的操作为：
        // 将head节点放在链表的第二个节点
        // 将第二个结点作为newHead节点
        // 当链表中没有节点，或者还有一个节点时停止递归
        // 返回newHead节点
        if(head == nullptr || head->next == nullptr){
            return head;
        }

        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};

K 个一组翻转链表

又新添加了一个新的疑问

class Solution {
public:
    // 模拟
    // prev = tail->next
    // p = head
    // nex等于p->next，也就是等于nex = head -> next
    // p->next = prev, 也就是head->next = tail->next
    // prev = p，也就是prev = head, tail->next = head
    // p = nex，也就是p = p -> next
    // 一次循环完成之后，p向后移动一个节点，prev也向后移动一个节点
    // 在待交换链表中（长度为k），交换流程是
    // 先初始化一个节点nxt用来存储最后一个节点的指向下一节点的照顾这边tail->next
    // 进行交换:tail->next = head->next
    // pre->next = tail
    // head->next = nxt
    pair<ListNode*, ListNode*> myReverse(ListNode *head, ListNode *tail){
        ListNode* prev = tail->next;
        ListNode* p = head;
        while(prev != tail){
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }

        return {tail, head};
    }


    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy;
        while(head){
            ListNode *tail = pre;
            for(int i = 0; i < k; i ++){
                tail = tail->next;
                if(!tail)
                    return dummy->next;
            }

            ListNode *nex = tail->next;
            auto result = myReverse(head, tail);
            head = result.first;
            tail = result.second;

            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 这道题最开始的难点就是我没理解翻转链表是如何做的
    // 理解了如何翻转链表就容易理解了
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        while(head){
            ListNode* tail = pre;
            for(int i = 0; i < k; i ++){
                tail = tail->next;
                if(!tail)
                    return dummy->next;
            }
            ListNode* nxt = tail->next;
            ListNode* prev = nxt;
            ListNode* curr = head;
            while(curr != nxt){
                ListNode* curnxt = curr->next;
                curr->next = prev;
                prev = curr;
                curr = curnxt;
            }
            // 将翻转后的链表接回到原来的链表中
            pre->next = tail;
            head->next = nxt;
            pre = head;
            head = head->next;
        }
        return dummy->next;
    }
};

将有序数组转换为二叉搜索树

class Solution {
public:
    TreeNode* dfs(vector<int> &nums, int left, int right){
        if(left == right)
            return nullptr;

        int mid = left + (right - left) / 2;
        return new TreeNode(nums[mid], dfs(nums, left, mid), dfs(nums, mid + 1, right));
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums, 0, nums.size());
    }
};

合并 K 个升序链表

暴力

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> allNums;
        for(auto &head: lists){
            ListNode* temp = head;
            while(temp != nullptr){
                allNums.push_back(temp->val);
                temp = temp->next;
            }
        }
        sort(allNums.begin(), allNums.end());

        ListNode* newHead = new ListNode();
        ListNode* prev = newHead;
        for(auto num: allNums){
            ListNode* node = new ListNode(num);
            prev->next = node;
            prev = node;
        }

        return newHead->next;
    }
};

LRU缓存

使用了双向链表和哈希表来实现了缓存的LRU机制
链表的节点中
双向链表实现缓存的结构，存储着key-value对，越最近被使用的节点越靠近链表头，越最晚被使用的节点越靠近链表尾
哈希表则通过key映射到双向链表，使得能在O(1)的时间复杂度中找到节点
put操作
- 首先判断这个key是否已经存在
  - 如果存在，则更新value（哈希表找到节点，双向链表将该节点移动到队头）
  - 如果不存在
    - 则新建一个节点
    - 判断当前链表size是否大于capacity，如果大于，则删除链表尾的元素，并size –；
    - 将节点插入链表头部
get操作
- 首先通过哈希表的count操作判断这个key是否存在，如果不存在则返回-1
- 如果存在，通过哈希表找到对应节点，并返回节点的value值

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(){
        key = 0;
        value = 0;
        prev = nullptr;
        next = nullptr;
    }
    DLinkedNode(int _key, int _value){
        key = _key;
        value = _value;
        prev = nullptr;
        next = nullptr;
    }
};

class LRUCache {
public:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

    LRUCache(int _capacity) {
        size = 0;
        capacity = _capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if(!cache.count(key))
            return -1;
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if(!cache.count(key)){
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;
            addToHead(node);
            ++ size;
            if(size > capacity){
                DLinkedNode* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
                -- size;
            }
        }else{
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node){
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(DLinkedNode* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node){
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail(){
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }


};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

图论

岛屿数量

class Solution {
public:

    void dfs(vector<vector<char>> &grid, int x, int y){
        int nr = grid.size();
        int nc = grid[0].size();

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

    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr)
            return 0;
        int nc = grid[0].size();
        int ans = 0;
        for(int i = 0; i < nr; i ++)
            for(int j = 0; j < nc; j ++){
                if(grid[i][j] == '1'){
                    ans ++;
                    dfs(grid, i, j);
                }
            }

        return ans;
    }
};

腐烂的橘子

class Solution {
    int cnt;
    int dis[10][10];
    int dir_x[4] = {1, -1, 0, 0};
    int dir_y[4] = {0, 0, 1, -1};
public:
    int orangesRotting(vector<vector<int>>& grid) {
        // 初始化队列，存储bfs过程中找到的腐烂橘子的节点
        queue<pair<int, int>> q;
        // 初始化距离数组，距离数组存储的实际上就是时间的值
        // 因为时间的值就是走了多少步
        memset(dis, -1, sizeof dis);
        cnt = 0;
        int n = grid.size();
        if(!n)
            return -1;

        int m = grid[0].size();
        int ans = 0;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++){
                if(grid[i][j] == 2){
                    // 假设这些橘子在-1s的时候全部同时腐烂
                    // 如果腐烂就将其进队
                    q.push({i, j});
                    dis[i][j] = 0;
                }
                else if(grid[i][j] == 1)
                {
                    cnt ++;
                }
            }

        while(q.size()){
            // 取出一个腐烂橘子节点
            auto t = q.front();
            q.pop();
            for(int i = 0; i < 4; i ++){
                // 上下左右探索
                int dx = t.first + dir_x[i];
                int dy = t.second + dir_y[i];
                // 如果越界、当前节点无橘子、已被探索过，则continue
                if(dx < 0 || dx >= n || dy < 0 || dy >= m || !grid[dx][dy] || dis[dx][dy] != -1)
                    continue;
                // 更新到该店的距离（时间）
                dis[dx][dy] = dis[t.first][t.second] + 1;
                // 入队
                q.push({dx, dy});
                if(grid[dx][dy] == 1){
                    // 未腐烂的橘子数量减一
                    cnt -= 1;
                    // 答案为最小时间的最大值（正常走就是最小时间）
                    ans = dis[dx][dy];
                    if(!cnt)
                        break;
                }
            }
        }
        // 如果未腐烂的橘子还有剩余，则返回-1
        // 没有剩余，则返回ans
        return cnt ? -1 : ans;
    }
};

回溯

子集

状态表示
利用二进制数表示状态
- 数位上为1，表示取数组中的数
- 数位上为0，表示不取数组中的数

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < (1 << n); i ++){
            t.clear();
            for(int j = 0; j < n ; j ++){
                if(i & (1 << j))
                    t.push_back(nums[j]);
            }
            ans.push_back(t);
        }
        return ans;
    }
};

电话号码的字母组合

可以利用哈希表直接建立字符与字符串之间的映射
string的容器操作有：
- empty()：判断字符串是否为空
- size()/length()：返回字符串的长度
- push_back(): 向字符串末尾加入字符
- pop_back(): 弹出字符串末尾的字符
其实这个回溯的过程就是有点像dfs
- 改变状态
- dfs——下一个位置递归调用函数
- 恢复状态

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if(digits.empty())
            return ans;
        unordered_map<char, string> tel{
            {'2',"abc"},
            {'3',"def"},
            {'4',"ghi"},
            {'5',"jkl"},
            {'6',"mno"},
            {'7',"pqrs"},
            {'8',"tuv"},
            {'9',"wxyz"}
        };
        string combination;
        helper(ans, tel, digits, 0, combination);
        return ans;
    }

    void helper(vector<string> &ans, const unordered_map<char, string> tel, string digits, int index, string &combination){
        if(index == digits.size())
            ans.push_back(combination);
        else{
            char digit = digits[index];
            const string &letters = tel.at(digit);
            for(const char &c: letters){
                combination.push_back(c);
                helper(ans, tel, digits, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};

括号生成

利用的是回溯的套路
重点在于左右括号的放置
左括号可以放置不超过n个
右括号也可以放置不超过n个，但是数量必须要小于等于左括号
当括号的总量，也就是字符串的长度等于2n的时候，回溯中止。

class Solution {
public:
    void dfs(vector<string> &ans, int l, int r, string& s, int n){
        if(s.size() == 2 * n){
            ans.push_back(s);
            return ;
        }

        if(l < n){
            s.push_back('(');
            dfs(ans, l + 1, r, s, n);
            s.pop_back();
        }

        if(r < l){
            s.push_back(')');
            dfs(ans, l, r + 1, s, n);
            s.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string s = "";
        dfs(ans, 0, 0, s, n);
        return ans;
    }
};

单词搜索

利用的是回溯经典套路
- 改变状态
- 递归调用函数
- 恢复状态
但是我在最开始构建的时候遗漏了一个问题，忘记了需要保存走过路径的状态，导致查找会往回查找
by the way，这道题是我自己做出来的

class Solution {
private:
    int m, n;
    bool flag;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
public:
    void backtrack(vector<vector<int>>& st, vector<vector<char>>& board, string word, int idx, int x, int y){
        // cout << "---------------------" << endl;
        // cout << "word[idx]: " << word[idx] << endl;
        // cout << "board[x][y]: " << board[x][y] << endl;
        // cout << "---------------------" << endl;
        if(board[x][y] != word[idx])
            return ;
        if(board[x][y] == word[idx] && idx == word.size() - 1){
            flag = true;
            return ;
        }

        for(int i = 0; i < 4; i ++){
            int tx = x + dx[i], ty = y + dy[i];
            if(tx >= 0 && tx < m && ty >= 0 && ty < n && !st[tx][ty]){
                st[tx][ty] = 1;
                backtrack(st, board, word, idx + 1, tx, ty);
                st[tx][ty] = 0;
            }else
                continue;
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        vector<vector<int>> st(m, vector<int>(n));
        flag = false;
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                st[i][j] = 1;
                backtrack(st, board, word, 0, i, j);
                st[i][j] = 0;
            }
        }
        // backtrack(board, word, 0, 0, 0);
        return flag;
    }
};

贪心算法

跳跃游戏

依次遍历每个位置，并维护一个变量rightmost，表示最远可以到达的位置
对于每一个可以到达的位置，即i <= rightmost，我们使用在这点最远可到达的距离与rightmost进行比较，并更新
遍历结束后，如果rightmost > n - 1，则说明可以到达

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rightmost = 0;
        for(int i = 0; i < n; i ++){
            if(i <= rightmost){
                rightmost = max(rightmost, i + nums[i]);
                if(rightmost >= n - 1)
                    return true;
            }
        }
        return false;


### [跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked)

- 这道题要求我们计算出来到达最后一个位置的最少步数
- 那么我们就要贪心的考虑，能到达最后一个位置并且距离最后一个位置最远的位置，即跳跃距离最远，这样能够使使用的步数最少
- 我们使用`pos`维护最后一个位置，将`pos`初始化为`n - 1`
- 接下来遍历，寻找能到达`pos`的点，并且符合条件
- 直至`pos`等于0
## 栈

### [字符串解码](https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked)

```cpp
class Solution {
public:
    int jump(vector<int>& nums) {
        int pos = nums.size() - 1;
        int steps = 0;
        while(pos > 0){
            for(int i = 0; i < pos; i ++){
                if(i + nums[i] >= pos){
                    pos = i;
                    steps ++;
                    break;
                }
            }
        }
        return steps;
    string decodeString(string s) {
        stack<int>   n_stk;
        stack<string>  s_stk;
        int j=0;
        string o="";
        for(int i=0;i<s.size();i++){
           if(isdigit(s[i])){
                int x = 0;
                int j = i;
                while(j < s.size() && isdigit(s[j])){ //读取整个数
                    x = x*10+s[j]-'0';
                    j++;
                }
                n_stk.push(x); //压栈
                i = j-1;
            }
          else if(s[i]=='['){
            s_stk.push(o);
            o="";
           }
          else if(s[i]>='a'&&s[i]<='z'){
            o=o+s[i];

           }
          else if(s[i]==']'){
            int n=n_stk.top();
            n_stk.pop();
             string q=s_stk.top();
              s_stk.pop();
              string e;
            for(int i=0;i<n;i++){
                e=e+o;
            }
            o=q+e;
          }

        }
        return o;

    }
};

每日温度

使用了单调栈
这个栈中存的都是单调递减的温度
如果一个新的元素需要入栈，首先判断与栈顶元素的关系，如果栈顶元素小于新的元素，那么就找到了栈顶元素后第一个比它高的温度，栈顶元素出栈
循环执行上面步骤，直至找到一个元素比新元素大，新元素入栈，满足单调栈的性质
栈存储的都是温度的下标

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 prevIndex = s.top();
                ans[prevIndex] = i - prevIndex;
                s.pop();
            }
            s.push(i);
        }

        return ans;
    }
};

划分字母区间

首先遍历字符串，使用一个数组存储每个字母最后一次出现的位置在哪里
初始化变量start和end用来表示片段的结尾
从头开始遍历，遍历过程中要不断更新end，end = max(end, last[s[i] - 'a'])
如果当前遍历的下标等于end，那么说明在end之前出现的字符最后一次出现的位置都在end前了
当前start~end的字符串符合条件
将end - start + 1推入答案vector中

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int length = s.size();
        for(int i = 0; i < length; i ++){
            last[s[i] - 'a'] = i;
        }
        vector<int> ans;
        int start = 0, end = 0;
        for(int i = 0; i < length; i ++){
            end = max(end, last[s[i] - 'a']);
            if(i == end){
                ans.push_back(end - start + 1);
                start = end + 1;
            }
        }

        return ans;
    }
};

堆

数据流的中位数

维护两个堆，分别为大根堆和小根堆
- 大根堆用来维护小于等于中位数的数字们
- 小根堆用来维护大于中位数的数字们
两个堆的堆头元素都是最靠近中位数的
当所有元素都进入两个堆之后
- 如果元素的个数为奇数，我们规定大根堆的元素个数比小根堆元素个数多一个，这样大根堆的堆头元素就是中位数
- 如果元素的个数为偶数，我们将大根堆堆头元素和小根堆堆头元素取平均，计算结果即为中位数
在将元素入堆的时候，我们要实时维护堆的大小
- 如果大根堆的元素个数比小根堆元素个数加1还要多，那么就要件大根堆堆头元素推入小根堆中，并将其从大根堆中弹出
- 如果小根堆元素的个数要多余大根堆的元素的个数，我们要讲小根堆堆头元素推入大根堆中，并将其从小根堆弹出

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;
    MedianFinder() {

    }

    void addNum(int num) {
        if(queMin.empty() || num <= queMin.top()){
            queMin.push(num);
            if(queMax.size() + 1 < queMin.size()){
                queMax.push(queMin.top());
                queMin.pop();
            }
        }
        else {
            queMax.push(num);
            if(queMax.size() > queMin.size()){
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }

    double findMedian() {
        if(queMin.size() > queMax.size())
            return queMin.top();
        return (queMin.top() + queMax.top()) / 2.0;
    }
};

动态规划

乘积最大子数组

class Solution {
public:
    // 这道题不能按照像最大子序列和那样那么想，那道题的思路是:
    // f[i]表示以下标i为结尾的子序列最大值f[i] = max(f[i - 1] + a[i], a[i])
    // 但是如果这么思考，则不符合最优子结构
    // 如果nums = {5,6,−3,4,−3}
    // 那么f = {5, 30, -3, 4, -3}
    // 很明显，答案应该是5 * 30 * -3 * 4 * -3
    // 但是f[4] = -3，这与答案是不符的，说明这种选法不具有最优子结构的性质
    // 事实上，最大乘积可能是这么组成的：
    // 在结尾为下标i - 1的序列中，其拥有一个负的最小值，并且恰好第i个数是负的
    // 这样的乘积成为了最大值
    // 所以我们在遍历过程中，需要维护两个值，一个是最大值，另一个最小值
    // 最终f[i] = max(a[i], max(f_max[i - 1] * a[i], f_min[i - 1] * a[i]))
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<long> maxF(n), minF(n);
        if(!n)
            return 0;
        maxF[0] = nums[0], minF[0] = nums[0];
        for(int i = 1; i < n; i ++){
            maxF[i] = max((long)nums[i], max(maxF[i - 1] * nums[i], minF[i - 1] * nums[i]));
            minF[i] = min((long)nums[i], min(maxF[i - 1] * nums[i], minF[i - 1] * nums[i]));
            if(minF[i] < INT_MIN)
                minF[i] = nums[i];
        }

        return *max_element(maxF.begin(), maxF.end());
    }
};

分割等和子集

这道题有许多特殊条件，可以上来就判断一个数组可不可以被分为两个和相等的子集
- 如果数组只有一个元素，则不可分割
- 如果数组的和为奇数，则不可分割
- 如果数组中最大元素，超过了和的二分之一，则不可分割
类似于背包问题
状态表示：dp[i][j]表示在前i个数中，可以挑选出几个数字，使得和为j
当nums[i] <= j时，dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
当nums[i] > j时，dp[i][j] = dp[i - 1][j]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if(n < 2)
            return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int maxNum = *max_element(nums.begin(), nums.end());
        if(sum & 1)
            return false;

        int target = sum / 2;
        if(maxNum > target)
            return false;
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        for(int i = 0; i < n; i ++){
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for(int i = 1; i < n; i ++){
            int num = nums[i];
            for(int j = 1; j <= target; j ++){
                if(j >= num){
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n - 1][target];
    }
};

最长有效括号

集合划分：使用dp[i]来表示第i位置前的最长有效括号串是多长
由于我们遍历括号字符串中的每一个字符，所以如果第i个字符为(。那么其dp[i]为0
如果第i个字符为)，我们继续判断倒数第二个字符
- 如果第i - 1字符为(，那么dp[i] = dp[i - 2] + 2
- 如果第i - 1字符为)，那么我们要接着判断以第i - 1个字符为结尾的最长有小括号串开始端的前一个字符
  - 如果该字符为(，那么dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), ans = 0;
        vector<int> dp(n);
        for(int i = 1; i < n; i ++){
            if(s[i] == ')'){
                if(s[i - 1] == '('){
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

分割回文串

回溯+动态规划
首先使用动态规划，判断从下标i到下标j的子串是不是为回文串
f[i][j]表示是不是回文串
因为状态转移方程是f[i][j] = f[i + 1][j - 1] && (s[i] == s[j])
所以在动态规划时，需要从后往前来，才能保证之前的状态已经生成了
然后使用回溯进行探索
如果f[i][j]表示该子串为回文串，加入ans中，并在j + 1的位置上继续回溯

class Solution {
private:
    vector<vector<string>> ret;
    vector<string> ans;
    vector<vector<int>> f;
    int n;
public:
    void dfs(string s, int i){
        if(i == n){
            ret.push_back(ans);
            return ;
        }
        for(int j = i; j < n; j ++){
            if(f[i][j]){
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ans.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n, true));
        for(int i = n - 1; i >= 0; i --)
            for(int j = i + 1; j < n; j ++)
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
        dfs(s, 0);
        return ret;
    }
};

技巧

只出现一次的数字

使用异或操作
- 任何数和0做异或运算，结果仍然是原来的数
- 任何数与其自身做异或运算，结果是0
- 异或运算满足交换律和结合律
数组中所有数字进行异或运算，最后的结果就是只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(auto e: nums)
            ret ^= e;
        return ret;
    }
};

多数元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> cnts;
        for(auto &num: nums){
            auto cnt = cnts.find(num);
            if(cnt == NULL){
                cnts.insert({num, 1});
            }else{
                cnts[num] ++;
            }
        }
        int n = nums.size() / 2;

        for(auto &num: nums){
            if(cnts[num] > n){
                return num;
            }
        }

        return -1;
    }
};

颜色分类

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums.begin(), nums.end());
    }
};

寻找重复数

利用二分查找
我们定义一个数组cnt[i]用来存储比i小的数有多少个
根据题给定的条件
- 假设重复的数字是target
- 那么在区间[1, target - 1]中，cnt[i] <= i
- 在区间[target, n]中，cnt[i] > i
具有明显的单调性，可以使用二分法
证明：
- 如果重复的数字target只重复出现两次
  - 给定nums有n + 1个位置，数字出现在1 ~ n中，那么对于[1, target - 1]中的数字，一定有cnt[i] <= i
- 如果重复的数字target只重复出现三次
  - 如果被替代的数字i小于target，那么[i, target - 1]的cnt都减1
  - 如果被替代的数字i大于target，那么[target, i - 1]的cnt都加1
  - 依旧符合性质

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1, ans = -1;
        while(l < r){
            int mid = l + r >> 1;
            int cnt = 0;
            for(int i = 0; i < n; i ++){
                if(nums[i] <= mid)
                    cnt ++;
            }
            if(cnt > mid)
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }
};

下一个排列

字典序：
- 比较两个数字序列的时候
- 从左向右逐个比较它们中的元素
- 如果找到第一个不同的元素，那么包含较小的元素的那个序列的字典序就更小
- 如果一个序列是另一个序列的前缀，那么较短的序列的字典序更小
我们想找到某一个序列的下一个排列，要满足
- 下一个序列的字典序大于当前序列
- 并且变大的幅度要尽可能的小
采用以下思路：
- 从后往前遍历
- 从倒数第二个数字开始判断，当前数字是否大于等于后一个数字
- 直至找到第一个不符合条件的数字（即nums[i] < nums[i + 1]
- 从最后往前开始遍历，找到第一个大于该不符合条件的数字
- 两个数字进行互换
- 以第一个不符合条件数字后面的位置（i + 1）开始，至末尾结束，翻转字符串
- 如果没有找到不符合条件的数字，说明当前数组排序已经为降序，直接进行翻转即可

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[j] <= nums[i]){
                j --;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

哈希

两数之和

双指针

滑动窗口

子串

普通数组

矩阵

解法1

解法2

解法1

解法2

二叉树

链表

图论

回溯

贪心算法

堆

动态规划

技巧

Enjoy Reading This Article?