Leetcode Top Interview 150

Source: Top Interview 150

88. Merge Sorted Array

画蛇添足的做法：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        priority_queue<int, vector<int>, greater<int>> que;    // 使用一个最小堆
        for(int i = 0; i < m; i++) que.push(nums1[i]);
        for(int j = 0; j < n; j++) que.push(nums2[j]);
        nums1.clear();    // 清空nums1中的元素
        while(!que.empty()){  // 逐个弹出最小堆中的元素
            nums1.push_back(que.top());
            que.pop();
        }
    }
};

暴力直接但能A过的做法：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = m, j = 0; i < m + n && j < n ; i++) nums1[i] = nums2[j++];
        sort(nums1.begin(), nums1.end());
    }
};

最希望看到的做法：#Two Pointers

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p = m + n - 1;  // 指向：排序后放入的位置
        int idx1 = m - 1;   // 指向：待排序的nums1的元素
        int idx2 = n - 1;   // 指向：待排序的nums2的元素
        while(idx1 >= 0 && idx2 >= 0){  // 存在比较的情况
            if(nums2[idx2] > nums1[idx1]){
                nums1[p] = nums2[idx2];
                idx2--;
            }
            else{                    
                nums1[p] = nums1[idx1];
                idx1--;
            }
            p--;
        }
        // 剩下没放完nums2的情况
        while(idx2 >= 0){
            nums1[p] = nums2[idx2];
            idx2--;
            p--;
        }
    }
};

优化过更好的代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p = m + n - 1;
        int i = m - 1;
        int j = n - 1;
        while(j >= 0){
            // nums1中还有元素能“挪动”的情况
            if(i >= 0 && nums1[i] >= nums2[j]) nums1[p--] = nums1[i--];
            // nums1中没有元素能“挪动”的情况，因此不断放入nums2的元素
            else nums1[p--] = nums2[j--];
        }
    }
};

27. Remove Element

方法：#Two Pointers

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int j = 0;   // 指向：不被移除的元素
        int cnt = 0;
        /* i用来遍历一遍数组 */
        for(int i = 0; i < nums.size(); i++){ 
            if(nums[i] == val) continue;
            else{
                cnt++;
                nums[j++] = nums[i];
            }
        }
        return cnt;
    }
};

26. Remove Duplicates from Sorted Array

方法：#Tow Pointers

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;
        int j = 0;   // 指向需要放入的元素
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] != nums[j]){
                j++;
                nums[j] = nums[i];
                k++;
            }
        }
        return ++k;
    }
};

80. Remove Duplicates from Sorted Array II

Solution: #Two Pointers

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int j = 0;    // 指向放入的位置
        int duplicates_count = 1; // 记录重复元素个数
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] == nums[j]){   // 元素相同的情况
                duplicates_count++;
                if(duplicates_count > 2) continue;  // 重复个数超过2，跳过
                else{   // 不超过2，则放入指定位置
                    nums[++j] = nums[i];  
                }
            }
            else{      // 不相同的情况，放入指定位置，重制重复元素个数
                duplicates_count = 1;
                nums[++j] = nums[i];
            }
        }
        return ++j;
    }
};

更简洁的代码:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 2;   // 指向应该放入的位置
        if(nums.size() <= 2) return nums.size();
        for(int i = 2; i < nums.size(); i++){
            if(nums[i] != nums[k - 2]){  // 直接与前面第二个元素进行比较
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
};

169. Majority Element

Solution: #Math

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

Solution: #Hash Map

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> mp;
        for(auto x : nums) mp[x]++;
        int n = nums.size();
        for(auto it : mp){
            if(it.second > n/2) return it.first;
        }
        return -1;
    }
};

Solution: #Boyer-Moore 多数投票算法

1. 初始化：

• candidate：候选元素，初始为 0。
• count：计数器，初始为 0。

2. 遍历数组：

• 如果 count == 0，则将当前元素设为候选元素 candidate。
• 如果当前元素等于 candidate，则 count 增加 1。
• 如果当前元素不等于 candidate，则 count 减少 1。

3. 返回结果：

• 遍历结束后，candidate 就是多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;
        for(auto x : nums){
            if(count == 0) candidate = x;
            if(x == candidate) count++;
            else count--;
        }
        return candidate;
    }
};

189. Rotate Array

Solution: #Simulation

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        vector<int> ans;  // 用来拷贝原数组 
        for(int i = nums.size() - k; i < nums.size(); i++) ans.push_back(nums[i]);
        for(int j = 0; j < nums.size() - k; j++) ans.push_back(nums[j]);
        nums = ans;
    }
};

Solution: #Math

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

reverse是algorithm 头文件中的一个标准函数,调用方式为:reverse(起始迭代器, 结束迭代器);

121. Best Time to Buy and Sell Stock

Solution: #Greedy

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

// 0, -6, 4, -2, 3, -2
// 0, -1, -2, -1, -2 

122. Best Time to Buy and Sell Stock II

Solution: #DP
这里的DP数组含义截止到i天，不持有/持有 股票时拥有的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][1] = -prices[0];
        for(int i = 1; i < n; i++){
            // 第i天有股票的情况：i-1天无股票在i天买 or i-1天有股票在i天继续持有
            dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            // 第i天无股票的情况：i-1天无股票在i天不买 or i-1天有股票在i天卖
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        }
        return dp[n - 1][0];    // 在n-1天没有股票是最好情况
    }
};

更加优化的方法：#Greedy

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(int i = 1; i < prices.size(); i++){
            // 第i天贪心选择：卖 or 不卖 利润最大的情况
            profit = max(profit, profit + prices[i] - prices[i - 1]);
        }
        return profit;
    }
};

55. Jump Game

Solution: #Greedy

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int edge = 0;  // 最大边界
        int n = nums.size();
        for(int i = 0; i < nums.size(); i++){
            if(edge < i) return false;  // 够不着下一个Index的情况
            /** 贪心维护最大边界 **/
            edge = max(edge, i + nums[i]); 
        }
        return true;
    }
};

Solution: 将上面的过程进行反推

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int goal = nums.size() - 1;
        for(int i = nums.size() - 2; i >= 0; i--){
            /** 不断放缩可以达到边界的起点 **/
            if(i + nums[i] >= goal) goal = i;
        }
        return goal == 0;  // 判断最后放缩到的起点是否index = 0；
    }
};

45. Jump Game II

这道题真的蛮有意思的，之前手撕出来了，时隔一段时间又来做又A不出来了…还是贪心的思路，贪心的选择最大边界，不过要维护一个当前边界和跳跃次数

class Solution {
public:
    int jump(vector<int>& nums) {
        int cnt = 0;  // 计数
        int end = 0;   // 当前边界
        int farthest = 0;   // 下一步可以达到的最远位置
        int goal = nums.size() - 1;  // 目标位置
        for(int i = 0; i < nums.size() - 1; i++){
            farthest = max(farthest, i + nums[i]);   // 计算当前能跳到的最大位置
            if(i == end){   // 到达当前边界，必须增加跳跃次数
                cnt++;
                end = farthest;
                if(end >= goal) break;
            }
        }
        return cnt;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int cnt = 0;
        int cur_end = 0;  // 当前边界
        int next_end = 0;   // 接下来的边界
        for(int i = 0; i < nums.size() -1; i++){
            next_end = max(next_end, i + nums[i]);  // 贪心选择接下来的边界
            if(i == cur_end){   // 循环到当前边界，需要更新接下来的边界
                cnt++;
                cur_end = next_end;
            }
        }
        return cnt;
    }
};

274. H-Index

Solution: #Brute Force

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int ans = 0;
        for(int i = 0; i < citations.size(); i++){
            int nominate = citations[i];  // 当前参照的元素
            if(nominate == 0) continue;  // 跳过引用次数为0的元素
            int cnt = 0;  // 记录大于等于参照元素引用的个数
            for(int j = 0; j < citations.size(); j++){
                if(citations[j] >= nominate) cnt++;
            }
            cnt = min(nominate, cnt);  // 取最小值
            ans = max(ans, cnt);   // 取最大值
        }
        return ans;
    }
};

Solution: #Sort

class Solution {
public:
    int hIndex(vector<int>& citations) {
        // 从小到大排列
        sort(citations.begin(), citations.end(), greater<int>());
        int ans = 0;
        for(int i = 0; i < citations.size(); i++){
            // 遍历找h-index
            if(citations[i] >= i + 1) ans = i + 1;
            else break;
        }
        return ans;
    }
};

380. Insert Delete GetRandom O(1)

Solution: #Simulation

class RandomizedSet {
public:
    unordered_map<int, int> mp;  // 元素 : 放入位置
    vector<int> vec;       // 存放元素
    RandomizedSet() {
        mp.clear();
        vec.clear();   // 初始化
    }
    
    bool insert(int val) {
        if(mp.count(val)) return false; // 已放入的情况
        vec.push_back(val);
        int idx = vec.size() - 1;  // 放入的index
        mp[val] = idx;   // 记录位置
        return true;
    }
    
    bool remove(int val) {
        if(!mp.count(val)) return false;  // 没放入的情况
        int idx = mp[val];   // 获取放入的位置
        int last_element = vec.back();  // 获取最后一个元素
        vec[idx] = last_element;  // 覆盖要删除的元素
        vec.pop_back();
        mp[last_element] = idx;  // 记录调整的元素位置
        mp.erase(val);  // 消除记录的位置
        return true;
    }
    
    int getRandom() {
        int idx = rand() % vec.size();  // 随机获取下标
        return vec[idx];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

238. Product of Array Except Self

Solution: #前缀数组和后缀数组

 class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre_product(n, 1);  // 前缀积
        int start = 1;
        for(int i = 1; i < n; i++){
            start *= nums[i - 1];
            pre_product[i] = start;
        }
        vector<int> nxt_product(n, 1); // 后缀积
        int end = 1;
        for(int i = n - 2; i >= 0; i--){
            end *= nums[i + 1];
            nxt_product[i] = end;
            
        }
        vector<int> ans(n, 0);
        for(int i = 0; i < n; i++){
            ans[i] = pre_product[i] * nxt_product[i];
        }
        return ans;
    }
};

优化后的代码如下:

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

134. Gas Station

纯暴力爆超时的做法(33/39)：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        vector<int> buff(n, 0);
        for(int i = 0; i < n; i++){
            buff[i] = gas[i] - cost[i];
        }
        vector<int> candidates;
        for(int i = 0; i < n; i++){
            if(buff[i] >= 0) candidates.push_back(i);
        }
        for(int j = 0; j < candidates.size(); j++){
            int idx = candidates[j];
            int sum = 0;
            bool flag = true;
            for(int i = idx; i < n; i++){
                sum += buff[i];
                if(sum < 0) flag = false;
            }
            for(int j = 0; j < idx; j++){
                if(!flag) continue;
                sum += buff[j];
                if(sum < 0) flag = false;
            }
            if(flag) return idx;
        }
        return -1;
    }
};

Solution: #Greedy

• 遍历每个加油站：
  • 对于每个加油站，计算出从当前加油站到下一个加油站所需的油量：curGas += (gas[i] - cost[i])。
  • 如果 curGas 变成了负值，意味着从当前加油站开始无法继续前进，因此将当前的起点更新为 i + 1，并且重置 curGas 为 0，尝试从下一个加油站作为起点重新开始。

这段代码的精妙之处在于：如果某一段的油量不足，前面的加油站不可能成为起点（因为从前一个加油站开始也不可能成功），所以可以跳过一段，直接从下一个加油站开始尝试。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int gasSum = 0;
        int costSum = 0;
        for(int i = 0; i < gas.size(); i++){
            gasSum += gas[i];
            costSum += cost[i];
        }
        if(gasSum < costSum) return -1;
        int curGas = 0;
        int start = 0;
        for(int i = 0; i < gas.size(); i++){
            curGas += (gas[i] - cost[i]);
            /*如果累加起来的gas总量小于0，那么这一段都不能作为起点*/
            if(curGas < 0){  
                curGas = 0;  // 重新从当前点出发
                start = i + 1; // 这里非常有数学意味
            }
        }
        return start;
    }
};

135. Candy

Solution: #Greedy，从左到右遍历局部最优，从右到左局部最优

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if(n <= 1) return n;
        vector<int> allo(n, 0);  // 每个元素的糖果分配情况
        allo[0] = 1;
        for(int i = 1; i < n; i++){ // 从左到右分配
            if(ratings[i] > ratings[i - 1]) allo[i] = allo[i -1] + 1;
            else allo[i] = 1;
        }
        for(int i = n - 2; i >= 0; i--){  // 从右到左分配
            if(ratings[i] > ratings[i + 1]){
                if(allo[i] <= allo[i + 1]) allo[i] = allo[i + 1] + 1;
            }
        }
        int sum = 0;
        for(auto x : allo) sum += x;
        return sum;
    }
};

42. Trapping Rain Water

Solution: #Monotonic Stack

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;   // 递增单调递减,存放index
        int sum = 0;
        for(int i = 0; i < height.size(); i++){
            while(!st.empty() && height[i] > height[st.top()]){
                int mid = height[st.top()];
                st.pop();
                if(!st.empty()){
                    int h = min(height[i], height[st.top()]) - mid;
                    int w = i - st.top() - 1;
                    sum += h * w;
                }
            }
            st.push(i);
        }
        return sum;
    }
};

Solution: #Two Pointers

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1; // 左右指针初始化
        int left_max = -1, right_max = -1; // 初始化左右最大高度
        int water = 0; // 用来累积水量
        
        // 双指针遍历，直到左右指针相遇
        while(l < r) {
            // 更新左右最大值
            left_max = max(left_max, height[l]);
            right_max = max(right_max, height[r]);
            
            // 根据左右最大值的大小来决定移动哪一边的指针
            if(left_max < right_max) {
                // 当前位置的水量 = 左侧最大值 - 当前柱子高度
                water += left_max - height[l++];
            } else {
                // 当前位置的水量 = 右侧最大值 - 当前柱子高度
                water += right_max - height[r--];
            }
        }
        return water; // 返回总的水量
    }
};

13. Roman to Integer

Solution: 暴力的做法，直接打表

class Solution {
public:
    unordered_map<char, int> mp = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000}
    };
    unordered_map<string, int> dmp = {
        {"IV", 4},
        {"IX", 9},
        {"XL", 40},
        {"XC", 90},
        {"CD", 400},
        {"CM", 900}
    };
    int romanToInt(string s) {
        int sum = 0;
        int i = 0;
        while(i + 1 < s.size()){
            char c1 = s[i];
            char c2 = s[i + 1];
            string tmp = {c1, c2};
            if(dmp.count(tmp)){
                sum += dmp[tmp];
                i += 2;
            }
            else{
                sum += mp[c1];
                i++;
            }
        }
        if(i == s.size() - 1){
            sum += mp[s[i]];
        }
        return sum;
    }
};

优化一下：

class Solution {
public:
    int romanToInt(string s) {
      unordered_map<char,int>m;
      m['I']=1;
      m['V']=5;
      m['X']=10;
      m['L']=50;
      m['C']=100;
      m['D']=500;
      m['M']=1000;
      int ans=0;
      for(int i=0;i<s.length();i++){
          if(m[s[i]]<m[s[i+1]]){
              ans-=m[s[i]];
          }
          else{
              ans+=m[s[i]];
          }
      }
      return ans;   
    }
};

12. Integer to Roman

Solution: #Hash Map, #Math

class Solution {
public:
    string intToRoman(int num) {
        int d[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string s[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        string ans = "";
        for(int i = 0 ; i < 13; i++){
            while(num >= d[i]){
                num -= d[i];
                ans += s[i];
            }
        }
        return ans;
    }
};

58. Length of Last Word

Solution: #STL

class Solution {
public:
    int lengthOfLastWord(string s) {
        istringstream iss(s);
        string words;
        vector<string> vec;
        while(iss >> words){
            vec.push_back(words);
        }
        return vec.back().size();
    }
};

Solution: 移动尾指针

class Solution {
public:
    int lengthOfLastWord(string s) {
        int p = s.size() - 1;
        int cnt = 0;
        /*定位到最后一个单词末尾*/ 
        while(p >= 0 && s[p] == ' '){
            p--;
        }
        /*计算最后一个单词长度*/
        while(p >= 0 && s[p] != ' '){
            p--;
            cnt++;
        }
        return cnt;
    }
};

Solution: #Flag

class Solution {
public:
    int lengthOfLastWord(string s) {
        int length = 0;
        bool counting = false; // 开始计数的标志
        for(int i = s.size() - 1; i >= 0; i--){
            if(s[i] != ' '){
                counting = true;
                length++;
            }
            else if(counting){  // 停止计数
                break;
            }
        }
        return length;
    }
};

14. Longest Common Prefix

Solution: #Greedy

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans = "";
        bool end = true;  // 比对结束的标志
        /*暴力枚举第一个字符串的所有前缀*/
        for(int i = 0; i < strs[0].size(); i++){
            /*对每个字符串进行暴力比对*/
            for(int j = 0; j < strs.size(); j++){
                if(strs[j][i] != strs[0][i]){
                    end = false;
                    break;
                }
            }
            if(end) ans += strs[0][i];
            else break;
        }
        return ans;
    }
};

Solution: #Sort, #Double Pointers

• 如果这些两个字符串有共同前缀，那么整个数组中的所有字符串也会有相同的前缀。因此，只需要比较数组中最小和最大字符串的前缀即可。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans = "";
        sort(strs.begin(), strs.end());
        int n = strs.size();
        string firstStr = strs[0];
        string lastStr = strs[n - 1];
        for(int i = 0; i < min(firstStr.size(), lastStr.size()); i++){
            if(firstStr[i] != lastStr[i]) break;
            ans += firstStr[i];
        }
        return ans;
    }
};

151. Reverse Words in a String

Solution: #STL

class Solution {
public:
    string reverseWords(string s) {
        string word;
        istringstream iss(s);
        vector<string> vec;
        while(iss >> word){
            vec.push_back(word);
        }
        string ans = "";
        for(int i = vec.size() - 1; i >= 0; i--){
            ans += vec[i];
            if(i != 0) ans += " ";
        }
        return ans;
    }
};

Solution: #Simulation

class Solution {
public:
    string reverseWords(string s) {
        string ans = "";
        string tmp = "";
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' '){   
                if(!tmp.empty()){  // 遍历完单词的情况
                    if(!ans.empty()) ans = tmp + " " + ans; // 不是第一个单词的情况
                    else ans = tmp;   // 是第一个单词的情况
                    tmp.clear();  
                }
            }
            else tmp += s[i];
        }
        if(!tmp.empty()){ // 还剩下最后一个单词
            if(!ans.empty()) ans = tmp + " " + ans;  // 不是第一个单词的情况
            else ans = tmp;  // 第一个单词的情况
        }
        return ans;
    }
};

Solution: #Two Pointers

class Solution {
public:
    string reverseWords(string s) {
        int slow = 0, fast = 0;
        reverse(s.begin(), s.end());  // 第一步：整体反转字符串
        bool wordStart = false;  // 标记是否正在处理一个单词

        // 使用 fast 指针遍历字符串
        for (fast = 0; fast < s.size(); fast++) {
            if (s[fast] != ' ') {  // 找到一个单词的开始
                if (wordStart && slow > 0) {
                    s[slow++] = ' ';  // 如果已经找到一个单词，且不是字符串开头，加空格分隔单词
                }
                int start = fast;
                while (fast < s.size() && s[fast] != ' ') {
                    s[slow++] = s[fast++];  // 把当前单词复制到新的位置
                }
                // 反转单词：把已复制的单词部分反转回来
                reverse(s.begin() + slow - (fast - start), s.begin() + slow);
                wordStart = true;  // 标记已经找到了一个单词
            }
        }

        // 调整字符串的大小，去掉多余的部分
        s.resize(slow);
        return s;
    }
};

6. Zigzag Conversion

Solution: #Simulation

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        unordered_map<int, vector<char>> mp;
        int r = 0;
        bool flop = false;  // 控制反转。初始化为false
        for(int i = 0; i < s.size(); i++){
            /*到达边界的时候，则需要反转*/
            if(r == 0 || r == numRows - 1) flop = !flop;
            mp[r].push_back(s[i]);
            if(flop) r++;
            else r--;
        }
        string ans = "";
        for(int i = 0; i < numRows; i++){
            for(auto c : mp[i]) ans += c;
        }
        return ans;
    }
};

优化后的代码：

class Solution {
public:
    string convert(string s, int numRows) {
        string ans;  
        vector<string> temp(numRows);
        int i = 0;
        while(i < s.size()){
            /*模拟从上到下的遍历过程*/
            for(int j = 0; j < numRows && i < s.size(); j++){
                temp[j] += s[i++];
            }
            /*模拟从下到上的过程*/
            for(int j = numRows - 2; j > 0 && i < s.size(); j--){
                temp[j] += s[i++];
            }
        }
        for(int i = 0; i < numRows; i++) ans += temp[i];
        return ans;
    }
};

28. Find the Index of the First Occurrence in a String

Solution: string类成员函数

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

正规的做法：#Tow Pointers

class Solution {
public:
    int strStr(string haystack, string needle) {
        int idx = -1;
        int j = 0;
        for(int i = 0; i < haystack.size(); i++){
            int start = i;
            while(start < haystack.size() && j < needle.size() && haystack[start] == needle[j]){
                start++;
                j++;
            }
            if(j == needle.size()) return i;
            else j = 0;
        }
        return -1;
    }
};

Solution：枚举子串进行比较

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(haystack.size() < needle.size()) return -1;
        for(int i = 0; i <= haystack.size() - needle.size(); i++){
            if(haystack.substr(i, needle.size()) == needle) return i;
        }
        return -1;
    }
};

68. Text Justification

Solution: #Greedy

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        vector<string> currentLine;  // 用来存储当前行的单词，直到该行的长度超过 maxWidth。
        int currentLength = 0; // 记录当前行中所有单词的总长度（不包括空格）
        for(const string& word : words){
            /* 判断当前行加上当前单词是否会超出 maxWidth */
            if(currentLength + word.length() + currentLine.size() > maxWidth){
                /* 计算当前行需要的空格*/
                int spaces = maxWidth - currentLength;
                /* 如果当前行只有一个单词，直接左对齐，空格填充右侧 */
                if(currentLine.size() == 1){
                    result.push_back(currentLine[0] + string(spaces, ' '));
                }
                else{
                    /* 均匀分配空格 */
                    int evenSpace = spaces / (currentLine.size() - 1);  // 每个空格应该有的基本数量
                    int extraSpace = spaces % (currentLine.size() - 1); // 剩余空格数量
                    string line = currentLine[0];
                    /* 分配空格 */
                    for(int i = 1; i < currentLine.size(); i++){
                        if(i <= extraSpace){
                            line += string(evenSpace + 1, ' ') + currentLine[i];
                        }
                        else{
                            line += string(evenSpace, ' ') + currentLine[i];
                        }
                    }
                    result.push_back(line);
                }
                /* 清空当前行的单词和长度，准备下一行 */
                currentLine.clear();
                currentLength = 0;
            }
            /* 将当前单词加入到当前行 */
            currentLine.push_back(word);
            currentLength += word.length();
        }
        /* 处理最后一行，左对齐 */
        string lastLine = "";
        for(int i = 0; i < currentLine.size(); i++){
            lastLine += currentLine[i];
            if(i < currentLine.size() - 1){
                lastLine += " ";
            }
        }
        lastLine += string(maxWidth - lastLine.length(), ' ');
        result.push_back(lastLine);
        return result;
    }
};

125. Valid Palindrome

Solution: #Simulation

class Solution {
public:
    string converString(string s){   // 清楚标点和大小写转换
        int gap = 'A' - 'a';
        string tmp = "";
        for(int i = 0; i < s.size(); i++){
            if('A' <= s[i] && s[i] <= 'Z'){
                tmp.push_back(s[i] - gap);
            }
            else if('a' <= s[i] && s[i] <= 'z' || '0' <= s[i] && s[i] <= '9'){
                tmp.push_back(s[i]);
            }
        }
        return tmp;
    }
    bool isPalindrome(string s) {
        string ss = converString(s);
        string tmp = ss;
        reverse(ss.begin(), ss.end()); 
        return tmp == ss;  // 反转后的字符串和反转前字符串比较
    }
};

Solution：#Tow Pointers, 使用双指针和类成员函数优化后的代码

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size(), l = 0, r = n - 1;
        while(l < r){
            while(l < r && !isalnum(s[l])) l++;
            while(l < r && !isalnum(s[r])) r--;
            if(tolower(s[l++]) != tolower(s[r--])) return false;
        }
        return true;
    }
};

392. Is Subsequence

Solution: #Tow Pointers

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size();
        int n = t.size();
        if(m == 0 && n == 0) return true;
        if(m > n) return false;
        int j = 0;
        for(int i = 0; i < n; i++){
            if(t[i] == s[j]) j++;
            if(j == m) return true;
        }
        return false;
    }
};

优化后的双指针写法：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int sptr = 0;
        int tptr = 0;
        while(sptr < s.size() && tptr < t.size()){
            if(s[sptr] == t[tptr]) sptr++;
            tptr++;
        }
        return sptr == s.size();
    }
};

Solution：#DP，也可以强行用动态规划来做

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();
        /* dp数组：当前两个字符串的子串所匹配的最大长度 */
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        return dp[n][m] == n;
    }
};

167. Two Sum II - Input Array Is Sorted

Solution: #Hash Table

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> ans;
        unordered_map<int, int> mp;
        for(int i = 0; i < numbers.size(); i++){
            /* 由小到大的index顺序 */
            if(mp.count(target - numbers[i]) && mp[target - numbers[i]] < i){
                ans.push_back(mp[target - numbers[i]] + 1);
                ans.push_back(i + 1);
            }
            /* 没找到匹配才建立映射，顺序不能在if执行之前*/
            mp[numbers[i]] = i;
        }
        return ans;
    }
};

更精简的写法：#Two Pointers

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int l = 0, r = n - 1;
        while(l < r){
            if(numbers[l] + numbers[r] == target) break;
            else if(numbers[l] + numbers[r] > target) r--;
            else l++;
        }
        return {l + 1, r + 1};
    }
};

11. Container With Most Water

Solution: #Two Pointers

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int ans = 0;
        while(l < r){
            int w = r - l;
            int h = min(height[l], height[r]);
            ans = max(ans, w * h);
            /* 优先移动高最小的边界 */
            if(height[l] < height[r]) l++;
            else r--;
        }
        return ans;
    }
};

15. 3Sum

Solution: #Two Pointers

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for(int i = 0; i < nums.size() - 2; i++){
            /*对目标元素进行去重*/
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1;
            int r = nums.size() - 1;
            while(l < r){
                if(nums[i] + nums[l] + nums[r] == 0){
                    ans.push_back({nums[i], nums[l], nums[r]});
                    /*对左右指针去重*/
                    while(l + 1 < r && nums[l + 1] == nums[l]) l++;
                    l++;
                    while(r - 1 > l && nums[r-1] == nums[r]) r--;
                    r--;
                }
                else if(nums[i] + nums[l] + nums[r] < 0) l++;
                else r--;
            }
        }
        return ans;
    }
};

209. Minimum Size Subarray Sum

Solution: #Sliding Window

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT_MAX;
        int start = 0;
        int sum = 0;
        for(int end = 0; end < nums.size(); end++){
            sum += nums[end];
            /* 当前和大于target则移动窗口左边界 */
            while(sum >= target){
                int subLength = end - start + 1;
                result = min(result, subLength);
                sum -= nums[start];
                start++;
            }
        }
        return result == INT_MAX ? 0 : result;
    }
};

3. Longest Substring Without Repeating Characters

Solution: #Sliding Window

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> st;
        int length = 0;
        int ans = 0;
        int start = 0;
        for(int end = 0; end < s.size(); end++){
            /* 果字符已存在于集合中，移动左边界 */
            while(st.count(s[end]) > 0){
                st.erase(s[start]);
                start++;
            }
            st.insert(s[end]);
            length = end - start + 1;
            ans = max(ans, length);
        }
        return ans;
    }
};

30. Substring with Concatenation of All Words

Solution: #Brute Force, #Sliding Window

class Solution {
public:
    bool checkSubstring(unordered_map<string, int> wordCount, string s, int wordLen){
        for(int i = 0; i < s.size(); i += wordLen){
            if(i + wordLen > s.size()) return false; // 确保不会越界
            string w = s.substr(i, wordLen);
            if(wordCount.find(w) != wordCount.end()){
                if(--wordCount[w] < 0) return false;
            }
            else return false;
        }
        return true;
    }
    
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        if(words.empty() || s.empty()) return ans;
        
        unordered_map<string, int> wordCount;
        for(auto x : words) wordCount[x]++;
        
        int wordLen = words[0].size();
        int subLen = words.size() * wordLen;
        
        // 如果子串长度超过原字符串长度，直接返回空结果
        if(subLen > s.size()) return ans;
        
        for(int i = 0; i <= s.size() - subLen; i++){
            if(checkSubstring(wordCount, s.substr(i, subLen), wordLen)) ans.push_back(i);
        }
        return ans;
    }
};

优化后的代码：#Sliding Window

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if (s.empty() || words.empty()) return result;
        
        int wordLength = words[0].size();
        int wordCount = words.size();
        int totalLength = wordLength * wordCount;
        
        if (totalLength > s.length()) return result;
        
        // 统计words中每个单词出现的次数
        unordered_map<string, int> wordFreq;
        for (const string& word : words) {
            wordFreq[word]++;
        }
        
        // 对每个可能的起始位置进行处理（由于单词长度可能大于1，需要考虑不同的偏移）
        for (int offset = 0; offset < wordLength; offset++) {
            // 对于每个偏移量，使用滑动窗口
            int left = offset;
            unordered_map<string, int> currentFreq;
            int count = 0; // 窗口内有效单词数量
            
            for (int right = offset; right <= s.length() - wordLength; right += wordLength) {
                string currentWord = s.substr(right, wordLength);
                
                // 如果当前单词不在words中，重置窗口
                if (wordFreq.find(currentWord) == wordFreq.end()) {
                    currentFreq.clear();
                    count = 0;
                    left = right + wordLength;
                    continue;
                }
                
                // 增加当前单词的计数
                currentFreq[currentWord]++;
                count++;
                
                // 如果当前单词出现次数过多，缩小窗口直到匹配
                while (currentFreq[currentWord] > wordFreq[currentWord]) {
                    string leftWord = s.substr(left, wordLength);
                    currentFreq[leftWord]--;
                    count--;
                    left += wordLength;
                }
                
                // 如果窗口大小正好等于所有单词的总数，找到一个匹配
                if (count == wordCount) {
                    result.push_back(left);
                    
                    // 移动窗口左边界，继续寻找下一个匹配
                    string leftWord = s.substr(left, wordLength);
                    currentFreq[leftWord]--;
                    count--;
                    left += wordLength;
                }
            }
        }
        
        return result;
    }
};

76. Minimum Window Substring

Solution: #Sliding Window

class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.size();
        int n = t.size();
        if(m < n) return "";
        unordered_map<char, int> charCount;
        for(char c : t) charCount[c]++; // 记录t中字符出现的次数
        int required = charCount.size();  // 需要匹配的字符种类
        int formed = 0;   // 已匹配成功的字符种类
        int left = 0;
        int right = 0;
        int minLen = INT_MAX;
        int start = 0;  // Start index of minimum window
        unordered_map<char, int> windowCount;
        while(right < s.size()){
            char c = s[right];
            windowCount[c]++;
            if(charCount.find(c) != charCount.end() && windowCount[c] == charCount[c]){
                formed++;    // 成功匹配完一类字符
            }
            /* 尝试缩小滑动窗口 */
            while(left <= right && formed == required){
                c = s[left];
                if(right - left + 1 < minLen){
                    minLen = right - left + 1;
                    start = left;
                }
                windowCount[c]--;
                if(charCount.find(c) != charCount.end() && windowCount[c] < charCount[c]){
                    formed--;   // 匹配次数减少，导致匹配字符类型数-1
                }
                left++;
            }
            right++;
        }
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

36. Valid Sudoku

Solution: #Simulation

class Solution {
public:
    /* 判断当前字符是否是1～9 */
    bool isValidChar(char c){
        if('1' <= c && c <= '9') return true;
        return false;
    }
    /* 检查 3x3 的格子是否有重复数字 */
    bool checkBox(vector<vector<char>>& board, int x, int y){
        set<char> st;
        for(int i = x; i < x + 3; i++){
            for(int j = y; j < y + 3; j++){
                char c = board[i][j];
                if(isValidChar(c)){
                    if(st.find(c) != st.end()) return false;
                    st.insert(c);
                }
            }
        }
        return true;
    }
    bool isValidSudoku(vector<vector<char>>& board) {
        set<char> row;
        set<char> col;
        for(int i = 0; i < 9; i++){   // 检查行
            row.clear();
            for(int j = 0; j < 9; j++){
                char c = board[i][j];
                if(isValidChar(c)){
                    if(row.find(c) != row.end()) return false;
                    row.insert(c);
                }
            }
        }
        for(int j = 0; j < 9; j++){  // 检查列
            col.clear();
            for(int i = 0; i < 9; i++){
                char c = board[i][j];
                if(isValidChar(c)){
                    if(col.find(c) != col.end()) return false;
                    col.insert(c);
                }
            }
        }
        for(int i = 0; i < 9; i += 3){  // 检查3x3的小格子
            for(int j = 0; j < 9; j += 3){
                if(!checkBox(board, i, j)) return false;
            }
        }
        return true;
    }
};

Solution: #Hash Table, 更加优化的方法，只用遍历一次数组，采用打表记录的方式

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // 使用3个9x9的布尔数组，分别记录行、列和方格中数字的出现情况
        bool row[9][9] = {false};  // row[i][j]表示第i行是否出现数字j+1
        bool col[9][9] = {false};  // col[i][j]表示第i列是否出现数字j+1
        bool box[9][9] = {false};  // box[i][j]表示第i个方格是否出现数字j+1
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                
                int num = board[i][j] - '1';  // 将字符转为0-8的索引
                int box_index = (i / 3) * 3 + j / 3;  // 计算当前位置属于哪个3x3方格
                
                // 检查当前数字在行、列、方格中是否已经出现过
                if (row[i][num] || col[j][num] || box[box_index][num]) {
                    return false;
                }
                
                // 标记数字已出现
                row[i][num] = true;
                col[j][num] = true;
                box[box_index][num] = true;
            }
        }
        
        return true;
    }
};

54. Spiral Matrix

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty()) return ans;
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0, right = n - 1, top = 0, bottom = m - 1;  // 设置边界
        while(left <= right && top <= bottom){ 
            for(int j = left; j <= right; j++) ans.push_back(matrix[top][j]);
            top++;
            for(int i = top; i <= bottom; i++) ans.push_back(matrix[i][right]);
            right--;
            if(top <= bottom){  // 从右到左（需要检查top <= bottom）
                for(int j = right; j >= left; j--) ans.push_back(matrix[bottom][j]);
                bottom--;
            }
            if(left <= right){   // 从下到上（需要检查left <= right）
                for(int i = bottom; i >= top; i--) ans.push_back(matrix[i][left]);
                left++;
            }
        }
        return ans;
    }
};

优化后的代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int m = matrix.size();      // line
        int n = matrix[0].size();   // column
        if(m == 0 || n == 0) return ans;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        while(left <= right && top <= bottom){
            for(int j = left; j <= right; j++) ans.push_back(matrix[top][j]);
            for(int i = top + 1; i <= bottom; i++) ans.push_back(matrix[i][right]);
            if(top < bottom && left < right){
                for(int j = right - 1; j > left; j--) ans.push_back(matrix[bottom][j]);
                for(int i = bottom; i > top; i--) ans.push_back(matrix[i][left]);
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        return ans;

    }
};

48. Rotate Image

Solution: #Queue，开一个队列把所有数装进来…

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        queue<int> que;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                que.push(matrix[i][j]);
            }
        }
        for(int j = n - 1; j >= 0; j--){
            for(int i = 0; i < n; i++){
                matrix[i][j] = que.front();
                que.pop();
            }
        }
        return;
    }
};

优化后的方案，不用开辟新的空间。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 先转置
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // 再反转
        for(int i = 0; i < n; i++){
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

73. Set Matrix Zeroes

Solution: #Brute Force

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

优化后的方法：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool firstRowZero = false, firstColZero = false;
        // 记录第一列是否有0
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0) firstColZero = true;
        }
        // 记录第一行是否有0
        for(int j = 0; j < n; j++){
            if(matrix[0][j] == 0) firstRowZero = true;
        }
        // 遍历整个矩阵，用第一行和第一列记录 0
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if(firstRowZero){
            for(int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if(firstColZero){
            for(int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
};

289. Game of Life

Solution: #Brute Force，对每一个点逐一检查

class Solution {
public:
    bool Alive(vector<vector<int>>& board, int x, int y){
        int bottom = board.size() - 1;
        int right = board[0].size() - 1;
        int cnt = 0;
        for(int i = x - 1; i <= x + 1; i++){
            for(int j = y - 1; j <= y + 1; j++){
                if(i >= 0 && i <= bottom && j >= 0 && j <= right){
                    if(i == x && j == y) continue;
                    else if(board[i][j] == 1) cnt++; 
                }
            }
        }
        bool curAlive = (board[x][y] == 1 ? true : false);
        if(curAlive && cnt < 2) return false;
        else if(curAlive && (cnt == 2 || cnt == 3)) return true;
        else if(curAlive && cnt >= 3) return false;
        else if(!curAlive && cnt == 3) return true;
        else return false;
    }
    void gameOfLife(vector<vector<int>>& board) {
        vector<vector<int>> tmp = board;
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(Alive(board, i, j)) tmp[i][j] = 1;
                else tmp[i][j] = 0;
            }
        }
        board = tmp;
        return;
    }
};

优化后的方法：

• -1 表示 活细胞变死（即原本是 1，但根据规则变成0）
• 2 表示 死细胞变活（即原本是 0，但根据规则变成1）。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        vector<int> directions = {-1, 0, 1}; // 方向数组，表示相邻八个方向的移动
        // 遍历计算每个细胞的状态
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int liveNeighbors = 0;
                for(int dx : directions){
                    for(int dy : directions){
                        if(dx == 0 && dy == 0) continue;  // 跳过自身
                        int ni = i + dx, nj = j + dy;
                        // 原地修改，注意找活细胞要用绝对值
                        if(ni >= 0 && ni < m && nj >= 0 && nj < n && abs(board[ni][nj]) == 1){
                            liveNeighbors++;
                        }
                    }
                }
                if(board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)){
                    board[i][j] = -1;     // 1 -> 0
                }
                else if(board[i][j] == 0 && liveNeighbors == 3){
                    board[i][j] = 2;    // 0 -> 1
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == -1) board[i][j] = 0;
                else if(board[i][j] == 2) board[i][j] = 1;
            }
        }
    }
};

383. Ransom Note

Solution: #Hash Table

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mp;  // 统计magazine中字符出现次数
        for(char c : magazine){
            mp[c]++;
        }
        for(char c : ransomNote){
            if(mp.find(c) == mp.end()) return false; // 字符不存在
            else{
                if(--mp[c] < 0) return false;  // 字符不够用
            }
        }
        return true;
    }
};

205. Isomorphic Strings

Solution: #Hash Table

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m = s.size(), n = t.size();
        if(m != n) return false;
        unordered_map<int, int> mp;
        set<char> st;              // 记录已经被map的字符
        for(int i = 0; i < m; i++){
            if(mp.find(s[i]) != mp.end()){        // 如果有记录
                if(mp[s[i]] != t[i]) return false;
            }
            else{      // 没有记录的情况
                if(st.find(t[i]) != st.end()) return false;
                else{
                    mp[s[i]] = t[i];
                    st.insert(t[i]);
                }
            }
        }
        return true;
    }
};

优化过的代码：

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> mp;
        for(int i = 0; i < s.size(); i++){
            char sc = s[i];
            char tc = t[i];
            if(mp.count(sc)){   // 映射不正确
                if(mp[sc] != tc) return false;
            }
            else{
                for(auto pair : mp){    // 检查是否映射冲突
                    if(pair.second == tc) return false;
                }
                mp[sc] = tc;
            }
        }
        return true;
    }
};

290. Word Pattern

Solution:# Hash Table

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> mp;
        vector<string> words;
        string tmp;
        istringstream iss(s);
        while(iss >> tmp){
            words.push_back(tmp);
        }
        if(pattern.size() != words.size()) return false;   // 比对数量不对等
        for(int i = 0; i < pattern.size(); i++){
            char pc = pattern[i];
            if(mp.count(pc)){
                if(mp[pc] != words[i]) return false;
            }
            else{
                for(pair str : mp){  // 检查是否有冲突映射
                    if(str.second == words[i]) return false;
                }
                mp[pc] = words[i];
            }
        }
        return true;
    }
};

242. Valid Anagram

Solution: #Sort

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

Solution: #Hash Table

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> mp;
        int kinds = 0;  // 记录字符种类
        for(auto c : t){
            if(mp.find(c) != mp.end()) mp[c]++;
            else{
                mp[c] = 1;
                kinds++;
            }
        }
        for(auto c : s){
            if(!mp.count(c)) return false;
            else{
                if(--mp[c] == 0) kinds--;  // 匹配完一种字符
                else if(mp[c] < 0) return false;
            }
        }
        return kinds == 0;
    }
};

Solution: #Hash Table，优化后的映射

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int>count(26, 0);
        for(auto c : s){
            count[c - 'a']++;
        }
        for(auto c : t){
            count[c - 'a']--;
        }
        for(auto num : count){
            if(num != 0) return false;
        }
        return true;
    }
};

49. Group Anagrams

Solution: #Hash Table, #Sort

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string, vector<int>> ump;
        for(int i = 0; i < strs.size(); i++){
            string tmp = strs[i];
            sort(tmp.begin(), tmp.end());    // sort调整顺序
            ump[tmp].push_back(i);
        }
        for(auto it : ump){
            vector<string> vec;
            for(auto idx : it.second){
                vec.push_back(strs[idx]);
            }
            ans.push_back(vec);
        }
        return ans;
    }
};

优化后的代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for(auto s : strs){
            string t = s;
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> ans;
        for(auto p : mp){
            ans.push_back(p.second);
        }
        return ans;
    }
};

手搓哈希映射的方法：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> ans;
        for(auto s : strs){
            array<int, 26> count = {0};
            for(char c : s){
                count[c - 'a']++;
            }
            string key;
            for(int num : count){
                key += to_string(num) + "#";  // 避免哈希冲突
            }
            ans[key].push_back(s);
        }
        vector<vector<string>> result;
        for(auto entry : ans){
            result.push_back(entry.second);
        }
        return result;
    }
};

1. Two Sum

Solution: #Hash Table

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;   // value : index
        for(int i = 0; i < nums.size(); i++){
            if(mp.count(target - nums[i])) return {mp[target - nums[i]], i};
            else mp[nums[i]] = i;
        }
        return {};
    }
};

Solution: #Two Pointers

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> v;
        for(int i = 0; i < nums.size(); i++) v.push_back({nums[i], i});  // 记录初始位置
        sort(v.begin(), v.end());
        int i = 0, j = nums.size() - 1;   // 双指针初始化
        while(i < j){
            if(v[i].first + v[j].first == target) return {v[i].second, v[j].second};
            else if(v[i].first + v[j].first > target) j--;
            else i++;
        }
        return {};
    }
};

202. Happy Number

class Solution {
public:
    int calc(int n){    // 计算每个digit的平方和
        string tmp = to_string(n);
        int sum = 0;
        for(int i = 0; i < tmp.size(); i++){
            sum += (tmp[i] - '0') * (tmp[i] - '0');
        }
        return sum;
    }
    bool isHappy(int n) {
        set<int> st;   // 检查是否有loop出现
        while(calc(n) != 1){
            if(st.count(calc(n))) return false;
            else{
                st.insert(calc(n));
                n = calc(n);
            }
        }
        return true;
    }
};

优化后的方法，使用快慢指针。#Tow Pointers

class Solution {
public:
    int calc(int n){  // 更优质的计算
        int sum = 0;
        while(n){
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n;
        int fast = n;
        do{                    // 快慢指针
            slow = calc(slow);
            fast = calc(calc(fast));
            if(fast == 1) return true;
        }while(slow != fast);
        return false;
    }
};

219. Contains Duplicate II

Solution: #Hash Table

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> mp;   // value : 最近一次出现的index
        for(int i = 0; i < nums.size(); i++){
            if(mp.count(nums[i])){
                if(i - mp[nums[i]] <= k) return true;
                else mp[nums[i]] = i;
            }
            else{
                mp[nums[i]] = i;
            }
        }
        return false;
    }
};

优化的解法#Sliding Window

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> window;   // 维护滑动窗口内的元素
        for(int i = 0; i < nums.size(); i++){
            if(window.count(nums[i])) return true;
            window.insert(nums[i]);
            if(window.size() > k) window.erase(nums[i - k]);   // 维护窗口大小
        }
        return false;
    }
};

128. Longest Consecutive Sequence

Solution: #Hash Table

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> st;
        for(auto x : nums) st.insert(x);  // 去重
        int result = 0;
        while(!st.empty()){
            int x = *st.begin();  // 取第一个元素
            int cnt = 1;
            int left = x - 1;
            int right = x + 1;
            while(st.count(left)){  // 向左寻找连续序列
                st.erase(left);
                left--;
                cnt++;
            }
            while(st.count(right)){ // 向右寻找连续序列
                st.erase(right);
                right++;
                cnt++;
            }
            result = max(result, cnt);
            st.erase(x);
        }
        return result;
    }
};

优化后的代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) return 0;
        unordered_set<int> st(nums.begin(), nums.end()); // 用 HashSet 存储去重后的元素
        int result = 0;
        for(int x : st){
            if(!st.count(x - 1)){  // 没有向左连续的情况，那么直接向右找连续元素
                int currNum = x;
                int cnt = 1;
                while(st.count(currNum + 1)){
                    currNum++;
                    cnt++;
                }
                result = max(result, cnt);
            }
        }
        return result;
    }
};

228. Summary Ranges

Solution: #Simulation

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
    vector<string> ans;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int start = nums[i];
        // 找出连续区间的结束位置
        while (i + 1 < n && nums[i + 1] == nums[i] + 1) i++;
        
        if (start == nums[i])
            ans.push_back(to_string(start));
        else
            ans.push_back(to_string(start) + "->" + to_string(nums[i]));
    }
    return ans;
}
};

56. Merge Intervals

Solution: #Greedy, #Sort

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

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> ans;
        if (intervals.empty()) return ans;
        ans.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] > ans.back()[1]) {  // 不合并区间
                ans.push_back(intervals[i]);
            } else {    // 合并区间的情况
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);
            }
        }
        return ans;
    }
};

可以稍微优化一下

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 1. 使用lambda表达式简化排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];  // 只需按起始点排序即可
        });
        
        vector<vector<int>> result;
        if (intervals.empty()) return result;
        
        result.push_back(intervals[0]);
        
        for (int i = 1; i < intervals.size(); i++) {
            // 检查是否可以合并
            if (intervals[i][0] <= result.back()[1]) {
                // 合并区间
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                // 添加新区间
                result.push_back(intervals[i]);
            }
        }
        
        return result;
    }
};

57. Insert Interval

Solution: #Greedy

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(),[](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
        ans.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++){
            int start = intervals[i][0];
            int end = intervals[i][1];
            if(start > ans.back()[1]) ans.push_back(intervals[i]);
            else ans.back()[1] = max(ans.back()[1], end);
        }
        return ans;
    }
};

优化后的代码：#Simulation

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        int i = 0;
        vector<vector<int>> ans;
        while(i < n && intervals[i][1] < newInterval[0]) ans.push_back(intervals[i++]);
        while(i < n && newInterval[1] >= intervals[i][0]){
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        ans.push_back(newInterval);
        while(i < n) ans.push_back(intervals[i++]);
        return ans;
    }
};

452. Minimum Number of Arrows to Burst Balloons

Solution: #Greedy

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size() == 0) return 0;
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b){
            return a[0] < b[0];
        });
        int ans = 1;
        int end = points[0][1];
        for(int i = 1; i < points.size(); i++){
            if(points[i][0] > end){
                end = points[i][1];
                ans++;
            }
            else{
                end = min(end, points[i][1]);
            }
        }
        return ans;
    }
};

20. Valid Parentheses

Solution: #Stack

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

Solution: #Hash Table

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

71. Simplify Path

Solution: #Stack

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> st;
        int i = 0;
        while(i < path.size()){
            if(path[i] == '/'){
                i++;
                continue;
            }
            string word;
            while(i < path.size() && path[i] != '/'){
                word += path[i];
                i++;
            }
            if(word == "."){
                i++;
                continue;
            }
            else if(word == ".."){
                if(!st.empty()) st.pop();
                i++;
                continue;
            }
            else{
                st.push(word);
                i++;
            }
        }
        string ans;
        if(st.empty()) return "/";
        while(!st.empty()){
            ans = "/" + st.top() + ans;
            st.pop();
        }
        return ans;
    }
};

优化后的代码：

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> st;
        int i = 0, n = path.size();

        while (i < n) {
            while (i < n && path[i] == '/') i++; // 跳过 '/'
            string word;
            while (i < n && path[i] != '/') word += path[i++];
            
            if (word == "." || word.empty()) continue;
            if (word == "..") {
                if (!st.empty()) st.pop_back();
            } else {
                st.push_back(word);
            }
        }

        string ans = "/";
        for (int i = 0; i < st.size(); i++) {
            if (i > 0) ans += "/";
            ans += st[i];
        }
        return ans;
    }
};

155. Min Stack

Solution: #Simulation

class MinStack {
public:
    vector<int> vec;
    MinStack() {
        vec.clear();
    }
    
    void push(int val) {
        vec.push_back(val);
    }
    
    void pop() {
        vec.pop_back();
    }
    
    int top() {
        return vec.back();
    }
    
    int getMin() {
        int minn = INT_MAX;
        for(auto x : vec) minn = min(minn, x);
        return minn;
    }
};

优化后的代码：

class MinStack {
public:
    stack<pair<int, int>> st;  // 放入元素 ： 当前栈的最小元素
    MinStack() {
        
    }
    
    void push(int val) {
        if(st.empty()) st.push({val, val});
        else st.push({val, min(st.top().second, val)}); // 维护栈顶的最小值
    }
    
    void pop() {
        st.pop();
    }
    
    int top() {
        return st.top().first;
    }
    
    int getMin() {
        return st.top().second;
    }
};

150. Evaluate Reverse Polish Notation

Solution: #Stack

class Solution {
public:
    stack<int> stNum;
    int evalRPN(vector<string>& tokens) {
        for(auto s : tokens){
            if(s[0] >= '0' && s[0] <= '9'){
                int num = stoi(s);
                stNum.push(num);
            }
            else if(s[0] == '-' && s[1] >= '0' && s[1] <= '9'){
                int num = stoi(s.substr(1));
                stNum.push(-1 * num);
            }
            else{
                int a, b;
                if(!stNum.empty()){
                    b = stNum.top();
                    stNum.pop();
                }
                if(!stNum.empty()){
                    a = stNum.top();
                    stNum.pop();
                }
                if(s == "+") stNum.push(a + b);
                else if(s == "-") stNum.push(a - b);
                else if(s == "*") stNum.push(a * b);
                else{
                    if(b != 0) stNum.push(a / b);
                }
            }
        }
        return stNum.top();
    }
};

优化后的代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(string c : tokens){
            if(c == "+"|| c == "-" || c == "*" || c == "/"){
                int nums2 = st.top(); st.pop();
                int nums1 = st.top(); st.pop();
                if (c == "+") st.push(nums1 + nums2);
                else if (c == "-") st.push(nums1 - nums2);
                else if (c == "*") st.push(nums1 * nums2);
                else if (c == "/") st.push(nums1 / nums2);
            }
            else st.push(stoi(c));
        }
        return st.top();
    }
};

224. Basic Calculator

Solution: #Stack, #Simulation

class Solution {
public:
    int calculate(string s) {
        int ans = 0;       // 结果变量，存储当前计算的总和
        int num = 0;       // 记录当前解析的数字
        int sign = 1;      // 记录当前的符号，初始为正（1 代表正，-1 代表负）
        stack<int> st;     // 栈用于存储括号内的符号作用
        st.push(sign);     // 初始化栈，默认作用域符号为 1（正号）

        // 遍历字符串中的每个字符
        for(const char c : s){
            // 如果是数字，构造当前数字（支持多位数）
            if(isdigit(c)){
                num = num * 10 + (c - '0');
            }
            // 遇到左括号 '('，表示进入新的作用域，将当前作用域的 sign 存入栈
            else if(c == '(') {
                st.push(sign);
            }
            // 遇到右括号 ')'，表示离开当前作用域，弹出栈顶的 sign
            else if(c == ')') {
                st.pop();
            }
            // 遇到加号 '+' 或减号 '-'，进行计算
            else if(c == '+' || c == '-'){
                ans += sign * num;  // 先计算前面解析的数字并累加到 ans
                sign = (c == '+' ? 1 : -1) * st.top(); // 更新当前符号，受括号作用域影响
                num = 0; // 归零，准备解析下一个数字
            }
        }

        // 处理最后一个数字
        return ans + sign * num;
    }
};

使用两个栈的方法：

class Solution {
public:
    int calculate(string s) {
        stack<int> numStack;
        stack<int> opStack; // 1 代表 '+', -1 代表 '-'
        int num = 0, sign = 1, ans = 0;      
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                ans += sign * num; // 计算当前数字
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                numStack.push(ans);
                opStack.push(sign);
                ans = 0;
                sign = 1;
            } else if (c == ')') {
                ans += sign * num; // 计算括号内的最后一个数
                num = 0;
                ans *= opStack.top(); opStack.pop(); // 处理括号前的符号
                ans += numStack.top(); numStack.pop(); // 叠加之前的计算结果
            }
        }
        return ans + sign * num; // 计算最后一个数
    }
};

141. Linked List Cycle

Solution: #Two Pointers

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr) return false;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

Solution: #Hash Table

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> st;
        ListNode* cur = head;
        while(cur != nullptr){
            if(st.find(cur) != st.end()) return true;
            st.insert(cur);
            cur = cur->next;
        }
        return false;
    }
};

2. Add Two Numbers

Solution: #Simulation

/**
 * 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:
    // 递归获取链表长度
    int listLength(ListNode* head){
        if(head == nullptr) return 0;
        return 1 + listLength(head->next);
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int size1 = listLength(l1);
        int size2 = listLength(l2);
        if(size1 < size2) swap(l1, l2);  // 保证l1是最长的链表;
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        int carry = 0;
        int cursum;
        ListNode* last = l1;
        while(cur2 != nullptr){
            cursum = cur1->val + cur2->val + carry;
            cur1->val = cursum % 10;
            carry = cursum / 10;
            last = cur1;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        while(cur1 != nullptr){
            cursum = cur1->val + carry;
            cur1->val = cursum % 10;
            carry = cursum / 10;
            last = cur1;
            cur1 = cur1->next;
        }
        if(carry > 0) last->next = new ListNode(carry);
        return l1;
    }
};

优化后的方法：使用虚拟头节点

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        ListNode* cur = dummy;
        int carry = 0;
        while(p1 != nullptr || p2 != nullptr || carry != 0){
            int x = (p1 != nullptr) ? p1->val : 0;
            int y = (p2 != nullptr) ? p2->val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if(p1 != nullptr) p1 = p1->next;
            if(p2 != nullptr) p2 = p2->next;
        }
        return dummy->next;
    }
};

21. Merge Two Sorted Lists

Solution: #Simulation

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(list1 != nullptr || list2 != nullptr){
            if(list1 != nullptr && list2 != nullptr){
                if(list1->val < list2->val){
                    cur->next = list1;
                    list1 = list1->next;
                }
                else{
                    cur->next = list2;
                    list2 = list2->next;
                }
                cur = cur->next;
            }
            else{
                while(list1 != nullptr){
                    cur->next = list1;
                    list1 = list1->next;
                    cur = cur->next;
                }
                while(list2 != nullptr){
                    cur->next = list2;
                    list2 = list2->next;
                    cur = cur->next;
                }
            }
        }
        return dummy->next;
    }
};

优化后的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(list1 && list2){
            if(list1->val < list2->val){
                cur->next =list1;
                list1 = list1->next;
            }
            else{
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        if(list1) cur->next = list1;
        if(list2) cur->next = list2;
        return dummy->next;
    }
};

138. Copy List with Random Pointer

Solution: #Hash Table

/*
// 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) {
        if(!head) return nullptr;
        unordered_map<Node*, Node*> mp; // 旧节点->新节点
        Node* cur = head;
        // 第一遍：创建所有新节点，并建立映射关系
        while(cur){
            mp[cur] = new Node(cur->val);
            cur = cur->next;
        }
        // 第二遍：复制 next 和 random 指针
        cur = head;
        while(cur){
            mp[cur]->next = mp[cur->next];
            mp[cur]->random = mp[cur->random];
            cur = cur->next;
        }
        return mp[head];
    }
};

• 浅拷贝 (Shallow Copy)：仅复制对象的指针，而不是内容。例如，如果 mp[cur] = cur; 这样做，新的链表仍然会指向原来的 random 节点。
• 深拷贝 (Deep Copy)：复制数据本身，确保新旧对象互不影响。本代码中的 new Node(cur->val)就是深拷贝的关键。

优化后的代码：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        // Step 1: 复制节点并插入到原链表
        Node* cur = head;
        while (cur) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }

        // Step 2: 复制 random 指针
        cur = head;
        while (cur) {
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }

        // Step 3: 拆分新旧链表
        Node* newHead = head->next;
        cur = head;
        Node* copyCur = newHead;
        while (cur) {
            cur->next = cur->next->next;
            if (copyCur->next) {
                copyCur->next = copyCur->next->next;
            }
            cur = cur->next;
            copyCur = copyCur->next;
        }

        return newHead;
    }
};

92. Reverse Linked List II

Solution: #Stack

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        if(!head || left == right) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;
        for(int i = 1; i < left; i++) cur = cur->next;
        ListNode* pre = cur;
        cur = cur->next;
        stack<ListNode*> st;
        for(int i = 0; i < right - left + 1; i++){
            st.push(cur);
            cur = cur->next;
        }
        while(!st.empty()){
            pre->next = st.top();
            pre = pre->next;
            st.pop();
        }
        pre->next = cur;
        return dummy->next;
    }
};

优化后的方法，Solution：#Simulation

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        if(!head || left == right) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        for(int i = 1; i < left; i++) pre = pre->next;
        ListNode* cur = pre->next;
        /*反转区间的节点*/
        for(int i = 0; i < right - left; i++){
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        return dummy->next;
    }
};

25. Reverse Nodes in k-Group

Solution: #Stack

/**
 * 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:
    int getLength(ListNode* head){
        if(head == nullptr) return 0;
        return 1 + getLength(head->next);
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = getLength(head);
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        stack<ListNode*> st;
        for(int i = 0; i + k <= n; i += k){
            for(int j = 0; j < k; j++){
                st.push(head);
                head = head->next;
            }
            while(!st.empty()){
                cur->next = st.top();
                st.pop();
                cur = cur->next;
            }
        }
        cur->next = head;
        return dummy->next;
    }
};

Solution: #Recursion, #Two Pointers

/**
 * 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* cur = head;
        for(int i = 0; i < k; i++){
            if(!cur) return head;  // 剩余节点不足 k 个，直接返回
            cur = cur->next;
        }
        ListNode* pre = nullptr;
        cur = head;
        for(int i = 0; i < k; i++){
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        head->next = reverseKGroup(cur, k); // 反转后，head 变成 k 组的最后一个节点
        return pre;
    }
};

与栈的方法类似，还可以使用双端队列deque

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        deque<ListNode*> dq;
        ListNode dummy(0);
        ListNode* cur = &dummy;

        while (head) {
            dq.push_back(head);
            head = head->next;
            if (dq.size() == k) {
                while (!dq.empty()) {
                    cur->next = dq.back();
                    dq.pop_back();
                    cur = cur->next;
                }
            }
        }
        
        while (!dq.empty()) {
            cur->next = dq.front();
            dq.pop_front();
            cur = cur->next;
        }

        cur->next = nullptr;
        return dummy.next;
    }
};

19. Remove Nth Node From End of List

Solution: #Simulation

/**
 * 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:
    int getLength(ListNode* head){
        if(head == nullptr) return 0;
        return 1 + getLength(head->next);
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len = getLength(head);
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = head;
        ListNode* prev = dummy;
        for(int i = 0; i < len - n; i++){
            prev = prev->next;
            cur = cur->next;
        }
        prev->next = cur->next;
        delete cur;
        return dummy->next;
    }
};

优化后的方法：使用快慢指针 #Two Pointers

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        for(int i = 0; i <= n; i++) fast = fast->next;
        while(fast != nullptr){
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;
        delete toDelete;
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

82. Remove Duplicates from Sorted List II

Solution: #Deque

/**
 * 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* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
        deque<ListNode*> que;
        ListNode* cur = head;
        while(cur){
            if(que.empty()){
                que.push_back(cur);
                cur = cur->next;
            }
            else{
                if(cur->val == que.back()->val){
                    while(cur && cur->val == que.back()->val) cur = cur->next;
                    que.pop_back();
                }
                else{
                    que.push_back(cur);
                    cur = cur->next;
                }
            }
        }
        ListNode* dummy = new ListNode(0);
        cur = dummy;
        while(!que.empty()){
            cur->next = que.front();
            que.pop_front();
            cur = cur->next;
        }
        cur->next = nullptr;  // 重塑指针，不然无法AC
        return dummy->next;
    }
};

更优化的方法：#Two Pointers

/**
 * 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* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* prev = dummy;
        ListNode* cur = head;
        while(cur){
            bool isDuplicate = false;
            while(cur->next && cur->val == cur->next->val){
                isDuplicate = true;
                cur = cur->next;
            }
            if(isDuplicate){
                prev->next = cur->next;
            }
            else{
                prev = cur;
            }
            cur = cur->next;
        }
        return dummy->next;
    }
};

61. Rotate List

Solution: #Deque

/**
 * 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:
    int getLength(ListNode* head){
        if(head == nullptr) return 0;
        return 1 + getLength(head->next);
    }
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || !head->next) return head; 
        int n = getLength(head);
        k = k % n;
        deque<ListNode*> que;
        ListNode* cur = head;
        while(cur){
            que.push_back(cur);
            cur = cur->next;
        }
        while(k--){
            ListNode* tmp = que.back();
            que.push_front(tmp);
            que.pop_back();
        }
        ListNode* dummy = new ListNode(0);
        cur = dummy;
        while(!que.empty()){
            cur->next = que.front();
            cur = cur->next;
            que.pop_front();
        }
        cur->next = nullptr;
        return dummy->next;
    }
};

优化的方法：计算长度 + 直接拼接

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || !head->next || k == 0) return head;
        int n = 1;
        ListNode* tail = head;
        while(tail->next){
            tail = tail->next;
            n++;
        }
        k = k % n;
        if(k == 0) return head;
        tail->next = head;  // 让链表变成一个环
        ListNode* newTail = head;
        for(int i = 0; i < n - k - 1; i++){
            newTail = newTail->next;  // 找到链表新的断点
        }
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        return newHead;
    }
};

使用快慢指针，#Two Pointers

/**
 * 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* rotateRight(ListNode* head, int k) {
        if(!head || !head->next || k == 0) return head;
        int n = 1;
        ListNode* tail = head;
        while(tail->next){
            tail = tail->next;
            n++;
        }
        k %= n;
        if(k == 0) return head;
        ListNode* fast = head; // 让fast先走k步
        for(int i = 0; i < k; i++) fast = fast->next;
        ListNode* slow = head; // slow和fast一起走
        while(fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* newHead = slow->next;
        slow->next = nullptr;
        fast->next = head;
        return newHead;

    }
};

86. Partition List

Solution: #Queue

/**
 * 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* partition(ListNode* head, int x) {
        if(!head) return head;
        queue<ListNode*> sml;
        queue<ListNode*> big;
        ListNode* cur = head;
        while(cur){
            if(cur->val < x) sml.push(cur);
            else big.push(cur);
            cur = cur->next;
        }
        ListNode* dummy = new ListNode(0);
        cur = dummy;
        while(!sml.empty()){
            cur->next = sml.front();
            cur = cur->next;
            sml.pop();
        }
        while(!big.empty()){
            cur->next = big.front();
            cur = cur->next;
            big.pop();
        }
        cur->next = nullptr;
        return dummy->next;
    }
};

优化后的方法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummy1 = new ListNode(0);
        ListNode* dummy2 = new ListNode(0);
        ListNode* ptr1 = dummy1;
        ListNode* ptr2 = dummy2;
        ListNode* cur = head;
        while(cur){
            if(cur->val < x){
                ptr1->next = cur;
                ptr1 = ptr1->next;
            }
            else{
                ptr2->next = cur;
                ptr2 = ptr2->next;
            }
            cur = cur->next;
        }
        ptr2->next = nullptr;
        ptr1->next = dummy2->next;
        return dummy1->next;
    }
};

146. LRU Cache

Solution: #list

class LRUCache {
private:
    int cap; // 缓存容量
    list<int> lruList; // 维护访问顺序，最近访问的在前
    unordered_map<int, pair<int, list<int>::iterator>> cache; // key -> {value, 在lruList中的位置}

public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1; // key 不存在

        // key 存在，移动到链表头部（表示最近使用）
        lruList.erase(cache[key].second);   // 先删除原来的位置
        lruList.push_front(key);            // 移动到前面
        cache[key].second = lruList.begin(); // 更新迭代器
        return cache[key].first;             // 返回值
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            // key 已存在，更新值，并移动到前面
            lruList.erase(cache[key].second);
            lruList.push_front(key);
            cache[key] = {value, lruList.begin()};
        } else {
            // key 不存在，检查是否超出容量
            if (cache.size() == cap) {
                int oldKey = lruList.back(); // 找到最久未使用的 key
                lruList.pop_back();          // 移除链表最后一个元素
                cache.erase(oldKey);         // 从哈希表中删除
            }
            // 插入新 key
            lruList.push_front(key);
            cache[key] = {value, lruList.begin()};
        }
    }
};

104. Maximum Depth of Binary Tree

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
       if(!root) return 0;
       return 1 + max(maxDepth(root->left), maxDepth(root->right)); 
    }
};

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int height = 0;
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            height++;
        }
        return height;
    }
};

100. Same Tree

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr) return true;
        else if(p == nullptr || q == nullptr) return false;
        else if(p -> val != q ->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que1;
        queue<TreeNode*> que2;
        que1.push(p);
        que2.push(q);
        while(!que1.empty() && !que2.empty()){
            auto node1 = que1.front();
            auto node2 = que2.front();
            que1.pop();
            que2.pop();
            if(node1 == nullptr || node2 == nullptr){
                if(node1 != node2) return false;
                continue;
            }
            if(node1->val != node2->val) return false;
            que1.push(node1->left);
            que1.push(node1->right);
            que2.push(node2->left);
            que2.push(node2->right);
        }
        return true;
    }
};

226. Invert Binary Tree

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

101. Symmetric Tree

Solution: Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool solve(TreeNode* l, TreeNode* r){
        if(!l && !r) return true;
        if(!l || !r) return false;
        if(l->val != r->val) return false;
        return solve(l->left, r->right) && solve(l->right, r->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return solve(root->left, root->right);
    }
};

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()){
            TreeNode* node1 = que.front();
            que.pop();
            TreeNode* node2 = que.front();
            que.pop();
            if(!node1 && !node2) continue;  // 都为空
            if(!node1 || !node2) return false; // 只有一个为空
            if(node1->val != node2->val) return false; // 值不相等
            que.push(node1->left);
            que.push(node2->right);
            que.push(node1->right);
            que.push(node2->left);
        }
        return true;
    }
};

105. Construct Binary Tree from Preorder and Inorder Traversal

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;   // 递归边界条件
        TreeNode* root = new TreeNode(preorder[0]);
        if(preorder.size() == 1 && inorder.size() == 1) return root;  // 边界条件
        vector<int> inleft;
        vector<int> inright;
        bool over = false;
        for(int i = 0; i < inorder.size(); i++){
            if(inorder[i] == root->val){
                over = true;
                continue;
            }
            else if(!over) inleft.push_back(inorder[i]);
            else inright.push_back(inorder[i]);
        }
        vector<int> preleft;
        vector<int> preright;
        int cnt = 0;
        for(int i = 1; i < preorder.size(); i++){
            if(cnt < inleft.size()){
                preleft.push_back(preorder[i]);
                cnt++;
            }
            else preright.push_back(preorder[i]);
        }
        root->left = buildTree(preleft, inleft);
        root->right = buildTree(preright, inright);
        return root;
    }
};

使用哈希表优化的递归解法

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inMap;
        // 将中序遍历的值与下标存储在哈希表中
        for (int i = 0; i < inorder.size(); i++) {
            inMap[inorder[i]] = i;
        }
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inMap);
    }
    
    TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, 
                           vector<int>& inorder, int inStart, int inEnd, 
                           unordered_map<int, int>& inMap) {
        if (preStart > preEnd || inStart > inEnd) {
            return nullptr;
        }
        
        // 前序遍历的第一个节点是根节点
        TreeNode* root = new TreeNode(preorder[preStart]);
        
        // 在中序遍历中找到根节点的位置
        int inRoot = inMap[root->val];
        // 计算左子树的节点数量
        int numsLeft = inRoot - inStart;
        
        // 递归构建左子树和右子树
        root->left = buildTreeHelper(preorder, preStart + 1, preStart + numsLeft, 
                                     inorder, inStart, inRoot - 1, inMap);
        root->right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd, 
                                      inorder, inRoot + 1, inEnd, inMap);
        
        return root;
    }
};

迭代解法（使用栈）

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;
        
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> st;
        st.push(root);
        
        int inorderIndex = 0;
        
        for (int i = 1; i < preorder.size(); i++) {
            TreeNode* curr = st.top();
            
            if (curr->val != inorder[inorderIndex]) {
                // 如果当前栈顶节点不等于中序遍历的当前节点
                // 说明当前前序遍历的节点是栈顶节点的左子节点
                curr->left = new TreeNode(preorder[i]);
                st.push(curr->left);
            } else {
                // 如果当前栈顶节点等于中序遍历的当前节点
                // 说明需要回溯到合适的父节点，然后添加右子节点
                while (!st.empty() && st.top()->val == inorder[inorderIndex]) {
                    curr = st.top();
                    st.pop();
                    inorderIndex++;
                }
                curr->right = new TreeNode(preorder[i]);
                st.push(curr->right);
            }
        }
        
        return root;
    }
};

使用索引而不是子数组的递归解法

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                  vector<int>& inorder, int inStart, int inEnd) {
        if (preStart > preEnd) return nullptr;
        
        // 前序遍历的第一个节点是根节点
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        
        // 在中序遍历中找到根节点的位置
        int rootIndex = inStart;
        while (inorder[rootIndex] != rootVal) rootIndex++;
        
        // 左子树的节点数量
        int leftSize = rootIndex - inStart;
        
        // 构建左子树和右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                         inorder, inStart, rootIndex - 1);
        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                          inorder, rootIndex + 1, inEnd);
        
        return root;
    }
};

106. Construct Binary Tree from Inorder and Postorder Traversal

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.empty()) return nullptr;
        int n = inorder.size();
        TreeNode* root = new TreeNode(postorder[n - 1]);
        vector<int> inleft;
        vector<int> inright;
        bool findRoot = false;
        unordered_set<int> ust;
        for(int i = 0; i < n; i++){
            if(!findRoot && inorder[i] != root->val){
                inleft.push_back(inorder[i]);
                ust.insert(inorder[i]);
            }
            else if(!findRoot) findRoot = true;
            else inright.push_back(inorder[i]);
        }
        vector<int> posleft;
        vector<int> posright;
        for(int i = 0; i < n - 1; i++){
            if(ust.find(postorder[i]) != ust.end()) posleft.push_back(postorder[i]);
            else posright.push_back(postorder[i]);
        }
        root->left = buildTree(inleft, posleft);
        root->right = buildTree(inright, posright);
        return root;
    }
};

简化的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* rec(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd){
        if(inStart > inEnd) return nullptr;
        TreeNode* root = new TreeNode(postorder[postEnd]);
        int index = inStart;
        while(inorder[index] != root->val) index++;   // 找到中序遍历左右子树划分位置
        int leftLen = index - inStart;       // 左子树长度
        root->left = rec(inorder, postorder, inStart, index - 1, postStart, postStart + leftLen - 1);
        root->right = rec(inorder, postorder, index + 1, inEnd, postStart + leftLen, postEnd - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return rec(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
};

Solution: #Iteration

• 入栈节点：表示当前树的右子树还没构建完。
• 出栈节点：表示右子树构建完成，需要转向左子树。

  class Solution {
  public:
      TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
          if (inorder.empty()) return nullptr;
  
          // 哈希表存储 inorder 中每个值的索引，O(1) 查询
          unordered_map<int, int> inMap;
          for (int i = 0; i < inorder.size(); i++) {
              inMap[inorder[i]] = i;
          }
  
          stack<TreeNode*> st;
          int postIndex = postorder.size() - 1;
          
          // 先创建根节点
          TreeNode* root = new TreeNode(postorder[postIndex--]);
          st.push(root);
  
          for (int i = postIndex; i >= 0; i--) {
              TreeNode* node = new TreeNode(postorder[i]);
              TreeNode* parent = nullptr;
  
              // 判断是否需要出栈（找到正确的父节点）
              while (!st.empty() && inMap[st.top()->val] > inMap[node->val]) {
                  parent = st.top();
                  st.pop();
              }
  
              // 根据 parent 是否存在决定插入左还是右子树
              if (parent) {
                  parent->left = node;
              } else {
                  st.top()->right = node;
              }
  
              st.push(node);
          }
  
          return root;
      }
  };

117. Populating Next Right Pointers in Each Node II

Solution: #Queue

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            int cnt = 0;
            while(n--){
                Node* node = que.front();
                que.pop();
                if(node->left){
                que.push(node->left);
                cnt++;
                }
                if(node->right){
                que.push(node->right);
                cnt++;
            }
            }
            while(cnt > 0){
                Node* cur = que.front();
                que.pop();
                que.push(cur);
                if(cnt == 1) break;
                cur->next = que.front();
                cnt--;
            }
        }
        return root;
    }
};

Solution：#Recursion #DFS

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    void DFS(Node* root, vector<Node*>& collect, int level){
        if(!root) return;
        if(collect.size() == level) collect.push_back(root);
        else{
            collect[level]->next = root;
            collect[level] = root;
        }
        DFS(root->left, collect, level + 1);
        DFS(root->right, collect, level + 1);
    }
    Node* connect(Node* root) {
        vector<Node*> collect;
        DFS(root, collect, 0);
        return root;
    }
};

Solution: #Pre Pointer

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            Node* prev = nullptr;  // 每一层的遍历设置一个pre指针
            for(int i = 0; i < n; i++){
                Node* cur = que.front();
                que.pop();
                if(prev){
                    prev->next = cur;
                }
                prev = cur;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

114. Flatten Binary Tree to Linked List

Solution: #Recursion #preOrder

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void preOrder(TreeNode* root, vector<TreeNode*>& vec){
        if(!root) return;
        vec.push_back(root);
        preOrder(root->left, vec);
        preOrder(root->right, vec);
    }
    void flatten(TreeNode* root) {
        vector<TreeNode*> vec;
        preOrder(root, vec);
        TreeNode* dummy = new TreeNode(0);
        TreeNode* cur = dummy;
        for(auto x : vec){
            x->left = nullptr;
            cur->right = x;
            cur = cur->right;
        }

    }
};

优化后的方法：#Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root) return;
        flatten(root->right);
        flatten(root->left);
        TreeNode* tmp = root->right;
        root->right = root->left;
        root->left = nullptr;
        while(root->right) root = root->right;
        root->right = tmp;
    }
};

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root) return;
        TreeNode* cur = root;
        while(cur){
            if(cur->left){
                TreeNode* rightmost = cur->left;
                while(rightmost->right) rightmost = rightmost->right;
                rightmost->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};

112. Path Sum

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        if(!root->left && !root->right && root->val == targetSum) return true;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        queue<pair<TreeNode*, int>> que;
        que.push({root, root->val});
        while(!que.empty()){
            TreeNode* node = que.front().first;
            int currSum = que.front().second;
            que.pop();
            if(!node->left && !node->right && currSum == targetSum) return true;
            if(node->left) que.push({node->left, currSum + node->left->val});
            if(node->right) que.push({node->right, currSum + node->right->val});
        }
        return false;
    }
};

129. Sum Root to Leaf Numbers

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if(!root) return 0;
        int ans = 0;
        queue<pair<TreeNode*, int>> que;
        que.push({root, root->val});
        while(!que.empty()){
            TreeNode* node = que.front().first;
            int curSum = que.front().second;
            que.pop();
            if(!node->left && !node->right) ans += curSum;
            if(node->left) que.push({node->left, node->left->val + curSum * 10});
            if(node->right) que.push({node->right, node->right->val + curSum * 10});
        }
        return ans;
    }
};

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void solve(TreeNode* root, int sum, vector<int>& nums){
        if(!root) return;
        sum = sum * 10 + root->val;
        if(!root->left && !root->right) nums.push_back(sum); // 叶子节点
        solve(root->left, sum, nums);
        solve(root->right, sum, nums);      
    }
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        vector<int> nums;
        solve(root, 0, nums);
        for(auto x : nums) ans += x;
        return ans;
    }
};

124. Binary Tree Maximum Path Sum

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int solve(TreeNode* node, int& maxSum){
        if(!node) return 0;
        int left = max(solve(node->left, maxSum), 0);
        int right = max(solve(node->right, maxSum), 0);
        int pathSum = left + right + node->val;
        maxSum = max(maxSum, pathSum);
        return node->val + max(left, right);
    }
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        solve(root, maxSum);
        return maxSum;
    }
};

优化后的代码：

class Solution {
public:
    unordered_map<TreeNode*, int> dp; // 记忆化存储最大路径和
    int solve(TreeNode* node, int& maxSum) {
        if (!node) return 0;
        if (dp.count(node)) return dp[node]; // 记忆化

        int left = max(solve(node->left, maxSum), 0);
        int right = max(solve(node->right, maxSum), 0);
        int pathSum = left + right + node->val;
        maxSum = max(maxSum, pathSum);

        return dp[node] = node->val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        solve(root, maxSum);
        return maxSum;
    }
};

173. Binary Search Tree Iterator

Solution: #中序遍历

class BSTIterator {
public:
    vector<int> nums;
    int index = 0;

    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        nums.push_back(root->val);
        inorder(root->right);
    }

    BSTIterator(TreeNode* root) {
        inorder(root);
    }

    int next() {
        return nums[index++];
    }

    bool hasNext() {
        return index < nums.size();
    }
};

Solution: #Stack

class BSTIterator {
public:
    stack<TreeNode*> st;
    BSTIterator(TreeNode* root) {
        pushLeft(root);
    }
    
    int next() {
        TreeNode* node = st.top();
        st.pop();
        pushLeft(node->right);
        return node->val;
    }
    
    bool hasNext() {
        return !st.empty();
    }
private:
    void pushLeft(TreeNode* node){
        while(node){
            st.push(node);
            node = node->left;
        }
    }
};

222. Count Complete Tree Nodes

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

Solution: #Iteration

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int res = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* cur = que.front();
                que.pop();
                res++;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return res;
    }
};

236. Lowest Common Ancestor of a Binary Tree

• 递归遍历二叉树，分别在 左子树 和 右子树 查找 p 和 q。
• 如果 p 和 q 分别出现在左右子树，则 root 是最近公共祖先。
• 如果 p 和 q 都出现在某一侧，就往那一侧递归。
• 如果当前 root == p 或 root == q，直接返回 root。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left == nullptr) return right;
        if(right == nullptr) return left;
        return root;
    }
};

Solution: #Iteration

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*, TreeNode*> parent;
        stack<TreeNode*> stk;
        parent[root] = nullptr;
        stk.push(root);
        
        // 遍历整棵树，记录每个节点的父节点
        while (parent.find(p) == parent.end() || parent.find(q) == parent.end()) {
            TreeNode* node = stk.top(); stk.pop();
            if (node->left) {
                parent[node->left] = node;
                stk.push(node->left);
            }
            if (node->right) {
                parent[node->right] = node;
                stk.push(node->right);
            }
        }
        
        // 记录 p 的所有祖先
        unordered_set<TreeNode*> ancestors;
        while (p) {
            ancestors.insert(p);
            p = parent[p];
        }
        
        // 找到 q 的第一个公共祖先
        while (!ancestors.count(q)) {
            q = parent[q];
        }
        return q;
    }
};

199. Binary Tree Right Side View

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        vector<int> ans;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                if(n == 0) ans.push_back(node->val);
            }
        }
        return ans;
    }
};

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, int depth, vector<int>& ans){
        if(!root) return;
        if(depth == ans.size()){
            ans.push_back(root->val);
        }
        dfs(root->right, depth + 1, ans);  // 保证右子树先被访问
        dfs(root->left, depth + 1, ans);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        dfs(root, 0, ans);
        return ans;
    }
};

637. Average of Levels in Binary Tree

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if(!root) return {};
        vector<double> ans;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            int num = que.size();
            double sum = 0;
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                sum += node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.push_back(sum / (num * 1.0));
        }
        return ans;
    }
};

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* node, int level, vector<double>& sum, vector<int>& count){
        if(!node) return;
        // sum 和 count 记录每一层的信息，初始为空。
        if(sum.size() <= level){
            sum.push_back(0);
            count.push_back(0);
        }
        sum[level] += node->val;
        count[level] += 1;
        dfs(node->left, level + 1, sum, count);
        dfs(node->right, level + 1, sum, count);
    }
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> sum;
        vector<int> count;
        dfs(root, 0, sum, count);
        vector<double> res;
        for(int i = 0; i < sum.size(); i++){
            res.push_back(sum[i] / count[i]);
        }
        return res;
    }
};

102. Binary Tree Level Order Traversal

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            vector<int> tmp;
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                tmp.push_back(node->val);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* node, int level, vector<vector<int>>& ans){
        if(!node) return;
        if(level >= ans.size()){
            ans.push_back({});
        }
        ans[level].push_back(node->val);
        dfs(node->left, level + 1, ans);
        dfs(node->right, level + 1, ans);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, 0, ans);
        return ans;
    }
};

103. Binary Tree Zigzag Level Order Traversal

Solution: #Iteration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode*> que;
        que.push(root);
        int level = 0;
        while(!que.empty()){
            level++;
            int n = que.size();
            vector<int> tmp;
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                tmp.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            if(level % 2 == 0) reverse(tmp.begin(), tmp.end());
            ans.push_back(tmp);
        }
        return ans;
    }
};

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* node, int level, vector<vector<int>>& ans){
        if(!node) return;
        if(level >= ans.size()) ans.push_back({});
        if(level % 2 == 0) ans[level].push_back(node->val);
        else ans[level].insert(ans[level].begin(), node->val); // 从右到左
        dfs(node->left, level + 1, ans);
        dfs(node->right, level + 1, ans);
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, 0, ans);
        return ans;
    }
};

530. Minimum Absolute Difference in BST

Solution: 笨办法#Brute Force

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> que;
        que.push(root);
        vector<int> nums;
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                nums.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        sort(nums.begin(), nums.end());
        int gap = INT_MAX;
        for(int i = 1; i < nums.size(); i++) gap = min(gap, nums[i] - nums[i - 1]);
        return gap;
    }
};

Solution: BST的中序遍历可以得到一个递增序列。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& nums){
        if(!root) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
    int getMinimumDifference(TreeNode* root) {
        vector<int> nums;
        inorder(root, nums);
        int gap = INT_MAX;
        for(int i = 1; i < nums.size(); i++){
            gap = min(gap, nums[i] - nums[i - 1]);
        }
        return gap;
    }
};

230. Kth Smallest Element in a BST

Solution: #Inorder

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& nums){
        if(!root) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> nums;
        inorder(root, nums);
        return nums[k - 1];
    }
};

优化后的方法：不需要完整遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int count = 0;
    int ans = 0;
    void inorder(TreeNode* root, int k){
        if(!root) return;
        inorder(root->left, k);
        count++;
        if(count == k){
            ans = root->val;
            return;
        }
        inorder(root->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        inorder(root, k);
        return ans;
    }
};

98. Validate Binary Search Tree

Solution: #Recursion

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& nums){
        if(!root) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> nums;
        inorder(root, nums);
        int pre = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] <= pre) return false;
            pre = nums[i];
        }
        return true;
    }
};

优化后的方法：不用完全遍历且不用额外空间

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* prev = nullptr;
    bool inorder(TreeNode* root){
        if(!root) return true;
        if(!inorder(root->left)) return false;  // 左子树不满足BST
        if(prev && root->val <= prev->val) return false;
        prev = root;
        return inorder(root->right);
    }
    bool isValidBST(TreeNode* root) {
        return inorder(root);
    }
};

200. Number of Islands

Solution: #BFS

class Solution {
public:
    int ox[4] = {-1, 0, 1, 0};
    int oy[4] = {0, 1, 0, -1};
    bool isValid(int x, int y, int m, int n, vector<vector<char>>& grid){
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1';  // 合法的'1'
    }
    void bfs(int x, int y, int m, int n, vector<vector<char>>& grid){
        if(!isValid(x, y, m, n, grid)) return;
        grid[x][y] = '0';
        for(int i = 0; i < 4; i++){
            int dx = x + ox[i];
            int dy = y + oy[i];
            bfs(dx, dy, m, n, grid);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        int m = grid.size();
        int n = grid[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1') {
                    bfs(i, j, m, n, grid);
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

Solution: #UnionSet

class Solution {
public:
    int find(int x, vector<int>& parent){
        if(parent[x] != x){
            parent[x] = find(parent[x], parent);  // 路径压缩
        }
        return parent[x];
    }

    void unionSets(int x, int y, vector<int>& parent, vector<int>& rank){
        int rootX = find(x, parent);
        int rootY = find(y, parent);
        if(rootX != rootY){
            if(rank[rootX] > rank[rootY]) parent[rootY] = rootX; // 合并小树到大树
            else if(rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else{
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        if(m == 0 || n == 0) return 0;
        vector<int> parent(m * n); // 并查集父节点数组
        vector<int> rank(m * n, 0); // 记录树的高度
        int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(int i = 0; i < m * n; i++) parent[i] = i;  // 初始化每个位置的父节点
        int numIslands = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    int cur = i * n + j;
                    for(auto& dir : directions){
                        int ni = i + dir[0];
                        int nj = j + dir[1];
                        if(ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == '1'){
                            int next = ni * n + nj;
                            unionSets(cur, next, parent, rank);
                        }
                    }
                }
            }
        }
        // 统计岛屿的数量，判断每个节点的根节点是否唯一
        unordered_set<int> islandRoots;
        for(int i = 0; i < m * n; i++){
            if(grid[i / n][i % n] == '1') islandRoots.insert(find(i, parent));
        }
        return islandRoots.size();
    }
};

130. Surrounded Regions

• 从边界上的 O 开始，用 BFS 标记所有能连到边界的 O（换成 #）。
• 遍历整个网格，把所有未标记的 O（被包围的）变成 X。
• 恢复标记的 # 变回 O（这些是原本连接到边界的 O）。

class Solution {
public:
    void bfs(vector<vector<char>>& board, int x, int y){
        int m = board.size();     // line
        int n = board[0].size();  // col
        if(x < 0 || x >= m || y < 0 || y >= n) return;  // 超出界限
        if(board[x][y] == 'O'){
            board[x][y] = '#';
            queue<pair<int, int>> que;
            que.push({x, y});
            while(!que.empty()){
                int i = que.front().first;
                int j = que.front().second;
                que.pop();
                if(i - 1 >= 0 && board[i - 1][j] == 'O'){
                    board[i - 1][j] = '#';
                    que.push({i - 1, j});
                }
                if(i + 1 < m && board[i + 1][j] == 'O'){
                    board[i + 1][j] = '#';
                    que.push({i + 1, j});
                }
                if(j - 1 >= 0 && board[i][j - 1] == 'O'){
                    board[i][j - 1] = '#';
                    que.push({i, j - 1});
                }
                if(j + 1 < n && board[i][j + 1] == 'O'){
                    board[i][j + 1] = '#';
                    que.push({i, j + 1});
                }
            }
        }
    }
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(m == 0) return;
        int n = board[0].size();
        for(int i = 0; i < m; i++){
            bfs(board, i, 0);
            bfs(board, i, n - 1);
        }
        for(int j = 0; j < n; j++){
            bfs(board, 0, j);
            bfs(board, m - 1, j);
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
};

Solution: #DFS

class Solution {
public:
    void dfs(vector<vector<char>>& board, int x, int y) {
        int m = board.size(), n = board[0].size();
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') return;
        
        board[x][y] = '#';  // 先标记
        dfs(board, x - 1, y);  // 上
        dfs(board, x + 1, y);  // 下
        dfs(board, x, y - 1);  // 左
        dfs(board, x, y + 1);  // 右
    }

    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();

        // 处理边界
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);      // 第一列
            dfs(board, i, n - 1);  // 最后一列
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);      // 第一行
            dfs(board, m - 1, j);  // 最后一行
        }

        // 遍历整个矩阵，修改值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
};

Solution: #Union-Find

class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) 
            parent[x] = find(parent[x]);  // 路径压缩
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        int dummy = m * n;  // 虚拟节点

        UnionFind uf(dummy + 1);

        // 遍历整个矩阵，处理边界上的 'O'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    int index = i * n + j;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        // 边界上的 'O' 连接到 dummy
                        uf.unite(index, dummy);
                    } else {
                        // 合并相邻的 'O'
                        if (i > 0 && board[i - 1][j] == 'O') uf.unite(index, (i - 1) * n + j);
                        if (i < m - 1 && board[i + 1][j] == 'O') uf.unite(index, (i + 1) * n + j);
                        if (j > 0 && board[i][j - 1] == 'O') uf.unite(index, i * n + (j - 1));
                        if (j < n - 1 && board[i][j + 1] == 'O') uf.unite(index, i * n + (j + 1));
                    }
                }
            }
        }

        // 遍历整个矩阵，修改值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    int index = i * n + j;
                    if (!uf.connected(index, dummy)) {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }
};

133. Clone Graph

Solution: #Hash Table

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> copies;
    Node* cloneGraph(Node* node) {
        if(!node) return nullptr;
        Node* copy = new Node(node->val);
        copies[node] = copy;
        queue<Node*> que;
        que.push(node);
        while(!que.empty()){
            Node* cur = que.front();
            que.pop();
            for(Node* neighbor : cur->neighbors){
                if(copies.find(neighbor) == copies.end()){
                    copies[neighbor] = new Node(neighbor->val);
                    que.push(neighbor);
                }
                copies[cur]->neighbors.push_back(copies[neighbor]);
            }
        }
        return copy;
    }
};

399. Evaluate Division

Solution: #Union-Find

class Solution {
public:
    unordered_map<string, string> parent;
    unordered_map<string, double> weight;

    string find(string x){
        if(parent.find(x) == parent.end()){
            parent[x] = x;
            weight[x] = 1.0;
        }
        if(parent[x] != x){
            string origin = parent[x];
            parent[x] = find(parent[x]); // 路径压缩
            weight[x] *= weight[origin];  // 更新路径中的比值
        }
        return parent[x];
    }

    void unionSets(string x, string y, double value){
        string rootX = find(x);
        string rootY = find(y);
        if(rootX != rootY){
            parent[rootX] = rootY;
            weight[rootX] = value * weight[y] / weight[x];
        }
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for(int i = 0; i < equations.size(); i++){
            string a = equations[i][0], b = equations[i][1];
            double value = values[i];
            unionSets(a, b, value);
        }
        vector<double> result;
        for(auto& query : queries){
            string a = query[0], b = query[1];
            if(parent.find(a) == parent.end() || parent.find(b) == parent.end() || find(a) != find(b)){
                result.push_back(-1.0);
            }
            else result.push_back(weight[a] / weight[b]);
        }
        return result;
    }
};

Solution：构图 + BFS

class Solution {
public:
    unordered_map<string, vector<pair<string, double>>> graph;

    double bfs(string start, string end) {
        if(graph.find(start) == graph.end() || graph.find(end) == graph.end()) return -1.0;

        queue<pair<string, double>> q;
        unordered_set<string> visited;
        q.push({start, 1.0});
        visited.insert(start);

        while(!q.empty()) {
            auto [curr, val] = q.front();
            q.pop();

            if(curr == end) return val;  // 找到目标

            for(auto& neighbor : graph[curr]) {
                string nextNode = neighbor.first;
                double weight = neighbor.second;
                if(visited.count(nextNode)) continue;  // 避免重复访问

                visited.insert(nextNode);
                q.push({nextNode, val * weight});  // 更新累计权重
            }
        }
        return -1.0;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // 1. 构造图
        for(int i = 0; i < equations.size(); i++) {
            string a = equations[i][0], b = equations[i][1];
            double value = values[i];
            graph[a].push_back({b, value});
            graph[b].push_back({a, 1.0 / value});
        }

        // 2. 处理查询
        vector<double> result;
        for(auto& query : queries) {
            result.push_back(bfs(query[0], query[1]));
        }
        return result;
    }
};

207. Course Schedule

Solution: #BFS

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);  // 邻接表
        vector<int> indegree(numCourses, 0);   // 入度表
        for(auto p : prerequisites){
            int a = p[0], b = p[1];
            graph[b].push_back(a);   // b -> a
            indegree[a]++;
        }
        queue<int> q;
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0) q.push(i);  // 入度为0的可以先学
        }
        int finished = 0;
        while(!q.empty()){
            int course = q.front();
            q.pop();
            finished++;
            for(int neighbor : graph[course]){
                indegree[neighbor]--;
                if(indegree[neighbor] == 0) q.push(neighbor);
            }
        }
        return finished == numCourses;
    }
};

210. Course Schedule II

Solution: #BFS

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);  // 邻接表
        vector<int> indegree(numCourses, 0);   // 入度表
        for(auto p : prerequisites){
            int a = p[0], b = p[1];
            graph[b].push_back(a);   // b -> a
            indegree[a]++;
        }
        queue<int> q;
        vector<int> ans;
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0){
                q.push(i);
                ans.push_back(i);
            }
        }
        while(!q.empty()){
            int course = q.front();
            q.pop();
            for(int neighbor : graph[course]){
                indegree[neighbor]--;
                if(indegree[neighbor] == 0){
                    q.push(neighbor);
                    ans.push_back(neighbor);
                }
            }
        }
        if(ans.size() == numCourses) return ans;
        else return {};
    }
};

909. Snakes and Ladders

Solution: #BFS

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        vector<int> flat(n * n + 1, -1); // 1-based indexing
        int idx = 1;
        bool leftToRight = true;
        for(int i = n - 1; i >= 0; i--){
            if(leftToRight){
                for(int j = 0; j < n; j++) flat[idx++] = board[i][j];
            }
            else{
                for(int j = n - 1; j >= 0; j--) flat[idx++] = board[i][j];
            }
            leftToRight = !leftToRight; // 换遍历方向
        }
        queue<int> que;
        vector<bool> visited(n * n + 1, false);
        que.push(1);
        visited[1] = true;
        int steps = 0;
        while(!que.empty()){
            int sz = que.size();
            while(sz--){
                int cur = que.front();
                que.pop();
                if(cur == n * n) return steps;
                for(int move = 1; move <= 6 && cur + move <= n * n; move++){
                    int next = cur + move;
                    if (flat[next] != -1) next = flat[next];
                    if(!visited[next]){
                        visited[next] = true;
                        que.push(next);
                    }
                }
            }
            steps++;
        }
        return -1;
    }
};

433. Minimum Genetic Mutation

Solution:#BFS

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> ust(bank.begin(), bank.end());
        if(ust.find(endGene) == ust.end()) return -1;  // 目标基因不在bank中
        unordered_set<string> visited;  // 用来记录已访问的基因
        queue<string> que;
        que.push(startGene);
        visited.insert(startGene);
        int mutations = 0;  // 记录变异次数
        string genes = "ACGT";
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i < size; i++){
                string curr = que.front();
                que.pop();
                if(curr == endGene) return mutations;
                for(int j = 0; j < 8; j++){
                    for(char c : genes){
                        if(curr[j] != c){
                            string newGene = curr;
                            newGene[j] = c;
                            if(ust.find(newGene) != ust.end() && visited.find(newGene) == visited.end()){
                                visited.insert(newGene);
                                que.push(newGene);
                            }
                        }
                    }
                }
            }
            mutations++;
        }
        return -1;
    }
};

127. Word Ladder

Solution: #BFS，暴力枚举可能出现的字段

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if(wordSet.find(endWord) == wordSet.end()) return 0;  // 终点不在wordList中
        unordered_set<string> visited;
        queue<string> que;
        que.push(beginWord);
        visited.insert(beginWord);
        int steps = 1;
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i < size; i++){
                string cur = que.front();
                que.pop();
                if(cur == endWord) return steps;
                for(int j = 0; j < cur.size(); j++){
                    char original = cur[j];
                    for(char c = 'a'; c <= 'z'; c++){
                        if(c == original) continue;
                        cur[j] = c;
                        if(wordSet.find(cur) != wordSet.end() && visited.find(cur) == visited.end()){
                        visited.insert(cur);
                        que.push(cur);
                        }
                    } 
                    cur[j] = original;  // 还原
                }
            }
            steps++;
        }
        return 0;
    }
};

208. Implement Trie (Prefix Tree)

Solution: 暴力映射找前缀

class Trie {
public:
    unordered_set<string> ust;
    Trie() {
        ust.clear();
    }
    
    void insert(string word) {
        ust.insert(word);
    }
    
    bool search(string word) {
        return !(ust.find(word) == ust.end());
    }
    
    bool startsWith(string prefix) {
        int n = prefix.size();
        for(auto str : ust){
            if(str.substr(0, n) == prefix) return true;
        }
        return false;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Solution: #BFS

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;  // 存储子节点
    bool is_end_of_word;  // 标记是否为单词的结尾
    
    TrieNode() : is_end_of_word(false) {}
};

class Trie {
public:
    TrieNode* root;  // 根节点
    
    Trie() {
        root = new TrieNode();  // 初始化根节点
    }
    
    // 插入单词
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->is_end_of_word = true;  // 标记该节点为单词的结尾
    }
    
    // 搜索单词
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;  // 如果某个字符不存在，返回 false
            }
            node = node->children[c];
        }
        return node->is_end_of_word;  // 如果到达的节点是单词的结尾，则返回 true
    }
    
    // 判断是否有单词以 prefix 开头
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;  // 如果某个字符不存在，返回 false
            }
            node = node->children[c];
        }
        return true;  // 如果遍历完 prefix 的所有字符，返回 true
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

🖼️ 图示（插入 “apple” 和 “app” 之后）

(root)
  |
  a
  |
  p
  |
  p*   ← app 的结尾（is_end_of_word = true）
  |
  l
  |
  e*   ← apple 的结尾（is_end_of_word = true）

211. Design Add and Search Words Data Structure

Solution: #Trie

class WordDictionary {
private:
    struct TrieNode {
        TrieNode* children[26] = {nullptr};
        bool isEnd = false;
    };

    TrieNode* root;

public:
    WordDictionary() {
        root = new TrieNode();
    }

    void addWord(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        return searchHelper(word, 0, root);
    }

private:
    bool searchHelper(const string& word, int index, TrieNode* node) {
        if (!node) return false;

        if (index == word.size())
            return node->isEnd;

        char c = word[index];
        if (c == '.') {
            // Try all possible children
            for (int i = 0; i < 26; ++i) {
                if (node->children[i] && searchHelper(word, index + 1, node->children[i]))
                    return true;
            }
            return false;
        } else {
            int idx = c - 'a';
            return searchHelper(word, index + 1, node->children[idx]);
        }
    }
};

字典树🌲插入方式如下

(root)
  ├── b
  │   └── a
  │       └── d*
  ├── d
  │   └── a
  │       └── d*
  └── m
      └── a
          └── d*

212. Word Search II

Solution: #Trie #BFS #Recursion

(root)
 ├── o
 │   └── a
 │       └── t
 │           └── h [word: "oath"]
 ├── p
 │   └── e
 │       └── a [word: "pea"]
 ├── e
 │   └── a
 │       └── t [word: "eat"]
 └── r
     └── a
         └── i
             └── n [word: "rain"]

class Solution {
public:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        string word = "";
    };
    
    TrieNode* buildTrie(const vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (const string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                if (!node->children.count(c)) {
                    node->children[c] = new TrieNode();
                }
                node = node->children[c];
            }
            node->word = word;  // Store word at the end node
        }
        return root;
    }

    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, vector<string>& result) {
        char c = board[i][j];
        if (c == '#' || !node->children.count(c)) return;

        node = node->children[c];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word = ""; // avoid duplicate
        }

        board[i][j] = '#'; // mark visited
        int dirs[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        for (auto& d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && y >= 0 && x < board.size() && y < board[0].size()) {
                dfs(board, x, y, node, result);
            }
        }
        board[i][j] = c; // backtrack
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> result;
        TrieNode* root = buildTrie(words);
        
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                dfs(board, i, j, root, result);
            }
        }

        return result;
    }
};

17. Letter Combinations of a Phone Number

Solution: #Recursion

class Solution {
private:
    unordered_map<char, string> mp = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };

    void rec(string digits, int idx, vector<string>& ans, string tmp){
        if(idx >= digits.size()){
            ans.push_back(tmp);
            return;
        }
        string word = mp[digits[idx]];
        for(int i = 0; i < word.size(); i++) rec(digits, idx + 1, ans, tmp + word[i]);
    }
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        vector<string> ans;
        string tmp = "";
        rec(digits, 0, ans, tmp);
        return ans;
    }
};

实例图

Level 0:
└── ""                     // 开始递归，空字符串

Level 1: 处理 digits[0] = '2' → "abc"
├── "a"
├── "b"
└── "c"

Level 2: 处理 digits[1] = '3' → "def"
├── "a"
│   ├── "ad"
│   ├── "ae"
│   └── "af"
├── "b"
│   ├── "bd"
│   ├── "be"
│   └── "bf"
└── "c"
    ├── "cd"
    ├── "ce"
    └── "cf"

最终结果：
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

77. Combinations