leetcode算法题hot100（1）

2025-03-05

字数统计: 7.1k | 阅读时长≈ 33 分钟

使用C++完成leetcode算法题hot100（有选择地记录），并记录算法思路和心路历程。

🔥哈希

1. 两数之和

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

思路简单，使用哈希映射记录下每一组数字到索引的映射，把数字作为key便于查找。每一次只需要查找当前值关于target的补值是否存在，存在就可以获取其索引。
记住find()和end()函数。

49. 字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hashtable;
        for(int i = 0; i < strs.size(); ++i){
            string key = strs[i];
            sort(key.begin(), key.end());
            hashtable[key].emplace_back(strs[i]);
        }
        vector<vector<string>> result;
        for (const auto& pair : hashtable) {
            result.push_back(pair.second);
        }
        return result;
    }
};

将每个字符串排序后作为key，原字符串存入value列表当中。最终只需要打印出每组value即可。
pair.first/second返回映射的第1、2个值（key和value）；emplace_back()和push_back()用于向容器尾部添加元素。

128. 最长连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet;
        for (const int& num: nums) {
            numSet.insert(num);
        }
        int result = 0;
        for (const int& num: numSet) {
            if (!numSet.count(num - 1)) {
                int curlen = 1;
                int curnum = num;
                while (numSet.count(curnum + 1)) {
                    curlen++;
                    curnum++;
                }
                result = max(result, curlen);
            }
        }
        return result;
    }
};

使用集合存储所有数，使用 count() 获取数是否存在（因为集合元素唯一，只能返回0、1），当前数的前缀不存在时该数就是一个序列的开头，就可以依次查找后缀是否存在来记录序列长度，维护最大长度。

🔥双指针和滑窗

11. 盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;
        while(left < right) {
            int width = right - left;
            maxArea = max(maxArea, min(height[left], height[right]) * width);
            if (height[left] < height[right]) {
                left++;
            }
            else {
                right--;
            }
        }
        return maxArea;
    }
};

左右双指针，每步更新最大面积，由于短边是瓶颈，意味着收缩指针应该选择短的那个向中间收缩。

15. 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());         // 升序排列
        vector<vector<int>> result;
        for(int left = 0; left < nums.size(); ++left){
            if(left > 0 && nums[left] == nums[left - 1]){     // 去重
                continue;
            }
            int right = nums.size() - 1;
            for(int i = left + 1; i <= right - 1; ++i){
                if(i > left + 1 && nums[i] == nums[i - 1]){     // 去重
                    continue;
                }
                while(i < right && nums[i] + nums[right] + nums[left] > 0){
                    right--;
                }
                if(i == right)  break;
                if(nums[left] + nums[i] + nums[right] == 0){
                    result.push_back({nums[left], nums[i], nums[right]});
                }
            }
        }
        return result;
    }
};

先排序，然后确定应该left点，然后对left右边的序列做两数之和的题目，只不过和不是0而是-nums[left]。
注意两层循环都需要去重。

42. 接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int water = 0;
        int lh = 0;
        int rh = 0;
        int left = 0;
        int right = height.size() - 1;
        int maxh = 0;
        while (left < right) {
            lh = max(lh, height[left]);
            rh = max(rh, height[right]);
            if (height[left] <= height[right]){
                water += lh - height[left];
                left++;
            }
            else{
                water += rh - height[right];
                right--;
            }
        }
        return water;
    }
};

和上一题本质是一样的，只需要知道本格的水高度一定是左右两边更矮的那一个与本格高度的差。只不过左右两边应该是维护各自的最大值。

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hash;
        int maxlen = 0, l = 0;
        for (int i = 0; i < s.size(); i++) {
            while (hash.count(s[i])) {
                hash.erase(s[l++]);
            }
            hash.insert(s[i]);
            maxlen = max(maxlen, i - l + 1);
        }
        return maxlen;
    }
};

滑窗思想，右指针没有出现重复时，滑窗延长，当出现重复时，左边缩短直到该重复字符被删掉（删掉老的那个，新的还是要加进去的）。

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

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int len = p.size();
        vector<int> cp(26);
        vector<int> cs(26);         // 维护s的子串对应的计数
        vector<int> result;
        if (len > s.size())     return {};
        for (int i = 0; i < len; i++) {
            cp[p[i] - 'a'] += 1;
            cs[s[i] - 'a'] += 1;
        }
        if (cs == cp)   result.push_back(0);
        for (int left = 0; left + len < s.size(); ++left){
            cs[s[left] - 'a'] -= 1;
            cs[s[left + len] - 'a'] += 1;
            if (cs == cp)   result.push_back(left + 1);
        }
        return result;
    }
};

固定滑窗，首先记录p的字母数量，然后维护滑窗p的字母计数，每步都判断p和滑窗的计数是否一致即可。

🔥子串

560. 和为 K 的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int sum = 0, result = 0;
        hash[0]++;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (hash.find(sum - k) != hash.end())
                result += hash[sum - k];
            hash[sum]++;
        }
        return result;
    }
};

用哈希表记录每个元素的前缀和，子串两端元素的前缀和之差为k，则该子串为目标子串。

239. 滑动窗口最大值

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

使用优先级队列（大根堆，自动从大到小排序）维护最大值及其索引，当最大值的索引不在滑窗内时就弹出，直到索引在滑窗内即为当前滑窗最大值。

76. 最小覆盖子串

class Solution {
public:
    unordered_map<char, int> tHash;
    bool check() {
        for (const auto &p: tHash) {
            if (p.second > 0) {
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        int n = s.size();
        int m = t.size();
        int ansL = -1;
        int len = INT_MAX, l = 0, r = 0;
        for (int i = 0; i < m; i++) {       // 哈希计数
            tHash[t[i]]++;
        }
        while (r < n) {
            if (tHash.find(s[r]) != tHash.end())      // 计数扣除
                tHash[s[r]]--;
            while (check() && l <= r) {         // 都为非正数，说明包含了t
                if (len > r - l + 1) {          // 目标子串更新
                    len = r - l + 1;
                    ansL = l;
                }
                if (tHash.find(s[l]) != tHash.end())
                    tHash[s[l]]++;          // 左边
                l++;
            }
            r++;
        }
        return ansL == -1 ? "": s.substr(ansL, len);
    }
};

滑窗，先用哈希映射记录t的字母数，不断右延长窗口，新的字符若存在于t当中，则减去哈希表对应计数。
当哈希表没有正数时，说明已经包含了t子串（负数说明多了），更新最短的答案子串。
这时候就需要左缩短窗口直到滑窗不在满足包含t的条件，再继续右延长操作。

🔥数组

53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int preSum = 0, minPreSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            preSum += nums[i];
            result = max(result, preSum - minPreSum);
            minPreSum = min(preSum, minPreSum);
        }
        return result;
    }
};

子数组和就是子数组端点的前缀和之差。记录最小前缀和，用每个元素的前缀和减去最小前缀和去维护最大子数组和即可。
注意result要比最小前缀和先维护，否则可能出现同一个前缀自减（得到0）到情况。

56. 合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<vector<int>> result;
        sort(intervals.begin(), intervals.end());
        if (n <=1)   return intervals;
        for (int i = 0; i < n; i++) {
            int left = intervals[i][0], right = intervals[i][1];
            if (result.size() == 0 || result.back()[1] < left) {
                result.push_back(intervals[i]);
            }
            else{
                result.back()[1] = max(result.back()[1], right);
            }
        }
        return result;
    }
};

按左端点排序，然后判断每个元素是否和result最后一个区间相交，不相交则直接加入result，相交则更新result最后一个区间的右端点。

189. 轮转数组

189. 轮转数组
方法一：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        multimap<int, int> hash;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            hash.insert(make_pair(nums[i], (i + k) % n));
        }
        for (const auto& pair : hash) {
            nums[pair.second] = pair.first; 
        }
    }
};

用一个哈希映射记录每个值及其新的索引，新的索引就是(原索引+k) % n，也就是只有余数是有意义的，然后重新赋值即可。
注意是用multimap，这个映射是允许key重复的。

方法二：

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());
    }
};

算是数学结论了，整个序列反转，然后前k个反转，后k个反转，就能得到结果。

238. 除自身以外数组的乘积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> left;
        vector<int> right;
        int n = nums.size();
        int mul = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0)  mul *= nums[i - 1];
            left.push_back(mul);
        }
        mul = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1)  mul *= nums[i + 1];
            right.push_back(mul);
        }
        for (int i = 0; i < n; i++) {
            left[i] *= right[n - i - 1];
        }
        return left;
    }
};

遍历两遍，分别记录每个元素的左乘积和右乘积（连乘），最后再遍历一次，把左右两边乘起来。
注意首个元素的左乘积和尾部元素的右乘积是1。

🔥矩阵

73. 矩阵置零

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> zeroPosX;
        unordered_set<int> zeroPosY;
        int n = matrix[0].size();
        int m = matrix.size();
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (matrix[i][j] == 0){
                    zeroPosX.insert(i);
                    zeroPosY.insert(j);
                }
            }
        }
        for (int x : zeroPosX){
            for (int j = 0; j < n; j++){
                matrix[x][j] = 0;
            }
        }
        for (int y : zeroPosY){
            for (int i = 0; i < m; i++){
                matrix[i][y] = 0;
            }
        }
    }
};

用哈希集合记录所有要被置零点行和列，然后通过两次遍历一次性置零即可。

54. 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int x = matrix[0].size();           // 横轴为x，纵轴为y
        int y = matrix.size();
        int lenx = x;
        int leny = y;
        int count = 0;
        vector<int> ans;
        while(lenx > 0 && leny > 0){
            int i = count;
            int j = count;
            if (lenx == 1 && leny == 1){
                ans.push_back(matrix[j][i]);
                return ans;
            }
            for (; i < x - 1 - count; ++i) {
                ans.push_back(matrix[j][i]);
                if (ans.size() == x * y)    return ans;
            }
            for (; j < y - 1 - count; ++j) {
                ans.push_back(matrix[j][i]);
                if (ans.size() == x * y)    return ans;
            }
            for (; i > count; --i) {
                ans.push_back(matrix[j][i]);
                if (ans.size() == x * y)    return ans;
            }
            for (; j > count; --j) {
                ans.push_back(matrix[j][i]);
                if (ans.size() == x * y)    return ans;
            }
            count++;
            lenx = lenx - 2;
            leny = leny - 2;
        }
        return ans;
    }
};

就是纯按要求循环，大循环嵌套四个方向的小循环，主要是折磨调代码和边界判断。

48. 旋转图像

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

按下图方法旋转，分为四块，嵌套双循环只遍历同颜色的部分，每次四大块分别交换一个小块，遍历完成后四大块就交换完了。
把内层的int j = 0; j < (n + 1) / 2; ++j改为int j = i; j < n - i - 1; ++j，即可实现一圈圈地循环，每圈循环边长-1次。

240. 搜索二维矩阵 II

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

从右上角开始向左下搜，如果太大就减列，小了就加行，相当于手握加减两种手段。

🔥技巧题

136. 只出现一次的数字

这题有很多简单的方法，比如用哈希计数，或者排序完找出单身狗就行了。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;    // 对所有数连续异或运算
        return ret;
    }
};

最巧的方法就是让整个数组做连续异或，相同的数按位异或后变成0，而单个数就只能和0异或，得到本身，这样直接就浮出水面了。

169. 多数元素

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

把数组排序，然后取中间的数就是多数元素。因为多数元素此时构成了一个滑窗，长度大于半个数组，所以再怎么样中间的元素一定都得是多数元素。

75. 颜色分类

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0){
                swap(nums[p], nums[i]);
                p++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                swap(nums[p], nums[i]);
                p++;
            }
        }
    }
};

就是排序，遍历两次分别对0和1进行检测，检测到就往左交换即可。原理和冒泡差不多。

31. 下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

偏背诵的题，不知道答案挺难想出简短的。
从右往左遍历，先找到左边小于右边的情况（升序），然后去小的这个位置i。再从右到左找到首次大于nums[i]的数，然后交换。
交换完成后把索引i右边（不包括i）的数都翻转。

287. 寻找重复数

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

快慢指针，快指针每次走两步，慢指针每次走一步，当快慢指针相遇时，慢指针回到起点，然后快指针继续走，相遇的点就是重复的数。
这个是借助链表的环路检测方法，算是数学推导的结果。

🔥链表

160. 相交链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> hash;
        ListNode* cur = headA;
        while (cur != nullptr) {
            hash.insert(cur);
            cur = cur->next;
        }
        cur = headB;
        while (cur != nullptr) {
            if (hash.find(cur) != hash.end()) {
                return cur;
            }
            cur = cur->next;
        }
        return nullptr;
    }
};

上面注释是单链表的定义。
思路就是哈希集合记录A链的所有节点，然后遍历B链，如果遇到哈希集合中的节点就返回即可。

206. 反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* temp;
        ListNode* pre = nullptr;
        while(cur != nullptr) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre; 
    }
};

设置三个指针，分别指代当前操作节点（cur）、原本的下一个节点（temp）、原本的上一个节点（pre）。
每次操作思路就是把cur的next指向pre，temp起到暂存的作用，最后把cur和pre都向右移动一位。

234. 回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* cur = head;
        int len = 0;
        vector<int> a;
        while (cur) {
            len++;
            a.push_back(cur -> val);
            cur = cur -> next;
        }
        for (int i = 0; i < len / 2; ++i) {
            if (a[i] != a[a.size() - 1 - i])    return false;
        }
        return true;
    }
};

遍历链表，然后把链表元素存到一个数组中，然后判断数组的前半部分和后半部分是否相等。

141. 环形链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        if (!fast) return false;
        while (fast->next) {
            if (!fast->next->next)  return false;
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};

快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针相遇，说明有环。
注意判断fast->next和fast->next->next存在。

142. 环形链表 II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        if (!fast) return nullptr;
        do{
            if (fast == nullptr || fast -> next == nullptr)     return nullptr;
            fast = fast -> next -> next;
            slow = slow -> next;
        }   while (fast != slow);
        slow = head;
        while (fast != slow){
            fast = fast -> next;
            slow = slow -> next;
        }
        return fast;
    }
};

快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针相遇，说明有环。
然后慢针回到起点，快慢针都以1步的速度寻访节点，相遇位置即为环入口。

21. 合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode(-1);
        ListNode* prev = head;
        while (list1 && list2) {
            if (list1 -> val < list2 -> val) {
                prev->next = list1;
                list1 = list1 -> next;
            }
            else {
                prev->next = list2;
                list2 = list2 -> next;
            }
            prev = prev->next;
        }
        prev->next = list1 ? list1 : list2;
        return head->next; 
    }
};

建立虚拟头节点head，然后逐步比较两个链表的节点，pre的next指向小的节点，最后剩下的链表直接拼接上即可。

2. 两数相加

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        int more = 0;
        while (l1 || l2) {
            int a = l1 ? l1->val : 0;
            int b = l2 ? l2->val : 0;
            int sum = a + b + more;
            cur->next = new ListNode(sum % 10);
            more = sum / 10;
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (more) {
            cur->next = new ListNode(1);
        }
        return head->next;
    }
};

很简单，模拟小学数学的方法，该进1就进1。
两个链表长度不同，到最后可能有一个链表结束了，所以灵活借助三目运算符减少代码量，把结束的链表高位用0代替。
循环结束后，如果最后多一个进位记得补上。

19. 删除链表的倒数第 N 个结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* fast = head;
        ListNode* slow = dummyHead;
        while(n--) {
            fast = fast->next;
        }
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummyHead->next;
    }
};

快慢针，fast先走n步，然后fast和slow同时走，直到fast到达链表末尾，slow的位置就是倒数第n个节点的前一个节点（因为要删除该节点得操作上一个节点）。

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = dummy;
        ListNode* second = dummy->next;
        if (!head || !head->next) return head;
        while (second && second->next) {
            ListNode* tmp = second->next->next;
            second->next->next = first->next;
            first->next = second->next;
            second->next = tmp;
            if (second->next) {
                first = second;
                second = second->next;
            }
        }
        return dummy->next;
    }
};

和反转链表差不多，只不过一次操作两个节点的指针，需要理好思路，不乱就行。
操作前second是第一个节点，first指向second，每次操作末尾要注意second此时已经是交换后的第二个节点了，所以直接赋值给first就行了。

138. 随机链表的复制

class Solution {
public:
    unordered_map<Node*, Node*> cache;
    Node* copyRandomList(Node* head) {
        if (!head)  return NULL;
        if (!cache.count(head)) {
            Node* newHead = new Node(head->val);
            cache[head] = newHead;
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }
        return cache[head];
    }
};

递归方法，每一层就负责复制一个节点，然后递归复制其next和random指针。已经构建的节点或指向为空就不需要构建了。

23. 合并 K 个升序链表

class Solution {
public:
    ListNode* merge(ListNode* a, ListNode* b) {
        if (!a || !b)   return a ? a : b;
        ListNode* head = new ListNode();
        ListNode* cur = head;
        ListNode* pa = a;
        ListNode* pb = b;
        while (pa && pb) {
            if (pa->val < pb->val) {
                cur->next = pa;
                pa = pa->next;
            }else {
                cur->next = pb;
                pb = pb->next;
            }
            cur = cur->next;
        }
        cur->next = pa ? pa : pb;       // 最多剩一个
        return head->next;
    }
    ListNode* mergeAll(vector<ListNode*>& lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r)  return nullptr;
        int mid = (l + r) / 2;
        return merge(mergeAll(lists, l, mid), mergeAll(lists, mid + 1, r));
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeAll(lists, 0, lists.size() - 1);
    }
};

两两合并之前做过，多个合并就是重复多次两两合并，这里用二分法递归合并，每一层递归负责将下面一层的两个合并结果合并起来。

146. LRU 缓存

class LRUCache {
public:
    queue<int> q;
    unordered_map<int, int> map, cnt;
    int size;
    LRUCache(int capacity) {
        size = capacity;
    }
    void updata(int key) {
        q.push(key);
        cnt[key]++;
        while (size < map.size()) {
            int x = q.front();
            q.pop();
            cnt[x]--;
            if (!cnt[x]) {
                map.erase(x);
                cnt.erase(x);
            }
        }
    }
    int get(int key) {
        if (map.count(key)) {
            updata(key);
            return map[key];
        }
        return -1;
    }
    
    void put(int key, int value) {
        map[key] = value;
        updata(key);
    }
};

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

使用队列来记录key的使用先后，用两个哈希映射分别记录键值对和key的使用个数（也就是队列中有多少个该key）。
使用包括put和get，所以两个操作都要更新队列和两个哈希映射。当某个key的计数为0，也就是不存在于队列当中时，就删除该key。

🔥二叉树

94. 二叉树的中序遍历

/**
 * 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> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        TreeNode* cur = root;
        while (!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur -> left;
            }
            else {
                result.push_back(st.top()->val);
                cur = st.top()->right;
                st.pop();
            }
        }
        return result;
    }
};

循环写法，一路向左子树，逐个入栈，到头后弹出栈顶节点（中间节点），开始寻访右子树。

104. 二叉树的最大深度

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

递归，每一层都将左右子树深度大者+1，也就是该节点作为根时，树的深度。

226. 翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL)   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. 对称二叉树

class Solution {
public:
    bool cmp(TreeNode* left, TreeNode* right) {
        if (left != NULL && right == NULL) return false;
        else if (left == NULL && right != NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val)   return false;
        bool outs = cmp(left->left, right->right);
        bool ins = cmp(left->right, right->left);
        return outs && ins;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return cmp(root->left, root->right);
    }
};

递归，每一层都把比较两个子树的根节点是否一致，然后再比较左树都左孩子和右树都右孩子的值是否一致，再比较左树的右孩子和右树的左孩子的值是否一致。

543. 二叉树的直径

class Solution {
public:
    int maxDepth = 0;
    int depth(TreeNode* node) {
        if (!node)  return 0;
        int left = depth(node->left);
        int right = depth(node->right);
        maxDepth = max(maxDepth, left + right);
        return max(left, right) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return maxDepth;
    }
};

递归，每一层对该节点求其左右子树的高度，更新最大路径。
注意根据示例，其实长度是只包括一个端点的，所以maxDepth = max(maxDepth, left + right)不用+1。
但回溯给上一层的只能是左右子树高度更大者+1，也就是该节点为根节点的树的高度。

102. 二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if (root != NULL) que.push(root);
        else return result;
        while (!que.empty()) {
            int size = que.size();          // 记下来，否则循环会变化
            vector<int> res;
            while (size--) {
                TreeNode* node = que.front();
                res.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                que.pop();
            }
            result.push_back(res);
        }
        return result;
    }
};

前面提到过，借助辅助队列即可。

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

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

递归回溯是最快的，使用二分法，每层给定区间，对区间二分，中间点mid作为根节点，mid左边的元素构成其左子树，右边就是右子树。

98. 验证二叉搜索树

class Solution {
public:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (!root) return;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }
    bool isValidBST(TreeNode* root) {
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            if (vec[i - 1] >= vec[i])    return false;
        }
        return true;
    }
};

递归回溯，中序遍历，每层负责按左中右（也就是中序）就行遍历，把节点逐个加入向量，最后统一判断是否升序即可。

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

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

其实可以按上一题改，当vec长度为k时，最后的元素就是第k小的了。
这里用循环实现，借助辅助栈完成中序遍历即可。

199. 二叉树的右视图

class Solution {
public:
    vector<int> ans;
    void search(TreeNode* root, int depth) {
        if (!root)  return;
        if (depth == ans.size())    ans.push_back(root->val);   // 第一次被记录的就是最右边的
        search(root->right, depth + 1);         // 先找右边
        search(root->left, depth + 1);
    }
    vector<int> rightSideView(TreeNode* root) {
        search(root, 0);
        return ans;
    }
};

递归（不回溯），每一层的节点都查看ans长度是否和深度一致，一致则说明该层还没有访问到最右边的那个节点，则该节点就是了。
接下来同一层的其他节点发现该层已经有值了，就不需要加入ans。

114. 二叉树展开为链表

class Solution {
public:
    TreeNode* move(TreeNode* root) {
        TreeNode* leaveL = root;
        TreeNode* leaveR = root;
        if (root->left)   leaveL = move(root->left);
        if (root->right)  leaveR = move(root->right);
        TreeNode* rightTree = root->right;
        root->right = root->left;
        leaveL->right = rightTree;
        root->left = NULL;
        if (rightTree == nullptr)   return leaveL;
        return leaveR;
    }
    void flatten(TreeNode* root) {
        if (!root)  return;
        move(root);
    }
};

递归回溯，每层的节点都负责把右子树嫁接到左子树的叶子上，然后把左子树嫁接成为右子树。
if (rightTree == nullptr)这句的作用：回溯时给上一层该子树的叶子用于嫁接，如果原右子树本来就不存在，那么直接返回原左子树的叶子即可；反之，则原右子树的叶子现在成为了新的叶子，应当被返回。

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

class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, int inorderB, int inorderE, vector<int>& preorder, int preorderB, int preorderE) {
        if (preorderB == preorderE) return NULL;
        int rootVal = preorder[preorderB];
        TreeNode* root = new TreeNode(rootVal);
        if (preorderE - preorderB == 1) return root;
        int cutIndex;
        for (cutIndex = inorderB; cutIndex < inorderE; cutIndex++) {
            if (inorder[cutIndex] == rootVal)   break;            
        }
        int leftInB = inorderB;
        int leftInE = cutIndex;
        int rightInB = leftInE + 1;
        int rightInE = inorderE;

        int leftPreB = preorderB + 1;
        int leftPreE = preorderB + 1 + cutIndex - leftInB;
        int rightPreB = leftPreE;
        int rightPreE = preorderE;

        root->left = traversal(inorder, leftInB, leftInE, preorder, leftPreB, leftPreE);
        root->right = traversal(inorder, rightInB, rightInE, preorder, rightPreB, rightPreE);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0) return NULL;
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
    }
};

公式题，递归，每个节点从前序的首个数出现在中序的位置作为分割点，分割两个数组为4个数组（两对左右序列），分割后取前序的两个子序列各自的首个元素作为左右孩子。如此往复继续分割左右序列。

437. 路径总和 III

class Solution {
public:
    int result = 0;
    void find(TreeNode* node, unordered_map<long long, int> hashSum, long long curSum, int targetSum) {
        if (node == NULL)   return;
        curSum += node->val;            // 更新当前和
        if (hashSum.find(curSum - targetSum) != hashSum.end()) { // 前缀和之差是目标值即可
            result += hashSum[curSum - targetSum];
        }
        hashSum[curSum]++;          // 最后再计入当前和（防止目标是0）
        find(node->left, hashSum, curSum, targetSum);
        find(node->right, hashSum, curSum, targetSum);
    }
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> hashSum;        // 记录前缀和及其次数
        hashSum[0] = 1;
        find(root, hashSum, 0, targetSum);
        return result;
    }
};

递归，每层每个节点都知道前面的所有前缀和，前缀和之差是目标和就说明路径正确，一条路上有可能有多次符合所以要用哈希映射计数。然后再把该节点更新后得到的信息传递下去。
初始化时hashSum[0] = 1防止漏掉根节点就是目标值的情况。

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

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

回溯，每个节点查找左右子树有没有q、p，当左子树存在q/p，返回左孩子节点（不一定是q、p本身）；右子树同理；当该节点左右子树各自存在q/p，当前节点就是目标节点了，把当前节点回溯上去即可。

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

class Solution {
public:
    int maxSum = INT_MIN;
    int find(TreeNode* node) {
        if (node == NULL)   return 0;
        int leftMax = max(0, find(node->left));     // 排除负数，最差也是0
        int rightMax = max(0, find(node->right));
        maxSum = max(maxSum, leftMax + rightMax + node->val);   // 更新最大路径
        return node->val + max(leftMax, rightMax);      // 给父节点的只能是大的那一边
    }
    int maxPathSum(TreeNode* root) {
        find(root);
        return maxSum;
    }
};

和二叉树直径同理，递归回溯，每个节点查找左右子树最大路径和，然后将该节点值加上两边最大和，更新最大路径。最后回溯给上面的只能是和更大的一边子树（记得加上本节点）。
和二叉树直径那题的区别就是，排除负数和的子树，也就是当有一边子树得到的路径和是负数，就不参与求和，因为纯纯是负作用。