2020暑假刷题笔记

二叉树

一. leetcode 113 路径总和2

前序遍历：

  1. 先处理当前结点（将该结点push到路径数组中，并且累加其结点值）；
  2. 再进行下一步的遍历；
  3. 完成当前结点的遍历后，回溯（将该结点pop出路径数组，并且更新结点值和）。
    一般代码结构如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void preOrder(TreeNode* root, vector<vector<int>>& result, vector<int>& path, int sum, int cur_sum) {
            if (root == NULL) return;
            path.push_back(root->val); // 更新路径
            cur_sum += root->val; // 更新当前和
            // 当前和与要求和相同，并且为叶子结点
            if (cur_sum == sum && root->left == NULL && root->right == NULL) {
                result.push_back(path);
            }
            preOrder(root->left, result, path, sum, cur_sum);
            preOrder(root->right, result, path, sum, cur_sum);
            // 左右子树都遍历完成后，在路径中删除当前值
            path.pop_back();
            cur_sum -= root->val;
        }

    二. leetcode 236 二叉树的最近公共祖先

  4. 分别以题目给出的两个结点为目标，对二叉树进行前序遍历，直到找到该目标，并且记录路径；
  5. 从头到尾对比两个路径，遇到的最后一个相同的即为最近公共祖先。

三. leetcode 114 二叉树展开为链表

递归主要讨论的是左子树与右子树都拉直后的连接过程，忽略具体拉直过程，每个递归返回的有用信息是该树右子树的最后一个结点指针。

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
/**
 * 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:
    void preOrder(TreeNode* node, TreeNode* &last) {
        if (!node) return;
        // 判断该结点是否为叶子结点
        // 是则为该子树的最后一个结点
        // 返回
        if (!node->left && !node->right) {
            last = node;
            return;
        }
        TreeNode* left = node->left;
        TreeNode* right = node->right;
        TreeNode* left_last = NULL;
        TreeNode* right_last = NULL; // 左右子树的最后一个结点
        // 前序遍历左子树
        if (left) {
            preOrder(left, left_last);
            node->left = NULL;
            node->right = left;
            last = left_last;
        }
        // 前序遍历右子树
        if (right) {
            preOrder(right, right_last);
            if (left_last) // 没有该判断 报错！last没有初始化，为空
                last->right = right;
            last = right_last;
        }
    }
    void flatten(TreeNode* root) {
        TreeNode * last;
        preOrder(root, last);
    }
};

图

一. leetcode 199 二叉树的右视图

图的宽度搜索（BFS）：

  1. 使用队列queue，pair存储结点与层数；
  2. 将当前结点的左右结点分别push到队列中，同时记录层数；
  3. 按先进先出的顺序访问结点；
  4. 不断更新该层的最后一个结点；
  5. 得到结果数组。
    一般代码结构为：
    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
    /**
     * 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:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> ans; // 按层遍历的最后一个结点
            queue<pair<TreeNode*, int> > myQueue;
            if (!root)return ans;
            myQueue.push(make_pair(root, 0));
            while (!myQueue.empty()) {
                TreeNode* cur_node = myQueue.front().first;
                int cur_depth = myQueue.front().second;
                myQueue.pop();
                if (ans.size() == cur_depth) { // 首次遇到在cur_depth层的结点 将结点值push到数组中
                    ans.push_back(cur_node->val);
                }
                else { // 更新ans[cur_depth]的值
                    ans[cur_depth] = cur_node->val;
                }
                if (cur_node->left) { // 存在左子树
                    myQueue.push(make_pair(cur_node->left, cur_depth + 1));
                }
                if (cur_node->right) { // 存在左子树
                    myQueue.push(make_pair(cur_node->right, cur_depth + 1));
                }
            }
            return ans;
        }
    };

二. leetcode 207 课程表

两种方法：

  1. DFS遍历过程中，没有重复访问正在访问的结点（即存在从该结点返回到初始位置的路径）。
    DFS的一般代码结构:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    bool DFS(GraphNode *node, vector<int> &visit) {
           // 标记当前结点值正在访问
           visit[node->label] = 0; 
           // 访问器邻接结点
           for (int i = 0; i < node->neighbors.size(); i++) {
               // 当前结点未被访问则继续深度遍历
               if (visit[node->neighbors[i]->label] == -1) {
                   if (!DFS(node->neighbors[i], visit))
                       return false;
               }
               // 当前结点出现环:访问正在访问的结点
               else if (visit[node->neighbors[i]->label] == 0) {
                   return false;
               }
           }
            // 标记当前结点值访问过
           visit[node->label] = 1;
           return true;
       }
  2. BFS遍历后，无环：所有入度减少为0；有环：存在不为0的入度。

二分查找

一. leetcode 35 搜索插入位置

标准二分查找法(重点：分析出未找到target值时，插入位置索引总是begin);
一般模板:

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

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

分别找左右边界，二分查找加入相等的处理判断;

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
// 找左边界
        while (begin <= end) {
            mid = (begin + end) / 2;
            // 前半部分
            if (nums[mid] > target) {
                end = mid - 1;
            }
            // 后半部分
            else if (nums[mid] < target) {
                begin = mid + 1;
            }
            // 相等的情况
            // 左边界要么就是mid，要么在前半部分
            else {
                // mid为左边界
                if (mid == 0 || nums[mid - 1] < target) {
                    left = mid;
                    break;
                }
                // 前半部分还有target值，继续二分查找
                else {
                    end = mid - 1;
                }
            }
        }

三、leetcode 33 搜索旋转排序数组

有点窒息的分类,二分查找的框架，每种情况都要清晰地讨论。

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int begin = 0, end = nums.size() - 1;
        int mid = 0;
        while (begin <= end) {
            mid = (begin + end ) / 2;
            // 目标小于中间值
            if (target < nums[mid]) {
                // 前半部分为顺序区间，后半部分为旋转区间
                if (nums[begin] <= nums[mid]) { // 注意！！等号表示mid与begin值相同时
                    // 在顺序区间中找
                    // 顺序区间内的最小值<=target，则在顺序区间中找
                    if (nums[begin] <= target) end = mid - 1;
                    // 在旋转区间中找
                    else {
                        begin = mid + 1;
                    }
                }
                // 后半部分为顺序区间，前半部分为旋转区间
                // 后半部分所有值都大于nums[mid] 即大于target
                // target一定在前半部分
                else {
                    end = mid - 1;
                }
            }
            // 目标大于中间值
            else if (target > nums[mid]) {
                // 前半部分为顺序区间，后半部分为旋转区间
                // 前半部分所有值都小于nums[mid] 即小于target
                // target一定在后半部分
                if (nums[begin] < nums[mid]) {
                    begin = mid + 1;
                }
                // 后半部分为顺序区间，前半部分为旋转区间
                else {
                    // 在旋转区间中找
                    // nums[end]是顺序区间中最大元素
                    // 该最大元素都比target小的话
                    // 则直接在旋转区间中找
                    if (nums[end] < target) end = mid - 1;
                    // 否则在该顺序区间中找
                    else {
                        begin = mid + 1;
                    }
                }
            }
            else return mid;
        }
        return -1;
    }
};

二叉搜索树

插入结点代码

1
2
3
4
5
6
7
8
9
10
void BST_insert(TreeNode* root, TreeNode* insert_node) {
        if (root->val > insert_node->val) {
            if (root->left) BST_insert(root->left, insert_node);
            else root->left = insert_node;
        }
        else {
            if (root->right) BST_insert(root->right, insert_node);
            else root->right = insert_node;
        }
    }

查找结点代码

一、leetcode 449 序列化和反序列化二叉搜索树

二、leetcode 315 计算右侧小于当前元素的个数

在插入的过程中计算小于当前结点值的结点数,不是获取当前结点的count_small值（记录的是整棵树中小于当前结点的值，而不是在插入他之前）。

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
class Solution {
public:
    // 计算右侧小于当前元素的个数
    // 反转数组
    // 将问题转换为：计算左侧小于当前元素的个数
    // 建立二叉搜索树,在建立的过程中，记录
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        int count_small;
        TreeNode(int x) : val(x), left(NULL), right(NULL), count_small(0) {}
     };
    
    void BST_insert(TreeNode* node, TreeNode* insert_node, int & count) {
        if (node->val >= insert_node->val) {
            node->count_small++;
            if (node->left) BST_insert(node->left, insert_node, count);
            else node->left = insert_node;
        }
        else {
            count += node->count_small + 1;
            if (node->right) BST_insert(node->right, insert_node, count);
            else node->right = insert_node;
        }
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans;
        if (nums.size() == 0) return ans;
        reverse(nums.begin(), nums.end());
        TreeNode* root = new TreeNode(nums[0]);
        ans.push_back(0);
        for (int i = 1; i < nums.size(); i++) {
            TreeNode * newNode =  new TreeNode(nums[i]);
            int count_small = 0;
            BST_insert(root, newNode, count_small);
            ans.push_back(count_small);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

哈希表

一、 leetcode 409 最长回文串

  1. 哈希表存放字符串s中各个不同的字母出现的次数；
  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
    25
    26
    27
    class Solution {
    public:
        int longestPalindrome(string s) {
            map<char, int> mp;
            for (int i = 0; i < s.length(); i++) {
                mp[s[i]]++;
            }
            map<char, int>::iterator it;
            int sum = 0;
            bool flag = false;
            for (it = mp.begin(); it != mp.end(); it++) {
                if (it->second % 2 == 0) { // 该字母出现次数为偶数次
                    sum += it->second; // 可构成回文
                }
                else { // 该字母出现次数为奇数次
                    if (flag) { // 已存在中间值
                        sum += it->second - 1; // 除掉中间值外 其他可构成回文
                    }
                    else {
                        sum += it->second;
                        flag = true;
                    }
                }
            }
            return sum;
        }
    };

二、leetcode 290 单词规律

分析字符串与模式字母的正确匹配情况与错误情况：

  1. map<string, char> mp; // 存储字符串对应的模式字母
    bool used[128] = {0}; // 标记模式字母是否出现过
  2. 模式字母未出现过：当前字符串却曾经出现过，则有字符串对应了多个模式字母，错误；
    模式字母出现过：当前字符串不曾出现，或者当前字符串不对应相应模式字母，错误；

三、leetcode 49 字母异位词分组

  1. map<string, int> mp; // 哈希表：基础字符串，对应在结果中的索引
    vector<vector > res; // 结果数组
  2. 字符串排序,作为map的key.

四、leetcode 3 无重复字符的最长子串

滑动窗口法：

  1. 确定左边界，遍历右边界，数组存储字母在该窗口中是否出现过；
  2. 当遍历过程中遇到出现过的字母，则右移左边界，直到找到该字母的位置;
  3. 当遍历过程中遇到出现过的字母，更新最大无重复子串长度。

    五、leetcode 187 重复的DNA序列

    ACGT四种情况，即二进制两位数可表示这4种不同的字母；
    不同的DNA序列可转化为对应不同的二进制数;
    使用哈希表存储出现的次数。

    六、leetcode 76 最小覆盖子串

    滑动窗口法+哈希表:
    根据条件更新左边界：当前S窗口s_map[begin_str] < T字符串中的t_map[begin_str]；或出现T字符串中没有的字母；
    遍历右边界，在每次遍历完成后，判断该窗口是否符合要求。
    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:
        bool is_window_ok(int x[], int y[], vector<int> vec) {
            for (int i = 0; i < vec.size(); i++) {
                if (x[vec[i]] > y[vec[i]]) return false;
            }
            return true;
        }
        
        string minWindow(string s, string t) {
            int t_map[128] = {0}; // 记录t字符串中各字母出现的次数
            int s_map[128] = {0}; // 记录s字符串窗口中各字母出现的次数
            vector<int> charvec; // 记录t中出现过的字母
            for (int i = 0; i < t.length(); i++) {
                if (t_map[t[i]] == 0) charvec.push_back(t[i]);
                t_map[t[i]]++;
            }
            int begini = 0; // 窗口左边界
            int min_len = s.length() + 1; // 结果字符串长度
            string res = "";
            // 遍历右边界
            for (int i = 0; i < s.length(); i++) {
                s_map[s[i]]++;
                while (begini < i) {
                    if (t_map[s[begini]] == 0) { // 窗口首字母在t字符串中不存在
                        begini++;
                    }// 窗口首字母在窗口字符串中出现次数>在t字符串出现次数
                    else if (s_map[s[begini]] > t_map[s[begini]]) {
                        s_map[s[begini]]--;
                        begini++;
                    }
                    else break;
                }
                // cout<<s.substr(begini, i - begini + 1)<<endl;
                if (is_window_ok(t_map, s_map, charvec)) {
                    int cur_len = i - begini + 1;
                    if (res == "" || cur_len < min_len) {
                        min_len = cur_len;
                        res = s.substr(begini, cur_len);
                    }
                }
            }
            return res;
        }
    };

    递归

    一、 leetcode 78 子集

    不考虑递归过程，直接根据结果来实现程序。
    求子集：
  4. 考虑当前元素是否应该加到子集中：加或不加，分别递归；
  5. 递归结束条件是：index>=nums.size()。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
        void generate (int i, vector<int> nums, vector<int> items, vector<vector<int>> &res) {
            if (i >= nums.size()) { // 当索引超出nums边界
                res.push_back(items);
                return;
            }
            items.push_back(nums[i]); // 当前子集选择nums[i]
            generate (i + 1, nums, items, res); // 进行下一步递归
            items.pop_back(); // 当前子集不选择nums[i]
            generate (i + 1, nums, items, res); // 进行下一步递归
        }
        
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int> > res;
            vector<int> items;
            generate (0, nums, items, res);
            return res;
        }
    };

    二、leetcode 90 子集 II

    先对nums排序，使用set<vector>对一致的子集去重。
    1
    2
    3
    4
    if (res_set.find(items) == res_set.end()) {
                    res.push_back(items);
                    res_set.insert(items);
                }

    三、leetcode 40 组合总和 II

    典型的递归题：
  6. 以开始位置start索引遍历候选数组，当当前索引未加入到路径中，并且加入候选值不会大于target值，则选择该索引位置的值，并进行下一步的递归；
  7. 递归结束条件是path值==target值，并且当前path首次出现(排序 set约束)。
    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:
        // 递归函数
        // 候选数组，开始位置，目标数值，结果数组，当前子集
        void backtracking(vector<int> candidates, int start, int target, vector<vector<int> >& res, vector<int>& path, bool help[], set<vector<int> >& res_set) {
            // 达到目标
            if ( target == 0 && res_set.find(path) == res_set.end()) {
                res.push_back(path);
                res_set.insert(path);
                return;
            }
            for (int i = start; i < candidates.size() && target-candidates[i] >= 0; i++){
                // 满足条件：当前值未使用 并且 子集和仍然小于target
                if (!help[i] && target - candidates[i] >= 0) {
                    path.push_back(candidates[i]); // 将当前值放入子集中
                    help[i] = true;
                    backtracking(candidates, i+1, target - candidates[i], res, path, help, res_set);
                    path.pop_back(); // 取出该值，进行新一轮选择
                    help[i] = false;
                }
            }
        }
        /*
        sort(candidates.begin(),candidates.end()); // 将数组排序
        backtracking(candidates, 0, target, res, path, help, res_set);
        */
    };

    四、leetcode 22. 括号生成

    典型递归题：
    给出n对左右括号的合理摆放顺序。
  8. 每一步有2种选择：’(‘或’)’，对两种选择分别进行下一步递归；
  9. 递归结束条件为：目标字符串长度到达2*n；
  10. 剪枝：去除不必要的递归步骤：只有n个左括号与n个右括号，超出的直接不做处理；左括号数不大于右括号数的，不可再选择’)’。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        void generate(string item, int left, int right, vector<string>& res) {
            if (left == 0 && right == 0) { // 当字符串成功放置n个左括号与n个右括号
                res.push_back(item);
                return;
            }
            if (left > 0) // 当左括号尚未完成
                generate(item + '(', left - 1, right, res);
            if (left < right) // 当左括号数>右括号数
                generate(item + ')', left, right - 1, res);
        }
        
        vector<string> generateParenthesis(int n) {
            vector<string> res;
            generate("", n, n, res);
            return res;
        }
    };

    五、leetcode 51. N皇后

    N皇后问题，典型的递归回溯法：
    关键点在于在递归之前，对当前mark标记数组与location结果状态的保存，以便在回溯阶段对状态进行复原，以进行下一步的递归。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    class Solution {
    public:
        int dir[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, // 上下左右
                        {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; // 左上 右上 左下 右下
        // 在(x,y)位置放置queue
        // 在(x,y)位置的八个方向延伸出去 都标志为-1 表示不可放置queue
        void put_down_the_queue(int x, int y, vector<vector<int> >& mark) {
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < mark.size(); j++) {
                    int index_x = x + dir[i][0] * j;
                    int index_y = y + dir[i][1] * j;
                    if (index_x < 0 || index_x >= mark.size()) continue;
                    if (index_y < 0 || index_y >= mark[0].size()) continue;
                    mark[index_x][index_y] = -1;
                }
            }
        }
        
        // 递归函数
        // k：完成k个皇后的放置
        // n：共n个皇后
        // location：当前摆放结果
        // res：最终结果
        // mark：标记数组
        void generate(int k, int n, vector<string>& location, vector<vector<string> >& res, vector<vector<int> >& mark) {
            if (k == n) {
                res.push_back(location);
                return;
            }
            for (int i = 0; i < n; i++) {
                if (mark[k][i] == 0) {
                    vector<vector<int> > temp_mark = mark; // 存储当前的mark数组(在递归过程中会改变)
                    put_down_the_queue(k, i, mark);
                    location[k][i] = 'Q';
                    generate(k + 1, n, location, res, mark); // 递归
                    mark = temp_mark; // 返回原本mark数组
                    location[k][i] = '.';  // 返回原本的location
                }
            }
        }
        
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<string> > res; // 存储最终结果
            vector<vector<int> > mark; // 标记棋盘是否可以放置皇后的二维数组
            vector<string> location; // 存储某个摆放结果
            // 初始化
            for (int i = 0; i < n; i++) {
                mark.push_back((vector<int>()));
                for (int j = 0; j < n; j++) {
                    mark[i].push_back(0);
                }
                location.push_back("");
                location[i].append(n, '.'); // location初始化为n个"."
            }
            generate(0, n, location, res, mark);
            return res;
        }
    };

    六、leetcode 315 计算右侧小于当前元素的个数

    归并排序思想：
    在merge两个子数组的同时，更新counts数组：
    当插入前半部分区间值sub_vec1[x]时，表示后半部分 y之前的所有值都已放置在vec中，
    则证明y之前都小于sub_vec1[x],因此对应值索引位置更新+y。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    class Solution {
    public:
        void merge_two_vec(vector<pair<int, int> > sub_vec1, vector<pair<int, int> > sub_vec2, vector<pair<int, int> >& vec, vector<int>& ans) {
            int x = 0, y = 0;
            while (x < sub_vec1.size() && y < sub_vec2.size()) {
                // 此时插入前半部分区间值sub_vec1[x]
                // y之前的所有值都已放置在vec中
                // 证明都小于sub_vec1[x]
                // 因此更新+y
                if (sub_vec1[x].first <= sub_vec2[y].first) {
                    ans[sub_vec1[x].second] += y; // 对应索引位置更新
                    vec.push_back(sub_vec1[x]);
                    x++;
                }
                // 此时插入后半部分区间值sub_vec2[x]
                else {
                    vec.push_back(sub_vec2[y]);
                    y++;
                }
            }
            // 处理剩余元素
            while (x < sub_vec1.size()) {
                ans[sub_vec1[x].second] += y; // 对应索引位置更新
                vec.push_back(sub_vec1[x]);
                x++;
            }
            while (y < sub_vec2.size()) {
                vec.push_back(sub_vec2[y]);
                y++;
            }
        }
        
        void merge_sort(vector<pair<int, int> >& vec, vector<int>& ans) {
            if (vec.size() < 2) return; // 当拆分后的数组大小<=1，则直接返回
            // 拆分为2个数组
            int mid = vec.size() / 2;
            vector<pair<int, int> > sub_vec1;
            vector<pair<int, int> > sub_vec2;
            for (int i = 0; i < mid; i++) {
                sub_vec1.push_back(vec[i]);
            }
            for (int i = mid; i < vec.size(); i++) {
                sub_vec2.push_back(vec[i]);
            }
            merge_sort(sub_vec1, ans);
            merge_sort(sub_vec2, ans);
            vec.clear(); // 清空 以存放归并后的数组
            merge_two_vec(sub_vec1, sub_vec2, vec, ans);
        }
        
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> ans;
            if (nums.size() == 0) return ans;
            vector<pair<int, int> > vec;
            for (int i = 0; i < nums.size(); i++) {
                ans.push_back(0); // 初始化结果数组
                vec.push_back(make_pair(nums[i], i)); // 存储nums[i]与对应索引i
            }
            merge_sort(vec, ans);
            return ans;
        }
    };

    搜索

    一、 leetcode 200. 岛屿数量

    基础DFS解法:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // DFS找到从（x,y）出发连接的'1'，即一个岛屿
    void DFS(vector<vector<char>>& grid, vector<vector<int> >& seen, int x, int y) {
        seen[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int next_x = x + dirs[i][0];
            int next_y = y + dirs[i][1];
            // 超出边界
            if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size()) 
                continue;
            // 已访问过
            if (seen[next_x][next_y]) continue;
            // 是岛屿 继续DFS
            if (grid[next_x][next_y] == '1') {
                DFS(grid, seen, next_x, next_y);
            }
        }
    }
    基础BFS解法:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    // BFS找到从（x,y）出发连接的'1'，即一个岛屿
        void BFS(vector<vector<char>>& grid, vector<vector<int> >& seen, int x, int y) {
        queue<pair<int, int> > mq;
        mq.push(make_pair(x, y));
        seen[x][y] = 1; // 入队标志
        while (!mq.empty()) {
            int cur_x = mq.front().first;
            int cur_y = mq.front().second;
            mq.pop();
            for (int i = 0; i < 4; i++) {
                int next_x = cur_x + dirs[i][0];
                int next_y = cur_y + dirs[i][1];
                // 超出边界
                if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size()) 
                    continue;
                // 是岛屿 继续DFS
                if (!seen[next_x][next_y] && grid[next_x][next_y] == '1') {
                    mq.push(make_pair(next_x, next_y)); // 入队
                    seen[next_x][next_y] = 1;
                }
            }
        }
    }

    二、leetcode 127. 单词接龙

  11. 建立图关系：差一个字母的单词有关系；
  12. BFS
    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
    class Solution {
    public:
        // 建立单词间关系图：相差一个字母的单词为一组
        void construct_graph(map<string, vector<string> >& graph, vector<string>& wordList, int len) {
            // 初始化graph
            for (int i = 0; i < wordList.size(); i++) {
                for (int j = 0; j < len; j++) {
                    string temp = wordList[i];
                    temp[j] = '*'; // 替换为‘*’,作为key
                    if (graph.count(temp) == 0) {
                        vector<string> vec;
                        vec.push_back(wordList[i]);
                        graph[temp] = vec;
                    }
                    else graph[temp].push_back(wordList[i]);
                }
            }
            return;
        }
        
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            int len = beginWord.length();
            map<string, vector<string> > graph; // 单词，相差一个字母的其他单词表
            wordList.push_back(beginWord); // 也需考虑beginWord
            construct_graph(graph, wordList, len);
            // 进行BFS
            queue<pair<string, int> > q; // 队列(单词，当前步数)
            set<string> visit; // 是否访问过
            q.push(make_pair(beginWord, 1));
            visit.insert(beginWord);
            while (!q.empty()) {
                string cur_s = q.front().first;
                int cur_step = q.front().second;
                q.pop();
                if (cur_s == endWord) {
                    return cur_step;
                }
                for (int i = 0; i < len; i++) { // 替换每个字母为'*', 都存在路径
                    string temp_s = cur_s;
                    temp_s[i] = '*';
                    vector<string> neighbors = graph[temp_s];
                    for (int j = 0; j < neighbors.size(); j++) {
                        if (visit.find(neighbors[j]) == visit.end()) {
                            q.push(make_pair(neighbors[j], cur_step + 1));
                            visit.insert(neighbors[j]);
                        }
                    }
                }
            }
            return 0;
        }
    };

    升级leetcode 126. 单词接龙 II

    记录单词接龙的路径：
  13. 使用vector作为BFS数组，建立Qitem数据结构，同时存储(word, step, parent_pos);
  14. map<string, int> visit 记录到某单词的最短路径;

三、leetcode 473. 火柴拼正方形

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
class Solution {
public:
    bool makesquare(vector<int>& nums) {
        if (nums.size() < 4) return false; // 个数不足4
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 4 != 0) return false; // 和不为4的倍数
        int target = sum / 4;
        vector<int> ok_subset;
        vector<int> ok_half;
        int all = 1 << nums.size();
        for (int i = 0; i < all; i++) {
            int sum = 0;
            for (int j = 0; j < nums.size(); j++) {
                if (i & (1 << j)) { // i代表的集合中存在第j个元素
                    sum += nums[j]; // 求该集合的和
                }
            }
            if (sum == target) ok_subset.push_back(i); // 和 = target，保存i集合
        }
        // 使4条边两两结合
        for (int i = 0; i < ok_subset.size(); i++) {
            for (int j = i + 1; j < ok_subset.size(); j++) {
                if ((ok_subset[i] & ok_subset[j]) == 0) { // 子集中存在的值不重合
                    ok_half.push_back((ok_subset[i] | ok_subset[j]));
                }
            }
        }
        // 使两部分两两结合 组成正方形
        for (int i = 0; i < ok_half.size(); i++) {
            for (int j = i + 1; j < ok_half.size(); j++) {
                if ((ok_half[i] & ok_half[j]) == 0) { // 子集中存在的值不重合
                    return true;
                }
            }
        }
        return false;
    }
};

动态规划

一、leetcode 70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        // dp状态数组：dp[i]表示到达i级阶梯有多少方法
        vector<int> dp(n + 1, 0);
        // 初始化
        dp[0] = 1; // 爬一个台阶
        dp[1] = 2; // 爬2个台阶或分别爬1个台阶
        // 状态转移
        // dp[i]的值为dp[i - 1]再爬1个 + dp[i - 2]爬2个
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n - 1];
    }
};

二、leetcode 198. 打家劫舍

dp[i]表示 [0, i]范围内的最高金额;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        // dp状态数组
        // dp[i]表示[0, i]的最高金额
        vector<int> dp(nums.size());
        // 初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        // 状态转移
        // i-1被偷，则不能偷i
        // i-2被偷，可以偷i
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

三 leetcode 53. 最大子序和

dp[i]:以nums[i]为结尾的最大子序和;

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 maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        // dp状态数组
        // dp[i]:以nums[i]为结尾的最大子序和
        vector<int> dp(nums.size());
        // 初始化
        dp[0] = nums[0];
        int res = dp[0];
        // 状态转移
        // dp[i]的值是以i-1为结尾的最大子序和+当前nums[i] 或者 以当前nums[i]开头
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if (res < dp[i]) {
                res = dp[i];
            }
        }
        return res;
    }
};

四、leetcode 322. 零钱兑换

dp[i]:i元时需要的最少硬币数

五、120. 三角形最小路径和

自底向上；
triangle直接作为状态数组，triangle[i][j]表示从底部到当前位置的最短路径长度；
状态转移方程为triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
最终结果为triangle[0][0].

六、300. 最长上升子序列

dp[i]:以nums[i]为结尾的最长上升子序列，结尾需要遍历dp，得出最大长度.

七、64. 最小路径和

自底向上；
grid[i][j]只可能从右侧或者下方回来，
状态转移方程：grid[i][j] += min(grid[i][j + 1], grid[i + 1][j]);

八、leetcode 174. 地下城游戏

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
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        if (m == 0) return 0;
        int n = dungeon[0].size();
        // dp[i][j]：从该位置到P 所需的初始点数
        vector<vector<int>> dp(m, vector<int>(n));
        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
        // 初始化
        // 最后一列
        for (int i = m - 2; i >= 0; i--) {
            // 当后一个所需血量可以被当前房间内抵消时，初始血量设置为1
            // 否则计算出相差血量，作为该位置的初始血量(dp[i][n - 1])
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        // 最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int dp_min = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(1, dp_min - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

Trie树(字典树)

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# define TRIE_MAX_CHAR_NUM 26
struct TrieNode {
    TrieNode * child[TRIE_MAX_CHAR_NUM]; // 孩子数组 后续26个字母
    bool is_end; // 单词结束标志
    TrieNode(): is_end(false) { // 构造函数 初始化
        for (int i = 0; i < TRIE_MAX_CHAR_NUM; i++) {
            child[i] = 0;
        }
    }
};
class TrieTree {
private:
    TrieNode _root;
    vector<TrieNode *> _node_vec; // 为了析构
    TrieNode * new_node() {
        TrieNode * node = new TrieNode();
        _node_vec.push_back(node);
        return node;
    }

public:
    TrieTree() {
    }
    ~TrieTree() {
        for (int i = 0; i < _node_Vec.size(); i++) {
            delete _node_vec[i];
        }
    }
    // 插入一个单词
    void insert(const char *word) {
        TrieNode *ptr = &_root; // 获取Trie树根节点
        while (*word) { // 直到到达单词尾部
            int pos = *word - 'a';
            if (!ptr->child[pos]) { // 空 新建
                ptr->child[pos] = new_node();
            }
            ptr = ptr->child[pos]; // 到达子节点位置
            word++; // word位置递增
        }
        ptr->is_end = true; // 标记单词结束
    }
    // 搜索单词是否存在
    bool search(const char *word) {
        TrieNode* ptr = &_root;
        while (*word) {
            if (!ptr->child[*word - 'a']) return false;
            ptr = ptr->child[*word - 'a'];
            word++;
        }
        return ptr->is_end;
    }
    // 判断是否存在该前缀
    bool startsWith(const char *prefix) {
        TrieNode* ptr = &_root;
        while (*prefix) {
            if (!ptr->child[*prefix - 'a']) return false;
            ptr = ptr->child[*prefix - 'a'];
            prefix++;
        }
        return true;
    }
}

一、leetcode 208. 实现 Trie (前缀树)

经典insert、search、startswith

二、leetcode 211. 添加与搜索单词 - 数据结构设计

DFS查找带有“.”的字符串在字典树中是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool dfs_search(TrieNode* ptr, string word, int i) {
        if (i >= word.length()) {
            if (ptr->is_end) return true;
            return false;
        }
        if (word[i] != '.') {  
            if (ptr->child[word[i] - 'a']) { // 匹配并且下一步为true
                if (dfs_search(ptr->child[word[i] - 'a'], word, i + 1)) return true;
            }
        }
        else { // 点字符 可匹配任意后续字母
            // 遍历后续字母 dfs
            for (int j = 0; j < TRIE_MAX_CHAR_NUM; j++) {
                if (ptr->child[j]) {  // 每一个可能的后续字符
                    if (dfs_search(ptr->child[j], word, i + 1)) return true;
                }
            }
        }
        return false;
    }

并查集

一、leetcode 547. 朋友圈

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
class Solution {
public:
    vector<int> friends;
    vector<int> _size; // 各子树规模
    int findfather(int x) {
        while (friends[x] != x) {
            friends[x] = friends[friends[x]]; // 路径压缩
            x = friends[x];
        }
        return x;
    }
    void union_two(int a, int b) {
        int a_father = findfather(a);
        int b_father = findfather(b);
        if (a_father == b_father) return;
        if (_size[a_father] < _size[b_father]) { // 小的向大的合并 以减小查询复杂度
            friends[a_father] = b_father;
            _size[b_father] += _size[a_father];
        }
        else {
            friends[b_father] = a_father;
            _size[a_father] += _size[b_father];
        }
        /*for (int i = 0; i < friends.size(); i++) { // 更新所有以b_father为父母的friends值
            if (friends[i] == b_father) {
                friends[i] = a_father; 
            }
        }*/
    }
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        // 并查集初始化
        for (int i = 0; i < n; i++) {
            friends.push_back(i);
            _size.push_back(1); // 本身大小1
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (M[i][j]) {
                    union_two(i, j);
                }
            }
        }
        // 找不同father总数
        map<int, int> mp;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (mp.find(findfather(friends[i])) == mp.end()) {
                res++;
                mp[findfather(friends[i])] = 1;
            }
        }
        return res;
    }
};

线段树

参考链接

leetcode 307. 区域和检索 - 数组可修改

求数组区间和：建立/更新/查询线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class NumArray {
private:
    vector<int> _values; // 线段树数组
    int _right_end; // 保存右边界
public:
    /// 构建线段树
    // value：线段树数组(存储区间和)
    // nums：用来构建线段树的数组(已知)
    // pos：在线段树数组value中的当前位置
    // left,right：nums数组中的区间左右边界
    void build_segment_tree(vector<int>& value, vector<int>& nums, int pos, int left, int right) {
        if (left == right) {
            value[pos] = nums[left];
            return;
        }
        int mid = (left + right) / 2;
        build_segment_tree(value, nums, 2 * pos + 1, left, mid); // 构建左子树
        build_segment_tree(value, nums, 2 * pos + 2, mid + 1, right); // 构建右子树
        value[pos] = value[2 * pos + 1] + value[2 * pos + 2]; // 合并
    }
    
    /// 线段树求和
    // value:线段树数组
    // pos：在value中的下标位置
    // left,right：nums数组的当前区间范围
    // qleft,qright：待查询区间
    // [left,right]因递归不断在缩小，[qleft,qright]不变
    int sum_range_segment_tree(vector<int>& value, int pos, int left, int right, int qleft, int qright) {
        if (qleft > right || qright < left) { // 区间不相交
            return 0;
        }
        if (qleft <= left && qright >= right) { // 区间有重叠部分
            return value[pos];
        }
        int mid = (left + right) / 2;
        return sum_range_segment_tree(value, 2 * pos + 1, left, mid, qleft, qright) + sum_range_segment_tree(value, 2 * pos + 2, mid + 1, right, qleft, qright);
    };
    
    /// 线段树更新
    // value:线段树数组
    // pos：在value中的下标位置
    // left,right：nums数组的当前区间范围
    // index：nums更新的下标值
    // new_val
    void updata_segment_tree(vector<int>& value, int pos, int left, int right, int index, int new_value) {
        if (index == left && index == right) { // 当前区间为待更新点
            value[pos] = new_value;
            return;
        }
        int mid = (left + right) / 2;
        if (mid >= index) updata_segment_tree(value, 2 * pos + 1, left, mid, index, new_value);
        else updata_segment_tree(value, 2 * pos + 2, mid + 1, right, index, new_value);
        value[pos] = value[2 * pos + 1] + value[2 * pos + 2];
    }
    
    NumArray(vector<int>& nums) {
        if (nums.size() == 0) return;
        int n = nums.size() * 4; // 一般线段树大小是原数组大小长度的4倍
        for (int i = 0; i < n; i++) {
            _values.push_back(0);
        }
        _right_end = nums.size() - 1;
        build_segment_tree(_values, nums, 0, 0, _right_end);
    }
    
    void update(int i, int val) {
        updata_segment_tree(_values, 0, 0, _right_end, i, val);
    }
    
    int sumRange(int i, int j) {
        return sum_range_segment_tree(_values, 0, 0, _right_end, i, j);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

二、leetcode 1157. 子数组中占绝大多数的元素

线段树中存储 在当前区间中，通过打擂法胜出的值；
在query过程中，找到查询区间中，出现次数最多的值x；
哈希表indices_map存储值与对应的索引数组；
在索引数组中找到在[left, right]区间内的个数，判断是否符合要求即可。

三、leetcode 218. 天际线问题

tree线段树数组存储 离散化x值数组各区间内的高度最大值;
使用懒下传。

贪心

在每一步做出在当前来看的最优选择。

一、leetcode 455. 分发饼干

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:
    // g:需求因子数组
    // s:糖果数组
    // 贪心思想：用最小的饼干量满足需求
    // 双指针：child cookie
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0, cookie = 0;
        while (child < g.size() && cookie < s.size()) {
            if (g[child] <= s[cookie]) { // 当前饼干量满足孩子需求
                child++;
                cookie++;
            }
            // 当前饼干量无法满足孩子需求 则也无法满足后续孩子需求
            // 是个废饼干
            else {
                cookie++;
            }
        }
        return child;
    }
};

二、leetcode 376. 摆动序列

状态机 + 贪心：从左到右的遍历过程中，若持续下降/上升，选取最右边界作为摆动序列的一部分，以使摆动序列最长；

三、leetcode 402. 移掉K位数字

栈 + 贪心：从左到右遍历（高位到低位）,如果对应数字大于下一位数字，则应该把该数字去掉，以取得最小数

四、leetcode 55. 跳跃游戏

当前位置cur_pos,当前可以到达的范围nums[cur_pos] + cur_pos,找到该范围中可以到达最远位置的下标值，作为跳跃目标。
升级题:leetcode 45. 跳跃游戏 II

五、leetcode 452. 用最少数量的箭引爆气球

六、leetcode 871. 最低加油次数

贪心+最大堆（有点跳跃游戏的思想：你尽管走，不够了就加）

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:
    // 贪心：在不得不加的时候加最多的油，使加油次数最少
    // station:0:距离起点的位置；1:油站所拥有的油量
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> Q; // 存储油量的最大堆
        int res = 0; 
        vector<int> temp(2);
        temp[0] = 0;
        temp[1] = startFuel;
        stations.push_back(temp);
        temp[0] = target;
        temp[1] = 0;
        stations.push_back(temp);
        sort(stations.begin(), stations.end()); // 从起点到终点
        int fuel = startFuel;
        for (int i = 1; i < stations.size(); i++) {
            int dis = stations[i][0] - stations[i - 1][0]; // 此次需要走的距离
            while (!Q.empty() && fuel < dis) { // 当前油量无法满足 则从最大堆中选取最大油量来加
                fuel += Q.top();
                Q.pop();
                res++;
            }
            if (Q.empty() && fuel < dis) return -1; // 加满油也无法前进dis
            fuel -= dis;
            Q.push(stations[i][1]); // 将油量放入最大堆
        }
        return res;
    }
};

其他

leetcode 122 买卖股票的最佳时机 II
leetcode 881 救生艇
leetcode 316. 去除重复字母
leetcode 435. 无重叠区间
贪心(区间调度):优先选择end小的(首先根据end升序排序)，使剩下的区间最多，则移除区间最少，与452类似.
leetcode 659. 分割数组为连续子序列
leetcode 861. 翻转矩阵后的得分
（难）321/330/757