Leetcode hot 100 刷题

估算算法的时间复杂度的时候一般低于10^7 次操作每秒为佳

sort 的时间复杂度与编译器具体实现相关，简单考虑成快速排序nlogn

哈希

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗

class Solution {
//map[数，索引]，构建反向索引，便于查找
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(size_t i = 0 ; i < nums.size(); i++){
            if(map.contains(target-nums[i])){
                vector<int> ret;
                ret.push_back(map[target-nums[i]]);
                ret.push_back(i);
                return ret;
            }
            map[nums[i]] = i;
        }
        return vector<int>();
    }
};

2.字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 “bat”。
字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 “ate” ，”eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

class Solution {
public:
    //排序s，原始序列相同的作为hash表的key
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> group_strs;
        for(auto& s : strs){
            string sorted_s  = s;
            ranges::sort(sorted_s);
            group_strs[sorted_s].push_back(s);
        }
        vector<vector<string>> ans;
        ans.reserve(group_strs.size());
        for(auto& [_,value] : group_strs){
            ans.push_back(value);
        }
        return ans;
    }
};

3.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //排序+o(n)
        if(nums.size() < 2) return nums.size();
        sort(nums.begin(), nums.end());
        int ans = 1;
        int start = 0;
        int cur = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] == nums[i - 1])  continue;
            if(nums[i] - nums[i - 1] == 1)
            {
                cur++;
                ans = max(cur, ans);
            }
            else
            {
                start = i;
                cur = 1;
            }
        }
        return ans;
    }
    
    int longestConsecutive(vector<int>& nums) {
	    //set + o(n)
        unordered_set<int> num_set;
        for(const int & num : nums){
            num_set.insert(num);
        }
        int longestStreak = 0;
        for(auto& num : num_set){
            if(!num_set.count(num - 1)){
                int currentNum = num;
                int currentStreak = 1;
                while( num_set.count(currentNum + 1)){
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = max(longestStreak,currentStreak);
            }
        }
        return longestStreak;
    }
};

双指针

4.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

进阶：你能尽量减少完成的操作次数吗？

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //快指针往前走，慢指针遇到0就停，然后swap
        //o(n)
        int n = nums.size(),left = 0 , right = 0 ;
        while(right < n){
            if(0 != nums[right]){
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }
};

5.盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

题解：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
关键：
接水量=两个指针指向的数字中较小值∗指针之间的距离

class Solution {
public:
    int maxArea(vector<int>& height) {
	    //双指针中靠，距离减少，移动两者中的较小值，看看能不能找到更大的最小值。
        int low = 0 , n = height.size(),high = n-1;
        int max_container = 0;
        while(low < high){
            int container = ( high - low ) * min(height[low],height[high]);
            max_container = max(max_container,container);
            if(height[low] < height[high]){
                low++;
            }else{
                high--;
            }
        }
        return max_container;
    }
};

6.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

class Solution {
public:

    vector<vector<int>> threeSum(vector<int>& nums) {
	    //排序后，
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        for(int i = 0 ; i < nums.size() - 2; i++ ){
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            if(nums[i] > 0){
                break;
            }
            int l = i + 1 , r = nums.size()-1 ;
            while(l < r ){
                int sum = nums[l]+nums[r]+nums[i];
                if(sum < 0){
                    l++;
                }else if(sum > 0){
                    r--;
                }else{
                    ans.push_back({nums[i],nums[l],nums[r]});
                    while(l < r && nums[l] == nums[l+1]){
                        l++;
                    }
                    while(l < r && nums[r] == nums[r-1]){
                        r--;
                    }
                    l++;r--;
                }
            }
        }
        return ans;
    }
};

7.接雨水

定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

题解

class Solution {
public:
    int trap(vector<int>& height) {
        //dp
        int total_sum = 0;
        vector<int> dp_l_max;
        vector<int>  dp_r_max;
        dp_l_max.reserve(height.size());
        dp_r_max.reserve(height.size());
        dp_l_max[0] = 0;
        int n = height.size();
        dp_r_max[n-1] = 0;
        for(int i = 0 ; i < height.size() - 1 ; i++)
        {

            dp_l_max[i+1] = max(dp_l_max[i],height[i]);
            dp_r_max[n-i-2] = max(dp_r_max[n-1-i],height[n-i-1]);

        }
        for(int i = 0 ; i < height.size(); i++){
            int max_l = dp_l_max[i], max_r = dp_r_max[i];
            if(max_r > height[i] && max_l > height[i]){
                total_sum += min(max_r,max_l) - height[i];
            }            
        }
        return total_sum;
    }

    int trap(vector<int>& height) {
        //    单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }

    int trap(vector<int>& height) {
        //  双指针 存水量只取决于短的柱子 只只关心两者中的较小值，是不是所以没有遍历到的最大值不影响
       int n = height.size();
       if (n<=2)   return 0;
       int l=0,r=n-1;
       int leftmax=height[l], rightmax=height[r];
       int res=0;
       while (l<r) {
           if (leftmax < rightmax) {
               res += leftmax-height[l];
               l++;
               leftmax = max(height[l], leftmax);
           }
           else {
               res += rightmax-height[r];
               r--;
               rightmax = max(height[r], rightmax);
           }
       }
       return res;
   }

};

滑动窗口

1.区分是固定长度的窗口还是非固定长度的窗口，非固定长度窗口参照7.的模板
2.字符串比较的不考虑顺序时可以采用字典集的方式降低时间复杂度
3.如果字符串中包含负数，如第9题，可能导致窗口伸缩状态不确定，这种情况滑动窗口不适用

8. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        ////外层循环扩展右边界，内层循环扩展左边界
        unordered_set<char> char_sets;
        int maxlength = 0;
        int curlength = 0;
        for(int l = 0, r = 0; r < s.length();r++){
            while(l < r && char_sets.contains(s[r])){
                char_sets.erase(s[l]);
                l++;
                curlength -- ;
            }
            char_sets.insert(s[r]);
            curlength++;
            maxlength = max(maxlength,curlength);
        }
        return maxlength;
    }
};

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

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        //本方法比较时的时间复杂度时o(26)如果排序则复杂度为o(pn)，都很大
        int sLen = s.size(), pLen = p.size();
        if (sLen < pLen) {
            return vector<int>();
        }
        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if (sCount == pCount) {
                ans.emplace_back(i + 1);
            }
        }
        return ans;
    }
};

子串

10.和为 k 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

前缀合+哈希表

class Solution {
public:
//如果 `prefix_sum[j] - prefix_sum[i-1] = k`，那么从 i 到 j 的子数组和就是 k
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        unordered_map<int,int> prefix_sum_count_map;//key=前缀和, value=该前缀和出现的次数
        prefix_sum_count_map[0] = 1;
        int cur_prefix_sum = 0;
        for(int i = 0 ; i < nums.size();i++){
            cur_prefix_sum += nums[i];
            if(prefix_sum_count_map.contains(cur_prefix_sum - k)){
                ans += prefix_sum_count_map[cur_prefix_sum-k];
            }
            if(prefix_sum_count_map.contains(cur_prefix_sum)){
                prefix_sum_count_map[cur_prefix_sum]++;
            }else{
                prefix_sum_count_map[cur_prefix_sum] = 1;
            }
        }
        return ans;
    }
};

11.滑动窗口中的最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例 2：
输入：nums = [1], k = 1
输出：[1]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> pq;//默认最大堆
        for(int i = 0 ; i < k ; i ++ ){
            pq.emplace(nums[i],i);
        }
        vector<int> ans;
        ans.push_back(pq.top().first);
        for(int i = k ; i < nums.size() ; ++i){
            
            pq.emplace(nums[i],i);
            // 移除不在当前窗口内的元素
            // 当前窗口范围是 [i-k+1, i]
            //相当于堆中可能有窗口之外的过期值，但是只要检查堆顶的时候通过索引pop掉即可
            // 堆顶元素的索引 <= i-k 说明它已经滑出窗口
            while(pq.top().second <= i-k)
            {
                pq.pop();
            }
            ans.push_back(pq.top().first);
        }
        return ans;
    }
};

12.最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 “”。

测试用例保证答案唯一。

  string minWindow(string s, string t) {
      unordered_map<char,int> need_map,cur_wind_map;
      for(auto& c : t){
          need_map[c]++;
      }
      int r= 0  , l = 0;
      int valid = 0;
      int minLen = INT_MAX, start = 0;

//右指针前走，找到包含子串t的子串
      for(;r < s.size();r++){
          if(need_map.contains(s[r])){
              cur_wind_map[s[r]]++;
              if(cur_wind_map[s[r]] == need_map[s[r]]){
                  valid++;
              }
          }
          while(valid == need_map.size()){
              if(r - l < minLen){
                  minLen = r + 1 - l;
                  start = l;
              }
              //左指针前行，缩短找到最短的合法指针
              if(need_map.contains(s[l])){                        
                  if(cur_wind_map[s[l]] == need_map[s[l]]){
                      valid--;
                  }
                  cur_wind_map[s[l]]--;
              }
              l++;
          }
      }
      if(minLen == INT_MAX){
          return "";
      }
      return s.substr(start,minLen);
  }

普通数组

13.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp;//dp[i]以i结尾的最大子数组和
        dp.reserve(nums.size());
        dp[0] = nums[0];
        int max_sum = dp[0];
        for(int i = 1 ; i < nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            max_sum = max(max_sum,dp[i]);
        }
        return max_sum;
    }
};

14.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() == 0){
            return {};
        }
        //按照区间的左端点进行升序排序
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> merged;
        for(int i = 0 ; i < intervals.size() ; i++){
        //拿每一个新区间和合并区间的右端点比较
            int l = intervals[i][0], r = intervals[i][1];
            if(merged.empty()){
                merged.push_back({l,r});
            }else{
                if(merged.back()[1] < l){
                    merged.push_back({l,r});
                }else{
                    merged.back()[1] = max(merged.back()[1],r);
                }
            }
        }
        return merged;
    }
};

15.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

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

16.除了自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。
题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
		    //分为前后两个因子，分别计算
        int n = nums.size();
        vector<int> L(n,0),R(n, 0);
        L[0] = 1;
        R[n - 1] = 1;
        for(int i = 1 ; i < n; i++){
            L[i] = nums[i-1]*L[i-1];
        }
        for(int i = n - 2; i >= 0 ; i--){
            R[i] = nums[i+1]* R[i+1];
        }
        vector<int> ans(n);
        for(int i = 0 ; i < n;i++){
            ans[i] = L[i]*R[i];
        }
        return ans;
    }

    vector<int> productExceptSelf(vector<int>& nums) {
        //不考虑输出数组时的O(1)空间复杂度
        int n = nums.size();
        vector<int> ans(n,0);
        ans[0] = 1;
        for(int i = 1 ; i < n; i++){
            ans[i] = ans[i-1]*nums[i-1];
        }
        int R = 1;
        for(int i = n - 2; i >= 0 ; i--){
            R = R * nums[i+1];
            ans[i] = ans[i] * R;
        }
        return ans;
    }
};

17.缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //长度为 n 的数组里，最小缺失正整数一定落在 [1, n+1]，<= 0 或者 > n 均不考虑
        //出现一个正数，就把一个对应正数的索引进行标记，之后查找第一个没有被标记的地方
        //标记时用了一个技巧，采用负数来进行标记
        int n = nums.size();
        for(int i = 0 ; i < n ; i++){
            if(nums[i] <= 0 || nums[i] > n){
                nums[i] = n+1;
            }
        }
        //如果数字 3 出现了，就把索引 （3-1） 处的数标记为负数
        for(int i = 0 ; i < n ; i++){
            int num = abs(nums[i]);
            if( num < n+1){
                if(nums[num - 1 ] > 0){
                    //对应的索引处的数组没有被标记，负数标记
                    nums[num - 1] = - nums[num - 1];
                }
            }
        }
        for(int i = 0 ; i < n; i++){
            if(nums[i] > 0){
                return i+1;
            }
        }
        return n + 1;
    }
};

矩阵

18.矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> row(m,0),col(n,0);
        for(int i = 0 ;  i < m ; i++){
            for(int j = 0 ; j < n ; j++ ){
                if(matrix[i][j] == 0){
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        }
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(row[i]==1 || col[j]==1){
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

19.螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int top = 0,left = 0 ; 
    int bottom = matrix.size()-1, right = matrix[0].size()-1;
    vector<int> ans;
    //按照层来进行做，但是注意最后一起集中更新层边界，第一次自己写就是边动边更新，导致刷新错误
    while(top <= bottom && left <= right){
        for(int col = left; col <= right ; col++){
            ans.push_back(matrix[top][col]);
        }
        for(int row = top + 1 ; row <= bottom; row++){
            ans.push_back(matrix[row][right]);
        }
        if(left < right && top < bottom){
            for(int col = right - 1; col > left; col--){
                ans.push_back(matrix[bottom][col]);
            }
            for(int row = bottom; row > top ; row -- ){
                ans.push_back(matrix[row][left]);
            }
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    return ans;
}

20.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

void rotate(vector<vector<int>>& matrix) {
    //只给了N2的旋转方案，原地翻转感觉没有意义
    int n = matrix.size();
    auto matrix_new = matrix;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            matrix_new[j][n - i - 1] = matrix[i][j];
        }
    }
    matrix = matrix_new;
}

21. 搜索二维矩阵

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

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

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

链表

22.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

//方法1.哈希，特殊的hash就是原地hash，遍历A，把A都改成负数，然后再遍历一次B，第一个负数就是交点。
//方法2.先对齐，长的指针先走几个。
//方法二，双指针，当两者长度二次遍历然后相同时，长度都为a+b-c

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

23.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL, *cur = head;
    if(cur == NULL){
        return NULL;
    }
    while(cur != NULL){
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        if(next == NULL){
            return cur;
        }
        cur = next;
    }
    return NULL;
}

24.回文链表

bool isPalindrome(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return true;  // 空链表或只有一个节点是回文
    }
        
    // 1. 使用快慢指针找到中点
    ListNode* slow = head;
    ListNode* fast = head;
        
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
        
    // 2. 反转后半部分链表
    ListNode* prev = nullptr;
    ListNode* curr = slow;  // slow 就是后半部分的起始点
    ListNode* next = nullptr;
        
    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
        
    // 3. 比较前半部分和反转后的后半部分
    ListNode* left = head;
    ListNode* right = prev;  // prev 现在是反转后的头节点
        
    while (right != nullptr) {
        if (left->val != right->val) {
            return false;
        }
        left = left->next;
        right = right->next;
    }
    return true;
}

25.环形链表

检测链表中有没有环形出现

bool hasCycle(ListNode *head) {
     //法1 小聪明：最大程度10000次，如果循环10001次，就说明有环
     //法2 龟兔赛跑
     if(head == nullptr || head->next == nullptr){
         return false;
     }
     ListNode * slow = head;
     ListNode * fast = head->next;

     while (slow != nullptr && fast != nullptr){
         if(fast == slow){
             return true;
         }
         slow = slow->next;
         if(fast->next != nullptr){
             fast = fast->next->next;
         }else{
             return false;
         }
     }
     return false;
 }

26.环形链表2

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

参考题解

ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (true) {
        if (fast == nullptr || fast->next == nullptr) return nullptr;
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;
    }
    fast = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}

27.合并有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* p1 = list1, * p2 = list2;
    ListNode* ans = new ListNode;
    ListNode *t = ans;
    while(p1 != nullptr && p2 != nullptr){
        if(p1->val <= p2->val){
            t->next = p1;
            t = t->next;
            p1 = p1->next;
        }else{
            t->next = p2;
            t = t->next;
            p2 = p2->next;
        }
    }
    while(p1 != nullptr ){
        t->next = p1;
        t = t->next;
        p1 = p1->next;
    }
    while(p2 != nullptr){
        t->next = p2;
        t = t->next;
        p2 = p2->next;
    }
    ListNode* anshead = ans;
    ans = ans->next;
    delete anshead;
    return ans; 
}

28.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* p1 = l1,*p2 = l2;
    int cin = 0;
    ListNode * pSum = new ListNode;
    ListNode *p = pSum;
    while(p1 != nullptr || p2 != nullptr){
        int val1 = 0,val2 = 0;
        if(p1 != nullptr){
            val1 = p1->val;
            p1 = p1->next;
        }
        if(p2 != nullptr){
            val2 = p2->val;
            p2 = p2->next;
        }
        int sum = val1 + val2 + cin;
        cin = sum / 10;
        ListNode * node = new ListNode;
        node->val = sum % 10; 
        p->next = node;
        p = p->next;
    }
    //注意两个数都结束但是还进位的情况 9+99
    if(cin == 1){
        ListNode * node = new ListNode;
        node->val = 1; 
        p->next = node;
        p = p->next;
    }

    //todo delete pSum
    return pSum->next;
}

29.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode * s = head,*f = head,*pre = nullptr;
    while( n-- > 0){
        f =  f->next;
    }
    //易错点，删除头节点
    if (f == nullptr) {
        ListNode* newHead = head->next;
        delete head;
        return newHead;
    }
    
    while( f != nullptr){
        f = f->next;
        pre = s;
        s = s->next;
    }
    pre->next = s->next;
    delete s;
    return head;
}

30.两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

//递归
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* first = head;
        ListNode* second = head->next;
        ListNode* rest = swapPairs(second->next);
        second->next = first;
        first->next = rest;
        return second; 
    }

//非递归
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        //加入哨兵节点一起操作很重要，否则很容仪的第二对和第一对连接不正确
        while (prev->next && prev->next->next) {
            ListNode* first = prev->next;
            ListNode* second = first->next;
            
            // 交换
            first->next = second->next;
            second->next = first;
            prev->next = second;
            
            // 移动到下一对
            prev = first;
        }
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }

31.K个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode * dummpy = new ListNode;
        dummpy->next = head;
        ListNode * pre = dummpy;
        ListNode* end = dummpy;
        while( end->next != nullptr){
            for(int i = 0 ;  i < k  && end != nullptr ; i++){
                end = end->next;
            }
            if(end == nullptr) break;
            ListNode * start = pre->next;
            ListNode * _next = end->next;
            end->next = nullptr;
            pre->next = reverse(start);
            start->next = _next;
            pre = start;
            end = pre;
        }
        return dummpy->next;
    }

    ListNode* reverse(ListNode * head){
        ListNode * cur = head;
        ListNode * pre = nullptr;
        while(cur != nullptr){
            ListNode * _next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = _next;
        }
        return pre;
    }
};

参考题解： https://leetcode.cn/problems/reverse-nodes-in-k-group/?envType=study-plan-v2&envId=top-100-liked

32.随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码只接受原链表的头节点 head 作为传入参数。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        //hash表 时间空间复杂度 ON
        if(head == nullptr){
            return nullptr;
        }
        Node * cur = head;
        unordered_map<Node* ,Node *> map;
        while(cur != nullptr){
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur != nullptr){
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[head];
    }
    Node* copyRandomList(Node* head) {
        //hash表 时间空间复杂度 ON
        if(head == nullptr){
            return nullptr;
        }
        Node * cur = head;
        //拼接式构建
        while(cur != nullptr){
            Node* next = cur->next;
            Node* newNode = new Node(cur->val);
            cur->next = newNode;
            newNode->next = next;
            cur = next;
        }
        //设置ramdom
        cur = head;
        while(cur != nullptr){
            if(cur->random != nullptr){
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        
        //设置分离
        cur = head->next;
        Node* pre = head,*res = head->next;
        while(cur->next != nullptr){
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr;
        return res;
    }
};

//参考题解 https://leetcode.cn/problems/copy-list-with-random-pointer/solutions/2361362/138-fu-zhi-dai-sui-ji-zhi-zhen-de-lian-b-6jeo/?envType=study-plan-v2&envId=top-100-liked

33.排序链表

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

//递归版 空间复杂度O（logN）
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* mid = findMid(head);
        ListNode* left = head,*right = mid->next;
        mid->next = nullptr;
        left = sortList(left);
        right = sortList(right);
        return merge(left,right);
    }
    private:
    ListNode* findMid(ListNode* head){
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode * slow = head,*fast = head->next;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* merge(ListNode* l1,ListNode* l2){
        ListNode dummpy(0);
        ListNode* t  = &dummpy;
        ListNode* p1 = l1,*p2 = l2;
        while(p1 && p2){
            if(p1->val <= p2->val){
                t->next = p1;
                p1 = p1->next;
            }else{
                t->next = p2;
                p2 = p2->next;
            }
            t= t->next;
        }
        if(p1){
            t->next = p1;
        }else{
            t->next = p2;
        }
        return dummpy.next;
    }
};

//迭代版，空间复杂度O（1）
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        int length = getLength(head);
        
        ListNode dummy(0);
        dummy.next = head;
        
        for(int step = 1 ; step < length ; step <<= 1 ){
            ListNode* prev = &dummy;  // 记录已排序部分的尾部
            ListNode* cur = dummy.next;
            
            while(cur != nullptr){
                ListNode* left = cur;
                ListNode* right = split(left, step);
                cur = split(right, step);
                
                ListNode* merged = merge(left, right);
                prev->next = merged;  
                
                while(prev->next != nullptr){
                    prev = prev->next;
                }
            }
        }
        return dummy.next;
    }
    
private:
    int getLength(ListNode * head){
        int length = 0;
        ListNode * cur = head;
        while(cur != nullptr){
            cur = cur->next;
            length++;
        }
        return length;
    }
    
    ListNode* split(ListNode* head, int size){
        if(head == nullptr) return nullptr;  
        
        ListNode * cur = head;
        for(int i = 1; i < size && cur->next != nullptr; i++){
            cur = cur->next;
        }
        ListNode *next = cur->next;
        cur->next = nullptr;
        return next;
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2){
        ListNode dummy(0); 
        ListNode* t  = &dummy;
        
        while(l1 && l2){
            if(l1->val <= l2->val){
                t->next = l1;
                l1 = l1->next;
            }else{
                t->next = l2;
                l2 = l2->next;
            }
            t = t->next;
        }
        
        t->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

34.合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

//暴力法
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummpy;
        ListNode * ret ;
        ListNode * t = &dummpy;
        vector<ListNode*> vec_cur = lists;
        int k = lists.size();

        while(1){
            bool all_empty = true;
            ListNode* minNode = nullptr;
            int min_i = 0;
            for(int i = 0 ; i < k ; i++){
                if(vec_cur[i]){
                    all_empty = false;
                    if(nullptr == minNode){
                        minNode = vec_cur[i];
                        min_i = i;
                    }
                     else if(minNode->val > vec_cur[i]->val){
                        minNode = vec_cur[i];
                        min_i = i;
                    }
                }
            }
            if(all_empty){
                break;
            }
            t->next = minNode;
            vec_cur[min_i] = vec_cur[min_i]->next;
            t = t->next;
        }
        return dummpy.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //优先队列 最小堆
        auto cmp =  [](const ListNode * a ,const ListNode * b ){
            return a->val > b->val;
        };
        priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> pq;
        for(auto head : lists){
            if(head){
                pq.push(head);
            }
        }
        ListNode dummpy;
        ListNode* cur = &dummpy;
        while(!pq.empty()){
            auto node = pq.top();
            pq.pop();
            if(node->next){
                pq.push(node->next);
            }
            cur->next = node;
            cur = cur->next;
        }
        return dummpy.next;
    }
};

35.LRU 缓存

struct Node{
    Node* pre;
    Node* next;
    int key;
    int value;
};
class LRUCache {
public:
    LRUCache(int capacity) {
        m_capacity = capacity;
        dummpy_head.next = &dummpy_tail;
        dummpy_tail.pre = &dummpy_head;
    }
    
    int get(int key) {
        if(m_map.contains(key)){
            Node * node = m_map[key];
            moveToHead(node);
            return node->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(m_map.contains(key)){
            Node * node = m_map[key];
            moveToHead(node);
            node->value = value;
        }else{
            Node* new_node = new Node;
            new_node->value = value;
            new_node->key = key; 
            m_map[key] = new_node;
            addToHead(new_node);
            ++m_size;
            if(m_size > m_capacity){
                Node* removed = removeTail();
                m_map.erase(removed->key);
                delete removed;
                m_size--;
            }

        }
        return ;
    }
private:
    void removeNode(Node* node){
        node->next->pre = node->pre;
        node->pre->next = node->next;
    }
    Node* removeTail(){
        Node* tail = dummpy_tail.pre;
        removeNode(tail);
        return tail;
    }
    void addToHead(Node* node){
        dummpy_head.next->pre = node;
        node->next = dummpy_head.next;
        node->pre = &dummpy_head;
        dummpy_head.next = node;
    }
    void moveToHead(Node* node){
        removeNode(node);
        addToHead(node);
    }
    unordered_map<int,Node*> m_map;
    int m_capacity{0};
    int m_size{0};
    Node dummpy_head;
    Node dummpy_tail;
};

二叉树

36.二叉树的中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        //递归
        vector<int> ret;
        if(root == nullptr) return ret;
        vector<int> tmp = inorderTraversal(root->left);
        ret.insert(ret.end(),tmp.begin(),tmp.end());
        ret.push_back(root->val);
        tmp = inorderTraversal(root->right);
        ret.insert(ret.end(),tmp.begin(),tmp.end());
        return ret;
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        //迭代
        stack<TreeNode*> stk;
        while(root != nullptr || !stk.empty()){
            while(root != nullptr){
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            ret.push_back(root->val);
            root = root->right;
        }
        return ret;
    }

};

37.二叉树的最大深度

优秀题解 DFS与BFS讲解 https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/2361697/104-er-cha-shu-de-zui-da-shen-du-hou-xu-txzrx/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(nullptr == root){
            return 0;
        }
        return 1 + std::max(maxDepth(root->left),maxDepth(root->right));
    }
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        vector<TreeNode*> que;
        que.push_back(root);
        int res = 0;
        while (!que.empty()) {
            vector<TreeNode*> tmp;
            //按层统计
            for(TreeNode* node : que) {
                if (node->left != nullptr) tmp.push_back(node->left);
                if (node->right != nullptr) tmp.push_back(node->right);
            }
            que = tmp;
            res++;
        }
        return res;
    }
};

38.翻转二叉树

class Solution {
public:
    void swap(TreeNode* root){
        if(root == nullptr){
            return;
        }
        TreeNode * tmp  = root->left;
        root->left = root->right;
        root->right = tmp;
        swap(root->left);
        swap(root->right);
        return;
    } 
    TreeNode* invertTree(TreeNode* root) {
        swap(root);
        return root;
    }
};

39.对称二叉树

class Solution {
public:
    void swap(TreeNode* root){
        if(root == nullptr){
            return;
        }
        TreeNode * tmp  = root->left;
        root->left = root->right;
        root->right = tmp;
        swap(root->left);
        swap(root->right);
        return;
    } 
    TreeNode* invertTree(TreeNode* root) {
        swap(root);
        return root;
    }
};

40.二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

//转化为深度处理
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans;
    }
private:
    int ans;
    int depth(TreeNode* root){
        if(nullptr == root){
            return 0;
        }
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans,L+R);
        return std::max(L,R)+1;
    }
};

41.二叉树的层次遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode* > q;
        vector<vector<int>> ret;
        if(!root){
            return ret;
        }
        q.push(root);

        while(!q.empty()){
            vector<TreeNode*> nextLayer;
            vector<int> tmp;
            while(!q.empty()){
                TreeNode* node = q.front();
                q.pop();
                if(!node) continue;
                tmp.push_back(node->val);
                if(node->left){
                    nextLayer.push_back(node->left);
                }
                if(node->right){
                    nextLayer.push_back(node->right);
                }
            }
            ret.push_back(tmp);
            for(auto node : nextLayer){
                q.push(node);
            }
        }
        return ret;
    }
};

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

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树（左右子树高度不超过1）。

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

43.验证有效的二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含严格小于当前节点的数。
节点的右子树只包含严格大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return check(root,LONG_MIN,LONG_MAX);
    }
private:
    bool check(TreeNode* node , long low,long high){
        if(!node){
            return true;
        }
        if(node->val >= high || node->val <= low){
            return false;
        }
        return check(node->left,low,node->val) && check(node->right,node->val,high);
    }
};

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

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

进阶题解 https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/1050055/er-cha-sou-suo-shu-zhong-di-kxiao-de-yua-8o07/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stack;
        while(root != nullptr || stack.size() > 0){
            while(root != nullptr){
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            --k;
            if(k == 0){
                break;
            }
            root = root->right;
        }
        return root->val;
    }
};

45.二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> ans;
        if(!root){
            return ans;
        }
        q.push(root);
        while(!q.empty()){
            int last_val = 0;
            vector<TreeNode*> tmp;
            while(!q.empty()){
                TreeNode* node = q.front();
                q.pop();
                if(node){
                    last_val = node->val;
                }else{
                    continue;
                }
                if(node->left){
                    tmp.push_back(node->left);
                }
                if(node->right){
                    tmp.push_back(node->right);
                }
            }
            ans.push_back(last_val);
            for(auto node :tmp){
                q.push(node);
            }
        }
        return ans;
    }
};

46.二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同

你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

class Solution {
public:
    void flatten(TreeNode* root) {
           vector<TreeNode * > l;
           stack<TreeNode*> stack;
           TreeNode * node = root;
           while(node != nullptr || !stack.empty()){
            while(node != nullptr){
                l.push_back(node);
                stack.push(node);
                node = node->left;
            }
            node = stack.top();
            stack.pop();
            node = node->right;
           }
           for(int i = 1 ; i < l.size(); i++){
                TreeNode* pre = l[i-1], *cur = l[i];
                pre->left = nullptr;
                pre->right =  cur;
           }
    }

        void flatten(TreeNode* root) {
            TreeNode* cur = root;
            while(cur != nullptr ){
                if(cur->left != nullptr){
                auto next = cur->left;
                auto predecessor = next;
                while(predecessor->right != nullptr ){
                    predecessor = predecessor->right;
                }
                predecessor->right = cur->right;
                cur->left = nullptr;
                cur->right = next;
                }
                cur = cur->right;
            }
    }

};

//参考题解 https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?envType=study-plan-v2&envId=top-100-liked

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
         int n = preorder.size();
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;//通过map,快速找到中序遍历结果对应的索引
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
private:
    unordered_map<int, int> index;
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        int size_left_subtree = inorder_root - inorder_left;
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
};

//题解参考： https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked

48.路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

class Solution {
public:
    int rootSum(TreeNode* root, long long targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
// 题解 https://leetcode.cn/problems/path-sum-iii/solutions/1021296/lu-jing-zong-he-iii-by-leetcode-solution-z9td/
};

49.二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

class Solution {
private:
    TreeNode* ans;
    bool dfs(TreeNode* root,TreeNode* p , TreeNode * q){
        //表示root节点中是否包含其中一个节点
        if(root == nullptr) return false;
        bool lson = dfs(root->left,p,q);
        bool rson = dfs(root->right,p,q);
        if((lson && rson)||((root->val == p->val || root->val == q->val)&& (lson || rson))){
            ans = root;
        }
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,q);
        return ans;
    }
};

50.二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其最大路径和。

class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;

        // 更新答案
        maxSum = max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }

//参考题解： https://leetcode.cn/problems/binary-tree-maximum-path-sum/solutions/297005/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/

};

图论

51.岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围

class Solution {
private:
    void dfs(vector<vector<char>>& grid,int r,int c){
        int rows = grid.size();
        int cols = grid[0].size();

        grid[r][c] = '0';
        if(r-1 >=0 && grid[r-1][c] == '1'){
            dfs(grid,r-1,c);
        }
        if(r+1 < rows && grid[r+1][c] == '1'){
            dfs(grid,r+1,c);
        }
        if(c-1 >= 0 && grid[r][c-1] == '1'){
            dfs(grid,r,c-1);
        }
        if(c+1 < cols && grid[r][c+1] == '1'){
            dfs(grid,r,c+1);
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size();
        if(rows == 0) return 0;
        int cols = grid[0].size();

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

52.腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 方向数组：上下左右
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        queue<pair<int, int>> q;
        int freshCount = 0;  // 新鲜橘子的数量
        
        // 初始化：将所有腐烂橘子加入队列，统计新鲜橘子数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        // 如果没有新鲜橘子，直接返回0
        if (freshCount == 0) return 0;
        
        int minutes = 0;
        
        // BFS
        while (!q.empty()) {
            int size = q.size();
            bool rotted = false;  // 标记这一轮是否有橘子腐烂
            
            for (int i = 0; i < size; i++) {
                auto [x, y] = q.front();
                q.pop();
                
                // 检查四个方向
                for (auto [dx, dy] : directions) {
                    int nx = x + dx;
                    int ny = y + dy;
                    
                    // 如果相邻位置在网格内且是新鲜橘子
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;  // 变为腐烂
                        q.push({nx, ny});   // 加入队列
                        freshCount--;        // 新鲜橘子数量减1
                        rotted = true;       // 标记这一轮发生了腐烂
                    }
                }
            }
            
            if (rotted) minutes++;  // 如果这一轮有腐烂发生，时间加1
        }
        
        // 如果还有新鲜橘子，返回-1；否则返回分钟数
        return freshCount == 0 ? minutes : -1;
    }
};

53.课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建邻接表
        vector<vector<int>> adj(numCourses);
        // 记录每个节点的入度
        vector<int> inDegree(numCourses, 0);
        
        // 构建图
        for (auto& pre : prerequisites) {
            int course = pre[0];      // 当前课程
            int prerequisite = pre[1]; // 先修课程
            adj[prerequisite].push_back(course); // prerequisite -> course
            inDegree[course]++; // 课程course的入度加1
        }
        
        // 队列存储入度为0的节点（不需要先修课程的课）
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        int count = 0; // 已学习的课程数量
        
        // BFS拓扑排序
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            count++;
            
            // 将当前课程的后继课程入度减1
            for (int next : adj[curr]) {
                inDegree[next]--;
                // 如果入度变为0，加入队列
                if (inDegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        // 如果能学习的课程数量等于总课程数，说明可以完成
        return count == numCourses;
    }
};

54.前缀树

Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True

class Trie {
private:
    struct TrieNode {
        bool isEnd;  // 标记是否为单词结尾
        TrieNode* children[26];  // 26个小写字母的子节点指针数组
        TrieNode() {
            isEnd = false;
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };
    
    TrieNode* root;  
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a'; 
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return true;
    }
    
    ~Trie() {
        clear(root);
    }
    
private:
    void clear(TrieNode* node) {
        if (node == nullptr) return;
        for (int i = 0; i < 26; i++) {
            if (node->children[i] != nullptr) {
                clear(node->children[i]);
            }
        }
        delete node;
    }
};

每个节点都发散出26个字母的节点。注意这种数据结构的组织方式

回溯

deepseek 提问：常见的回溯类型、模板、区别、执行过程推演。

void backtrack(参数) {
    // 1. 终止条件
    if (满足结束条件) {
        存放结果;
        return;
    }
    
    // 2. 遍历所有选择
    //顺序重要就用startIndex
    for (选择 : 所有可能的选择) {
        // 3. 剪枝（可选）：跳过无效选择
        if (选择无效) continue;
        
        // 4. 做选择
        做选择（标记已使用）;
        
        // 5. 递归进入下一层
        backtrack(新参数);
        
        // 6. 撤销选择（回溯）
        撤销选择（取消标记）;
    }
}

55.全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<bool> used(nums.size(),false);
        vector<int> curr;
        backtrace(ans,nums,used,curr);
        return ans;
    }
    private:
    void backtrace(vector<vector<int>>& ans,vector<int>&nums,vector<bool>& used,vector<int>& curr){
        if(nums.size() == curr.size()){
            ans.push_back(curr);
            return;
        }
        for(int i = 0 ; i < nums.size();i++){
            if(used[i]){
                continue;
            }
            used[i] = true;
            curr.push_back(nums[i]);
            
            backtrace(ans,nums,used,curr);

            used[i] = false;
            curr.pop_back();
        }
    }
};

56.子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        backtrace(res,cur,0,nums);
        return res;
    }
private:
    void backtrace(vector<vector<int>>& res,vector<int>& cur,int start_index,vector<int>& nums){
        //思考点：返回值条件？
        res.push_back(cur);

        for(int i = start_index ; i < nums.size();i++){
            cur.push_back(nums[i]);
            
            backtrace(res,cur,i+1,nums);

            cur.pop_back();
        }
    }
};

57.电话号码的字母组合

class Solution {
    vector<vector<char>> char_map;
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        if(digits.empty()){
            return ret;
        }
        string curr;
        char_map = {{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
        backtrace(ret,digits,0,curr);
        return ret;
    }
    void backtrace(vector<string>& ret,string digits,int index,string &  curr){
        if(index == digits.length()){
            ret.push_back(curr);
            return;
        }
        int num = digits.at(index) - '0';
        for(auto ch : char_map[num]){
            curr += ch;
            backtrace(ret,digits,index+1,curr);
            curr.pop_back(); 
        }
    }
};

58.组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> curr;
        backtrace(ret,curr,candidates,target,0);
        return ret;
    }
    void backtrace(vector<vector<int>> & ret,vector<int>& curr,vector<int>& candidates,int target,int startIndex){
        if(target == 0){
            ret.push_back(curr);
            return;
        }
        if(target < 0){
            return;
        }

        //这里要区分重复，所哟需要使用startIndex去重
        for(int i = startIndex ; i < candidates.size();i++){
            int num = candidates.at(i);
            curr.push_back(num);
            target -= num;
            backtrace(ret,curr,candidates,target,i);
            target += num;
            curr.pop_back();
        }
    }
};

59.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string curr;
        backtrace(ret,n,n,curr);
        return ret;
    }
private:
    void backtrace(vector<string>&ret,int left,int right, string& curr){
        if(left == 0 && right ==0){
            ret.push_back(curr);
            return;
        }

        if(left > 0){
            curr += '(';
            backtrace(ret,left-1,right,curr);
            curr.pop_back();
        }

        if(right > 0  && right > left){
            //第二个条件易遗漏
            curr += ')';
            backtrace(ret,left,right-1,curr);
            curr.pop_back();
        }
    }
};

60.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。


class Solution {
public:
    vector<pair<int,int>> vec_dics = {{1,0},{-1,0},{0,1},{0,-1}};
    
    bool exist(vector<vector<char>>& board, string word) {
        int row = board.size();
        int col = board[0].size();
        vector<vector<bool>> used(row, vector<bool>(col, false));
        
        for(int r = 0; r < row; r++){
            for(int c = 0; c < col; c++){
                if(board[r][c] == word[0]){
                    if(backtrace(board, word, 0, r, c, used)){
                        return true;
                    }
                }
            }
        }        
        return false;
    }
    
    bool backtrace(vector<vector<char>>& board, string word, int index, 
                   int r, int c, vector<vector<bool>>& used){
        // 终止条件：找到了完整单词
        if(index == word.length()){
            return true;
        }
        
        int row = board.size();
        int col = board[0].size();
        
        // 边界检查 和 字符匹配检查 和 是否已使用检查
        if(r < 0 || r >= row || c < 0 || c >= col || 
           used[r][c] || board[r][c] != word[index]){
            return false;
        }
        
        // 标记当前格子已使用
        used[r][c] = true;
        
        // 向四个方向探索
        for(auto dic : vec_dics){
            int next_r = r + dic.first;
            int next_c = c + dic.second;
            
            if(backtrace(board, word, index + 1, next_r, next_c, used)){
                return true;
            }
        }
        
        // 回溯：取消标记
        used[r][c] = false;
        
        return false;
    }
};

61.分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        vector<string> curs;
        backTrace(ret,s,curs,0);
        return ret;
    }
    void backTrace(vector<vector<string>>& ret,string s,vector<string>& curs,int startIndex){
        if(startIndex == s.length()){
            ret.push_back(curs);
            return;
        }

        for(int i = startIndex ; i < s.length() ; i++){
            if(isPalindrome(s,startIndex,i)){
                string substr = s.substr(startIndex,i-startIndex+1);
                curs.push_back(substr);
                backTrace(ret,s,curs,i+1);
                curs.pop_back();
            }
        }
    }
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

62.N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

class Solution {
private:
    vector<vector<string>> result;
    // 检查在 (row, col) 放置皇后是否合法
    bool isValid(vector<string>& board, int row, int col, int n) {
        // 检查同一列的上方
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        
        // 检查左上方对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        
        // 检查右上方对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }
    
    // 回溯：逐行放置皇后
    void backtrack(vector<string>& board, int row, int n) {
        // 终止条件：所有行都放置完毕
        if (row == n) {
            result.push_back(board);
            return;
        }
        
        // 尝试当前行的每一列
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col, n)) {
                // 做选择
                board[row][col] = 'Q';
                
                // 递归下一行
                backtrack(board, row + 1, n);
                
                // 撤销选择
                board[row][col] = '.';
            }
        }
    }  
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        // 初始化棋盘，全部为 '.'
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0, n);
        return result;
    }
};

二分查找

63.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

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

64.搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    
    int m = matrix.size();
    int n = matrix[0].size();
    
    int left = 0;
    int right = m * n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;
        int value = matrix[row][col];
        
        if (value == target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}
};

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto first = lower_bound(nums.begin(), nums.end(), target);
        auto last = upper_bound(nums.begin(), nums.end(), target);
        
        if (first == nums.end() || *first != target) {
            return {-1, -1};
        }
        
        return {static_cast<int>(first - nums.begin()), 
                static_cast<int>(last - nums.begin() - 1)};
    }
};

66.搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了向左旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2]。
给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution {
public:
//在旋转排序数组中，每次二分时，至少有一半是有序的。我们可以利用这个有序的半部分来判断target的位置。
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        
        int left = 0;
        int right = nums.size() - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断左半部分是否有序
            if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;  // target 在左半部分
                } else {
                    left = mid + 1;   // target 在右半部分
                }
            } 
            // 右半部分有序
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;   // target 在右半部分
                } else {
                    right = mid - 1;  // target 在左半部分
                }
            }
        }
        
        return -1;
    }
};

67.寻找排序数组的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

class Solution {
public:
//数组被分成两个有序的部分
//最小值正好是两个有序部分的分界点
//最小值右边的所有元素都小于左边的所有元素
//如果 nums[mid] > nums[right]：说明mid在旋转点的左边，最小值在mid右边
//如果 nums[mid] < nums[right]：说明mid在旋转点的右边，最小值在mid左边（或就是mid）
    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;
            } 
            // 否则最小值在左半部分（包括mid）
            else {
                right = mid;
            }
        }
        
        // 循环结束时，left == right，指向最小值
        return nums[left];
    }
};

68. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.size();
        int n = nums2.size();
        int totalLeft = (m + n + 1) / 2;  // 左半部分需要的总元素个数
        int left = 0;

        int right = m;
        // 在 nums1 的索引范围 [0, m] 上二分查找合适的 i
        //长度条件：左半部分元素总数 = (m + n + 1) / 2
        //大小条件：左半部分所有元素 ≤ 右半部分所有元素
        //nums1[i-1] ≤ nums2[j] 且 nums2[j-1] ≤ nums1[i]
        
        while (left < right) {
            int i = left + (right - left + 1) / 2;  // nums1 中取前 i 个
            int j = totalLeft - i;                   // nums2 中取前 j 个
            
            if (nums1[i - 1] > nums2[j]) {
                // nums1 左边太大，需要减小 i
                right = i - 1;
            } else {
                // nums1 左边 <= nums2 右边，i 可能合适或太小
                left = i;
            }
        }
        
        int i = left;
        int j = totalLeft - i;
        
        // 处理边界情况
        int nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1];
        int nums1RightMin = (i == m) ? INT_MAX : nums1[i];
        int nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1];
        int nums2RightMin = (j == n) ? INT_MAX : nums2[j];
        
        // 计算中位数
        if ((m + n) % 2 == 1) {
            // 奇数长度
            return max(nums1LeftMax, nums2LeftMax);
        } else {
            // 偶数长度
            return (max(nums1LeftMax, nums2LeftMax) + 
                    min(nums1RightMin, nums2RightMin)) / 2.0;
        }
    }
};

栈

69.有效的括号

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;      
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } 
            else {
                if (st.empty()) {
                    return false;
                }
                char top = st.top();
                if ((c == ')' && top == '(') ||
                    (c == ']' && top == '[') ||
                    (c == '}' && top == '{')) {
                    st.pop(); 
                } else {
                    return false;  
                }
            }
        }
        return st.empty();
    }
};

70.最小栈

方法一：辅助栈法（最常用）
使用两个栈：
数据栈：正常存储所有元素
最小栈：同步存储当前栈的最小值

方法二：单栈法（存储差值）
只用一个栈，存储元素与当前最小值的差值
需要额外的数学计算，但节省空间

class MinStack {
private:
    stack<long long> st;  // 存储差值，用 long long 防止溢出
    long long minVal;     // 当前最小值
    
public:
    MinStack() {
        minVal = 0;  // 初始值无所谓，会在第一次 push 时设置
    }
    
    void push(int val) {
        if (st.empty()) {
            // 第一个元素
            st.push(0);      // 差值为0
            minVal = val;
        } else {
            // 存储当前值与最小值的差值
            long long diff = (long long)val - minVal;
            st.push(diff);
            
            // 更新最小值
            if (diff < 0) {
                // 如果 diff < 0，说明 val 比当前最小值小
                minVal = val;
            }
        }
    }
    
    void pop() {
        long long diff = st.top();
        st.pop();
        
        if (diff < 0) {
            // 如果弹出的差值小于0，说明当时 push 的是最小值
            // 需要恢复前一个最小值：前一个最小值 = 当前最小值 - diff
            // 因为 diff = val - minVal，且 val = 旧的最小值
            minVal = minVal - diff;
        }
        // 如果 diff >= 0，最小值不变
    }
    
    int top() {
        long long diff = st.top();
        
        if (diff < 0) {
            // 如果差值小于0，栈顶就是当前最小值
            return minVal;
        } else {
            // 否则栈顶 = 最小值 + 差值
            return minVal + diff;
        }
    }
    
    int getMin() {
        return minVal;
    }
};

71.字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。

示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”

方法一：辅助栈法（最常用）
使用两个栈：
数字栈：保存当前的重复次数
字符串栈：保存当前层之前的结果
遇到 [ 时，将当前数字和字符串压栈，然后重置
遇到 ] 时，从栈中弹出数字和之前的字符串，进行拼接

方法二：递归法
利用递归处理嵌套，遇到 [ 就递归调用，遇到 ] 就返回

class Solution {
public:
    string decodeString(string s) {
        stack<int> numStack;      // 存储重复次数
        stack<string> strStack;   // 存储之前的字符串
        string currStr = "";      // 当前正在构建的字符串
        int num = 0;              // 当前数字
        
        for (char c : s) {
            if (isdigit(c)) {
                // 处理多位数
                num = num * 10 + (c - '0');
            }
            else if (c == '[') {
                // 遇到左括号，将当前状态入栈
                numStack.push(num);
                strStack.push(currStr);
                // 重置
                currStr = "";
                num = 0;
            }
            else if (c == ']') {
                // 遇到右括号，解码
                int repeatTimes = numStack.top(); numStack.pop();
                string prevStr = strStack.top(); strStack.pop();
                
                // 将当前字符串重复 repeatTimes 次
                string temp = "";
                for (int i = 0; i < repeatTimes; i++) {
                    temp += currStr;
                }
                
                // 拼接到之前的字符串
                currStr = prevStr + temp;
            }
            else {
                // 普通字符
                currStr += c;
            }
        }
        
        return currStr;
    }
};

72.每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> answer(n, 0);
        stack<int> st;
        
        for (int i = 0; i < n; i++) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int prevIndex = st.top();
                st.pop();
                answer[prevIndex] = i - prevIndex;
            }
            st.push(i);
        }
        
        return answer;
    }
};

73.柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 在数组前后各加一个0，简化边界处理
        vector<int> newHeights(heights.size() + 2, 0);
        for (int i = 0; i < heights.size(); i++) {
            newHeights[i + 1] = heights[i];
        }
        stack<int> st;
        int maxArea = 0;
        for (int i = 0; i < newHeights.size(); i++) {
            // 当当前高度小于栈顶高度时，说明找到了栈顶的右边界
            while (!st.empty() && newHeights[i] < newHeights[st.top()]) {
                int height = newHeights[st.top()];
                st.pop();
                // 左边界是新的栈顶（因为栈内递增，栈顶的下一个就是左边第一个小于当前高度的）
                int left = st.top();
                int right = i;
                int width = right - left - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        
        return maxArea;
    }
};

74.数组中第K大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

题解
https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcod-2/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

75.前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 1. 统计频率
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        // 2. 定义最小堆：pair<频率, 元素>
        // 注意：priority_queue默认是最大堆，用greater变成最小堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        
        // 3. 遍历频率表，维护大小为k的最小堆
        for (auto& [num, count] : freq) {
            minHeap.push({count, num});
            
            // 如果堆大小超过k，弹出频率最小的
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        
        // 4. 取出堆中的元素
        vector<int> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second);
            minHeap.pop();
        }
        
        return result;
    }
};

76.数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

class MedianFinder {
private:
    // 最大堆：存储较小的一半元素
    priority_queue<int> maxHeap;
    // 最小堆：存储较大的一半元素
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
public:
    MedianFinder() {
        // 初始化两个堆
    }
    
    void addNum(int num) {
        // 1. 决定放入哪个堆
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }
        
        // 2. 平衡两个堆的大小
        // 保证：maxHeap.size() >= minHeap.size()
        // 且两个堆的大小差不超过1
        
        // 如果maxHeap比minHeap多2个以上，移动一个到minHeap
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
        // 如果minHeap比maxHeap多，移动一个到maxHeap
        else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        // 如果两个堆大小相等，取两个堆顶的平均值
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
        // 否则，maxHeap多一个，它的堆顶就是中位数
        else {
            return maxHeap.top();
        }
    }
};

贪心

77.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        
        int minPrice = prices[0];  // 历史最低价格
        int maxProfit = 0;          // 最大利润
        
        for (int i = 1; i < prices.size(); i++) {
            // 如果当前价格比历史最低还低，更新最低价
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } 
            // 否则计算当前卖出能获得的利润
            else {
                maxProfit = max(maxProfit, prices[i] - minPrice);
            }
        }
        
        return maxProfit;
    }

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        
        // dp[i][0]：第i天持有股票的利润
        // dp[i][1]：第i天不持有股票的利润
        vector<vector<int>> dp(n, vector<int>(2));
        
        dp[0][0] = -prices[0];  // 第0天买入，利润为负
        dp[0][1] = 0;            // 第0天不持有，利润为0
        
        for (int i = 1; i < n; i++) {
            // 第i天持有：要么前一天就持有，要么今天买入
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            
            // 第i天不持有：要么前一天就不持有，要么今天卖出
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        
        return dp[n-1][1];  // 最后一天不持有股票的最大利润
    }
};

78.跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;  // 当前能到达的最远位置
        
        for (int i = 0; i < nums.size(); i++) {
            // 如果当前位置超过了能到达的最远距离，说明无法到达这里
            if (i > maxReach) {
                return false;
            }
            
            // 更新能到达的最远距离
            maxReach = max(maxReach, i + nums[i]);
            
            // 如果已经能到达最后一个位置，提前返回
            if (maxReach >= nums.size() - 1) {
                return true;
            }
        }
        
        return maxReach >= nums.size() - 1;
    }
};

79.跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        
        int jumps = 0;          // 跳跃次数
        int currentEnd = 0;     // 当前跳跃能到达的边界
        int farthest = 0;       // 所有位置能到达的最远距离
        
        for (int i = 0; i < n - 1; i++) {
            // 更新能到达的最远距离
            farthest = max(farthest, i + nums[i]);
            
            // 到达当前跳跃的边界，必须进行一次跳跃
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;  // 更新下一次跳跃的边界
            }
        }
        
        return jumps;
    }
};

80.划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // 1. 记录每个字符最后出现的位置
        vector<int> lastPos(26, 0);
        for (int i = 0; i < s.length(); i++) {
            lastPos[s[i] - 'a'] = i;
        }
        
        // 2. 划分片段
        vector<int> result;
        int start = 0;      // 当前片段的起始位置
        int end = 0;        // 当前片段的结束位置
        
        for (int i = 0; i < s.length(); i++) {
            // 更新当前片段的最远结束位置
            end = max(end, lastPos[s[i] - 'a']);
            
            // 如果当前位置等于当前片段的最远结束位置
            // 说明当前片段可以结束了
            if (i == end) {
                result.push_back(end - start + 1);
                start = i + 1;  // 下一个片段的开始
            }
        }
        
        return result;
    }
};

递归

81，爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n - 1; i++){
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
    }
};

82.杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> triangle;
        
        for (int i = 0; i < numRows; i++) {
            // 当前行有 i+1 个元素
            vector<int> row(i + 1, 1);  // 全部初始化为1
            
            // 从第2行开始（索引2），中间的元素需要计算
            for (int j = 1; j < i; j++) {
                // 左上角 + 右上角
                row[j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
            
            triangle.push_back(row);
        }
        
        return triangle;
    }
};

83.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        // dp[i] 表示偷窃前 i 间房屋能得到的最高金额
        vector<int> dp(n, 0);
        
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            // 偷第i间：dp[i-2] + nums[i]
            // 不偷第i间：dp[i-1]
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp[n-1];
    }
};

84.完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        //dp[i] = 组成数字 i 所需的最少完全平方数的个数
        // 1. 先遍历背包容量（每个数字j）
        for (int j = 1; j <= n; j++) {
            // 2. 再遍历物品（尝试所有可能的平方数）
            for (int i = 1; i * i <= j; i++) {
                // 状态转移：j 可以由 (j - i²) 加上一个 i² 得到
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
};

85.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
         // dp[i] 表示凑成金额 i 所需的最少硬币数
        vector<int> dp(amount + 1, amount + 1);  // 初始化为一个不可能的大数
        dp[0] = 0;
        
        // 遍历所有金额
        for (int i = 1; i <= amount; i++) {
            // 尝试每种硬币
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // 如果 dp[amount] 仍然是初始值，说明无法凑成
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

86.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
                // 将字典转换为unordered_set，方便快速查找
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.length();
        
        // dp[i] 表示 s[0..i-1] 能否被拆分
        vector<bool> dp(n + 1, false);
        dp[0] = true;  // 空字符串
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // 如果前j个字符可以拆分，且s[j..i-1]在字典中
                if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;  // 找到一个即可
                }
            }
        }
        
        return dp[n];
    }
};

87.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

class Solution {
public:
    //  回溯法：时间O(2^n)
    int lengthOfLIS(vector<int>& nums) {
    // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    //如果 nums[j] < nums[i]，则 nums[i] 可以接在 nums[j] 后面
    //o(n2)
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> dp(n, 1);  // dp[i] 表示以nums[i]结尾的LIS长度
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
};

88.乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位整数。

需要注意到负数的情况

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> maxDP(n), minDP(n);
        maxDP[0] = nums[0];
        minDP[0] = nums[0];
        int result = nums[0];
        for (int i = 1; i < n; i++) {
            maxDP[i] = max({nums[i], 
                           maxDP[i-1] * nums[i], 
                           minDP[i-1] * nums[i]});
            minDP[i] = min({nums[i], 
                           maxDP[i-1] * nums[i], 
                           minDP[i-1] * nums[i]});
            
            result = max(result, maxDP[i]);
        }
        
        return result;
    }
};

89.分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
    //01 背包问题
    //dfs回溯
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        
        // 如果和为奇数，不可能平分
        if (sum % 2 != 0) return false;
        
        int target = sum / 2;
        int n = nums.size();
        
        // dp[i][j] 表示前i个数能否凑出和j
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        
        // 初始化：和为0总是可行的
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; 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]];
                }
            }
        }
        
        return dp[n][target];
    }
};

90.最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        if (n < 2) return 0;
        
        vector<int> dp(n, 0);//以 s[i] 结尾的最长有效括号子串的长度
        int maxLen = 0;
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i-1] == '(') {
                    //情况1：s[i-1] == '('，形如 "...()"
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                }
                else if (i - dp[i-1] > 0 && s[i - dp[i-1] - 1] == '(') {
                    //s[i-1] == ')'，形如 "...))"
                    // 情况2：...((...))
                    dp[i] = dp[i-1] + 2;
                    if (i - dp[i-1] >= 2) {
                        dp[i] += dp[i - dp[i-1] - 2];
                    }
                }
                maxLen = max(maxLen, dp[i]);
            }
        }
        
        return maxLen;
    }
};

多维动态规划

91.不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp[i][j] 表示到达 (i,j) 的路径数
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // 初始化第一行和第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        
        // 填充dp数组
        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];
    }
};

92.最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // dp[i][j] 表示到达 (i,j) 的最小路径和
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // 初始化起点
        dp[0][0] = grid[0][0];
        
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        
        // 初始化第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        
        // 填充剩余位置
        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];
    }
};

93.最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
private:
    // 从中心向两边扩展，返回回文串长度
    int expandAroundCenter(string& s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s[L] == s[R]) {
            L--;
            R++;
        }
        // 返回回文串长度（注意循环结束时L和R指向不相等的位置）
        return R - L - 1;
    }
    
public:
    string longestPalindrome(string s) {
        if (s.length() < 2) return s;
        
        int start = 0, maxLen = 1;
        
        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度回文
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                // 计算起始位置
                start = i - (len - 1) / 2;
            }
        }
        
        return s.substr(start, maxLen);
    }

string longestPalindrome(string s) {
        int n = s.length();
        if (n < 2) return s;
        
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        // dp[i][j] 表示子串 s[i..j] 是否是回文串
        int start = 0, maxLen = 1;
        
        // 所有长度为1的子串都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // 按子串长度从小到大遍历
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                
                if (s[i] == s[j]) {
                    if (len == 2) {
                        dp[i][j] = true;  // 长度为2的回文
                    } else {
                        dp[i][j] = dp[i+1][j-1];  // 依赖于内部子串
                    }
                } else {
                    dp[i][j] = false;
                }
                
                // 更新最长回文
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }
        
        return s.substr(start, maxLen);
    }
};

94.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length();
        int n = text2.length();
        
        // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的LCS长度
        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];
    }
};

95.编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();  // 第一个单词的长度
        int n = word2.length();  // 第二个单词的长度
        
        /**
         * dp[i][j] 表示 word1[0..i-1] 转换成 word2[0..j-1] 的最少操作次数
         */
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        /**
         * 初始化：
         * dp[0][j]：空串变成 word2[0..j-1] 需要插入 j 个字符
         * dp[i][0]：word1[0..i-1] 变成空串需要删除 i 个字符
         */
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;  // 插入操作
        }
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;  // 删除操作
        }
        
        // 遍历所有状态
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                
                /**
                 * 状态转移方程分析：
                 * 
                 * 情况1：当前字符相等 (word1[i-1] == word2[j-1])
                 *   不需要额外操作，直接继承左上角的值
                 *   dp[i][j] = dp[i-1][j-1]
                 * 
                 * 情况2：当前字符不相等，有三种操作可选：
                 *   1. 删除 word1[i-1]：dp[i-1][j] + 1
                 *      问题变为 word1[0..i-2] -> word2[0..j-1]
                 *   
                 *   2. 插入 word2[j-1]（相当于在word1末尾插入）：dp[i][j-1] + 1
                 *      问题变为 word1[0..i-1] -> word2[0..j-2]
                 *   
                 *   3. 替换 word1[i-1] 为 word2[j-1]：dp[i-1][j-1] + 1
                 *      问题变为 word1[0..i-2] -> word2[0..j-2]
                 *   
                 *   取三种操作的最小值
                 */
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min({
                        dp[i-1][j] + 1,      // 删除
                        dp[i][j-1] + 1,      // 插入
                        dp[i-1][j-1] + 1     // 替换
                    });
                }
            }
        }
        
        // dp[m][n] 就是整个字符串转换的最少操作次数
        return dp[m][n];
    }
};

技巧

96.只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        /**
         * 异或运算解法：
         * 利用 a ^ a = 0 和 a ^ 0 = a 的性质
         * 将所有数字异或，成对的会抵消，剩下的就是只出现一次的数字
         * 时间复杂度：O(n)，空间复杂度：O(1)
         */
        int result = 0;
        for (int num : nums) {
            result ^= num;  // 异或运算
        }
        return result;
    }
};

97.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        /**
         * 摩尔投票算法
         * 核心思想：不同元素相互抵消，剩下的就是多数元素
         * 时间复杂度：O(n)
         * 空间复杂度：O(1)
         */
        int candidate = nums[0];  // 候选元素
        int count = 1;            // 计数器
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == candidate) {
                count++;  // 相同，计数增加
            } else {
                count--;  // 不同，计数减少
                
                if (count == 0) {
                    // 计数归零，更换候选元素
                    candidate = nums[i];
                    count = 1;
                }
            }
        }
        
        return candidate;
    }
};

98.颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        /**
         * 三指针解法（荷兰国旗问题）
         * 指针含义：
         *   left: 红色区域的右边界（下一个0应该放的位置）
         *   mid: 当前遍历指针
         *   right: 蓝色区域的左边界（下一个2应该放的位置）
         * 
         * 区域划分：
         *   [0, left)   : 0
         *   [left, mid) : 1
         *   [mid, right]: 待处理
         *   (right, n-1]: 2
         */
        int left = 0;          // 指向下一个0的位置
        int mid = 0;           // 当前遍历指针
        int right = nums.size() - 1;  // 指向下一个2的位置
        
        while (mid <= right) {
            if (nums[mid] == 0) {
                // 遇到0，交换到左边
                swap(nums[left], nums[mid]);
                left++;
                mid++;  // 交换过来的数一定是1（因为mid左边的都已经处理过）
            }
            else if (nums[mid] == 1) {
                // 遇到1，正好在中间区域
                mid++;
            }
            else {  // nums[mid] == 2
                // 遇到2，交换到右边
                swap(nums[mid], nums[right]);
                right--;  // 注意：这里mid不增加，因为交换过来的数还没处理
            }
        }
    }
};

99.下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
要求：必须原地修改，只使用常数额外空间。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        /**
         * 寻找下一个排列的三步算法
         * 1. 从右向左找到第一个升序对 (nums[i] < nums[i+1])
         * 2. 从右向左找到第一个大于 nums[i] 的数 nums[j]
         * 3. 交换 nums[i] 和 nums[j]，然后反转 i+1 到末尾
         */
        int n = nums.size();
        
        // 步骤1：从右向左找第一个升序对
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }
        
        // 步骤2：如果找到了这样的 i
        if (i >= 0) {
            // 从右向左找第一个大于 nums[i] 的数
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // 步骤3：交换
            swap(nums[i], nums[j]);
        }
        
        // 步骤4：反转 i+1 到末尾
        // 无论是否找到 i，都需要反转（如果没找到，i=-1，反转整个数组）
        reverse(nums.begin() + i + 1, nums.end());
    }
};

100.寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有一个重复的整数，返回这个重复的数。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        /**
         * 二分查找解法（对值域二分）
         * 核心思想：对于数mid，统计<=mid的数的个数
         * 如果count > mid，说明重复数在[1, mid]中
         * 否则在[mid+1, n]中
         * 
         * 时间复杂度：O(n log n)
         * 空间复杂度：O(1)
         */
        int left = 1;
        int right = nums.size() - 1;  // n = nums.size() - 1
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            
            // 统计小于等于mid的数的个数
            for (int num : nums) {
                if (num <= mid) {
                    count++;
                }
            }
            
            // 根据鸽巢原理判断
            if (count > mid) {
                right = mid;  // 重复数在左边
            } else {
                left = mid + 1;  // 重复数在右边
            }
        }
        
        return left;
    }
};