秋招已经基本结束，重新整理一下各种笔记资料，这里整理以下leetcode分类刷题的资料。

github地址：https://github.com/lxztju/leetcode-algorithm

更加详细的分类刷题笔记，请跳转github页面查看，这里主要整理部分相关类型的题目，长文预警，整理不易，先赞后看。

全文的pdf版本，请到文末的小哲AI中，回leetcode自取。

一、 双指针

主要有两种： 对撞指针和快慢指针

1.1 对撞指针

对撞指针的问题,一般是数组首尾各有一个指针,这俩指针往中间移动过,解决相对应的问题

• 167 有序数组的 Two Sum 2 (easy)
• 125 验证回文串(easy)
• 11 盛最多水容器(medium)

167 有序数组的 Two Sum 2 (easy)

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

• 题解思路:
  • 数组是升序排列, 首尾各设置一个指针, 查找两个指针的值的和为target.
  • 当二者之和大于target时,尾指针前移,这两个数的和减小; 小于target时,首指针后移,直到二者数组的和等于target.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // 首尾指针
        int head = 0, tail = numbers.size() - 1;
        while (head <= tail){
            int point_sum = numbers[head] + numbers[tail];
            if ( point_sum== target)
                return {head + 1, tail + 1};
            // 和小于target,首指针后移
            else if (point_sum < target)
                head++;
            // 和大于target, 尾指针前移
            else
                tail--;
        }
        return {};
    }
};

125 验证回文串(easy)

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

class Solution {
public:
    bool isPalindrome(string s) {
        int head = 0, tail = s.size() -1;
        while (head < tail){
            // isalnum() 数字或者字母时为真.
            if (isalnum(s[head]) && isalnum(s[tail])){
                // 忽略大小写,直接将其都转化为小写进行比较
                if (tolower(s[head]) != tolower(s[tail]))
                    return false;
                else
                    head++; tail--;
            }
            else if (! isalnum(s[head]))
                head++;
            else if (! isalnum(s[tail]))
                tail--;
        }
        return true;
    }
};

11 盛最多水容器(medium)

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

• 题解:
  • 这道题依然采用首尾指针, 这个矩形的面积为长x高, 长为两个指针之间的距离, 高由两个指针所对应的元素中的最小值决定.
  • 两个指针中高度较小的指针向内移动,找对应的更高的值.例如左边低,那么左指针右移虽然长变小了,但是高可能变高,整体面积才可能变大. 如果右指针左移,那么高永远由左边决定,此时长也变小了,整体的面积更小.
  • 因此只能移动短边对应的指针.

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 定义头尾指针
        int head = 0, tail = height.size() - 1;
        // 保存最大的矩形面积
        long maxarea = 0;
        while (head < tail){
            // 左边低, 那么左指针右移找寻更高的 高
            // 如果右指针左移, 那么高还是左指针的值,但是长变小了,只能移动短边
            if (height[head] < height[tail]){
                long area = height[head] * (tail - head);
                maxarea = max(maxarea, area);
                head++;
            }
            // 右边低,右指针左移
            else {
                long area = height[tail] * (tail - head);
                maxarea = max(maxarea, area); 
                tail--;               
            }
        }
        return maxarea;
    }
};

1.2 快慢指针

快慢指针是指两个指针从头开始一个快一个慢指针, 一般就是, 最经典的题目就是针对链表的问题(快慢指针查找链表的中心点).

• 141 判断列表是否存在环(easy)
• 283 移动零(easy)
• 26 删除排序数组中的重复项(easy)
• 80 删除排序数组中的重复项 II(medium)

141 判断列表是否存在环(easy)

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

• 题解:
  • 使用快慢指针,就像赛跑,一个人跑得快一个人跑得慢两个人肯定会相遇.
  • 这道题快慢指针,如果二者相遇之后就说明二者有环,否则快指针就会首先达到链表末尾.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return false;
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head->next;
        // 如果fast指针没有到达链表的结尾,就持续移动快慢指针.
        while (fast != nullptr && fast->next != nullptr){
            // 如果二者相遇,说明有环
            if (fast == slow) return true;
            slow = slow->next;
            fast = fast->next->next;
        }
        // 快指针到达链表的结尾,说明没有环.
        return false;
    }
};

26 删除排序数组中的重复项(easy)

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

• 题解:
  • 使用快慢指针,慢指针指向最终保留的数字,也就是待交换的数字,快指针向后遍历找寻不重复的元素与慢指针的位置进行交换,从而首先将不重复的元素保留在数组的前部.
  • 快指针向后遍历,当快慢指针对应的值不相同的时候,说明出现了一个新的不重复数字,将其进行交换.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 快慢指针
        int slow = 0, fast = 0;
        if (nums.size() == 0) return 0;
        while (fast < nums.size()){
            if (nums[fast] != nums[slow]){
                slow++;
                swap(nums[fast], nums[slow]);
            }
                fast++;
        }
        return slow+1;
    }
};

80 删除排序数组中的重复项 II(medium)

给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

这道题与上一题相比难在重复的字符可以出现两次.

• 题解:
  • 这里就需要在上一题的基础上加以改进,也就是要判断字符已经保存的次数cnt表示

class Solution {
public:
  int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return 1;
    
    int slow = 0, fast = 1;
    int cnt = 1;    //cnt表示某个字符出现的次数

    while (fast < nums.size() ) {
        if (nums[fast] == nums[slow]) {
            // 如果这个字符仅仅出现了一次, 那么慢指针后移并赋值
            if (cnt == 1) {
                slow++;
                nums[slow] = nums[fast];
                cnt++;
            }
            //如果已经出现了两次,就直接快指针后移
        } 
        // 如果不相等,那么直接复制,也就是字符仅仅出现一次
        else {
            slow++;
            nums[slow] = nums[fast];
            cnt = 1;
        }
        fast++;
    }
    return slow + 1;
  }
};

二、 哈希表

哈希表是一种很有用的数据结构, 其作用主要是以空间换时间, 在c++中主要是unordered_set与unordered_map,在python中主要是set与dict.

• 1 两数之和 (Easy)
• 217 存在重复元素 (Easy)
• 594 最长和谐子序列 (Easy)
• 128 最长连续序列 (Hard)
• 349 两个数组的交集（easy）
• 350 两个数组的交集 II（easy）
• 242 有效的字母异位词（easy）
• 202 快乐数（easy）
• 205 同构字符串（easy）
• 451 根据字符出现频率排序（medium）
• 15 三数之和（medium）
• 18 四数之和（medium）
• 454 四数相加 II（medium）
• 49 字母异位词分组（medium）
• 447 回旋镖的数量（easy）
• 219 存在重复元素 II（easy）

1 两数之和 (Easy)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍

• 题解:
  • 1. 使用哈希表(unordered_map)存储访问过的元素,这道题需要返回索引,因此键为元素的值,值为其对应的索引.
  • 2. 遍历整个数组,对于nums[i], 如果target-nums[i]存在于哈希表中,那就说明找到了这两个数.
  • 3. 如果target - nums[i]不在哈希表中就将nums[i]存在哈希表中.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 定义哈希表
        unordered_map<int, int> visited;
        for(int i = 0; i < nums.size(); i++){
            int tmp = target - nums[i];
            if (visited.find(tmp) != visited.end())
                return {i, visited[tmp]};
            else
                visited.insert(make_pair(nums[i], i));
        }
        return {};
    }
};

217 存在重复元素 (Easy)

• 题解1:

  • 简单使用哈希表存储访问过的元素,然后依次判断遍历的元素是否被访问过.

• 题解2:

  • 排序,然后查找是否有相邻的相等元素.

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // 使用unordered_set存储访问过的元素.
        unordered_set<int> visited;
        for (auto num: nums){
            if (visited.find(num) != visited.end())
                return true;
            visited.insert(num);
        }
        return false;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size() < 2) return false;
        // 排序.
        sort(nums.begin(), nums.end());
        for (int i = 1; i< nums.size(); i++){
            if (nums[i] == nums[i-1])
                return true;
        }
        return false;
    }
};

594 最长和谐子序列 (Easy)

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度

• 题解:
  • 遍历一遍vector,使用哈希表存储每个数字出现的次数
  • 遍历哈希表,找相邻数字出现次数之和最大.

class Solution {
public:
    int findLHS(vector<int>& nums) {
        // 遍历一遍存储每个字符出现的次数
        // 判断相邻数目最大的和.
        unordered_map<int, int> numCnt;
        int res = 0;
        for (auto num: nums){
            if (numCnt.find(num) == numCnt.end())
                numCnt.insert(make_pair(num, 1));
            else
                numCnt[num]++;
        }
        for (auto e = numCnt.begin(); e != numCnt.end(); e++){
            if (numCnt.find(e->first+1) == numCnt.end())
                continue;
            else
                res = max(res, e->second + numCnt[e->first+1]);
        }
        return res;
    }
};

128 最长连续序列 (Hard)

• 题解1 : 哈希暴力法(超时)
  • 将数组中所有的元素存入unordered_set中
  • 遍历数组,以每个元素作为开头,找寻连续子列的长度
  • 保存最长的长度

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 暴力法.直接以每个数字为开头,遍历所有的元素,找寻最长的子列, 超时
        unordered_set<int> nums_set(nums.begin(), nums.end());
        int max_length = 0;
        for (auto num: nums){
            int length = 0;
            int tmp = num;
            while (nums_set.find(tmp) != nums_set.end()){
                tmp++;
                length++;
            }
            max_length = max(max_length, length);
        }
        return max_length;
    }
};

• 题解2: 找寻合适开头去重
  • 上边的方法以数组中每个元素均作为开头进行处理,存在大量重复计算
  • 针对数组中的元素, 如果其减一之后的数字,依然存在数组中,说明其不适合作为开头,跳过这个元素.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 直接采用暴力法以每个字符为开头,期间包含很多重复不必要的工作
        // 因此需要找到一个合适的开头进行扫描,如果元素减一存在于数组中,那么说明不能以这个字符作为开头
        unordered_set<int> nums_set(nums.begin(), nums.end());
        int max_length = 0;
        for (auto num: nums){
            int tmp = num;
            if (nums_set.find(--num) != nums_set.end()) continue;

            int length = 0;
            while (nums_set.find(tmp) != nums_set.end()){
                tmp++;
                length++;
            }
            max_length = max(max_length, length);
        }
        return max_length;
    }
};

349 两个数组的交集（easy）

• 题解: 哈希表
  • 将其中较短的数组存入unordered_set中
  • 遍历另一个数组中的元素是否在这个哈希表中,记录存在的元素
  • 如果发现一个元素存在哈希表中需要删除这个元素,防止重复.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        if (nums1.size() > nums2.size()){
            unordered_set<int> nums_set(nums2.begin(), nums2.end());
            for (auto num: nums1){
                if (nums_set.find(num) != nums_set.end()){
                    res.push_back(num);
                    nums_set.erase(num);
                }
            }
        }
        else{
            unordered_set<int> nums_set(nums1.begin(), nums1.end());
            for (auto num: nums2){
                if (nums_set.find(num) != nums_set.end()){
                    res.push_back(num);
                    nums_set.erase(num);
                }
            }            
        }
        return res;
    }
};

350 两个数组的交集 II（easy）

• 题解:
  • 需要统计重复数字出现的数目,因此采用unordered_map统计数组中的元素数目

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        //使用两个unordered_map分别记录两个数组中出现的次数的最大值.
        unordered_map<int, int> nums1_map;
        unordered_map<int, int> nums2_map;
        vector<int> res;
        for(auto num: nums1)
            nums1_map[num]++;
        for (auto num: nums2)
            nums2_map[num]++;

        for (auto e=nums1_map.begin(); e!= nums1_map.end(); e++){
            if (nums2_map.find(e->first) != nums2_map.end()){
                int cnt = min(nums2_map[e->first], e->second);
                for(int i = 0; i< cnt; i++)
                    res.push_back(e->first);
            }
        }
        return res;
    }
};

242 有效的字母异位词（easy）

• 题解:
  • 使用哈希表统计两个字符串中每个字符出现的次数
  • 对比两个哈希表的内容是否相同

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 直接使用哈希表进行遍历对比即可. 
        // 使用map统计么个字符出现的次数,可以仅仅使用一个map
        if (s.size() != t.size()) return false;
        unordered_map<int, int> scnt;
        for (auto s_substring : s){
            scnt[s_substring]++;
        } 
        for (auto t_substring : t){
            if (scnt[t_substring] < 0) return false;
            scnt[t_substring]--;
        }

        for (auto e=scnt.begin(); e!=scnt.end(); e++){
            if (e->second != 0) return false;
        }
        return true;
    }
};

202 快乐数（easy）

• 题解:
  • 使用哈希表保存已经访问过的元素
  • 如果下一个的和,已经出现过,说明出现了死循环,这就不是快乐数

class Solution {
public:
    bool isHappy(int n) {
        // 使用哈希表保存已经访问过的元素, 防止出现死循环
        unordered_set<int> visited;
        int res = n;
        while (true){
            if (res == 1) return true;
            else if (visited.find(res) != visited.end()){
                return false;
            }
            int dec = res;
            visited.insert(res);
            int sum_values = 0;
            while (dec){
                int re = dec % 10;
                dec /= 10;
                sum_values += pow(re, 2);
                res = sum_values;
            }
        }
    }
    
};

205 同构字符串（easy）

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;
        unordered_map<char, char> s2t;
        unordered_map<char, char> t2s;
        int len = s.size();
        for (int i = 0; i < len; ++i) {
            char x = s[i], y = t[i];
            if ((s2t.find(x)!= s2t.end() && s2t[x] != y) || (t2s.find(y) != t2s.end() && t2s[y] != x)) {
                return false;
            }
            s2t[x] = y;
            t2s[y] = x;
        }
        return true;
    }
};

451 根据字符出现频率排序（medium）

• 题解:
  • 使用unordered_map保存每个字符出现的次数
  • 将map中对应的pair保存至vector中
  • 根据pair的第二个参数(数字)进行sort排序
  • 保存string结果

class Solution {
public:
    string frequencySort(string s) {
        // 使用map保存每个字符出现的次数
        // 采用vector保存结果并进行排序
        // 返回string格式的结果
        unordered_map<char, int> snum;
        for (auto chr : s){
            snum[chr]++;
        }
        string res;
        res = sortfreq(snum);
        return res;
    }
    string sortfreq(unordered_map<char, int>& snum){
        vector<pair<char, int>> snumpair;
        string s;
        for (auto e = snum.begin(); e!=snum.end(); e++){
            snumpair.push_back(make_pair(e->first, e->second));
        }
        sort(snumpair.begin(), snumpair.end(), freqdecend);
        for (auto spair: snumpair){
            string c1(spair.second, spair.first);
            s += c1;
        }
        return s;
    }
    // 排序的谓词
    static bool freqdecend(pair<char,int>&s1, pair<char, int>& s2){
        return s1.second > s2.second;
    }
};

15 三数之和（medium）

• 题解1:暴力法, 时间复杂度n^3
  • 直接三重循环,找到三个数字
  • 其中需要考虑重复的情况,因此在开始的时候将整个数组排序去重.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 暴力法,三层循环
        vector< vector<int> > res;
        if (nums.size() < 3) return {};
        sort(nums.begin(), nums.end());
        for (int i=0; i < nums.size()-2; i++){
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j=i+1; j<nums.size()-1; j++){
                if (j > i+1 && nums[j] == nums[j-1]) continue;
                for (int k=j+1; k<nums.size(); k++){
                    if (k > j+1 && nums[k] == nums[k-1]) continue;
                    if (nums[i] + nums[j] + nums[k] == 0)
                        res.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return res;
    }
};

• 题解2: 排序后的双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 哈希表,时间换空间.
        vector< vector<int> > res;
        if (nums.size() < 3) return {};

        sort(nums.begin(), nums.end());

        for (int i=0; i < nums.size()-2; i++){
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int target = -nums[i]; // 这就变成了两数之和为target的问题.
            int l = i+1, r = nums.size() - 1;
            while (l < r){
                // cout<< l<< "  "<< r<<endl;
                if (l > i+1 && nums[l] == nums[l-1]) {
                    l++; 
                    continue;
                }
                if (r < nums.size() - 1 && nums[r] == nums[r+1]){
                    r--;
                    continue;
                }
                if (nums[l] + nums[r] == target){
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++; r--;
                }
                else if (nums[l] + nums[r] < target)
                    l++;
                else
                    r--;
            }

        }
        return res;
    }
};

18 四数之和（medium）

• 题解:
  • 同上一题一样, 排序加上双指针

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if (nums.size() < 4) return {};
        vector< vector<int> > res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 3; i++){
            if (i > 0 && nums[i] == nums[i-1]) continue;

            for (int j = i+1; j < nums.size() - 2; j++){
                if (j > i+1 && nums[j] == nums[j-1]) continue;

                int t = target - nums[i] - nums[j];
                int l = j+1, r = nums.size() -1;
                while (l < r){
                    if (l >j+1 && nums[l] == nums[l-1]){
                        l++;
                        continue;
                    }
                    if (r < nums.size()-1 && nums[r] == nums[r+1]){
                        r--;
                        continue;
                    }
                    if (nums[l] + nums[r] == t){
                        res.push_back({nums[i], nums[j], nums[l], nums[r]});
                        l++;
                        r--;
                    }
                    else if(nums[l] + nums[r] < t)
                        l++;
                    else
                        r--;
                }
            }
        } 
        return res;
    }
};

454 四数相加 II（medium）

• 题解:暴力法,超时, 时间复杂度n^4

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        // 直接暴力法,先试试
        int res = 0;
        for (auto numA : A){
            for (auto numB: B){
                for (auto numC: C){
                    for (auto numD: D){
                        if(numA+ numB + numC+ numD == 0){
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
};

• 题解:
  • 将AB作为一组,将CD作为一组,
  • 使用map分别保存每个组合的和与对应的数目
  • 最终和为0的总次数由两个map中互为相反数的键的乘积得到.

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        // 直接暴力法,先试试
        int res = 0;
        unordered_map<int, int> AB_num;
        unordered_map<int, int> CD_num;
        for (auto numA : A){
            for (auto numB: B){
                AB_num[numA+numB]++;
            }
        }
        for (auto numC : C){
            for (auto numD: D){
                CD_num[numC+numD]++;
            }
        }
        
        for (auto e = AB_num.begin(); e!=AB_num.end(); e++){
            res += (e->second) * CD_num[(-(e->first))];
        }
        
        return res;
    }
};

49 字母异位词分组（medium）

• 题解:
  • 排序, 然后直接使用map存储对应的string即可.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string> > code2s;
        vector<vector<string>> res;
        for (string& s: strs){
            string key =  s;
            sort(key.begin(), key.end());
            code2s[key].push_back(s);
        }
        for (auto e = code2s.begin(); e!= code2s.end(); e++){
            res.push_back(e->second);
        }
        return res;
    }
};

447 回旋镖的数量（easy）

• 题解:
  • 以每个点为起始点, 使用map统计这个点与其他点距离的数目.
  • 同一个距离的回旋镖的数目为n*(n-1), n为距离的数目.

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int res = 0;
        for (auto p : points) {
            unordered_map<int, int> dist2num;
            for (auto q : points) {
                int dx = p[0]-q[0];
                int dy = p[1]-q[1];
                dist2num[pow(dy, 2)+pow(dx, 2)]++;
            }

            for (auto x : dist2num) {
                res += x.second * (x.second-1);
            }
        }
        return res;
    }
};

219 存在重复元素 II（easy）

• 题解:
  • 使用unordered_set存储一个不超过k个元素的序列
  • 如果下一个元素存在于列表中,那就说明存在
  • 如果set中元素超过k个,移除最早的元素.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        // 维护一个哈希表,这个哈希表中最多出现k个元素
        // 如果下一个遍历的元素存在于哈希表中,那么说明存在
        if (nums.size() < 2 || k == 0) return false;
        
        unordered_set<int> knums;
        for (int i =0; i < nums.size(); i++){
            if (knums.find(nums[i]) != knums.end()) 
                return true;
            knums.insert(nums[i]);

            if (knums.size() > k){
                knums.erase(nums[i- k]);
            }
        }
        return false;
    }
};

三、二分查找

二分查找是针对一个排序列表,每次利用中间元素折半去掉部分元素,减少重复的查找遍历.

• 对于一个排序数组nums,查找指定的一个数字target,采用二分查找的解题思路
• 利用target与nums数组的中间元素相比较,
  1. 如果target> nums[mid],说明target在数组的后半部分,
  2. 如果target < nums[mid], 说明target在数组的前半部分
  3. 如果target == nums[mid], 找到target.

二分查找的典型解题思路模板代码:

int binary_search(vector<int>& nums, int target){
	int l = 0, r = nums.size() - 1;
	while (l <= r){
		int mid = l + (r - l) / 2;  // 直接采用(r+l)/2. 容易出现整形溢出
		// 找到对应的元素,返回索引
		if (nums[mid] == target) return mid;
		// target比中间值大,说明存在数组后半部分
		else if (nums[mid] < target)
			l = mid + 1;
		// target小, 说明存在数组的前半部分.
		else
			r = mid - 1;
	}
	return -1;
}

两个非常困扰而且易错的细节点:

• while循环的判断条件是l<r还是l<=r
• 当target != nums[mid]时, 使用mid还是mid (+或者-) 1

解决这两个问题的只需要考虑清楚,查找区间的封闭情况, 例如对于上边写的代码,采用的方式为(左右均为闭区间)[l, r], 因此决定了循环判断条件为l<=r. 同时 l = mid + 1与r = mid - 1, 在过程中始终保持全闭区间的情况不变

当然代码也可以采用左开右闭或者左闭右开的区间进行查找,然后判断需要如何更改这两个问题.

• 69 x 的平方根 (Easy)
• 744 寻找比目标字母大的最小字母 (Easy)
• 278 第一个错误的版本 (Easy)
• 540 有序数组中的单一元素 (Medium)
• 153 寻找旋转排序数组中的最小值 (Medium)
• 34 在排序数组中查找元素的第一个和最后一个位置(medium)

69 x 的平方根 (Easy)

• 题解: 二分查找
  • 全闭区间进行搜索
  • 注意在计算过程中,直接平方会导致int溢出,需要转换为double,或者long long

class Solution {
public:
    int mySqrt(int x) {
        // 采用二分查找
        // 查找区间为[l, r]
        int l=0, r=x/2;
        while (l <= r){
            int mid = l + (r - l) / 2;
            double pow1 = static_cast<double>(mid) * mid;
            double pow2 = static_cast<double>(mid + 1) * (mid + 1);
            if (pow2 == x) return mid + 1;
            else if (pow1 == x || (pow1 < x && pow2 > x)) return mid;
            else if (pow1 > x)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
};

744 寻找比目标字母大的最小字母 (Easy)

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        if (target >= *(letters.end() - 1)) return *(letters.begin());
        // 全闭区间
        int l = 0, r = letters.size() - 1;
        while (l <= r){
            int mid = l + (r - l) / 2;
            if (target < letters[mid])
                r = mid - 1;
            else if (target >= letters[mid])
                l = mid + 1;
        }
        return letters[l];
    }
};

278 第一个错误的版本 (Easy)

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        // 直接二分即可,找到第一个为false的版本
        // 全闭区间
        int l = 1, r = n;
        while (l <= r){
            int mid = l + (r - l) /2 ;
            if (isBadVersion(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
};

540 有序数组中的单一元素 (Medium)

• 题解: 二分查找
  • 这道题直接判断中间元素左右两侧的子数组哪一部分是奇数,说明单一元素就存在对应的部分
  • 如果mid后半部分的数组是偶数:
  • 1. 那么如果mid与mid+1位置的元素相等, 那么去掉这俩元素后,后半部分就是奇数,说明单一元素存在右半部分, l = mid + 2
  • 2. 如果mid与mid - 1位置相等,那么单一元素存在左半部分, r = mid - 2
  • 同理分析mid的后半部分是奇数.
  • 如果两侧均为偶数,那么mid即为待查找的单一元素.

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        // 二分查找
        // mid为数组中间的元素索引
        // 如果mid与后边或者前边的元素相等, 那么判断哪一侧是奇数就说明在哪一侧
        // 如果mid刚好就是单独的元素,那么直接返回即可
        int l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = l + (r - l) / 2;
            // 后半部分是偶数
            bool second_even = ((r - mid) % 2 == 0);

            if (nums[mid + 1] == nums[mid]){
                if (second_even)
                    l = mid + 2;
                else
                    r = mid - 1;
            }
            else if (nums[mid] == nums[mid - 1]){
                if (second_even)
                    r = mid - 2;
                else
                    l = mid + 1;
            }
            else
                return nums[mid];
        }
        return nums[l];
    }
};

153 寻找旋转排序数组中的最小值 (Medium)

• 题解1: 简单顺序查找
  • 遍历数组, 如果nums[i] > nums[i+1] return num[i+1]
  • 如果遍历完全没有找到,就说明nums[0]是最小的元素.

class Solution {
public:
    int findMin(vector<int>& nums) {
        // 顺序查找, 如果前边元素,大于后边,那么就找到了对应的元素
        for (int i = 0; i < nums.size() - 1; i++){
            if (nums[i] > nums[i+1])
                return nums[i+1];
        }
        return nums[0];
    }
};

• 题解2: 二分查找
  • 采用中间元素与首尾元素进行对比的方式
  • 如果中间元素大于数组尾元素,说明反转点在mid的右边
  • 如果中间元素小于数组的尾部元素. 说明反转点在mid或者在mid的左边

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {          
                left = mid + 1;
            } else {                               
                right = mid;
            }
        }
        return nums[left];
    }
};

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

• 题解: 顺序查找

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 直接顺序查找
        int l = 0, r = nums.size() - 1;
        vector<int> res;
        while (l <nums.size() && nums[l] != target)
            l++;
        while (r > 0 && nums[r] != target )
            r--;
        if (l != nums.size())
            return {l, r};
        else
            return {-1, -1};
    }
};

• 题解2: 二分查找
  • 首先利用二分查找,找到对应的target
  • 然后顺序往左右扩展找到对应的边界

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        // 使用二分查找,找到对应元素, 然后左右遍历得到两个坐标
        int index = -1;
        while (l <= r){
            int mid = l + ( r - l ) / 2;
            //找到对应的元素索引
            if (nums[mid] == target){
                index = mid;
                break;
            }
            else if(nums[mid] < target)
                l = mid + 1;
            else
                r = mid - 1;
        }
		// 没有找到对应的索引
        if (index == -1) 
            return {-1, -1};

        int left = index, right = index;
        // 向左扩展,找到元素左边界
        while (left >= 0 && nums[left] == target )
            left--;
        // 向右扩展找到有边界
        while (right < nums.size() && nums[right] == target)
            right++;
        return {left + 1, right - 1};
    }
};

四、数组和矩阵

• 240 Search a 2D Matrix II (Medium)
• 378 Kth Smallest Element in a Sorted Matrix ((Medium))
• 287 Find the Duplicate Number (Medium)
• 697 Degree of an Array (Easy)
• 766 Toeplitz Matrix (Easy)
• 565 Array Nesting (Medium)

240 Search a 2D Matrix II (Medium)

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

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

• 最直观的想法, 直接遍历二维数组进行对比,这就变成了一道简单题,没有用到题目当中的条件

• 从右上角开始遍历,因为这样遍历,比target小的在左边,比target大的在下边

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 从右上角开始遍历
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n-1;
        while (i >= 0 && i < m && j >= 0 && j < n){
                if (matrix[i][j] == target) 
                    return true;
                else if (matrix[i][j] > target)
                    j--;
                else 
                    i++;
        }
        return false;
    }
};

378 Kth Smallest Element in a Sorted Matrix ((Medium))

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

• 第一个思路: 直接将其变为一维数组,然后直接进行排序,找到第k小的元素.

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> res(m*n, 0);
        int index = 0;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                res[index] = matrix[i][j];
                index++;
            }
        }
        sort(res.begin(), res.end());
        return res[k-1];
    }
};

• 第二个思路,利用优先级队列.

将所有的元素全部插入优先级队列中,然后找到第k个

class point{
    public:
        int val, x, y;
        point()=default;
        point(int val, int x, int y): val(val), x(x), y(y) {}
        bool operator > (const point& a) const {
            return this->val > a.val;
        }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        //按行进行归并排序
        //定义优先级队列,这个队列采用vector实现
        priority_queue<point, vector<point>, greater<point>> q;
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
            q.emplace(point(matrix[i][j], i, j));
        }
        point res;
        for (int i = 0; i < k - 1; i++) {
            res = q.top();
            q.pop();
        }
        return q.top().val;
    }
};

插入的时候不需要将所有的元素均插入,按照其升序的特点,只需要按行插入右侧元素即可,找到最小的k个

class point{
    public:
        int val, x, y;
        point()=default;
        point(int val, int x, int y): val(val), x(x), y(y) {}
        bool operator > (const point& a) const {
            return this->val > a.val;
        }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        //按行进行归并排序
        //定义优先级队列,这个队列采用vector实现
        priority_queue<point, vector<point>, greater<point>> q;
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            q.emplace(point(matrix[i][0], i, 0));
        }
        for (int i = 0; i < k - 1; i++) {
            point now = q.top();
            q.pop();
            if (now.y != n - 1) {
                q.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
            }
        }
        return q.top().val;
    }
};

287 Find the Duplicate Number (Medium)

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和n） 可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

直观的几种想法:

• 直接遍历,两重循环,每次查找元素nums[i]是否在nums[i+1:]的范围内出现,时间复杂度n2,不满足题意
• hash表存储访问过的元素,空间复杂度o(n),不满足题意
• 先排序,然后遍历相邻的相同元素即为重复元素,不满足"不能更改原数组"的要求.

这道题的限制条件,直接堵死了常用的几种直观的思路.

这里采用二分查找来解决这个问题.

题解:

1. 这道题的数字的范围均在1~n之间,且只有一个重复的数.举个例子就知道 例如 [1,3,4,2,2], n=4,因此设置mid = (1+4) / 2=2, 那么小于等于2的数字有3个大于选定的mid,因此重复的数字就肯定小于等于mid,否则重复的数字大于mid

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size()-1;
        int l= 0, r = n;
        // 二分法查找区间
        while (l < r){
            int mid = l + (r - l) / 2;
            int cnt = 0;
            // 统计小于等于mid的数字的数目
            for (auto num :nums){
                if (num <= mid)
                    cnt++;
            }
            // 如果统计的数字大于mid,那么最终重复的数字位于左侧
            if (cnt > mid)
                r = mid;
            else
                l = mid+1;
        }
        return l;
    }
};

697 Degree of an Array (Easy)

给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

简单的题目,但是注意频数最大的数组元素不一定只有一个

#include <algorithm>

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        // 使用无序映射表来存储每个元素在数组中出现的索引列表
        unordered_map<int, vector<int>> res;
        for (auto e : nums){
            res.insert(make_pair(e, vector<int>()));
        }

        for (int i=0; i <nums.size(); i++){
            res[nums[i]].push_back(i);
        }
        
        int min_dis = nums.size();
        int max_ferq = 0;
        // 查找出现最多的索引出现的次数
        for (auto e=res.cbegin(); e != res.end(); e++){
            vector<int> index = e->second;
            int dis = index.size();
            max_ferq = max(max_ferq, dis);
        }
        //统计最小的连续子数组
        for (auto e=res.cbegin(); e != res.end(); e++){
            vector<int> index = e->second;
            if (index.size() == max_ferq){
                min_dis = min(min_dis, index[index.size()-1] - index[0] + 1);
            }
        }
        return min_dis;
    }
};

766 Toeplitz Matrix (Easy)

如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

简单的题目, 仅仅需要发现同一条对角线上的横纵坐标差值为常数(在做八皇后问题也会遇到)就可以了,然后借助map可以轻松求解.

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        // 利用哈希表来,键为行列坐标的差值, 值为对应的数字
        unordered_map<int, int> indexdiff_value;
        for (int i = 0; i < matrix.size(); i++){
            for (int j = 0; j < matrix[0].size(); j++){
                if (indexdiff_value.find(i - j) == indexdiff_value.end())
                    indexdiff_value.insert(make_pair(i-j, matrix[i][j]));
                else{
                    if (matrix[i][j] != indexdiff_value[i-j])
                        return false;
                }
            }
        }
        return true;
    }
};

565 Array Nesting (Medium)

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。

假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。

看似复杂,其实只需要将所有的 这种嵌套的子列全部查找出来,并找到最长的满足条件的最长的长度即可.

例如,对于[5,4,0,3,1,6,2]这个序列,其满足条件的S分别为: [5, 6, 0, 2], [4,1]与[3]这三个从中找到最短的即可.

基本办法就是遍历+ hash表去重

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        //利用哈希表记录访问过的元素,避免重复访问.
        unordered_set<int> visited;

        int res = 0; // 最终的结果,最长的S
        // 遍历,找到所有的字串
        for (int i = 0; i < nums.size(); i++){
            if( visited.find(nums[i]) != visited.end() ) continue;

            int length = 1;  // S的长度
            // 开始查找一个满足条件的S.
            int index = i;
            while (nums[index] != i){
                visited.insert(nums[index]);
                index = nums[index];
                length++;
            }
            visited.insert(nums[i]);
            res = max(res, length);
        }
        return res;
    }
};

五、链表

针对链表这种数据结构,采用指针访问元素,而且指针只可向一个方向移动, 几种主要的操作:

• 快慢指针,找到链表的中点

• 通过pre cur与nex三个指针模拟题目中的流程

• 注意虚拟头节点(在头节点前边新建一个虚拟节点指向头节点)的使用

• 160 相交链表 (Easy)

• 206 反转链表 (Easy)

• 21 合并两个有序链表 (Easy)

• 83 删除排序链表中的重复元素 (Easy)

• 234 回文链表 (Easy)

• 19 删除链表的倒数第N个节点 (Medium)

• 24 两两交换链表中的节点 (Medium)

• 445 两数相加 II (Medium)

• 725 分隔链表 (Medium)

• 328 奇偶链表 (Medium)

160 相交链表 (Easy)

• 题解: 哈希表
  • 一个链表的指针存储到哈希表
  • 遍历另一个链表,查找元素是否存在于哈希表中,如果存在返回指定的元素, 如果不存在返回nullptr

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 哈希表
        //将一个链表存储到哈希表中, 遍历另一个链表查找是否存在哈希表中
        unordered_set<ListNode*> hashset;
        // 将A链表存储至哈希表中
        while (headA != nullptr){
            hashset.insert(headA);
            headA = headA->next;
        }
        // 遍历查找B链表
        while (headB != nullptr){
            if (hashset.find(headB) != hashset.end())
                return headB;
            headB = headB->next;
        }
        return nullptr;
    }
};

• 题解: 双指针
  • 使用两个指针分别指向数组的两个链表的头节点
  • 当headA达到链表A的尾部时,将headA指向B, 当headB达到链表B的尾部时,将headB指向A
  • 当headA与headB相遇时的节点就是相遇节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 双指针
        ListNode* pA = headA;
        ListNode* pB = headB;
        while (pA != pB){
            if (pA == nullptr)
                pA = headB;
            else
                pA = pA->next;

            if (pB == nullptr)
                pB = headA;
            else
                pB = pB->next;
        }
        return pA;
    }
};

206 反转链表 (Easy)

• 题解:
  • 直接模拟反转的过程, 使用三个指针, 一个前置指针pre, 一个当前指针cur, 一个后置指针next
  • 反转的过程: cur指向pre, cur后移, pre后移, 直到cur移动到最后一个节点.
  • 最后设置反转后的链表的结尾(head->next = nullptr).

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 直接模拟反转的过程
        ListNode* pre = head;
        if (head == nullptr ||head->next == nullptr) return head;
        ListNode* cur = head->next;
        while (cur != nullptr){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        head->next = nullptr;
        return pre;      
    }
};

21 合并两个有序链表 (Easy)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 设定一个虚拟的头节点, 比较大小,移动指针.
        ListNode* dummyHead = new ListNode(0);
        ListNode* dummy = dummyHead;
        while (l1 && l2){
            if ((l1->val) >= (l2->val)){
                dummyHead->next = l2;
                l2 = l2->next;
            }
            else{
                dummyHead->next = l1;
                l1 = l1->next;
            }
        dummyHead = dummyHead->next;

        }
        if (l1)
            dummyHead->next = l1;
        else    
            dummyHead->next = l2;
        
        return dummy->next;

    }
};

83 删除排序链表中的重复元素 (Easy)

直接模拟题目的执行过程. 所谓删除,就是使用指针跳过相对应的重复元素.

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 所谓删除,就是使用指针跳过相对应的重复元素.
        ListNode* pre = head;
        ListNode* cur = head;
        while(cur){
            // 利用pre指向所有的元素
            // 当pre与cur的节点的值相等时, pre不动, cur后移
            if( pre->val == cur->val)
                cur = cur->next;
            // 当二者不等时,pre指向cur, 然后pre cur均后移 
            else{
                pre->next = cur;
                pre = pre->next;
                cur = cur->next;
            }
        }
        if (pre != cur)
            pre->next = nullptr;
        return head;

    }
};

234 回文链表 (Easy)

• 题解1: 利用数组
  • 直接遍历并取出链表中的元素存入vector中
  • 利用首尾指针遍历元素,判断是否回文

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> nums;
        while (head){
            nums.push_back(head->val);
            head = head->next;
        }
        int l = 0, r = nums.size() - 1;
        while (l < r){
            if (nums[l] != nums[r])
                return false;
            l++; r--;
        }
        return true;
    }
};

• 题解2: 反转后半部分的链表
  • 利用快慢指针,找到链表中点位置
  • 反转后半部分的链表
  • 再次利用快慢指针找到反转后链表的中点位置,然后对比比较两部分的链表内容是否一致.

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 找到链表后半部分的头节点
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* lastHeadpre = findLastHead(dummy);

        // 反转链表的后半部分
        ListNode* lastHead = lastHeadpre->next;
        if (lastHead == nullptr) return true;
        ListNode* pre = lastHead;
        ListNode* cur = lastHead->next;
        while (cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        
        lastHead->next = nullptr;
        lastHeadpre->next = pre;

        // 找到中间节点
        ListNode* newlastHeadpre = findLastHead(dummy);
        ListNode* newlastHead = newlastHeadpre->next;
        // 判断是否回文
        while(head && newlastHead && head != newlastHead){
            if (head->val != newlastHead->val)
                return false;
            head = head->next;
            newlastHead = newlastHead->next;
        }
        return true;    
    }


    ListNode* findLastHead(ListNode* head){
        // 找到链表后半部分的头节点的前置节点
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

19 删除链表的倒数第N个节点 (Medium)

• 题解: 滑窗 双指针
  • 利用滑窗(双指针), 两个指针之间的距离为n
  • 当后指针达到nullptr(链表结尾)时, 前指针刚好指向倒数第n个节点的前一个节点
  • 利用虚拟头节点,解决删除头节点的问题.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 利用滑窗(双指针), 两个指针之间的距离为n
        // 当后指针达到nullptr(链表结尾)时, 前指针刚好指向倒数第n个节点的前一个节点
        // 利用虚拟头节点,解决删除头节点的问题.
        if (!head) return nullptr;
        ListNode* dummy = new ListNode(0);
        ListNode* first = dummy;
        ListNode* second = dummy;
        dummy->next = head;
        while (second && n >= 0){
            second = second->next;
            n--;
        }
        while (second){
            first = first->next;
            second = second->next;
        }
        first->next = first->next->next;
        return dummy->next;
    }
};

24 两两交换链表中的节点 (Medium)

• 题解: 模拟交换过程
  • 需要四个指针, pre, cur1, cur2, nex
  • 模拟交换的过程,交换cur1与cur2两个节点
  1. pre->next = cur2
  2. cur1->next = nex
  3. cur2->next = cur1
  4. pre = cur1; cur1 = cur1->next;

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;

        while (head && head->next){
            ListNode* cur1 = head;
            ListNode* cur2 = head->next;
            ListNode* nex = cur2->next;

            pre->next = cur2;
            cur2->next = cur1;
            cur1->next = nex;

            pre = cur1;
            head = cur1->next;
        }
        return dummy->next;
        
    }
};

445 两数相加 II (Medium)

• 题解: 反转链表,然后相加

• 题解: 也可以遍历一遍,将结果存储到数组中,然后相加.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    	// 反转两个链表
        ListNode* newl1 = reverseListNode(l1);
        ListNode* newl2 = reverseListNode(l2);
        // 新建结果链表
        ListNode* head = new ListNode(0);
        ListNode* res = head;
        int carry = 0;
        while (newl1 || newl2){
            int l1val = newl1 ? newl1->val : 0;
            int l2val = newl2 ? newl2->val : 0;
            long sumval = l1val + l2val + carry;
            int nodeval = sumval % 10;
            carry = sumval / 10;
            head->next = new ListNode(nodeval);
            if (newl1) newl1 = newl1->next;
            if (newl2) newl2 = newl2->next;
            head = head->next;
        }
        if (carry) head->next = new ListNode(carry);
        return reverseListNode(res->next);
    }

    ListNode* reverseListNode(ListNode* head){
    	// 反转链表
        ListNode* pre = head;
        if (head == nullptr) return head;
        ListNode* cur = head->next;
        while ( cur){
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        head->next = nullptr;
        return pre;
    }
};

725 分隔链表 (Medium)

• 题解:
  • 统计链表中的节点个数
  • 计算每部分应该有几个节点
  • 分割链表

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        // 统计链表的节点数目为cnt
        ListNode* head = root;
        int cnt = 0;
        while (head){
            head = head->next;
            cnt++;
        }
        int quotient = cnt / k;  
        int reminder = cnt % k;

        // 那么结果vector中前reminder的元素中存入quotient+1个节点, 后边的存入quotient个节点
        vector< ListNode* > res;
        ListNode* cur = root;
        int count = 0; 
        int vectorNodeSize = quotient==0 ? reminder : k; // vector中仅仅前reminder中存储节点,后边存储null;
        while (count < vectorNodeSize){
            // 子链表的开头
            ListNode* pre = cur;
            //vector中需要保存的节点数目
            int num = count < reminder ?  quotient + 1 : quotient;
            while (num - 1){
                cur = cur->next;
                num--;
            }
            ListNode * tmp = cur->next;
            cur->next = nullptr;
            res.push_back(pre);
            cur = tmp;
            count++;
        }
        // 链表后边补充nullptr
        for (int i = vectorNodeSize; i < k; i++)
            res.push_back(nullptr);

        return res;
    }
};

328 奇偶链表 (Medium)

• 题解:
  • 使用两个链表分别保存奇数节点与偶数节点
  • 连接两个链表

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //新建两个节点,分别作为奇数与偶数子链表的头节点
        ListNode* oddhead = new ListNode(0);
        ListNode* evenhead = new ListNode(0);

        ListNode* odd = oddhead;
        ListNode* even =evenhead;

        bool flag = true; // 当flag为true时说明此节点为奇数节点, 否则为偶节点
        while (head){
            if(flag){
                ListNode* oddpre = head; // 奇数链表的前置节点
                odd->next = head;
                flag = false;
                odd = odd->next;
            }
            else{
                even->next = head;
                flag = true;
                even = even->next;
            }
            head = head->next;
        }

        // 连接连个链表
        odd->next = evenhead->next;
        even->next = nullptr;
        
        return oddhead->next; 
    }
};

六、栈和队列

栈: 先进先出 队列: 先进后出

利用这两类数据结构的特性解题.

其中一类非常经典的题目是: 单调栈(leetcode496题, 经典题目).

• 单调递减栈, 是指针对每一个待遍历的元素x, 将x与栈顶元素相比, 如果大于栈顶元素将栈顶元素出栈, 重新循环对比,直到小于栈顶元素,然后将x入栈.
• 单调递增栈: 同理分析

---

• 232 用栈实现队列 (Easy)
• 225 用队列实现栈 (Easy)
• 155 最小栈 (Easy)
• 20 有效的括号 (Easy)
• 1021 删除最外层的括号 (easy)
• 496 下一个更大元素 I (easy)
• 503 下一个更大元素 II (Medium)
• 739 每日温度 (Medium)

232 用栈实现队列 (Easy)

• 题解: 两个栈实现

  • 栈的特点时先进后出, 而队列是先进先出
  • 使用两个栈实现先进先出
  • stackin控制入队, stackout控制出队
  • 当入队时,直接压入stackin即可
  • 出队时, 当stackout为空时,将stackin中的元素依次弹出压入stackout中, 然后执行stackout的出栈也就是出队操作.

• 示例 先入队[1,2], 然后执行一次出队, 再入队[3,4], 然后执行两次出队

1. 入队之后stackin为[1,2], stackout为空
2. 执行出队时,将stackin中元素依次压入stackout中, 此时stackout为[2,1], 出队1, stackout为[2], stackin为空
3. 再次入队, stackin为[3,4], 此时stackout为[2]
4. 执行第一次出队时, stackout非空直接出队2, 此时stackin为[3,4], stackout为空
5. 当再次执行出队时, stackout为空,与第二步相同.

class MyQueue {
public:
    stack<int> stackin;
    stack<int> stackout;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stackin.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 如果stackout为空,将stackin中的元素依次放入stackout
        if(stackout.empty())
            while (!stackin.empty() ){
                int tmp = stackin.top();
                stackin.pop();
                stackout.push(tmp);
            }
        // 返回stackout的栈顶元素
        int tmp = stackout.top();
        stackout.pop();
        return tmp;
    }
    
    /** Get the front element. */
    int peek() {
        // 如果stackout为空,将stackin中的元素依次放入stackout
        if(stackout.empty())
            while (!stackin.empty() ){
                int tmp = stackin.top();
                stackin.pop();
                stackout.push(tmp);
            }
        // 返回stackout的栈顶元素
        return stackout.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        if (stackin.empty() && stackout.empty())
            return true;
        else
            return false;
    }
};

225 用队列实现栈 (Easy)

• 题解: 两个队列实现

  • 栈是先进后出的, 队列是先进先出的.
  • 使用队列实现栈就是要 将入队的元素,放置在队首.
  • 这样出栈时, 直接使用队列出队实现.

• q1存储栈中的元素, q2作为入栈时的辅助栈

• 入栈时,先将元素入队到q2, 然后将q1中的元素出队并放入q2中, 此时q2队首的元素即为栈顶元素, 将q1与q2互换, q2始终作为辅助栈.

class MyStack {
public:
    /** Initialize your data structure here. */
    queue<int> q1;
    queue<int> q2;
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        q2.push(x);
        while(!q1.empty()){
            q2.push(q1.front());
            q1.pop();
        }
        swap(q1, q2);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int tmp = q1.front();
        q1.pop();
        return tmp;
    }
    
    /** Get the top element. */
    int top() {
        return q1.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
};

155 最小栈 (Easy)

• 题解: 辅助栈
  • 采用另外的一个辅助栈s2
  • 每次s1入栈出栈时,均在s2的对应位置存入此时对应的最小值
  • 对于辅助栈s2的操作, 对于一个待入栈的元素x, 如果其大于s2的栈顶,就在s2中再次压入栈顶元素, 否则压入x

class MinStack {
public:
    stack<int> s1;
    stack<int> s2;  // 辅助栈
    /** initialize your data structure here. */

    MinStack() {
    }
    
    void push(int x) {
        s1.push(x);
        if (s2.empty())
            s2.push(x);
        else{
            int tmp = s2.top();
            if (x <= tmp)
                s2.push(x);
            else
                s2.push(tmp);
        }
    }
    
    void pop() {
        s1.pop();
        s2.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
};

20 有效的括号 (Easy)

• 题解
  • 最经典的一道使用栈的题目
  • 遇到左括号直接入栈, 遇到右括号,左括号出栈对比

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> parentheses = {{'(', ')'}, {'[', ']'}, {'{', '}'}};  // 字典
        stack<char> stack1;
        for (auto s1: s){
            // s1为右括号
            if (parentheses.find(s1) == parentheses.end()){
                // 如果栈为空, 返回false
                if (stack1.empty()) return false;
                else{
                    char tmp = stack1.top();
                    stack1.pop();
                    // 如果栈顶元素与s1不对应, 返回false
                    if (parentheses[tmp] != s1) return false;
                }
            }
            // s1为左括号, 入栈
            else{
                stack1.push(s1);
            }
        }
        //最后栈为空返回true, 否则返回false.
        if (!stack1.empty()) return false;
        else return true;
    }
};

1021 删除最外层的括号 (easy)

• 题解
  • 括号的匹配, 要使用栈
  • 遍历字符串
  • 如果遇到左括号直接入栈, 如果此时栈中有超过1个左括号, 说明这个左括号需要保留
  • 如果遇到右括号, 左括号对应出栈, 如果此时栈中依然存在左括号, 那么这个右括号需要保留
  • 否则不保留.

class Solution {
public:
    string removeOuterParentheses(string S) {
        string res;
        stack<char> stack1;
        for (auto s1: S){
            if (s1 == '('){
                stack1.push(s1);
                if (stack1.size() > 1)
                    res += s1;
            }
            else{
                stack1.pop();
                if (stack1.size() >= 1)
                    res += ')';
            }
        }
        return res;
    }
};

496 下一个更大元素 I (easy)

• 题解: 暴力法
  • 利用map存储nums2中每个元素与索引的位置
  • 对于nums1中的每个元素, 从nums2中与其对应的下一个位置开始查找

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> nums2Index;
        for (int i = 0; i< nums2.size(); i++){
            nums2Index.insert(make_pair(nums2[i], i));
        }
        // 暴力法
        for(int i = 0; i< nums1.size(); i++){
            bool flag = true;
            for (int j = nums2Index[nums1[i]]; j< nums2.size(); j++){
                if (nums2[j] > nums1[i]){
                    res.push_back(nums2[j]);
                    flag = false;
                    break;
                }
            }
            if (flag) res.push_back(-1);
        }
        return res;
    }
};

• 题解2: 单调栈
  • 依次遍历数组nums1, 如果栈为空将nums1[i]入栈
  • 如果nums[i+1] 大于栈顶元素, 就将栈顶出栈, 此时对应栈顶的下一个大的元素就是nums[i+1]
  • 如果nums[i+1] 不大于nums[i], 就将nums[i+1]入栈, 直到找到nums[j]大于栈顶就依次比较出栈.

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> nums2Index;

        // 单调栈
        stack<int> decendStack;
        for (int i = 0; i < nums2.size(); i++){
            if (decendStack.empty() || decendStack.top() >= nums2[i])
                decendStack.push(nums2[i]);
            else{
                while (!decendStack.empty() && decendStack.top() < nums2[i]){
                    nums2Index[decendStack.top()] = nums2[i];
                    decendStack.pop();
                }
                decendStack.push(nums2[i]);
            }
        }

        // 最终如果栈非空, 那么栈中下一个最大的元素不存在
        while (! decendStack.empty()){
            int tmp = decendStack.top();
            decendStack.pop();
            nums2Index[tmp] = -1;        
        }


        for(int i = 0; i< nums1.size(); i++){
            res.push_back(nums2Index[nums1[i]]);
        }
        return res;
    }
};

503 下一个更大元素 II (Medium)

• 题解: 单调栈
  • 循环数组, 那么直接遍历两遍就可以了
  • 还有一个不同点就是,这里可能会出现相同的元素, 因此使用map会导致错误(这里我就搞错了依次)
  • 遍历数组两次，每次pop之前都去更新一下res

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> stk;
        vector<int> res(nums.size(), -1);
        for(int i = 0; i < nums.size() * 2; i++)
        {
            int index = i % nums.size();
            while(!stk.empty() && nums[stk.top()] < nums[index])
            {
                // 如果已经找到了下一个最大的元素, 那么跳过
                if(res[stk.top()] == -1)
                {
                    res[stk.top()] = nums[index];
                }
                stk.pop();
            }
            stk.push(index);
        }
        return res;
    }
};

739 每日温度 (Medium)

• 题解: 单调栈
  • 与496题目一样, 找寻下一个最大的元素
  • 不同的是这里需要保存的是索引之间的差值.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> res(T.size(), 0);
        stack<int> stk;
        // 遍历T
        for (int i = 0; i< T.size(); i++){
            // 如果新的气温大于栈顶的气温, 那么保存需要等待的天数(索引值差)
            // 栈顶出栈
            while(!stk.empty() && T[stk.top()] < T[i]){
                res[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return res;
    }
};

七、 树和递归

7.1 递归

• 104 二叉树的最大深度 (Easy)
• 110 平衡二叉树 (Easy)
• 543 二叉树的直径 (Easy)
• 226 翻转二叉树 (Easy)
• 617 合并二叉树 (Easy)
• 112 路径总和 (Easy)
• 437 路径总和 III (Easy)
• 572 另一个树的子树 (Easy)
• 101 对称二叉树 (Easy)
• 111 二叉树的最小深度 (Easy)
• 404 左叶子之和 (Easy)
• 687 最长同值路径 (Easy)
• 100 相同的树 (easy)
• 222 完全二叉树的节点个数 (medium)
• 257 二叉树的所有路径 (easy)
• 113 路径总和 II (medium)
• 129 求根到叶子节点数字之和 (medium)

104 二叉树的最大深度 (Easy)

• 题解：递归
  • 对于一棵树，左子树的最大深度l， 左子树的最大深度为r。
  • 那么整个树的最大深度为l与r的较大值加上本身根节点的1.
  • 这里求一棵树的最大深度分别求了左右子树的最大深度，形成递归结构。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if ( root == nullptr ) return 0;  
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        return max(l, r) + 1;
    }
};

110 平衡二叉树 (Easy)

• 递归
  • 一棵树为平衡二叉树，那么根节点是平衡二叉树， 左子节点与右右子节点均为平衡二叉树， 形成递归结构
  • 利用上一题的最大深度

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        return abs( maxDepth(root->left) - maxDepth(root->right) ) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }

    int maxDepth( TreeNode* root){
        // 求一棵树的深度（也就是最大深度）
        if (root == nullptr) return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        return max(l, r) + 1;
    }
};

543 二叉树的直径 (Easy)

• 对于某个节点来说其做大的直径为其左子树的最大深度与右子树最大深度之和加1.
• 依然是求最大深度问题
• 只是在每次计算过程中，需要替换最大的直径。

class Solution {
public:
    int res = 1;  // 保存最大值
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return res - 1;
    }
    int maxDepth(TreeNode* root){
        if (root == nullptr) return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        res = max(res, l + r + 1);
        return max(l , r) + 1;
    }
};

226 翻转二叉树 (Easy)

• 非常简单，遍历整个二叉树，对于一个节点将其左右子树交换即可。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 对于一个节点，交换其左右子树的节点
        if (root == nullptr) return nullptr;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

617 合并二叉树 (Easy)

• 其实就是一个遍历的过程，直接采用前序遍历。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

        if (t1 == nullptr && t2 == nullptr) return nullptr;
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1; 
        TreeNode* root = new TreeNode(t1->val + t2->val);
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

112 路径总和 (Easy)

• 如果刚好遍历到叶子节点，并且路径和刚好为targetSum，返回True。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr ) return false;
        if(root->left == nullptr && root->right == nullptr && targetSum - root->val == 0) return true;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

572 另一个树的子树 (Easy)

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == nullptr && t == nullptr) return true;
        if (s == nullptr || t== nullptr) return false;
		
		// 如果两个节点均存在，如果值相等，判断以这个开始的子树是否相等， 相等返回true，不等的话继续遍历。
        if (s->val == t->val)
            if (equalTree(s, t)) return true;
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }

    bool equalTree(TreeNode* t1, TreeNode* t2){
    // 判断两棵树是否相等
        if (t1 == nullptr && t2 == nullptr) return true;
        if (t1 == nullptr || t2 == nullptr) return false;
        return t1->val == t2->val && equalTree(t1->left, t2->left) && equalTree(t1->right, t2->right);
    }
};

101 对称二叉树 (Easy)

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;

        return TreeSymmetric(root->left, root->right);
    }
    bool TreeSymmetric(TreeNode* s, TreeNode* t){
        // 判断两颗树是否镜面对称。
        if (s== nullptr && t == nullptr) return true;
        if (s == nullptr || t == nullptr) return false;
        return s->val == t->val && TreeSymmetric(s->left, t->right) && TreeSymmetric(s->right, t->left);
    }
};

111 二叉树的最小深度 (Easy)

• 这个题与最大深度的题目不一样，不能直接左右子树的最小值加1.因为其要求到叶子节点的距离
• 如果这棵树是一条仅仅由左子树构成的一条链表式的树， 那么直接左右子树的最小值加1，结果返回就是1.
• 但是此时不满足题意，题目要求到叶子节点。
• 正解需要分情况讨论。见代码中分析。

class Solution {
public:
    int minDepth(TreeNode* root) {
        // 这个题与最大深度的题目不一样，不能直接左右子树的最小值加1.因为其要求到叶子节点的距离
        // 如果这棵树是一条仅仅由左子树构成的一条链表式的树， 那么直接左右子树的最小值加1，结果返回就是1.
        // 但是此时不满足题意，题目要求到叶子节点。

        if (root == nullptr) return 0;
        int l = minDepth(root->left);
        int r = minDepth(root->right);
        // 如果左子树存在，右子树不存在
        if (root->left != nullptr && root ->right == nullptr)
            return  l+ 1;
        // 如果左子树不存在，右子树存在
        if (root->right != nullptr && root->left == nullptr)
            return r + 1;
        // 左右子树均存在。
        return min(l, r) + 1;
    }
};

404 左叶子之和 (Easy)

• 遍历所有的节点， 将所有的左叶子节点求和即可。

class Solution {
public:
    int res = 0;
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr){
            res += root->left->val;
        }
        sumOfLeftLeaves(root->left);
        sumOfLeftLeaves(root->right);
        return res;
    }
};

100 相同的树 (easy)

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;
        return (p->val == q->val ) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

257 二叉树的所有路径 (easy)

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string path;
        treePaths(root, res, path);
        return res;
    }
    
    void treePaths(TreeNode* root, vector<string>& res, string path){
    // 保存所有路径
        if (root == nullptr) return;
        if(root->left == nullptr && root->right == nullptr) {
            path += to_string(root->val);
            res.push_back(path);
            return;
        }
        path += to_string(root->val);
        path += "->";
        treePaths(root->left, res, path);
        treePaths(root->right, res, path);
    }
};

222 完全二叉树的节点个数 (medium)

• 方法1： 不考虑完全二叉树，直接遍历所有的节点

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int l = countNodes(root->left);
        int r = countNodes(root->right);
        return (l + r + 1);
    }
};

• 方法2： 利用完全二叉树的性质

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        // 分别求左右两颗子树的高度
        int l = treeDepth(root->left);
        int r = treeDepth(root->right);
        // 如果两颗子树高度相等，说明左子树为满二叉树，右子树不满
        if (l == r){
            return pow(2, l) + countNodes(root->right);
        }
        // 高度不等，说明右子树是满二叉树，左子树不满。
        else
            return pow(2, r) + countNodes(root->left);
    }
    int treeDepth(TreeNode* root){
    //求一棵完全二叉树的高度
        if (root == nullptr) return 0;
        int l = treeDepth(root->left);
        return l + 1;
    }
};

687 最长同值路径 (medium)

• 最长同值路径就是过某个节点最长同值路径中的最大值。

class Solution {
public:
    int res = 0;
    int longestUnivaluePath(TreeNode* root) {
        if (root == nullptr) return 0;
        arrowLength(root);
        return res;
    }
    int arrowLength(TreeNode* root){
    // 以某个节点作为根节点的最长同值路径。
        if (root == nullptr) return 0;
        int l = arrowLength(root->left);
        int r = arrowLength(root->right);
        int left = 0, right = 0;
        if (root->left != nullptr && root->val == root->left->val)
            left = l + 1;
        if (root->right != nullptr && root->val == root->right->val)
            right = r + 1; 
        res = max(res, left + right);
        return max(left, right);
    }
};

113 路径总和 II (medium)

• 套路代码

class Solution {
public:
    
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int> > res;
        vector<int> path;
        pathsum(root, res, path, targetSum);
        return res;
    }
    void pathsum(TreeNode* root, vector<vector<int>>& res, vector<int> path, int target){
        if (root == nullptr) return;
        if (root->left == nullptr && root->right == nullptr && target == root->val){
            path.push_back(root->val);
            res.push_back(path);
            return ;
        }
        path.push_back(root->val);
        target -= root->val;
        pathsum(root->left, res, path, target);
        pathsum(root->right, res, path, target);
        return ;            
    }
};

129 求根到叶子节点数字之和 (medium)

• 先求出所有的路径， 然后求和。

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        vector<vector<int> > res;
        vector<int> path;
        Path(root, res, path);
        int ans = 0;
        for (int i=0; i < res.size(); i++){
            int tmp = 0;
            for (int j = res[i].size()-1; j >= 0; j--){
                tmp += (res[i][j] * pow(10, res[i].size()-1 - j));
            }
            ans += tmp;
        }
        return ans;
    }

    void Path(TreeNode* root, vector<vector<int>>& res, vector<int> path){
    // 得到所有的路径，保存至vector中
        if (root == nullptr) return;
        if (root->left == nullptr && root->right == nullptr ){
            path.push_back(root->val);
            res.push_back(path);
            return ;
        }
        path.push_back(root->val);
        Path(root->left, res, path);
        Path(root->right, res, path);
        return ;            
    }
};

437 路径总和 III (medium)

class Solution {
public:
    int res = 0;
    int pathSum(TreeNode* root, int sum) {
        if (root == nullptr) return 0;
        // 以根节点开始
        pathsum(root, sum);
        //  遍历整个树
        pathSum(root->left, sum);
        pathSum(root->right, sum);
        return res;
    }
    void pathsum(TreeNode* root, int target){
        // 以某个节点开始一共有多少路径和为target的路径。
        if (root == nullptr) return ;
        target -= root->val;
        if (target == 0){
            res += 1;
        }
        pathsum(root->left, target);
        pathsum(root->right, target);
        return ;
    }
};

7.2 BFS与DFS（包括迭代法遍历二叉树）

层次遍历（BFS）

• 102 二叉树的层序遍历(medium)
• 637 二叉树的层平均值 (Easy)
• 513 找树左下角的值 (medium)

深度优先遍历（DFS）

• 144 二叉树的前序遍历 (meidum)
• 145 二叉树的后序遍历 (hard)
• 94 二叉树的中序遍历 (Medium)

宽度优先遍历（BFS）采用队列的方式，依次遍历一棵树。

基本的套路代码，就是102题目中的代码思路。

102 二叉树的层序遍历(medium)

• 题解 BFS
  • 使用队列存储当前节点的指针以及当前节点的层次
  • 循环遍历队列中的元素
  • 对于一个队首节点，如果其左子节点存在就将左子节点入队，如果右子节点存在，将右子节点入队列
  • 按照队首节点的层次数，将节点的值插入vector中对于的位置。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return {};
        // 使用队列存储节点与节点所对应的层次
        queue<pair<TreeNode*, int>> nodeQ;
        vector<vector<int>> res;
        // 将根节点以及对应的层次0，入队
        nodeQ.push(make_pair(root, 0));
        // 如果队列不为空，就一直遍历队列元素
        while (!nodeQ.empty()){
            // 拿出队首的节点指针以及层次
            auto nodeLevel = nodeQ.front();
            auto nodePoint = nodeLevel.first;
            int level = nodeLevel.second;
            nodeQ.pop();  // 队首元素出队

            if (res.size() <= level){
                res.push_back({});
            }
            res[level].push_back(nodePoint->val);

            // 如果左子树存在，就将左子节点入队
            if (nodePoint->left){
                nodeQ.push(make_pair(nodePoint->left, level+1));
            }
            // 如果右子树存在，就将右子节点入队
            if (nodePoint->right){
                nodeQ.push(make_pair(nodePoint->right, level+1));
            }
        }
        return res;  
    }
};

637 二叉树的层平均值 (Easy)

与上一题一致

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (! root) return {};
        vector<double> nodesum;
        vector<int> cnt;
        queue<pair<TreeNode*, int>> nodeQ;
        nodeQ.push(make_pair(root, 0)); 
        while (!nodeQ.empty()){
            // 拿出队首的节点指针以及层次
            auto nodeLevel = nodeQ.front();
            auto nodePoint = nodeLevel.first;
            int level = nodeLevel.second;
            nodeQ.pop();  // 队首元素出队
            if (nodesum.size() <= level){
                nodesum.push_back(nodePoint->val);
                cnt.push_back(1);
            }
            else{
                nodesum[level] += nodePoint->val;
                cnt[level]++;
            }

            // 如果左子树存在，就将左子节点入队
            if (nodePoint->left){
                nodeQ.push(make_pair(nodePoint->left, level+1));
            }
            // 如果右子树存在，就将右子节点入队
            if (nodePoint->right){
                nodeQ.push(make_pair(nodePoint->right, level+1));
            }
        }
        for (int i = 0; i< nodesum.size(); i++){
            nodesum[i] /= cnt[i];
        }
        return nodesum;
    }
};

513 找树左下角的值 (medium)

• 题解： 最左边的值，就是采用层次遍历保存每层开始的第一个值
  • 同样的层次遍历方法。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if (root == nullptr) return {};

        // 使用队列存储节点与节点所对应的层次
        queue<pair<TreeNode*, int>> nodeQ;
        // pair的第一个参数为每层的第一个节点值，第二个参数为层次
        pair<int, int> res(0, -1);
        // 将根节点以及对应的层次0，入队
        nodeQ.push(make_pair(root, 0));
        // 如果队列不为空，就一直遍历队列元素
        while (!nodeQ.empty()){
            // 拿出队首的节点指针以及层次
            auto nodeLevel = nodeQ.front();
            auto nodePoint = nodeLevel.first;
            int level = nodeLevel.second;
            nodeQ.pop();  // 队首元素出队

            // 如果开始了一个新的层次，将在这一层最左侧的元素保存。
            if (level > res.second){
                res.first = nodePoint->val;
                res.second = level;
            }

            // 如果左子树存在，就将左子节点入队
            if (nodePoint->left){
                nodeQ.push(make_pair(nodePoint->left, level+1));
            }
            // 如果右子树存在，就将右子节点入队
            if (nodePoint->right){
                nodeQ.push(make_pair(nodePoint->right, level+1));
            }
        }
        return res.first;  
    }
};

DFS

深度优先遍历（DFS）就是递归访问一棵树。

144 二叉树的前序遍历 (meidum)

前序遍历： 根——左——右

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
    void preorder(TreeNode* root, vector<int>& res){
        if (root == nullptr) return;
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }
};

• 迭代法

• 根 左 右

• 每次遇到一个节点，就直接访问它，需要先遍历左子树，然后遍历右子树，因此在访问左子树前，将右子树入栈。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while (cur != nullptr || !stk.empty()){
            while(cur != nullptr){
                res.push_back(cur->val);
                stk.push(cur->right);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
        }
        return res;
    }
};

145 二叉树的后序遍历 (hard)

后序遍历： 左——右——根

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode* root, vector<int>& res){
        if (root == nullptr) return;
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }
};

• 迭代法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        // 后序遍历：  左 右 根

        if (root == nullptr) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while (cur != nullptr || !stk.empty()){
            // 直接遍历左子树，将所有的节点入栈
            while(cur != nullptr){
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            // 如果现在cur的右侧节点不为空并且右子树之前没有访问过，那么访问右子树
            if (cur->right != nullptr && cur->right != prev){
                cur = cur->right;
            }
            // 如果右侧节点为空，或者右侧节点上次访问过，说明该访问cur节点。
            else{
                res.push_back(cur->val);
                stk.pop();
                prev = cur;
                cur = nullptr;
            }
        }
        return res;
    }
};

• 前序遍历的简单修改

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        // 后序遍历：  左 右 根
        // 前序遍历： 根左右   根右左    翻转最终的res数组
        if (root == nullptr) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while (cur != nullptr || !stk.empty()){
            while(cur != nullptr){
                res.push_back(cur->val);
                stk.push(cur->left);
                cur = cur->right;
            }
            cur = stk.top();
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

94 二叉树的中序遍历 (Medium)

中序遍历： 左——根——右

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode* root, vector<int> & res){
        if (root == nullptr) return ;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
};

• 迭代法

• 左 根 右

• 对于一个节点node，先将其入栈，然后遍历左子树，然后访问节点node，然后遍历右子树

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while (cur != nullptr || !stk.empty()){
            while(cur != nullptr){
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }
};

7.3 二叉搜索树

二叉搜索树是指 左子树的节点值均小于根节点的值， 右子树的节点值大于根节点的值（递归的概念，对于每个节点都成立）

二叉搜索树的中序遍历是排序数组

• 235 二叉搜索树的最近公共祖先 (Easy)
• 108 将有序数组转换为二叉搜索树 (Easy)
• 653 两数之和 IV - 输入 BST (Easy)
• 530 二叉搜索树的最小绝对差 (Easy)
• 501 二叉搜索树中的众数 (Easy)
• 669 修剪二叉搜索树 (medium)
• 230 二叉搜索树中第K小的元素 (Medium)
• 538 把二叉搜索树转换为累加树 (medium)
• 109 有序链表转换二叉搜索树 (Medium)
• 236 二叉树的最近公共祖先 (Medium)

235 二叉搜索树的最近公共祖先 (Easy)

• 如果当前节点值大于pq，那么说明分叉点存在于当前节点的左子树中
• 如果当前节点值小于pq， 那么说明分叉点存在当前节点的右子树中
• 否则，说明找到分叉点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        // 大于pq，搜索左子树
        if(root->val > p->val && root->val > q->val) 
            return lowestCommonAncestor(root->left, p, q);
        // 小于pq，搜索右子树
        else if (root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);
       	// 找到分叉点。
        else    
            return root;
    }
};

108 将有序数组转换为二叉搜索树 (Easy)

• 二叉搜索树的中序遍历是有序数组
• 根据这个性质，排序数组的中间元素是根节点，左半部分是左子树，右半部分是右子树，递归构建

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArray2BST(nums, 0, nums.size()-1);
    }
    TreeNode* sortedArray2BST(vector<int>& nums, int left, int right){
        if (left > right) return nullptr;
        int middle = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[middle]);
        root->left = sortedArray2BST(nums, left, middle-1);
        root->right = sortedArray2BST(nums, middle+1, right);
        return root;
    }
};

653 两数之和 IV - 输入 BST (Easy)

• 中序遍历得到排序数组
• 然后双指针

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> nums;
        inorder(root, nums);
        int l = 0, r = nums.size() -1;
        while (l < r){
            int lrSum = nums[l] + nums[r];
            if (lrSum == k)
                return true;
            else if (lrSum > k)
                r--;
            else 
                l++;
        }
        return false;
    }
	//中序遍历
    void inorder(TreeNode* root, vector<int>& nums){
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
};

530 二叉搜索树的最小绝对差 (Easy)

• 依然利用中序遍历为有序数组的特点。

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> nums;
        inorder(root, nums);
        int res = nums[1] - nums[0];
        for (int i = 1; i < nums.size(); i++){
            res = min(res, nums[i] - nums[i-1]);
        }
        return res;
    }
	//中序遍历
    void inorder(TreeNode* root, vector<int>& nums){
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
};

501 二叉搜索树中的众数 (Easy)

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        // 直接使用unordered_map，没有用到二叉搜索树的特定
        unordered_map<int, int> nodeFreq;
        vector<int> res;
        traversal(root, nodeFreq);
        int freq = 0;
        for (auto e = nodeFreq.begin(); e != nodeFreq.end(); e++){
            freq = max(freq, e->second);
        }
        for (auto e = nodeFreq.begin(); e != nodeFreq.end(); e++){
            if (e->second == freq)
                res.push_back(e->first);
        }
        return res;
    }
    void traversal(TreeNode* root, unordered_map<int, int>& nodeFreq){
        if (root == nullptr) return;
        nodeFreq[root->val]++;
        traversal(root->left, nodeFreq);
        traversal(root->right, nodeFreq);
    }
};

如果不使用额外的空间。

• 针对二叉搜索树而言，其中序遍历是一个有序数组， 所有相等的元素均在一起出现
• 利用cnt变量来统计当前元素出现的次数， maxcnt为最大频率的元素出现的次数，res保存众数

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        int cnt = 1;
        int maxcnt = 1;
        int base;
        inorder(root, cnt, maxcnt, res, base);
        return res;
    }
    void inorder(TreeNode* root, int& cnt, int& maxcnt, vector<int>& res, int& base){
        if (root == nullptr) return;
        
        inorder(root->left, cnt, maxcnt, res, base);

        if (root->val == base){
            cnt++;
        }
        else{
            cnt = 1;
            base = root->val;
        }
        if (cnt > maxcnt){
            res.clear();
            res.push_back(base);
            maxcnt = cnt;
        }
        else if (cnt == maxcnt){
            res.push_back(base);
        }

        inorder(root->right, cnt, maxcnt, res, base);
    }
};

669 修剪二叉搜索树 (medium)

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr) return nullptr;
        if (root->val < low)
            return trimBST(root->right, low, high);
        else if (root->val > high)
            return trimBST(root->left, low, high);
        else{
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
        }
        return root;
    }
};

230 二叉搜索树中第K小的元素 (Medium)

• 最直观的想法，二叉搜索树的中序遍历为排序数组

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> nums;
        inorder(root, nums);
        return nums[k-1];
    }

    //中序遍历
    void inorder(TreeNode* root, vector<int>& nums){
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
};

538 把二叉搜索树转换为累加树 (medium)

• 反中序遍历
• 从最右侧看，根节点的值为根+=右子树的值
• 左子树的值为左子树的值+=根的值

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int val = 0;
        inverseInorder(root, val);
        return root;
    }
    // 反中序遍历
    void inverseInorder(TreeNode* root, int& val){
        if (root == nullptr) return;
        inverseInorder(root->right, val);
        val += root->val;
        root->val  = val;
        inverseInorder(root->left, val);
    }
};

109 有序链表转换二叉搜索树 (Medium)

• 有序链表转换为二叉搜索树与数组的转换方式基本一致
• 只需要将链表分为左右两部分分别构成BST的左右子树即可

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) return nullptr;
        // 返回链表中间节点的前驱节点
        ListNode* premiddle = premiddleList(head);
        cout<< (premiddle->val) << endl;
        // 链表的中间节点
        int val = 0;
        ListNode* middle = premiddle->next;
        if (middle == nullptr) {
            TreeNode* root = new TreeNode(premiddle->val);
            return root;
        }
        else{
            TreeNode* root = new TreeNode(middle->val);
            premiddle->next = nullptr;
            root->left = sortedListToBST(head);
            root->right = sortedListToBST(middle->next);
            return root;
        }
    }


    // 获得链表的中间节点的前一个节点。
    ListNode* premiddleList(ListNode* head){
        if ( head == nullptr) return nullptr;
        ListNode* slow = head;
        ListNode* pre = slow;
        ListNode* fast = head->next;
        while (fast != nullptr && fast->next != nullptr){
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        return pre;
    }
};

236 二叉树的最近公共祖先 (Medium)

• 直接遍历查找，如果一棵树的左右子树中分别存在p与q，那么直接返回这个结点

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        if ( root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr) return root;
        else if (left == nullptr)
            return right;
        else if (right == nullptr)
            return left; 
        else return nullptr;
    }
};

7.4 回溯

回溯法其实就是暴力法。经常使用的暴力法就是多层循环， 但是面对树形结构的话很难采用循环的方式进行遍历。这时就要采用递归回溯的方法实现暴力法。

这类题目看似比较难，但是其实时很简单规范的套路性的代码， 下边几道题会有一个固定的模板套路， 请耐心体会。

• 17 电话号码的字母组合(medium)
• 93 复原IP地址（medium）
• 131 分割回文串(medium)
• 46 全排列(medium)
• 47 全排列 II(medium)
• 77 组合(medium)
• 39 组合总和(medium)
• 40 组合总和 II
• 216 组合总和 III
• 78 子集(medium)
• 90 子集II(medium)
• 79 单词搜索(medicum)
• 200 岛屿数量（medium）
• 130 被围绕的区域(medium)
• 417 太平洋大西洋水流问题（medium)
• 51 N皇后（hard）
• 52 N皇后 II（hard）
• 37 解数独（hard）

17 电话号码的字母组合(medium)

• 一个树形结构
• 例如输入的数字为“23
• 那么这棵树的第一层有三个节点是 abc， 每个节点的下边有三个节点def。遍历这棵树得到所有的路径。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // 构建字典映射
        unordered_map<char, string> character2Num({
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        });
        // 定义返回值
        vector<string> res;
        string path;
        backtrace(digits, res, 0, path, character2Num);
        return res;
    }

    void backtrace(string digits, vector<string>& res, int index, string path, unordered_map<char, string>& character2Num){
        // 回溯递归函数
        if (digits.empty()) return ;
        // 如果遍历完成所有的数字，就保存得到的字母组合。
        if (index == digits.size()) {
            res.push_back(path);
            return ;
        }
        // 得到某个数字映射得到的字符串
        auto characters = character2Num[digits[index]];
        // 遍历这个字符串，相当于树形结构中的一层
        for (int i = 0; i < characters.size(); i++){
            path += characters[i];
            // 向树的下一层进行遍历
            backtrace(digits, res, index + 1, path, character2Num);
            // 回溯到上一层的时候，需要去除这一层的元素。
            path.pop_back();
        }   
     }
};

93 复原IP地址（medium）

• 这个题也可以直接四层循环来做， 因为限制了最多分为4部分
• 这里依然采用回溯搜索法来处理。这种分割字符串的题目，使用回溯法是一个通用的套路。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector< string> res;
        string path;

        backtrace(s, res, path, 0, 0);
        return res;
    }
    void backtrace(string& s, vector<string>& res, string path, int cnt, int startindex){
        // cnt表示分割的部分的数目，一共需要分割为4部分， startindex为接下来这一部分的开始位置
        if (cnt == 4){ 
            if (startindex == s.size())
                res.push_back(path);
            return;
        }
        
        for (int i = startindex; i < s.size(); i++){
            // 每一部分的最长长度为3
            if (i - startindex == 3) break;
            auto prepath = path;
            auto substring = s.substr(startindex, i - startindex + 1);
            // 如果长度部位0， 且开头的数字为0， 不合法的ip
            if ( i - startindex > 0 && s[startindex] == '0') break;

            // 如果大于255直接返回。
            if (stoi(substring) > 255 ) break;
            path += substring;
            if (i != s.size() - 1)
                path += ".";
            backtrace(s, res, path, cnt+1, i + 1);
            path = prepath;
        }
    }
};

131 分割回文串(medium)

• 与上一题思路差不多， 没有上一题那么多需要排除的边界条件。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        // 得到所有的子字符串，判断得到的是否都是回文串。
        vector<vector<string>> res;
        vector<string> palstring;
        string path;

        backtrace(s, res, palstring, 0);
        return res;
    }
    void backtrace(string& s, vector<vector<string>>& res, vector<string>& palstring, int startindex){
        if (startindex == s.size()){
            res.push_back(palstring);
            return ;
        }
        for (int i = startindex; i < s.size(); i++){
            auto substring = s.substr(startindex, i - startindex + 1);
            if ( ! ispalindrome(substring)) continue;
            palstring.push_back(substring);
            backtrace(s, res, palstring, i + 1);
            palstring.pop_back();
        }

    }
    bool ispalindrome(string s){
        int l = 0, r = s.size() - 1;
        while ( l < r){
            if (s[l] != s[r])
                return false;
            l++; r--;
        }
        return true;
    }

};

46 全排列(medium)

• 依然是一个树形结构，标准的回溯法套路代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        unordered_set<int> visited;
        backtrace(nums, res, path, visited, 0);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& path, unordered_set<int>& visited, int index){
        if (index == nums.size()){
            res.push_back(path);
            return ;
        }
        for (int i = 0; i< nums.size(); i++){
            if(visited.find(nums[i]) != visited.end()) continue;
            visited.insert(nums[i]);
            path.push_back(nums[i]);
            backtrace(nums, res, path, visited,  index+1);
            visited.erase(nums[i]);
            path.pop_back();
        }
    }
};

47 全排列 II(medium)

• 与上一题的不同之处在于，这里存在重复的数字
• 也就是说如果在同一层中出现了相同的数字，那么会出现重复的情况。
• 采用排序的方式去重。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> path;
        vector< vector<int> > res;
        unordered_set<int> visited;
        backtrace(nums, res, path, visited, 0);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& path, unordered_set<int>& visited, int index){
        if (index == nums.size()){
            res.push_back(path);
            return ;
        }
        for (int i=0; i< nums.size(); i++){
            if (visited.find(i) != visited.end()) continue;
            // 这里采用nums中第i-1个元素如果没有访问过，说明在之后依然会出现，造成重复。
            if (i > 0 && nums[i] == nums[i-1] && visited.find(i - 1) == visited.end()) continue;
            visited.insert(i);
            path.push_back(nums[i]);
            backtrace(nums, res, path, visited, index+1);
            path.pop_back();
            visited.erase(i);
        }
    }
};

77 组合(medium)

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        baketrace(n, k, 0, res, path);
        return res;
    }
    void baketrace(int n, int k, int index, vector<vector<int>>& res, vector<int>& path){
        if (k == 0){
            res.push_back(path);
            return;
        }
        // 如果剩余的数字不够组成k个数字的组合，那么直接返回
        if (n - index + 1 < k) return ;

        for(int i = 1; i <= n; i++){
            if (i <= index) continue;
            path.push_back(i);
            baketrace(n, k-1, i, res, path);
            path.pop_back();
        }
    }
};

39 组合总和(medium)

• 与上一题的主要不同点在于一个元素可以多次选择，因此这里层的起始索引不再是i+1，而是i

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;
        
        backtrace(candidates, res, path, target, 0);
        return res;
    }
    void backtrace(vector<int>& candidates, vector<vector<int>>&res, vector<int>& path, int target, int index){
        if (target == 0){
            res.push_back(path);
            return ;
        }
        for (int i = 0; i< candidates.size(); i++){
            if (candidates[i] > target) continue;
            if (i < index) continue;
            path.push_back(candidates[i]);
            backtrace(candidates, res, path, target- candidates[i], i);
            path.pop_back();
        }
    }
};

40 组合总和 II

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    // 每个数字只可以使用一次，并且可能含有重复的数字
    vector<vector<int>> res;
    vector<int> path;
    // 排序去重
    sort(candidates.begin(), candidates.end());
    unordered_set<int> visited;
    backtrace(candidates, res,  path, visited, 0, target);
    return res;
    }
    void backtrace(vector<int>& candidates, vector<vector<int>>&res, vector<int>& path, unordered_set<int>& visited, int index, int target){
        if(target == 0){
            res.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size(); i++){
            
            if (candidates[i] > target) break;
            if ( i > 0 && candidates[i] == candidates[i-1] && visited.find(i-1) == visited.end()) continue;
            path.push_back(candidates[i]);
            visited.insert(i);
            backtrace(candidates, res, path, visited, i+1, target - candidates[i]);
            path.pop_back();
            visited.erase(i);
        }
    }
};

216 组合总和 III

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        if ( k > 9 || n > 45) return {};
        vector<vector<int>> res;
        vector<int> path;
        vector<int> candidates({1,2,3,4,5,6,7,8,9});
        backtrace(candidates, res,  path,  0, n, k);
        return res;
    }
    void backtrace(vector<int>& candidates, vector<vector<int>>&res, vector<int>& path, int index, int target, int depth){
        if(target == 0 && depth == 0){
            res.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size(); i++){
            if (candidates[i] > target) break;
            path.push_back(candidates[i]);
            backtrace(candidates, res, path, i+1, target - candidates[i], depth-1);
            path.pop_back();
        }
    }
};

78 子集(medium)

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrace(nums, res, path, 0);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& path, int index ){

        res.push_back(path);

        for (int i = index; i < nums.size(); i++){
            path.push_back(nums[i]);
            backtrace(nums, res, path, i+1);
            path.pop_back();
        }
    }
};

90 子集II(medium)

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 同一层中不能有相同的元素， 排序去重
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        unordered_set<int> visited;
        backtrace(nums, res, path, visited, 0);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& path,unordered_set<int>& visited, int index){
        res.push_back(path);
        for (int i = index; i< nums.size(); i++){
            if (i > 0 && nums[i] == nums[i-1] && visited.find(i - 1) == visited.end()) continue;
            visited.insert(i);
            path.push_back(nums[i]);
            backtrace(nums, res, path, visited, i + 1);
            path.pop_back();
            visited.erase(i);
        }
    }
};

• 下边的几道搜索的问题，也是一类非常经典的回溯问题。

79 单词搜索(medicum)

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<pair<int, int>> offsets({ {-1, 0}, {0, 1}, {1, 0}, {0 ,-1} });
        vector<vector<int>> visited(board.size(), vector<int>(board[0].size(), 0));

        for (int i = 0; i< board.size(); i++){
            for (int j = 0; j< board[0].size(); j++){
                if (board[i][j] == word[0]){
                    if (backtrace(board, word, visited, offsets, i, j, 1))
                        return true;
                }
            }
        }
        return false;
    }

    bool backtrace(vector<vector<char>>& board, string& word, vector<vector<int>>& visited, vector<pair<int, int>>& offsets, int x, int y, int index){
        // if (board[x][y] != word[index]) return false;
        visited[x][y] = 1;

        if (index == word.size()) return true;

        for (auto off :offsets){

            int new_x = x + off.first;
            int new_y = y + off.second;

            if (!inboard(board, new_x, new_y)) continue;

            if (visited[new_x][new_y] == 1) continue;

            if (board[new_x][new_y] != word[index]) continue;

            if (backtrace(board, word, visited, offsets, new_x, new_y, index + 1))
                return true;
        }
        visited[x][y] = 0;
        return false;
    }
    bool inboard(vector<vector<char>>& board, int x, int y){
        return (x >= 0 && x < board.size()) && ( y >= 0 && y < board[0].size());
    }
};

200 岛屿数量（medium）

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int res = 0;
        vector<pair<int, int>> offsets({ {-1, 0},{1, 0}, {0, 1}, {0, -1} });
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j++){
                if (grid[i][j] == '1'){
                    res++;
                    backtrace(grid, i, j, m, n, offsets);
                }
            }
        }
        return res;
    }
    void backtrace(vector<vector<char>>& grid, int x, int y, int m, int n, vector<pair<int,int>>& offsets){
        grid[x][y] = '0';
        for (auto off: offsets){
            int new_x = x + off.first;
            int new_y = y + off.second;
            if (!inboard(m, n, new_x, new_y) || grid[new_x][new_y] == '0') continue;
            backtrace(grid, new_x, new_y, m, n, offsets);
        }    
    }

    bool inboard(int m, int n, int x, int y){
        return (x >= 0 && x < m) && (y >= 0 && y < n);
    }
};

130 被围绕的区域(medium)

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        //找到与边界联通的O，标记为o，然后将剩余的O变为x，o变为O即可
        if (board.empty()) return ;
        vector<pair<int, int>> offsets({{1, 0},{-1, 0}, {0, 1}, {0, -1}});
        int m = board.size(), n = board[0].size();
        // 遍历边界
        for ( int i = 0; i< m; i++){
            if (board[i][0] == 'O')
                backtrace(board, i, 0, offsets);
            if (board[i][n-1] == 'O')
                backtrace(board, i, n-1, offsets);
        }
        for (int j = 0; j < n; j++){
            if (board[0][j] == 'O')
                backtrace(board, 0, j, offsets);
            if (board[m- 1][j] == 'O')
                backtrace(board, m-1, j, offsets);            
        }
        // 替换内部的O
        for ( int i = 0;i< m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
        // 将边界的o换回O
        for ( int i = 0;i< m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == 'o')
                    board[i][j] = 'O';
            }
        }
    }

    void backtrace(vector<vector<char>>& board, int x, int y, vector<pair<int, int>>& offsets){
        board[x][y] = 'o';
        for (auto off: offsets ){
            int new_x = x + off.first;
            int new_y = y + off.second;
            if (! inboard(board, new_x, new_y) || board[new_x][new_y] != 'O') continue;
            backtrace(board, new_x, new_y, offsets);
        }
    }

    bool inboard(vector<vector<char>>& board, int x, int y){
        return (x >= 0 && x < board.size()) && ( y >= 0 && y < board[0].size());
    }
};

417 太平洋大西洋水流问题（medium)

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        //使用两个数组分别表示能流到大西洋atlantic与太平洋pacific的位置
        if (matrix.empty()) return {};
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        vector<vector<bool>> pacific(m, vector<bool>(n, false));

        vector<pair<int, int>> offsets({ {-1, 0},{0, -1},{1, 0},{0, 1}});
        vector<vector<int>> res;

        for (int i  = 0; i< m; i++){
            if (! pacific[i][0])
                backtrace(matrix, i, 0, pacific, offsets);
            if (! atlantic[i][n-1])
                backtrace(matrix, i, n-1, atlantic, offsets);
        }
        for (int j  = 0; j< n; j++){
            if (! pacific[0][j])
                backtrace(matrix, 0, j, pacific, offsets);
            if (! atlantic[m-1][j])
                backtrace(matrix, m-1, j, atlantic, offsets);
        }
        for (int i =0; i<m; i++){
            for (int j = 0; j<n; j++){
                if (atlantic[i][j] && pacific[i][j])
                    res.push_back({i, j});
            }
        }
        return res;
    }
    
    void backtrace(vector<vector<int>>& matrix, int x, int y, vector<vector<bool>>& ocean, vector<pair<int, int>>& offsets){
        ocean[x][y] = true;
        for (auto off: offsets){
            int new_x = x + off.first;
            int new_y = y + off.second;
            if (!inboard(matrix, new_x, new_y) || matrix[new_x][new_y] < matrix[x][y] || ocean[new_x][new_y]) continue;
            backtrace(matrix, new_x, new_y, ocean, offsets);
        }
    }

    bool inboard(vector<vector<int>>& matrix, int x, int y){
        return (x >= 0 && x < matrix.size()) && ( y >= 0 && y < matrix[0].size());
    }
};

51 N皇后（hard）

class Solution {
public:
    vector<vector<string>> queues;
    vector<vector<string>> solveNQueens(int n) {
        //主对角线i- j为常数，范围为1-n到n-1
        // 副对角线i+j为常数，范围为0到2*n-2
        vector<int> diag(2*n-1, false); //主对角线，i - j + n - 1为其索引对应的对角线
        vector<int> otherdiag(2*n-1, false); // 副对角线i + j 为其索引对应的对角线。
        vector<int> queue(n, -1); //表示每行放置在哪一列。
        unordered_set<int> cols;  // 表示已经放置的列


        backtrace(n, diag, otherdiag, queue, cols, 0);

        return queues; 

    }
    void backtrace(int n, vector<int>& diag, vector<int>& otherdiag, vector<int>& queue, unordered_set<int> cols, int row){
        if (row == n){
            queues.push_back(generateString(queue, n));
            return ;
        }
        for (int j = 0; j < n; j++){
            if (diag[row-j+n-1] || otherdiag[row+j] || cols.find(j) != cols.end()) continue;
            diag[row-j+n-1] = true;
            otherdiag[row+j] = true;
            cols.insert(j);
            queue[row] = j;
            backtrace(n, diag, otherdiag, queue, cols, row + 1);
            diag[row-j+n-1] = false;
            otherdiag[row+j] = false;
            queue[row] = -1;
            cols.erase(j);
        }
    }
    vector<string> generateString(vector<int>& queue, int n){
        vector<string> res(n, string(n, '.'));

        for (int i=0; i< n; i++)
            res[i][queue[i]] = 'Q';

        return res;
    }
};

52 N皇后 II（hard）

class Solution {
public:
    int totalNQueens(int n) {
        vector<bool> diag(2*n - 1, false); // 主对角线是否占用， i-j+n-1为其主对角线的索引
        vector<bool> otherdiag(2*n-1, false); //副对角线，i+j为其索引
        unordered_set<int> cols; // 保存已经被占用的列
        vector<int> queue(n, -1); //表示每个元素分别放置在第j列的位置。
        int res = 0;
        backtrace(n, diag, otherdiag, cols, queue, res, 0);
        return res;
    }
    void backtrace(int n, vector<bool>& diag, vector<bool>& otherdiag, unordered_set<int>& cols, vector<int>& queue, int& res, int row){
        if (row == n){
            res++;
            return ;
        }
        // 第row行可以放的列的位置，遍历查找
        for (int i=0; i< n; i++){
            if(diag[row - i + n - 1] || otherdiag[row + i] || cols.find(i) != cols.end()) continue;
            diag[row - i + n - 1 ] = true;
            otherdiag[row + i] = true;
            cols.insert(i);
            queue[row] = i;
            backtrace(n, diag, otherdiag, cols, queue, res, row+1);
            diag[row - i + n - 1 ] = false;
            otherdiag[row + i] = false;
            cols.erase(i);
            queue[row] = -1;           
        }
    }
};

37 解数独（hard）

class Solution {
public:
    bool valid = false;
    void solveSudoku(vector<vector<char>>& board) {
        vector<unordered_set<int>> rows(9, unordered_set<int>()); //每行出现过的数字
        vector<unordered_set<int>> cols(9, unordered_set<int>()); //每列出现过的数字
        vector< unordered_set<int> > grids(9, unordered_set<int>()); // 第i个3x3的格子出现过的数字，其索引为（i/3）*3 + j/3
        vector<pair<int, int>> spaces;
        for ( int i = 0; i <9; i++){
            for (int j = 0; j < 9; j++){
                if (board[i][j] == '.')
                    spaces.push_back(make_pair(i, j));
                else{
                    int digit = int(board[i][j] - '0');
                    rows[i].insert(digit);
                    cols[j].insert(digit);
                    grids[(i/3)*3+j/3].insert(digit);
                }
            }
        }
        backtrace(board, rows, cols, grids, spaces, 0);
        return;
    }
    void backtrace(vector<vector<char>>& board, vector<unordered_set<int>>& rows, vector<unordered_set<int>>& cols, vector<unordered_set<int>>& grids, vector<pair<int, int>>& spaces, int index){
        if ( index == spaces.size()) {
            valid = true;
            return ;
        }
        int i = spaces[index].first;
        int j = spaces[index].second;
        // 放置 k 这个数字
        for (int k = 1; k <= 9; k++){
            if (valid) break;
            if ( rows[i].find(k) != rows[i].end() || cols[j].find(k) != cols[j].end() || grids[(i/3)*3+j/3] .find(k) != grids[(i/3)*3+j/3].end() ) 
                continue;
            rows[i].insert(k);
            cols[j].insert(k);
            grids[(i/3)*3+j/3].insert(k);
            board[i][j] = (char) ('0' + k);
            backtrace(board, rows, cols, grids, spaces, index+1);
            rows[i].erase(k);
            cols[j].erase(k);
            grids[(i/3)*3+j/3].erase(k);
            // board[i][j] = '.';
        }
    }
};

八、贪心

贪心算法是指每步都选择最优的策略，以此达到全局的最优。局部最优—>全局最优

贪心策略的选择必须具备无后效性，也就是说某个状态以前的过程不会影响以后的状态，只与当前状态有关。

• 455 分发饼干 (Easy)
• 121 买卖股票的最佳时机 (Easy)
• 122 买卖股票的最佳时机 II (Easy)
• 605 种花问题 (Easy)
• 665 非递减数列 (Easy)
• 53 最大子序和 (Easy)
• 435 无重叠区间 (Medium)
• 452 用最少数量的箭引爆气球 (Medium)
• 406 根据身高重建队列(Medium)
• 763 划分字母区间 (Medium)

455 分发饼干 (Easy)

• 二者排序之后采用双指针比较。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 分别将二者排序
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, j = 0;
        int res = 0;
        while (i < g.size() && j < s.size()){
            if (s[j] >= g[i]){
                i++;
                res++;
            }
            j++;
        }
        return res;
    }
};

121 买卖股票的最佳时机 (Easy)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 暴力法
        // 双重循环，从第i天买入可以获得的最大利润，计算最大值
        int maxprofit = 0;
        for ( int i = 0; i < prices.size() - 1; i++){
            for (int j = i + 1; j < prices.size(); j++){
                int profit = prices[j] - prices[i];
                maxprofit = max(profit, maxprofit);
            }
        }
        return maxprofit;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 使用minprice变量保存当前天之前的最低价格， 如果在此之前采用最低价格买入，那么当前卖出的利润最大
        int maxprofit = 0;
        int minprice = INT_MAX;
        for(auto price : prices){
            minprice = min(minprice, price);
            maxprofit = max(maxprofit, price - minprice);
        }
        return maxprofit;
    }
};

122 买卖股票的最佳时机 II (Easy)

• 与上一题的主要区别就是，可以多次交易
• 也就是当前只要获利为正就可以交易。

class Solution {
public:
    int maxProfit(vector<int>& prices) {   
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i) {
            ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

605 种花问题 (Easy)

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        // 贪心的种植， 可以种植的位置，直接众，只要左右联测均为0，就可以种植。
        // 需要考虑首尾的两个元素的特殊情况。将首尾各补上0
        int res = 0;
        for (int i = 0; i< flowerbed.size(); i++){
            int left = (i == 0) ? 0 : flowerbed[i-1];
            int right = (i == flowerbed.size()-1) ? 0 : flowerbed[i+1];
            if (left == 0 && right == 0 && flowerbed[i] == 0){
                // cout<<res<<" " <<i<<endl;
                res++;
                flowerbed[i] = 1;
            }
        }
        return res >= n;
    }
};

665 非递减数列 (Easy)

• 遇到nums[i]>nums[i+1]需要将nums[i]变小或者nums[i+1]变大
• 如果nums[i + 1] < nums[i - 1]，需要将nums[i+1]变大
• 其他情况下nums[i]变小

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int cnt = 0;
        for (int i = 0; i < nums.size()-1 && cnt < 2; i++) {
            if (nums[i] > nums[i + 1]) {
                cnt++;
                if (i > 0 && nums[i + 1] < nums[i - 1]) {
                    nums[i + 1] = nums[i];
                } 
                else {
                    nums[i] = nums[i + 1];
                }
            }
        }
        return cnt < 2;
    }
};

53 最大子序和 (Easy)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 暴力法
        int maxnum = nums[0];
        int tmp = 0;
        for (int i = 0; i < nums.size(); i++){
            tmp = nums[i];
            maxnum = max(maxnum, tmp);
            for (int j = i+1; j < nums.size(); j++){
                tmp += nums[j];
                maxnum = max(maxnum, tmp);
            }
        }
        return maxnum;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 动态规划
        int maxnum = nums[0];
        vector<int> dp(nums.size(), 0); // dp表示到i位置的最长子序和。
        dp[0] = nums[0];
        for (int i = 1; i< nums.size(); i++){
            dp[i] = max(nums[i], dp[i-1] + nums[i]);
            maxnum = max(dp[i], maxnum);
        }
        
        return maxnum;
    }
};

435 无重叠区间 (Medium)

class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);

        int cnt = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                cnt++;
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return cnt;
    }
};

452 用最少数量的箭引爆气球 (Medium)

class Solution {
public:
    // 按照区间的右端点排序
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        // 与上一题的最大不重叠区间的问题实际是一样的
        if(points.size() < 2) return points.size();
        sort(points.begin(), points.end(), cmp);
        int cnt = 1;
        for (int i = 1; i < points.size(); i++){
            if (points[i][0] > points[i-1][1])
                cnt++;
            else
                points[i][1] = min(points[i][1], points[i-1][1]);
        }
        return cnt;
    }
};

406 根据身高重建队列(Medium)

class Solution {
public:
    static bool cmp(const vector<int> a, const vector<int> b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};

763 划分字母区间 (Medium)

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[0] < b[0];
    }
    vector<int> partitionLabels(string S) {
        // 这个题目实际上还是求最大的不重合区间的个数
        // 首先遍历字符串S，求出每个字符首次与最后一次出现的次数
        // 这样还是一个不重合区间的个数问题

        vector<vector<int>> boards(26, vector<int>(2, -1));
        for (int i = 0; i < S.size(); i++){
            int index = S[i] - 'a';
            if (boards[index][0] == -1){
                boards[index][0] = i;
                boards[index][1] = i;
            }
            else 
                boards[index][1] = i;
        }

        sort(boards.begin(), boards.end(), cmp);

        vector<int> res;

        int i = 0;
        while (i < 26){
            if (boards[i][1] != -1) break;
            i++;
        }

        int min_board = boards[i][0];
        int max_board = boards[i][1];
        // i++;
        while ( i < 26){
            if ( boards[i][0] > max_board){
                res.push_back(max_board - min_board + 1);
                min_board = boards[i][0];
            }

            max_board = max(max_board,boards[i][1]);
            i++;
        }
        res.push_back(max_board - min_board + 1);
        return res;
    }
};

九、分治

分而治之： 就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并

• 241 为运算表达式设计优先级 (Medium)
• 95 不同的二叉搜索树 II (Medium)

241 为运算表达式设计优先级 (Medium)

• 以运算符为分界将计算过程分为两部分，左侧的计算结果与右侧的结果相互组合运算即可。

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        int index = 0;
        int num = 0;
        while (index < input.size() && isdigit(input[index])){
            num = num* 10 + input[index] - '0';
            index++;
        }
        if (index == input.size())
            return {num};
        vector<int> ans;
        for(int i = index; i< input.size(); i++){
            if (input[i] == '+' || input[i] == '-' || input[i] == '*'){
                auto left = diffWaysToCompute(input.substr(0, i));
                auto right = diffWaysToCompute(input.substr(i+1));
                for (auto l : left){
                    for (auto r: right){
                        if (input[i] == '+')
                            ans.push_back(l + r);
                        else if (input[i] == '-')
                            ans.push_back(l - r);
                        else
                            ans.push_back(l * r);
                    }
                }
            }
        }
        return ans;
    }
};

95 不同的二叉搜索树 II (Medium)

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {    
        auto res = buildBST(1, n);
        return res; 
    }
    vector<TreeNode*> buildBST(int left, int right){
        if (left > right) return {nullptr};
        vector<TreeNode*> trees;
        for (int i = left; i <= right; i++){
            auto leftTrees = buildBST(left, i-1);
            auto rightTrees = buildBST(i+1, right);
            for (auto l : leftTrees){
                for (auto r : rightTrees){
                    TreeNode* root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    trees.push_back(root);
                }
            }
        }
        return trees;
    }
};

十、动态规划

10.1 动态规划

动规就是以空间换取时间。

动态规划常常适用于有重叠子问题和最优子结构性质的问题。

一些思考的套路： 递归 （自顶向下）——> 记忆化递归（自顶向下消除重复） ——> 动态规划（自底而上）

1. 斐波那契数列

• 70 爬楼梯（easy）
• 198 打家劫舍（easy）
• 213 打家劫舍 II（medium）

2. 矩阵路径

• 64 最小路径和（medium）
• 62 不同路径（medium）

3. 数组区间

• 303 区域和检索 - 数组不可变（easy）
• 413 等差数列划分（medium）

4. 分割整数

• 343 整数拆分（medium）
• 279 完全平方数（medium）
• 91 解码方法（medium）

5. 最长递增子序列

• 300 最长上升子序列（medium）
• 646 最长数对链（medium）
• 376 摆动序列（medium）

6. 最长公共子序列

• 1143 最长公共子序列（medium）

7. 股票交易

• 121 买卖股票的最佳时机（easy）
• 122 买卖股票的最佳时机II（easy）
• 123 买卖股票的最佳时机 III（hard）
• 188 买卖股票的最佳时机 IV（hard）
• 309 最佳买卖股票时机含冷冻期（medium）
• 714 买卖股票的最佳时机含手续费（medium）

8. 字符串编辑

• 583 两个字符串的删除操作（medium）

• 72 编辑距离（hard）

• 650 只有两个键的键盘（medium）

• 1. 斐波那契数列 这类题目是斐波那契数列是最简单的动态规划的问题，对于这类题目，我会首先使用递归直观解决问题， 然后利用记忆化递归的方法去重，最后使用动态规划实现自底而上的方法。

70 爬楼梯（easy）

• 递归
• n-1到n有一种方法，第n-2到n有1种方法。
• 因此到达第n阶楼梯的方法为到达第n-1阶的方法与第n-2阶楼梯的方法和

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

• 记忆化递归
• 因为在上述递归方法种
• 例如要求 f(10) = f(9) + f(8)，就要求f(9)与f(8) f(9) = f(8) + f(7) f(8) = f(7) + f(6) 从上边的分析，可以看出存在大量的重复计算，随着所求数字的增大，重复计算大量的增加，这里采用map来存储已经计算过的元素，例如在求f(9)时f(8)保存下来，然后遇到求f(8)的位置，不进行往下计算，实现递归树的剪枝

class Solution {
public:
    unordered_map<int, int> memo;
    int climbStairs(int n) {
        if (n <= 2) return n;
        if (memo.find(n) == memo.end())
            memo.insert(make_pair(n, climbStairs(n-1) + climbStairs(n-2)));
        
        return memo[n];
    }
};

• 记忆化递归时自上而下的方法， 动态规划是自下而上的方法

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i< n+1; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

198 打家劫舍（easy）

• 递归

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        return helper(nums.size() - 1, nums);
    }
    int helper(int n, vector<int>& nums){
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        // 偷盗第n-1房，与偷盗n房的最值
        return max(helper(n-1, nums), helper(n-2, nums) + nums[n]);
    }
};

• 记忆化递归

class Solution {
public:
    unordered_map<int, int> memo;
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        return helper(nums.size() - 1, nums);
    }
    int helper(int n, vector<int>& nums){
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        if (memo.find(n-1) == memo.end())
            memo[n-1] = helper(n-1, nums);
        if (memo.find(n-2) == memo.end())
            memo[n-2] = helper(n-2, nums);
        // 偷盗第n-1房，与偷盗n房的最值
        return max(memo[n-1], memo[n-2] + nums[n]);
    }
};

• 动态规划

class Solution {
public:
    unordered_map<int, int> memo;
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i< nums.size(); i++){
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

213 打家劫舍 II（medium）

• 这个题与上一题的主要区别在于这里的数组是循环的。

• 直观的思路可以分为两种情况，一种是选择第一间房丢掉最后一间房nums(nums.begin(), nums.end() - 1)，第二种是选择最后一间房丢掉第一间房nums(nums.begin() + 1, nums.end())。在二者中取得最大值即可

• 直接采用动态规划， 懒得用递归了

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp1(nums.size() - 1, 0); //丢掉最后一个 
        vector<int> dp2(nums.size() - 1, 0); // 丢掉第一个元素
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);
        dp1[0] = nums[0];
        dp1[1] = max(nums[0], nums[1]);
        dp2[0] = nums[1];
        dp2[1] = max(nums[1], nums[2]);
        for (int i = 2; i< nums.size()-1; i++){
            dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i]);
            dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i+1]);
        }
        return max(dp1[nums.size()-2], dp2[nums.size()-2]);
    }
};

• 2. 矩阵路径

这类题目是在一个矩阵中找寻满足题意的路径。

依然采用 递归-> 记忆化递归 -> 动态规划的三种方法来求解这个问题。

64 最小路径和（medium）

• 递归
• 假设f(i,j)为从起始位置到i， j位置的最小路径和，从上边和左边两个方向可以到达i j 。
• 因此f(i,j) = min( f(i-1, j), f(i, j-1) ) + grid[i][j]

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        return pathsum(m-1, n-1, grid);
    }
    int pathsum(int i, int j, vector<vector<int>>& grid){
        if (i == 0 && j == 0) return grid[0][0];
        int left = i-1 >= 0 ? pathsum(i-1, j, grid) : INT_MAX;
        int up = j-1 >= 0 ? pathsum(i, j-1, grid) : INT_MAX;
        return min(left, up) + grid[i][j];
    }
};

• 记忆化递归
• 可以直观看出存在大量的重复运算，采用记忆化数组来消除重复计算

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        return pathsum(m - 1, n - 1, grid, memo);
    }

    int pathsum(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& memo){
        if (i == 0 && j == 0) return grid[0][0];

        int left = INT_MAX;
        if (i - 1 >= 0){
            if (memo[i-1][j] == -1)
                memo[i-1][j] = pathsum(i-1, j, grid, memo);
            left = memo[i-1][j];
        }

        int up = INT_MAX;
        if (j - 1 >= 0){
            if (memo[i][j - 1] == -1)
                memo[i][j - 1] = pathsum(i, j - 1, grid, memo);
            up = memo[i][j-1];
        }
        return min(left, up) + grid[i][j];
    }
};

• 动态规划： 自底而上

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(grid); // dp[i][j]表示从起始点达到ij的最小的路径和。
        for (int i = 1; i< m; i++){
            dp[i][0] +=dp[i-1][0];
        }
        for (int j = 1; j < n; j++){
            dp[0][j] += dp[0][j-1];
        }
        for (int i = 1; i< m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

62 不同路径（medium）

• 直接使用动态规划

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for (int i = 1; i< m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

• 3. 数组区间

303 区域和检索 - 数组不可变（easy）

• 直接使用dp[i][j]保存ij之间的距离, 每次需要的时候直接查找即可。

class NumArray {

private:
    vector<vector<int>> dp;
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        dp = vector<vector<int>> (n, vector<int>(n, 0));
        for ( int  i = 0; i < n; i++){
            dp[i][i] = nums[i];
        }
        for (int i = 0; i < n-1; i++){
            for (int j = i+1; j < n; j++){
                dp[i][j] = dp[i][j-1] + nums[j];
            }
        }
    }
    
    int sumRange(int i, int j) {
        return dp[i][j];
    }
};

• 也可以使用dp[i]保存起始位置到i的序列和
• ij之间的距离采用dp[j] - dp[i]得到

class NumArray {

private:
    vector<int> dp;
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        dp =  vector<int>(n, 0);
        if ( n > 0){
            dp[0] = nums[0];
            for ( int  i = 1; i < n; i++){
                dp[i] = dp[i-1] + nums[i];
            }
        }
    }
    
    int sumRange(int i, int j) {
        if (i == 0) return dp[j];
        return dp[j] - dp[i - 1];
    }
};

413 等差数列划分（medium）

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        vector<int> dp(A.size(), 0);
        int res = 0;
        for (int i = 2; i< A.size(); i++){
            if (A[i] + A[i-2] == 2 * A[i-1]){
                dp[i] = dp[i-1] + 1;
                res += dp[i];
            }
        }
        return res;
    }
};

• 4. 分割整数

343 整数拆分（medium）

• dp[i]表示i拆分后的最值， dp[i]可以拆分为j, i-j， 那么i-j可以选择继续拆分与否，取最值
• 为什么不考虑j是否拆分呢，考虑递归树即可想明白。
• 考虑一棵直观的递归树。 求dp[n]， 可以分为1dp[n-1],或者2 dp[n-2] ...... (n-1) * dp[1]。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 1);
        dp[0] = 0;
        for (int i = 2; i< n+1; i++){
            for (int j = 1; j < i; j++){
                dp[i] = max(dp[i], max(j * dp[i - j], j * (i-j)));
            }
        }
        return dp[n];
    }
};

279 完全平方数（medium）

• dp[i]表示i为结尾的完全平方数
• i分为j与i - jj， 那么dp[i] = dp[i-jj] + 1

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i< n+1; i++){
            int tmp = sqrt(i);
            for (int j = 1; j < tmp + 1; j++){
                dp[i] = min(dp[i], dp[i - j * j] + 1 );
            }
            // cout<<dp[i]<<endl;
        }
        return dp[n];
    }
};

91 解码方法（medium）

• dp[i]表示从开始到i为止的解码方案
• 分为如下的三种情况：
  • 1. s[i]== '0' 那么这个字符只能与前边的匹 配 dp[i] = dp[i-2]
  • 2. s[i] != '0' && 能与前边字符匹配 dp[i] = dp[i-1] + dp[i-2]
  • 3. s[i] != '0' 并且不能与前置字符匹配 dp[i] = dp[i-1]

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        if (n == 0) return 0;
        if (s[0] - '0' == 0) return 0;
        dp[0] = 1;
        dp[1] = s[0] != '0' ? 1 : 0;
        for (int i = 1; i < s.size(); i++){

            if (patch(s, i) && s[i] == '0')
                dp[i + 1] = dp[i-1];
            else if (s[i] != '0' && patch(s, i))
                dp[i+1] = dp[i] + dp[i-1];
            else if (s[i] != '0' && ! patch(s, i))
                dp[i+1] = dp[i];
        }

        return dp[n];
    }
    bool patch(string& s, int i){
        int tmp1 = s[i-1] - '0';
        int tmp2 = tmp1 * 10 + s[i] - '0';
        if (tmp2 >=10 && tmp2 <= 26)
            return true;
        return false;
    }
};

• 5. 最长递增子序列

300 最长上升子序列（medium）

• dp[i]表示以第i元素为结尾的最长上升子列的长度
• dp[i] = max(dp[j]) + 1 并且 nums[i] > nums[j],也就是针对所以小于i的dp子数组，如果nums[j] < nums[i] 那么选择其中最大的加一， 如果全部小于nums[i]，那么dp[i] = 1

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = 1;
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    dp[i]  = max(dp[i], dp[j]);
                }
            }
            dp[i]++;
        }
    }
};

646 最长数对链（medium）

• 与上一题类似

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if (a[1] == b[1]) return a[0] < b[0];
        return a[1] < b[1];
    } 

    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();

        sort(pairs.begin(), pairs.end(), cmp);  

        vector<int> dp(n, 0);
        dp[0] = 1;
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                if ( pairs[i][0] > pairs[j][1] )
                    dp[i] = max(dp[i], dp[j]);
            }
            dp[i]++;
        }

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

376 摆动序列（medium）

• 与前两题一致， 这里采用dp[i][0]表示以i为结尾的最长的序列最后一个差值为负数

•   								dp[i][1]最后一个差值为正数
  

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        if ( n < 2) return n;
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = 1;
        dp[0][1] = 1;
        for ( int i = 1; i< n; i++){
            for (int j = 0; j < n; j++){
                if (nums[i] - nums[j] > 0){
                    dp[i][1] = max(dp[i][1], dp[j][0]);
                }
                else if (nums[i] - nums[j] < 0){
                    dp[i][0] = max(dp[i][0], dp[j][1]);
                }
                    
            }
            dp[i][0]++;
            dp[i][1]++;
            res = max(res, max(dp[i][0], dp[i][1]));
        }
        return res;
    }
};

• 6. 最长公共子序列

1143 最长公共子序列（medium）

• dp[i][j]表示text1的前i个字符， text2的前j个字符中二者的公共子序列的长度
• 如果text[i] == text2[j] 那么 dp[i][j] = dp[i-1][j-1]+1
• 如果text1[i] != text2[j] 那么： dp[i][j] = max(dp[i-1][j], dp[i][j-1])

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n=  text2.size();

        vector<vector<int>>dp(m+1, vector<int>(n+1, 0));
        for (int i = 1; i <= m; i++ ){
            for (int j = 1; j<=n; j++){
                if (text1[i-1] == text2[j-1])
                    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];
    }
};

• 7. 股票交易 对于这类股票交易的问题，可以使用一个同意的模板来解决这类问题。

• 状态方程为：

状态转移方程：
状态方程中的 i 表示第i天， k表示剩余的操作次数(这里以购买作为操作次数的记录）， 0表示不持有股票，1表示持有股票
再第i天不持有股票， 那么其最大利润为上一天不持有股票与上一天持有股票卖掉二者的最大值
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
在第i天持有股票，那么其最大利润为上一天持有股票与上一天不持有股票，然后重新购买二者的最大值
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

• 边界条件：

base case：
#时间从第一天开始
dp[0][k][0] = 0
dp[0][k][1] = -prices[0]

# k为0表示不允许交易
dp[i][0][0] = 0
dp[i][0][1] = -infinity

当然利用这种方法进行处理并不一定是最优的，有时候会存在大量的冗余， 这里主要引入这种统一的解决思路

121 买卖股票的最佳时机（easy）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 这里只能交易一次，因此k为1， 这里就只需要定义二维数组
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i=1; i< n; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 这里由于只能交易1次。dp[i][0][0] = 0;
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }
        return dp[n-1][0];
    }
};

122 买卖股票的最佳时机II（easy）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 这里可以交易无数次，因此k不做限制， 这里就只需要定义二维数组
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i=1; i< n; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};

123 买卖股票的最佳时机 III（hard）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 这里最多能够完成两笔交易，因此k = 2，需要定义三维数组
        int n = prices.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2, 0)));
        
        for ( int k = 0; k < 3; k++){
            dp[0][k][0] = 0;
            dp[0][k][1] = -prices[0];
        }
        for (int i = 0; i < n; i++){
            dp[i][0][0] = 0;
            dp[i][0][1] = -INT_MAX;
        }
        for ( int i = 1; i< n; i++){
            for (int k = 1; k <3; k++){
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
        }
        return dp[n-1][2][0];
    }
};

188 买卖股票的最佳时机 IV（hard）

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // 这里最多能够完成k笔交易，需要定义三维数组
        int n = prices.size();
        if (n ==0 || k == 0) return 0;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k+1, vector<int>(2, 0)));
        
        for ( int k1 = 0; k1 < k+1; k1++){
            dp[0][k1][0] = 0;
            dp[0][k1][1] = -prices[0];
        }
        for (int i = 0; i < n; i++){
            dp[i][0][0] = 0;
            dp[i][0][1] = -INT_MAX;
        }
        for ( int i = 1; i< n; i++){
            for (int k1 = 1; k1 <k+1; k1++){
                dp[i][k1][0] = max(dp[i-1][k1][0], dp[i-1][k1][1] + prices[i]);
                dp[i][k1][1] = max(dp[i-1][k1][1], dp[i-1][k1-1][0] - prices[i]);
            }
        }
        return dp[n-1][k][0];
    }
};

309 最佳买卖股票时机含冷冻期（medium）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 可以实现无数次的交易，定义二维数组作为dp
        int n = prices.size();
        if ( n == 0 ) return 0;
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        if (n == 1 ) return 0;
        dp[1][0] = max(0, prices[1] - prices[0]);
        dp[1][1] = max(-prices[0], -prices[1]);
        for (int i = 2; i < n; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 下次购买的时候只能在i-2天不持有的情况下购买
            dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
        }
        return dp[n-1][0];
    }
};

714 买卖股票的最佳时机含手续费（medium）

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        // 这里可以交易无数次，因此k不做限制， 这里就只需要定义二维数组
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i=1; i< n; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
            
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};

• 8. 字符串编辑

583 两个字符串的删除操作（medium）

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 实际就是求最长公共子序列， 剩余的部分为即为需要操作的部分
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                if (word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return m + n-2 * dp[m][n];
    }
};

72 编辑距离（hard）

• 设dp[i][j]为word1的前i个字符转换为word2的前j个字符所需要的操作数。
• 当word1[i] == word2[j]时候，dp[i][j] = dp[i-1][j-1]
• 当word1[i] != word2[j]时候
  • 如果此时word1[i-1]与 word[j]已经转换完成， 那么此时删除word1[i]即可 此时dp[i][j] = dp[i-1][j] + 1
  • 如果此时word1[i]与 word[j-1]已经转换完成， 那么此时插入word1[i]即可 此时dp[i][j] = dp[i][j-1] + 1
  • 如果此时word1[i-1]与 word[j-1]已经转换完成， 那么此时替换word1[i]即可 此时dp[i][j] = dp[i-1][j-1] + 1
  • 从这三种情况中取得最小值即可

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        // 空字符转换为word2
        for (int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j-1] + 1;
        // word1转换为空字符
        for (int i = 1; i <= m; i++)
            dp[i][0] = dp[i-1][0] + 1;

        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++ ){
                if (word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])) + 1;
            }
        }
        return dp[m][n];
    }
};

650 只有两个键的键盘（medium）

• dp[i]表示打印i个A需要的最小的次数。

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[1] = 0;
        for (int i = 2; i <= n; i++){
            for (int j = 1; j < i; j++){
                if ( i % j == 0)
                    dp[i] = min(dp[i], dp[j] + i / j);
            }
        }
        return dp[n];
    }
};

10.2 背包问题

以空间换取时间。

0-1背包是背包问题的一个主要的表现形式，在01背包的基础上发展出来的还有完全背包以及多维背包问题。

1. 0-1背包

问题描述为： 存在一个容量为 C 的背包，和N类物品。这些物品分别有两个属性，重量w 和价值 v，每个物品的重量为w[i], 价值为v[i]，每种物品只有一个。在不超过背包容量的情况下能够装入最大的价值为多少？（这个背包可以不装满）。

如果采用暴力法，每个物品都有装入与不装入两种情况，复杂度为2的n次幂，复杂度为指数级别的复杂度。如果使用动态规划，时间复杂度会降低至O（N*C）。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=C

dp表为(N+1)x(C+1)维的二维数组

• 状态转移方程

1. 不装入第i件物品时，dp[i][j] = dp[i-1][j];
2. 装入第i件物品，dp[i][j] = dp[i-1][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大于w[i])
状态转移方程：
	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])  

• base case

第0个物品时不存在的，价值为0。
dp[0][:] = 0;

• 基本的实现过程：

// 定义dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定义base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
// 执行状态转移
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
		dp[i][j] = dp[i-1][j];
		if (j >= w[i])
			dp[i][j]  = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);	
	}
}
return dp[N][C];

• 优化的实现过程（dp采用一维数组）

初始dp[j]均为0
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
		if (j >= w[i])
			dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);	
	}
}

2. 完全背包 问题描述为： 存在一个容量为 C 的背包，和N类物品。这些物品分别有两个属性，重量w 和价值 v，每种物品的重量为w[i], 价值为v[i]，每种物品有无穷多个。在不超过背包容量的情况下能够装入最大的价值为多少？（这个背包可以不装满）。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=C

dp表为(N+1)x（C+1）维的二维数组

完全背包与01背包的思路基本一致，只是每种物品可以有无限多个，因此每次装入第i种物品后，还能继续装入i种物品。

• 状态转移方程

1. 不装入第i种物品时，dp[i][j] = dp[i-1][j];
2. 装入第i件物品，dp[i][j] = dp[i][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大于w[i])
状态转移方程：
	dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])  

• base case

第0个物品时不存在的，价值为0。
dp[0][:] = 0;

• 基本的实现过程：

// 定义dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定义base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
// 执行状态转移
for (int i = 1; i < N+1; i++){
	for (int j = 0; j <=C ; j++){
		dp[i][j] = dp[i-1][j];
		if (j >= w[i])
			dp[i][j]  = max(dp[i][j], dp[i][j-w[i]] + v[i]);	
	}
}
return dp[N][C];

• 优化的实现过程（dp采用一维数组）

初始dp[j]均为0
for (int i = 1; i < N+1; i++){
	for (int j = 0; j <= C; j++){
		if (j >= w[i])
			dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);	
	}
}

3. 多重背包

问题描述为： 存在一个容量为 C 的背包，和N类物品。这些物品分别有三个属性，重量w ，价值 v和数量n，每种物品的重量为w[i], 价值为v[i]，每种物品分别有n[i]个。在不超过背包容量的情况下能够装入最大的价值为多少？（这个背包可以不装满）。

与前边的01背包类似，不同之处在于第i件物品的数目为n[i]，这里的分析思路就是针对第i种物品，分别可以装入0，1，2，3, ... ,n[i]件（同时还得满足不能超过背包的容量）。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=C

dp表为(N+1)x（C+1）维的二维数组

• 状态转移方程

1. 不装入第i种物品时，dp[i][j] = dp[i-1][j];

2. 对于第i种物品， k为装入第i种物品的件数, k <= min(n[i], j/w[i])
dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for i in range(k)}

	dp[i][j] = max(dp[i][j], dp[i][j-k* w[i]]+ k* v[i])  

• base case

第0个物品时不存在的，价值为0。
dp[0][:] = 0;

• 基本的实现过程：

// 定义dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定义base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
	
// 执行状态转移
for (int i = 1; i < N+1; i++){
	for (int j = C; j >=0 ; j--){
		dp[i][j] = dp[i-1][j];
		int tmp = min(n[i], j / w[i]);
		for (int k = 0; k<=tmp; k++){
			dp[i][j]  = max(dp[i][j], dp[i][j-k*w[i]] + k*v[i]);	
		}
	}
}
return dp[N][C];

• 优化的实现过程（dp采用一维数组）

初始dp[j]均为0
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
	
		int tmp = min(n[i], j / w[i]);
		
		for (int k = 0; k<=tmp; k++){
			dp[j]  = max(dp[j], dp[j-k*w[i]] + k*v[i]);	
		}
	}
}

• 416 分割等和子集（medium）
• 494 目标和（medium）
• 474 一和零（medium）
• 322 零钱兑换（medium）
• 518 零钱兑换 II（medium）
• 139 单词拆分（medium）
• 377 组合总和 Ⅳ（medium）

416 分割等和子集（medium）

• 01背包问题

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if ( n < 2) return false;
        int numsSum = 0;
        for (auto num: nums) numsSum += num;
        if (numsSum %2 != 0) return false;
        int target = numsSum / 2;
        // 这就是一个01背包问题， 背包的容量为target， 能否恰好装满这个背包
        // nums数组的每个元素就是一种物品，nums[i]即为第i种物品的重量。
        vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));
        dp[0][0] = true;
        for(int i = 1; i <= n; i++){
            for (int j = target; j>=0; j--){
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1])
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
                if (dp[i][target] == true)
                    return true;
            }
        }
        return false;
    }
};

• 优化后的一维数组解决方案

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if ( n < 2) return false;
        int numsSum = 0;
        for (auto num: nums) numsSum += num;
        if (numsSum %2 != 0) return false;
        int target = numsSum / 2;
        // 这就是一个01背包问题， 背包的容量为target， 能否恰好装满这个背包
        // nums数组的每个元素就是一种物品，nums[i]即为第i种物品的重量。
        vector<bool>dp (target+1, false);
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            for (int j = target; j>=0; j--){
                if (j >= nums[i-1])
                    dp[j] = dp[j] || dp[j-nums[i-1]];
                if (dp[target] == true)
                    return true;
            }
        }
        return false;
    }
};

494 目标和（medium）

• 01 背包问题， 求方案数目
• sum(P) - sum(N) = target
• sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
• 2 * sum(P) = target + sum(nums)
• target为计算后的target，找子序列和为target的个数
• 背包容量为target，物品重量为元素的值

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for(int &num: nums) sum += num;
        if(S > sum || sum < -S) return 0; 
        if((S + sum) % 2 != 0) return 0; 
        int target = (S + sum) / 2;

        vector<int>dp(target + 1, 0);

        dp[0] = 1;
        for(int i = 1; i <= nums.size(); i++)
            for(int j = target; j >= nums[i-1]; j--)
                dp[j] = dp[j] + dp[j - nums[i-1]];

        return dp[target];
    }
};

474 一和零（medium）

• 01背包问题， 二维背包问题
• 背包的容量为m与n
• 每个物品的重量为0的个数与1的个数
• 每个物品的价值均为1， 求价值最大问题。
• dp[j][k] = max(dp[j][k], dp[j-nums[i][0]][k - nums[i][1])

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> nums(strs.size(), vector<int>(2, 0));
        int num0 = 0, num1 = 0;
        for(int i = 0; i<strs.size(); i++){
            nums[i][0] = count(strs[i].begin(), strs[i].end(), '0');
            nums[i][1] = count(strs[i].begin(), strs[i].end(), '1');
            num0 += nums[i][0];
            num1 += nums[i][1];
        }
        for (auto s: nums)
            cout<<s[0] << "  "<< s[1]<<endl;

        if (num0 == m && num1 == n) return nums.size();

        vector<vector<int>> dp (m+1, vector<int>(n+1, 0));
        for (int i = 0; i < nums.size(); i++){
            for (int j = m; j >= nums[i][0]; j--){
                for (int k = n; k >= nums[i][1]; k--){
                    dp[j][k] = max(dp[j][k], dp[j - nums[i][0]][k - nums[i][1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

322 零钱兑换（medium）

• 完全背包问题
• 背包容量为amount
• 每件物品的重量为coins[i]， 每件物品的价值为1， 求刚好装满背包的物品的价值最小。
• dp[j] = min(dp[j], dp[j-coins[i-1]]+1)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        
        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < coins.size() + 1; i++){
            for (int j = coins[i-1]; j <= amount; j++){
                if(dp[j] - 1 > dp[j - coins[i-1]])
                    dp[j] = min(dp[j], 1 + dp[j - coins[i-1]]);   
            }
        }
        return dp[amount]==INT_MAX ? -1 : dp[amount];
    }
};

518 零钱兑换 II（medium）

• 完全背包问题
• 背包的容量为amount， 每个物品的重量为coins[i]，求刚好装满背包的方案数
• dp[j] = sum(dp[j] + dp[j-coins[i-1]])

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (int i = 1; i< n+1; i++){
            for (int j = coins[i-1]; j<= amount; j++)
                dp[j] = dp[j] + dp[j- coins[i-1]];
        }
        return dp[amount];
    }
};

• 接下来的这两道题，需要考虑输出的顺序，因此循环遍历的顺序与前边几道题不一致，外层遍历背包，内层遍历物品

139 单词拆分（medium）

• 完全背包
• 物品就是单词字典，每个物品可以有无数个， 背包就是字符串， 看能否完全装满背包

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++){ // 遍历背包
            for (int j = 0; j < i; j++){  // 遍历物品
                string word = s.substr(j, i - j); // 
                if (wordSet.find(word) != wordSet.end())
                    dp[i] = dp[i] || dp[j];
            }
        }
        return dp[s.size()];
    }
};

377 组合总和 Ⅳ（medium）

• 完全背包问题
• 物品的重量为nums[i]，背包容量为target， 刚好装满背包的组合数
• dp[j] = sum(dp[j], dp[j-nums[i-1]])

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for (int i = 0; i < target+1; i++){ // 遍历背包
            for (int j = 1; j < n+1; j++ ){ // 遍历物品
                if ( i >= nums[j-1])
                    dp[i] = (dp[i] >= INT_MAX - dp[i-nums[j-1]]) ? INT_MAX : dp[i] + dp[i-nums[j-1]];
            }
        }
        return dp[target];
    }
};

十一、图

1. BFS与DFS

• 785 判断二分图 (Medium)
• 207 课程表 (Medium)
• 210 课程表 II (Medium)

2. 并查集

并查集是一种树型的数据结构，主要用于处理连通域的问题，用于处理一些不交集的合并及查询问题。主要的操作有如下的步骤：

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union：将两个子集合并成同一个集合。

• 684 冗余连接 (Medium)

11.1 BFS与DFS

785 判断二分图 (Medium)

使用染色法，0代表一种颜色，1代表另外一种颜色， -1表示未染色，相邻的元素不能染成同样的颜色。

• DFS

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> colors(n, -1);
        for (int i = 0; i< n; i++){
            if (colors[i] == -1){
                if (!dfs(graph, colors, i, 0))
                    return false;
            }
        }
        return true;
    }
    
    bool dfs(vector<vector<int>>& graph, vector<int>& colors, int index, int c){
        
        colors[index] = c;
        for (int i = 0; i < graph[index].size(); i++){
            int node = graph[index][i];
            if (colors[node] != -1){
                if (colors[node] == c) return false;
                else continue;
            }
            else    
                if ( ! dfs(graph, colors, node, 1-c))
                    return false;
        }
        return true;
    }
};

• BFS

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> colors(n, -1);
        queue<pair<int, int>> q;
        for (int i = 0; i<n; i++){
            if ( colors[i] != -1) continue;
            q.push(make_pair(i, 0));
            while (! q.empty()){
                auto nodeLevel = q.front();
                int node = nodeLevel.first;
                int level = nodeLevel.second;
                q.pop();
                if (level % 2 == 0){
                    if (colors[node] == 1)
                        return false;
                    colors[node] = 0;
                }
                else{
                    if (colors[node] == 0)
                        return false;
                    colors[node] = 1;
                }
                for (auto node1 : graph[node]){
                    if (colors[node1] == -1)
                        q.push(make_pair(node1, level+1));
                }
            }
        }
        return true;
    }
};

207 课程表 (Medium)

• DFS

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 不能有环， dfs
        vector<int> visited(numCourses, -1); // -1表示没有访问过， 0表示被其他节点访问过，1表示被本节点访问过
        vector<vector<int>> edges(numCourses, vector<int>());

        // 构建邻接表
        for (int i = 0; i < prerequisites.size(); i++){
            int start = prerequisites[i][1];
            int end = prerequisites[i][0];
            // cout<<start<<" "<<end<<endl;
            edges[start].push_back(end);
        }

        for( int i = 0; i < numCourses; i++){
            if (visited[i] != -1) continue;
            if (! dfs(edges, visited, i))
                return false;
        }
        return true;
    }

    bool dfs(vector<vector<int>>& edges, vector<int>& visited,int index){
        
        if (visited[index] == 1) return false;
        if (visited[index] == 0) return true;
        visited[index] = 1;
        for (auto node : edges[index]){
            if (! dfs(edges, visited, node))
                return false;
        }
        visited[index] = 0;
        return true;
    }
};

• BFS（入度表）

/*
1. 转换为邻接表并生成入度表
2. 将入度为0的节点入队。
3. 遍历整个队列，如果队列不为空，将队首出列，并将邻接节点的入度减一，将入度为0的节点重新入度。
*/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 不能有环， dfs
        vector<int> indegrees(numCourses, 0);
        vector<vector<int>> edges(numCourses, vector<int>());

        // 构建邻接表与入度表
        for (int i = 0; i < prerequisites.size(); i++){
            int start = prerequisites[i][1];
            int end = prerequisites[i][0];
            edges[start].push_back(end);
            indegrees[end]++;
        }
        queue<int> q;
        // 将入度为0的节点入队
        for (int i = 0; i < numCourses; i++){
            if (indegrees[i] == 0)
                q.push(i);
        }
        while (!q.empty()){
            int node = q.front();
            q.pop();
            // 将邻接的节点入度数减一，并将入度为0的节点入队
            for (auto j : edges[node]){
                indegrees[j]--;
                if (indegrees[j] == 0)
                    q.push(j);
            }
        }
        // 如果有的节点入度数不为0，那么说明存在环
        for (auto i: indegrees){
            if (i != 0) return false;
        }
        return true;
    }
};

210 课程表 II (Medium)

• DFS

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses, vector<int>());
        for (int i= 0; i < prerequisites.size(); i++){
            int start = prerequisites[i][1];
            int end = prerequisites[i][0];
            edges[start].push_back(end);
        }

        // for(auto p: edges){
        //     for (auto v:p)
        //         cout<<v<<"  ";
        //     cout<<endl;
        // }

        vector<int> visited(numCourses, -1); // -1表示没有访问过， 0表示被其他节点访问过，1表示被本节点访问过
        vector<int> res;
        for( int i = 0; i < numCourses; i++){
            if (visited[i] != -1) continue;
            if (! dfs(edges, visited, res, i))
                return {};
        }
        reverse(res.begin(), res.end());
        return res;
    }

    bool dfs(vector<vector<int>>& edges, vector<int>& visited, vector<int>& res,  int index){
        
        if (visited[index] == 1) return false;
        if (visited[index] == 0) return true;
        visited[index] = 1;
        for (auto node : edges[index]){
            if (!dfs(edges, visited, res, node))
                return false;
        }
        res.push_back(index);
        visited[index] = 0;
        return true;
    }
};

• BFS

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses, vector<int>());
        vector<int> indegress(numCourses, 0);
		// 构建邻接表，入度表
        for (int i= 0; i < prerequisites.size(); i++){
            int start = prerequisites[i][1];
            int end = prerequisites[i][0];
            edges[start].push_back(end);
            indegress[end]++;
        }

        queue<int> q;
        vector<int> res;
		// 将入度为0的节点入队
        for (int i = 0; i < numCourses; i++){
            if (indegress[i] == 0)
                q.push(i);
        }
        // 遍历队列
        while (!q.empty()){
            int node = q.front();
            res.push_back(node);
            q.pop();
            // 将邻接节点的入度数减一，并将入度为0的节点入队。
            for (auto i : edges[node]){
                indegress[i]--;
                if (indegress[i] == 0)
                    q.push(i); 
            }
        }
        // 如果存在入度不为0的节点，说明存在一个环
        for (auto i: indegress){
            if ( i != 0) 
                return {};
        }
        return res;
    }
};

11.2 并查集

684 冗余连接 (Medium)

经典的并查集的套路代码。

class Solution {
public:
    int find(vector<int>&parent, int index){
    // 查找一个给定节点的父亲节点。递归的操作。
        if (parent[index] != index)
            parent[index] = find(parent, parent[index]);
        return parent[index];
    }

    void Union(vector<int>& parent, int index1, int index2){
    // index2的父亲节点转换为index1与index2共同的父亲节点。
        parent[find(parent,index1)] = find(parent,index2);
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n+1, 0);
        // 初始化的情况下，每个节点的父亲节点都是自身
        for (int i = 1; i< n+1; i++){
            parent[i] = i;
        }

        for (auto edge: edges){
            int node1 = edge[0], node2 = edge[1];
            // 对于两个节点，如果其父亲节点不一样就融合这两个节点
            if (find(parent, node1) != find(parent, node2))
                Union(parent, node1, node2);
            else
                return edge;
        }
        return {};
    }   
};

更多文章请关注

• 微信公众号： 小哲AI

  

• csdn博客： https://blog.csdn.net/lxztju

• 知乎专栏： https://www.zhihu.com/column/c_1101089619118026752