↓ 跳过正文
3ing の Blog

算法 Hot100

·10596 字·22 分钟· loading ·
算法 热题100
3ing
作者
3ing
Always looking forward to tomorrow.
目录

热题100
#

1. 两数之和 简单题 哈希表
#

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

2. 字母异位词分组 中等题 哈希表
#

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        vector<vector<string>> ans;
        unordered_map<string, vector<string>> map;
        for (int i = 0; i < n; i++) {
            string key = strs[i];
            sort(key.begin(), key.end());
            map[key].push_back(strs[i]);
        }
        for (auto [_, value] : map) {
            ans.push_back(value);
        }
        return ans;
    }
};

3. 最长连续序列 中等题 哈希表
#

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        int n = nums.size();
        int ans = 0;
        for (int num : set) {
            if (!set.count(num - 1)) {
                int curN = num, curL = 1;
                while(set.count(curN + 1)) {
                    curN++;
                    curL++;
                }
                ans = max(ans, curL);
            }
        }
        return ans;
    }
};

4. 移动零 简单题 双指针
#

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

5. 盛最多水的容器 中等题 双指针
#

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

6. 三数之和 中等题 双指针 剪枝
#

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
            if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ans.push_back({nums[i], nums[left], nums[right]}); 
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
        }
        return ans;
    }
};

7. 接雨水 困难题 双指针
#

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

8. 无重复字符的最长子串 中等题 滑动窗口 哈希表
#

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        unordered_map<char, int> map;
        int left = 0, ans = 0;
        for (int right = 0; right < n; right++) {
            map[s[right]]++;
            while (map[s[right]] > 1) {
                map[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

9. 找到字符串中所有字母异位词 中等题 滑动窗口 哈希表
#

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size();
        if (m < n) return {};
        vector<int> ans;
        vector<int> sMap(26), pMap(26);
        for (int i = 0; i < n; i++) {
            pMap[p[i] - 'a']++;
        }
        for (int right = 0; right < m; right++) {
            sMap[s[right] - 'a']++;
            int left = right - n + 1;
            if (left < 0) continue;
            if (sMap == pMap) ans.push_back(left);
            sMap[s[left] - 'a']--;
        }
        return ans;
    }
};

10. 和为 K 的子数组 中等题 前缀和 哈希表
#

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        map[0] = 1;
        int sum = 0, ans = 0;
        for (int n : nums) {
            sum += n;
            if (map.count(sum - k)) {
                ans += map[sum - k];
            }
            map[sum]++;
        }
        return ans;
    }
};

11. 滑动窗口最大值 困难题 滑动窗口 双向队列
#

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        deque<int> q;
        for (int i = 0; i < n; i++) {
            while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            int left = i - k + 1;
            if (q.front() < left) q.pop_front();
            if (left >= 0) ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

12. 最小覆盖子串 困难题 滑动窗口 哈希表
#

class Solution {
public:
    string minWindow(string s, string t) {
        int cnt[128]{};
        for (char c : t) cnt[c]++;
        int left = 0, right = 0;
        int need = t.size(), minLen = INT_MAX, start = 0;
        while (right < s.size()) {
            if (cnt[s[right]] > 0) need--;
            cnt[s[right]]--;
            right++;
            while (need == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
                cnt[s[left]]++;
                if (cnt[s[left]] > 0) need++;
                left++;
            }
        }   
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

13. 最大子数组和 中等题 前缀和 贪心
#

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

14. 合并区间 中等题 排序
#

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end());
        for (vector<int> interval : intervals) {
            int n = ans.size();
            if (!ans.empty() && interval[0] <= ans[n - 1][1]) {
                ans[n - 1][1] = max(interval[1], ans[n - 1][1]);
            } else {
                ans.push_back(interval);
            }
        }
        return ans;
    }
};

15. 轮转数组 中等题 双指针
#

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

16. 除了自身以外数组的乘积 中等题 前缀积 后缀积
#

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

17. 缺失的第一个正数 困难题 原地哈希
#

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

18. 矩阵置零 中等题 矩阵 哈希表
#

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

19. 螺旋矩阵 中等题 矩阵 方向
#

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //右下左上
        vector<int> ans(m * n);
        int dir = 0, i = 0, j = 0;
        for (int k = 0; k < m * n; k++) {
            ans[k] = matrix[i][j];
            matrix[i][j] = INT_MAX;
            int x = i + dirs[dir][0], y = j + dirs[dir][1];
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == INT_MAX) {
                dir = (dir + 1) % 4;
            }
            i += dirs[dir][0];
            j += dirs[dir][1];
        }
        return ans;
    }
};

20. 旋转图像 中等题 矩阵
#

//顺时针
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};
//逆时针
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }   
    }
};

21. 搜索二维矩阵 II 中等题 矩阵 二分查找
#

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

22. 相交链表 简单题 链表 双指针
#

/**
 * 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) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode* p = headA;
        ListNode* q = headB;
        while (p != q) {
            if (p == nullptr) p = headB;
            else p = p->next;
            if (q == nullptr) q = headA;
            else q = q->next;
        }
        return p;
    }
};

23. 反转链表 简单题 链表
#

/**
 * 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* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while (cur != nullptr) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

24. 回文链表 简单题 链表 双指针
#

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            vals.push_back(cur->val);
        }
        int n = vals.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            if (vals[left] != vals[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};
/**
 * 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:
    bool isPalindrome(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *pre = nullptr, *cur = slow, *nex;
        while (cur) {
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        slow = pre;
        while (slow) {
            if (head->val != slow->val) return false;
            head = head->next;
            slow = slow->next;
        }
        return true;
    }
};

25. 环形链表 简单题 快慢指针
#

/**
 * 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) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

26. 环形链表 II 中等题 快慢指针
#

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

27. 合并两个有序链表 简单题 链表 哨兵节点
#

/**
 * 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;
        else cur->next = list2;
        return dummy->next;
    }
};

28. 两数相加 中等题 链表 哨兵节点
#

/**
 * 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* cur = dummy;
        int carry = 0;
        while(l1 || l2 || carry > 0) {
            int sum = carry;
            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }
            ListNode* newNode = new ListNode(sum % 10);
            cur->next = newNode;
            cur = cur->next;
            carry = sum / 10;
        }
        return dummy->next;
    }
};

29. 删除链表的倒数第 N 个结点 中等题 快慢指针 哨兵节点
#

/**
 * 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->next) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummy->next;
    }
};

30. 两两交换链表中的节点 中等题 链表 双指针 哨兵节点
#

/**
 * 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* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;
        while (cur->next && cur->next->next) {
            ListNode* first = cur->next;
            ListNode* second = cur->next->next;
            first->next = second->next;
            second->next = first;
            cur->next = second;
            cur = first;
        }
        return dummy->next;
    }
};

31. K 个一组翻转链表 困难题 链表 哨兵节点
#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* p0 = dummy;
        int n = 0;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            n++;
        }
        ListNode* cur = p0->next;
        while (n >= k) {
            n -= k;
            ListNode* tail = cur;
            ListNode* pre = nullptr;
            for (int i = 0; i < k; i++) {
                ListNode* nxt = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
            }
            p0->next = pre;
            tail->next = cur;
            p0 = tail;
        }
        return dummy->next;
    }
};

32. 随机链表的复制 中等题 链表
#

/*
// 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 == nullptr) {
            return nullptr;
        }
        for (Node* cur = head; cur; cur = cur->next->next) {
            cur->next = new Node(cur->val, cur->next, nullptr);
        }
        for (Node* cur = head; cur; cur = cur->next->next) {
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
        }
        Node* new_head = head->next;
        Node* cur = head;
        for (; cur->next->next; cur = cur->next) {
            Node* copy = cur->next;
            cur->next = copy->next;
            copy->next = copy->next->next;
        }
        cur->next = nullptr;
        return new_head;
    }
};

33. 排序链表 中等题 快慢指针 归并排序
#

/**
 * 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;
        } else {
            cur->next = list2;
        }
        return dummy->next;
    }
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* fast = head->next;
        ListNode* slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* mid = slow->next;
        slow->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        return mergeTwoLists(left, right);
    }
};

34. 合并 K 个升序链表 困难题 链表 归并排序
#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        int n = lists.size();
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; i++) {
                lists[i] = merge2Lists(lists[i], lists[i + k]);
            } 
            n = k;
        }
        return lists[0];
    }
    ListNode* merge2Lists(ListNode* node1, ListNode* node2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (node1 && node2) {
            if (node1->val < node2->val) {
                cur->next = node1;
                node1 = node1->next;
            } else {
                cur->next = node2;
                node2 = node2->next;
            }
            cur = cur->next;
        }
        if (node1) cur->next = node1;
        else cur->next = node2;
        return dummy->next;
    }
};

35. LRU 缓存 中等题 双向链表 哈希表
#

type Node struct {
    key, val int
    prev, next *Node
}

type LRUCache struct {
    Capacity int
    Cache map[int]*Node
    Head *Node
    Tail *Node
}

func Constructor(capacity int) LRUCache {
    head := &Node{}
    tail := &Node{}
    head.next = tail
    tail.prev = head
    return LRUCache{
        Capacity: capacity,
        Cache: make(map[int]*Node),
        Head: head,
        Tail: tail,
    }
}

func (l *LRUCache) addToHead(node *Node) {
    node.prev = l.Head
    node.next = l.Head.next
    l.Head.next.prev = node
    l.Head.next = node
}

func (l *LRUCache) deleteNode(node *Node) {
    node.next.prev = node.prev
    node.prev.next = node.next
}

func (l *LRUCache) Get(key int) int {
    if node, ok := l.Cache[key]; ok {
        l.deleteNode(node);
        l.addToHead(node);
        return node.val
    }
    return -1
}

func (l *LRUCache) Put(key int, value int)  {
    if node, ok := l.Cache[key]; ok {
        node.val = value
        l.deleteNode(node)
        l.addToHead(node)
    } else {
        if len(l.Cache) >= l.Capacity {
            deleteNode := l.Tail.prev
            l.deleteNode(deleteNode)
            delete(l.Cache, deleteNode.key)
        }
        newNode := &Node{key: key, val: value}
        l.addToHead(newNode)
        l.Cache[key] = newNode
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

36. 二叉树的中序遍历 简单题 二叉树 DFS 递归
#

/**
 * 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> ans;
    void dfs(TreeNode* node) {
        if (node == nullptr) return;
        dfs(node->left);
        ans.push_back(node->val);
        dfs(node->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

37. 二叉树的最大深度 简单题 二叉树 DFS 递归
#

/**
 * 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 == nullptr) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left, right) + 1;
    } 
};

38. 翻转二叉树 简单题 二叉树 DFS 递归
#

/**
 * 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 == nullptr) return root;
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

39. 对称二叉树 简单题 二叉树 DFS 递归
#

/**
 * 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 isSame(TreeNode* node1, TreeNode* node2) {
        if (node1 == nullptr || node2 == nullptr) return node1 == node2;
        return isSame(node1->left, node2->right) && isSame(node1->right, node2->left) && node1->val == node2->val;
    }
    bool isSymmetric(TreeNode* root) {
        return isSame(root->left, root->right);
    }
};

40. 二叉树的直径 简单题 二叉树 DFS 递归
#

/**
 * 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 ans = 0;
    int dfs(TreeNode* node) {
        if (node == nullptr) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        ans = max(ans, left + right);
        return max(left, right) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

41. 二叉树的层序遍历 中等题 二叉树 BFS 队列
#

/**
 * 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) {
        if (root == nullptr) return  {};
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> vals;
            for (int i = 0; i < n; i++) {
                TreeNode* node = q.front();
                q.pop();
                vals.push_back(node->val);
                if (node->left != nullptr) q.push(node->left);
                if (node->right != nullptr) q.push(node->right);
            }
            ans.push_back(vals);
        }
        return ans;
    }
};

42. 将有序数组转换为二叉搜索树 简单题 二叉树 DFS 递归
#

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums, 0, nums.size() - 1);
    }
    TreeNode* dfs(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
};

43. 验证二叉搜索树 中等题 二叉树 DFS 递归 前序遍历
#

/**
 * 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:
    long pre = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        if (!isValidBST(root->left)) return false;
        if (root->val <= pre) return false;
        pre = root->val;
        return isValidBST(root->right);
    }
};

44. 二叉搜索树中第 K 小的元素 中等题 二叉树 DFS 递归 中序遍历
#

/**
 * 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 dfs(TreeNode* node, int& k) {
        if (node == nullptr) return -1;
        int left = dfs(node->left, k);
        if (left != -1) return left;
        k--;
        if (k == 0) return node->val;
        return dfs(node->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        return dfs(root, k);
    }
};

45. 二叉树的右视图 中等题 二叉树 DFS 递归
#

/**
 * 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> ans;
    void dfs(TreeNode* node, int depth) {
        if (node == nullptr) return;
        if (depth == ans.size()) ans.push_back(node->val);
        dfs(node->right, depth + 1);
        dfs(node->left, depth + 1);
    }
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) return {};
        dfs(root, 0);
        return ans;
    }
};
/**
 * 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> ans;
    void dfs(TreeNode* node, int depth) {
        if (node == nullptr) return;
        if (depth == ans.size()) ans.push_back(node->val);
        dfs(node->left, depth + 1);
        dfs(node->right, depth + 1);
    }
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) return {};
        dfs(root, 0);
        return ans;
    }
};

46. 二叉树展开为链表 中等题 二叉树 链表 DFS 递归
#

/**
 * 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* head;
    void dfs(TreeNode* node) {
        if (node == nullptr) return;
        dfs(node->right);
        dfs(node->left);
        node->left = nullptr;
        node->right = head;
        head = node;
    }
    void flatten(TreeNode* root) {
        dfs(root);
    }
};

47. 从前序与中序遍历序列构造二叉树 中等题 二叉树 DFS 递归
#

/**
 * 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) {
        return dfs(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode* dfs(vector<int>& preorder, int pL, int pR, vector<int>& inorder, int iL, int iR) {
        if (pL > pR) return nullptr;
        int rootVal = preorder[pL];
        TreeNode* root = new TreeNode(rootVal);
        int idx = iL;
        while (inorder[idx] != rootVal) idx++;
        int leftSize = idx - iL;
        root->left = dfs(preorder, pL + 1, pL + leftSize, inorder, iL, idx -1);
        root->right = dfs(preorder, pL + leftSize + 1, pR, inorder, idx + 1, iR);
        return root; 
    }
};

48. 路径总和 III 中等题 二叉树 DFS 递归
#

/**
 * 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 dfs(TreeNode* node, long targetSum) {
        if (node == nullptr) return 0;
        int ans = 0;
        targetSum -= node->val;
        if (targetSum == 0) {
            ans++;
        }
        ans += dfs(node->left, targetSum);
        ans += dfs(node->right, targetSum);
        return ans;
    }
    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return 0;
        return dfs(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
};

49. 二叉树的最近公共祖先 中等题 二叉树 DFS 递归
#

/**
 * 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 && right != nullptr) return root;
        if (left != nullptr) return left;
        return right;
    }
};

50. 二叉树中的最大路径和 困难题 二叉树 DFS 递归
#

/**
 * 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 ans = INT_MIN;
    int dfs(TreeNode* node) {
        if (node == nullptr) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        ans = max(ans, left + right + node->val);
        return max(0, max(left, right) + node->val);
    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

51. 岛屿数量 中等题 矩阵 DFS 递归
#

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, m, n, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
    void dfs(vector<vector<char>>& grid, int m, int n, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, m, n, i + 1, j);
        dfs(grid, m, n, i - 1, j);
        dfs(grid, m, n, i, j + 1);
        dfs(grid, m, n, i, j - 1);
    }
};

52. 腐烂的橘子 中等题 矩阵 BFS 队列
#

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        int fresh = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        int minute = 0;
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.empty() && fresh != 0) {
            minute++;
            int l = q.size();
            for (int i = 0; i < l; i++) {
                auto [x, y] = q.front();
                q.pop();
                for (auto d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx < 0 || nx >= m || ny <0 || ny >= n || grid[nx][ny] != 1) {
                        continue;
                    }
                    grid[nx][ny] = 2;
                    fresh--;
                    q.push({nx, ny});
                }
            }
        }
        return fresh == 0 ? minute : -1;
    }
};

53. 课程表 中等题 图论 BFS 队列
#

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        for (vector<int>& p : prerequisites) {
            int a = p[0], b = p[1];
            graph[b].push_back(a);
            indegree[a]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.push(i);
        } 
        int count = 0;
        while (!q.empty()) {
            int curCourse = q.front();
            q.pop();
            count++;
            for (int nxt : graph[curCourse]) {
                indegree[nxt]--;
                if (indegree[nxt] == 0) q.push(nxt);
            }
        }
        return count == numCourses;
    }
};

54. 实现 Trie (前缀树) 中等题 哈希表 字典树
#

type Trie struct {
    children [26]*Trie
    isEnd bool    
}

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string)  {
    node := t
    for _, c := range word {
        c -= 'a'
        if node.children[c] == nil {
            node.children[c] = &Trie{}
        }
        node = node.children[c]
    }
    node.isEnd = true;
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
    node := t
    for _, ch := range prefix {
        ch -= 'a'
        if node.children[ch] == nil {
            return nil
        }
        node = node.children[ch]
    }
    return node
}

func (t *Trie) Search(word string) bool {
    node := t.SearchPrefix(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.SearchPrefix(prefix) != nil
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

55. 全排列 中等题 回溯 哈希表
#

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

56. 子集 中等题 回溯 选与不选
#

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void dfs(vector<int>& nums, int i, int n) {
        if (i == n) {
            ans.push_back(path);
            return;
        }
        dfs(nums, i + 1, n);
        path.push_back(nums[i]);
        dfs(nums, i + 1, n);
        path.pop_back();
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0, nums.size());
        return ans;
    }
};

57. 电话号码的字母组合 中等题 回溯 哈希表
#

class Solution {
public:
    string phoneMap[10] = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };
    vector<string> ans;
    string path;
    void dfs(string digits, int i, int n) {
        if (i == n) {
            ans.push_back(path);
            return;
        }
        for (char c : phoneMap[digits[i] - '0']) {
            path.push_back(c);
            dfs(digits, i+1, n);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        int n = digits.size();
        dfs(digits, 0, n);
        return ans;
    }
};

58. 括号生成 中等题 回溯
#

class Solution {
public:
    vector<string> ans;
    string path;
    void dfs(int n, int close, int open) {
        if (close == n) {
            ans.push_back(path);
            return ;
        }
        if (open < n) {
            path.push_back('(');
            dfs(n, close, open + 1);
            path.pop_back();
        }
        if (close < open) {
            path.push_back(')');
            dfs(n, close + 1, open);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) { 
        dfs(n, 0, 0);
        return ans;
    }
};

59. 组合总和 中等题 回溯 选与不选 可重复选
#

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void dfs(vector<int>& candidates, int target, int i, int n) {
        if (i == n || target < 0) return ;
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        dfs(candidates, target, i + 1, n);
        path.push_back(candidates[i]);
        dfs(candidates, target - candidates[i], i, n);
        path.pop_back();
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0, candidates.size());
        return ans;
    }
};

60. 单词搜索 中等题 矩阵 DFS 递归
#

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, m, n, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string word, int m, int n, int i, int j, int idx, vector<vector<bool>>& visited) {
        if (idx == word.size()) return true;
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        bool found = dfs(board, word, m, n, i + 1, j, idx + 1, visited) ||
                     dfs(board, word, m, n, i - 1, j, idx + 1, visited) ||
                     dfs(board, word, m, n, i, j + 1, idx + 1, visited) ||
                     dfs(board, word, m, n, i, j - 1, idx + 1, visited);
        visited[i][j] = false;
        return found;
    }
};

61. 分割回文串 中等题 回溯
#

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    bool isPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    void dfs(string s, int i, int n) {
        if (i == n) {
            ans.push_back(path);
            return;
        }
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j)) {
                path.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1, n);
                path.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        dfs(s, 0, s.size());
        return ans;
    }
};

62. N 皇后 困难题 回溯
#

class Solution {
public:
    vector<vector<string>> ans;
    vector<int> path;
    vector<bool> col, diag1, diag2;
    void dfs(int n, int row) {
        if (row == n) {
            vector<string> board(n, string(n, '.'));
            for (int i = 0; i < n; i++) {
                board[i][path[i]] = 'Q';
            }
            ans.push_back(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (col[c] || diag1[row - c + n] || diag2[row + c])
                continue;
            // 放皇后
            path[row] = c;
            col[c] = diag1[row - c + n] = diag2[row + c] = true;
            dfs(n, row + 1);
            col[c] = diag1[row - c + n] = diag2[row + c] = false;
            path[row] = -1;
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        path = vector<int>(n, -1);
        col = vector<bool>(n, false);
        diag1 = vector<bool>(2 * n, false);
        diag2 = vector<bool>(2 * n, false);
        dfs(n, 0);
        return ans;
    }
};

63. 搜索插入位置 简单题 二分查找
#

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

64. 搜索二维矩阵 中等题 二分查找 矩阵
#

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

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

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

66. 搜索旋转排序数组 中等题 二分查找
#

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

67. 寻找旋转排序数组中的最小值 中等题 二分查找
#

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

68. 寻找两个正序数组的中位数 困难题 二分查找
#

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        if (n1 > n2) return findMedianSortedArrays(nums2, nums1);
        int left = 0, right = n1;
        while (left <= right) {
            int i = (left + right) / 2;
            int j = (n1 + n2 + 1) / 2 - i;
            int L1, R1, L2, R2;
            // nums1 左边界
            if (i == 0) L1 = INT_MIN;        // nums1 左边没有元素
                else L1 = nums1[i - 1];  // nums1 左边最后一个元素
            // nums1 右边界
            if (i == n1) R1 = INT_MAX;       // nums1 右边没有元素
                else R1 = nums1[i];     // nums1 右边第一个元素
            // nums2 左边界
            if (j == 0) L2 = INT_MIN;       // nums2 左边没有元素
                else L2 = nums2[j - 1]; // nums2 左边最后一个元素
            // nums2 右边界
            if (j == n2) R2 = INT_MAX;       // nums2 右边没有元素
                else R2 = nums2[j];     // nums2 右边第一个元素
            if (L1 <= R2 && L2 <= R1) {
                if ((n1 + n2) % 2 == 1) {
                    return max(L1, L2);
                } else {
                    return (max(L1, L2) + min(R1, R2)) / 2.0;
                }
            } 
            else if (L1 > R2) {
                right = i - 1;
            } 
            else {
                left = i + 1;
            }
        }
        return 0.0;
    }
};

69. 有效的括号 简单题 栈 哈希表
#

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char,char> map = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        int n = s.size();
        stack<char> st;
        if (n % 2 != 0) return false;
        for (int i = 0; i < n; i++) {
            if (map.count(s[i]) == 0) {
                st.push(s[i]);
            } else {
                if (st.empty() || st.top() != map[s[i]]) return false;
                st.pop();
            }
        } 
        return st.empty();
    }
};

70. 最小栈 中等题 双栈 设计
#

type MinStack struct {
    stack []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{}
}

func (st *MinStack) Push(val int)  {
    st.stack = append(st.stack, val)
    if len(st.minStack) > 0 {
        top := st.minStack[len(st.minStack) - 1]
        st.minStack = append(st.minStack, min(top, val))
    } else {
        st.minStack = append(st.minStack, val)
    }
}

func (st *MinStack) Pop()  {
    st.stack = st.stack[:len(st.stack) - 1]
    st.minStack = st.minStack[:len(st.minStack) - 1]
}

func (st *MinStack) Top() int {
    return st.stack[len(st.stack) - 1]
}

func (st *MinStack) GetMin() int {
    return st.minStack[len(st.minStack) - 1]
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

71. 字符串解码 中等题 双栈
#

    class Solution {
    public:
        string decodeString(string s) {
            stack<int> numStack;
            stack<string> charStack;
            int num = 0;
            string ans = "";
            int n = s.size();
            for (int i = 0; i < n; i++) {
                if (isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                } else if (s[i] == '[') {
                    numStack.push(num);
                    charStack.push(ans);
                    ans = "";
                    num = 0;
                } else if (s[i] == ']') {
                    int times = numStack.top();
                    numStack.pop();
                    string preStr = charStack.top();
                    charStack.pop();
                    string temp = "";
                    for (int i = 0; i < times; i++) {
                        temp += ans;
                    }
                    ans = preStr + temp;
                } else {
                    ans += s[i];
                }
            }
            return ans;
        }
    };

72. 每日温度 中等题 栈 单调栈
#

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

73. 柱状图中最大的矩形 困难题 栈 单调栈 哨兵节点
#

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;
        heights.push_back(-1);
        int ans = 0;
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int idx = st.top();
                st.pop();
                int h = heights[idx];
                int width;
                if (st.empty()) {
                    width = i;
                } else {
                    width = i - st.top() - 1;
                }
                ans = max(ans, h * width);
            }
            st.push(i);
        }
        return ans;
    }
};

74. 数组中的第K个最大元素 中等题 快速选择
#

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        int n = nums.size();
        return quickSelect(nums, n - k, 0, n - 1);
    }
    int quickSelect(vector<int>& nums, int k, int left, int right) {
        if (left == right) return nums[left];
        int random = left + rand() % (right - left + 1);
        swap(nums[left], nums[random]);
        int pivot = nums[left];
        int i = left - 1, j = right + 1;
        while (true) {
            do i++; while (nums[i] < pivot);
            do j--; while (nums[j] > pivot);
            if (i >= j) break;
            swap(nums[i], nums[j]);
        }
        if (k <= j) return quickSelect(nums, k, left, j);
        else return quickSelect(nums, k, j + 1, right);
    }
};

75. 前 K 个高频元素 中等题 桶排序
#

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int maxCnt = 0;
        for (int x : nums) {
            cnt[x]++;
            maxCnt = max(maxCnt, cnt[x]);
        }
        vector<vector<int>> buckets(maxCnt + 1);
        for (auto& [x, count] : cnt) {
            buckets[count].push_back(x);
        }
        vector<int> ans;
        for (int i = maxCnt; i >= 0 && ans.size() < k; i--) {
            for (int num : buckets[i]) {
                ans.push_back(num);
                if (ans.size() == k) break;
            }
        }
        return ans;
    }
};

76. 数据流的中位数 困难题 堆 设计 大顶堆 小顶堆
#

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;
    MedianFinder() {}
    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }
    double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

77. 买卖股票的最佳时机 简单题 贪心
#

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

78. 跳跃游戏 中等题 贪心
#

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int maxReach = 0;
        for (int i = 0; i < n; i++) {
            if (i <= maxReach) {
                maxReach = max(maxReach, i + nums[i]);
            }
            if (maxReach >= n - 1) return true;
        }
        return false;
    }
};

79. 跳跃游戏 II 中等题 贪心
#


class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        int end = 0;
        int maxReach = 0;
        for (int i = 0; i < n - 1; i++) {
            maxReach = max(maxReach, i + nums[i]);
            // 走到当前跳跃的边界，必须再跳一次
            if (i == end) {
                ans++;
                end = maxReach;
            }
        }
        return ans;
    }
};

80. 划分字母区间 中等题 贪心 哈希表 双指针
#

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.size();
        vector<int> ans;
        unordered_map<char, int> map;
        for(int i = 0; i < n; i++) map[s[i]] = i;;
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            end = max(end, map[s[i]]);
            if (end == i) {
                ans.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return ans;
    }
};

81. 爬楼梯 简单题 dp
#

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

82. 杨辉三角 简单题 dp
#

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> dp(numRows);
        for (int i = 0; i < numRows; i++) {
            dp[i].resize(i + 1, 1);
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        return dp;
    }
};

83. 打家劫舍 中等题 dp
#

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

84. 完全平方数 中等题 dp
#

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

85. 零钱兑换 中等题 dp
#

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

86. 单词拆分 中等题 dp 哈希表
#

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

87. 最长递增子序列 中等题 dp
#

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

88. 乘积最大子数组 中等题 dp 双dp
#

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> dpMax(n), dpMin(n);
        dpMax[0] = dpMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] >= 0) {
                dpMax[i] = max(nums[i], dpMax[i - 1] * nums[i]);
                dpMin[i] = min(nums[i], dpMin[i - 1] * nums[i]);
            } else {
                dpMax[i] = max(nums[i], dpMin[i - 1] * nums[i]);
                dpMin[i] = min(nums[i], dpMax[i - 1] * nums[i]);
            }
        }
        return *max_element(dpMax.begin(), dpMax.end());
    }
};

89. 分割等和子集 中等题 dp
#

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        vector<vector<bool>> dp(n + 1, vector<bool> (target + 1, false));
        dp[0][0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i + 1][j] = dp[i][j];
                if (j >= nums[i]) {
                    dp[i + 1][j] = dp[i + 1][j] || dp[i][j - nums[i]];
                }
            }
        }
        return dp[n][target];
    }
};

90. 最长有效括号 困难题 栈 哨兵节点
#

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int ans = 0;
        stack<int> st;
        st.push(-1);
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                }
                ans = max(ans, i - st.top());
            }
        }
        return ans;
    }
};

91. 不同路径 中等题 dp 多维dp
#

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

92. 最小路径和 中等题 dp 多维dp
#

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

93. 最长回文子串 中等题 双指针 中心扩散算法
#

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            auto [l1, r1] = expandFromCenter(s, i, i);
            auto [l2, r2] = expandFromCenter(s, i, i + 1);
            if (r1 - l1 > end - start) {
                start = l1;
                end = r1;
            }
            if (r2 - l2 > end - start) {
                start = l2;
                end = r2;
            }
        }
        return s.substr(start, end - start + 1);
    }
    pair<int, int> expandFromCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return {left + 1, right - 1};
    }
};

94. 最长公共子序列 中等题 dp 多维dp
#

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.size(), n2 = text2.size();
        vector<vector<int>> dp(n1 + 1, vector<int> (n2 + 1, 0));
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                if (text1[i] == text2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        } 
        return dp[n1][n2];
    }
};

95. 编辑距离 中等题 dp 多维dp
#

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int> (n + 1));
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (word1[i] == word2[j]) {
                    dp[i + 1][j + 1] = dp[i][j];
                } else {
                    dp[i + 1][j + 1] = min({dp[i + 1][j], dp[i][j + 1], dp[i][j]}) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

96. 只出现一次的数字 简单题 位运算
#

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }   
        return ans;
    }
};

97. 多数元素 简单题 排序 哈希表 摩尔投票
#

// 排序
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};
// 哈希表
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            counts[num]++;
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};
// 摩尔投票
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int votes = 0;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            if (votes == 0) {
                candidate = num;
                votes = 1;
            } else if (num == candidate) {
                votes++;
            } else {
                votes--;
            }
        }
        return candidate;
    }
};

98. 颜色分类 中等题 双指针
#

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

99. 下一个排列 中等题 双指针
#

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

100. 寻找重复数 中等题 双指针 快慢指针
#

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

相关文章

算法 2.11

·1054 字·3 分钟· loading
算法
每日算法-2.11

算法 2.10

·1241 字·3 分钟· loading
算法
每日算法-2.10

算法 2.6

·1474 字·3 分钟· loading
算法
每日算法-2.6