力扣HOT100题目及代码

1
2
3
4
5
6
7
8
9
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); i++) hash[nums[i]] = i;
    for (int i = 0; i < nums.size(); i++) {
        if (hash.count(target - nums[i]) && hash[target - nums[i]] != i)
            return {i, hash[target - nums[i]]};
    }
    return {-1, -1};
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    auto dummy = new ListNode(-1);
    auto p = dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = (n1 + n2 + carry) % 10;
        carry = (n1 + n2 + carry) / 10;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
        p->next = new ListNode(sum);
        p = p->next;
    }
    return dummy->next;
}

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> hash;
    int res = 0;
    for (int i = 0, j = 0; j < s.size(); j++) {
        hash[s[j]]++;
        while (hash[s[j]] > 1) hash[s[i++]]--;
        res = max(res, j - i + 1);
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    vector<int> res;
    int p1 = 0, p2 = 0;
    while (p1 < nums1.size() && p2 < nums2.size()) {
        if (nums1[p1] < nums2[p2])
            res.push_back(nums1[p1++]);
        else
            res.push_back(nums2[p2++]);
    }
    while (p1 < nums1.size()) res.push_back(nums1[p1++]);
    while (p2 < nums2.size()) res.push_back(nums2[p2++]);
    if (res.size() & 1)
        return res[res.size() / 2];
    else
        return (double)(res[res.size() / 2] + res[res.size() / 2 - 1]) / 2;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string longestPalindrome(string s) {
    string res;
    for (int i = 0; i < s.size(); i++) {
        string s1 = helper(s, i, i);
        string s2 = helper(s, i, i + 1);
        res = res.size() > s1.size() ? res : s1;
        res = res.size() > s2.size() ? res : s2;
    }
    return res;
}

string helper(string s, int l, int r) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
    return s.substr(l + 1, r - l - 1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
    dp[0][0] = true;
    for (int i = 2; i <= n; i++)
        if (p[i - 1] == '*') dp[0][i] = dp[0][i - 2];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == p[j - 1] || p[j - 1] == '.')
                dp[i][j] = dp[i - 1][j - 1];
            if (p[j - 1] == '*') {
                if (p[j - 2] != s[i - 1] && p[j - 2] != '.')
                    dp[i][j] = dp[i][j - 2];
                else
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
            }
        }
    }
    return dp[m][n];
}

1
2
3
4
5
6
7
8
9
10
11
12
int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1;
    int res = 0;
    while (l < r) {
        res = max(res, min(height[l], height[r]) * (r - l));
        if (height[l] < height[r])
            l++;
        else
            r--;
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    if (nums.size() < 3) return res;
    sort(nums.begin(), nums.end());  // 为了去重
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        if (i == 0 || nums[i] != nums[i - 1]) { // 第一次去重
            int l = i + 1, r = n - 1;
            while (l < r) {
                if (nums[l] + nums[r] > -nums[i])
                    r--;
                else if (nums[l] + nums[r] < -nums[i])
                    l++;
                else {
                    if (l == i + 1 || nums[l] != nums[l - 1]) { // 第二次去重
                        res.push_back({nums[l], nums[r], nums[i]});
                    }
                    l++, r--;
                }
            }
        }
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<string> res;
// 设置键盘的映射
vector<string> letterCombinations(string digits) {
    if (digits.empty()) return res;
    string path;
    dfs(digits, 0, path);
    return res;
}

void dfs(string& s, int idx, string& path) {
    if (idx == s.size()) {
        res.push_back(path);
        return;
    }

    string t = m[s[idx]];
    for (auto c : t) {
        path.push_back(c);
        dfs(s, idx + 1, path);
        path.pop_back();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (!head) return nullptr;
    auto dummy = new ListNode(-1);
    dummy->next = head;
    auto pre = dummy, cur = head;
    for (int i = 0; i < n; i++) cur = cur->next;
    while (cur) {
        pre = pre->next;
        cur = cur->next;
    }
    pre->next = pre->next->next;
    return dummy->next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isValid(string s) {
    if (s.empty()) return true;
    unordered_map<char, char> m; // 初始化括号对，因为解析的问题没有具体初始化
    stack<char> stk;
    for (auto c : s) {
        if (stk.empty())
            stk.push(c);
        else if (c == m[stk.top()])
            stk.pop();
        else
            stk.push(c);
    }
    return stk.empty();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    auto dummy = new ListNode(-1);
    auto p = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
            p = p->next;
        } else {
            p->next = l2;
            l2 = l2->next;
            p = p->next;
        }
    }
    while (l1) {
        p->next = l1;
        l1 = l1->next;
        p = p->next;
    }
    while (l2) {
        p->next = l2;
        l2 = l2->next;
        p = p->next;
    }
    return dummy->next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<string> res;
// 回溯 做减法
vector<string> generateParenthesis(int n) {
    string path;
    dfs(n, n, path);
    return res;
}

void dfs(int l, int r, string& path) {
    if (l == 0 && r == 0) {
        res.push_back(path);
        return;
    }
    if (l > 0) {
        path.push_back('(');
        dfs(l - 1, r, path);
        path.pop_back();
    }
    if (l < r && r > 0) {
        path.push_back(')');
        dfs(l, r - 1, path);
        path.pop_back();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
ListNode* mergeKLists(vector<ListNode*>& lists) {
    return merge(lists, 0, lists.size() - 1);
}

// 分治 两路两路归并
ListNode* merge(vector<ListNode*>& lists, int l, int r) {
    if (l == r) return lists[l];
    if (l < r) {
        int mid = (l + r) >> 1;
        return mergeLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    return nullptr;
}

ListNode* mergeLists(ListNode* l1, ListNode* l2) {
    auto dummy = new ListNode(-1);
    auto p = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
            p = p->next;
        } else {
            p->next = l2;
            l2 = l2->next;
            p = p->next;
        }
    }
    while (l1) {
        p->next = l1;
        l1 = l1->next;
        p = p->next;
    }
    while (l2) {
        p->next = l2;
        l2 = l2->next;
        p = p->next;
    }
    return dummy->next;
}

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int longestValidParentheses(string s) {
    int l = 0, r = 0, maxLen = 0;
    for (int i = 0; i < s.size(); i++) { // 从左向右统计
        if (s[i] == '(')
            l++;
        else
            r++;
        if (l == r) maxLen = max(maxLen, l + r);
        if (r > l) l = 0, r = 0;
    }
    l = 0, r = 0;
    for (int i = s.size() - 1; i >= 0; i--) { // 从右向左统计
        if (s[i] == ')')
            r++;
        else
            l++;
        if (l == r) maxLen = max(maxLen, l + r);
        if (l > r) l = 0, r = 0;
    }
    return maxLen;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int search(vector<int>& nums, int target) {
    if (!nums.size()) return -1;
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] <= nums.back())
            r = mid;
        else
            l = mid + 1;
    }
    if (target <= nums.back()) {
        r = nums.size() - 1;
    } else {
        l = 0, r--;
    }
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] >= target)
            r = mid;
        else
            l = mid + 1;
    }
    return nums[l] == target ? l : -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> searchRange(vector<int>& nums, int target) {
    if (!nums.size()) return {-1, -1};
    int l = 0, r = nums.size() - 1;
    while (l < r) { // 左边界
        int mid = l + r >> 1;
        if (nums[mid] >= target)
            r = mid;
        else
            l = mid + 1;
    }
    if (nums[l] != target) return {-1, -1};
    int t = l;
    l = 0, r = nums.size() - 1;
    while (l < r) { // 右边界
        int mid = l + r + 1 >> 1;
        if (nums[mid] <= target)
            l = mid;
        else
            r = mid - 1;
    }
    return {t, l};
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    if (!candidates.size()) return res;
    vector<int> path;
    dfs(candidates, 0, target, path);
    return res;
}

void dfs(vector<int>& candidates, int idx, int target, vector<int>& path) {
    if (target == 0) {
        res.push_back(path);
        return;
    }
    for (int i = idx; i < candidates.size(); i++) {
        if (candidates[i] <= target) {
            path.push_back(candidates[i]);
            dfs(candidates, i, target - candidates[i], path);
            path.pop_back();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int trap(vector<int>& height) { // 单调栈
    int res = 0;
    stack<int> stk;
    for (int i = 0; i < height.size(); i++) {
        int last = 0;  // 记录之前的高度
        // 维护一个单调递减栈
        while (stk.size() && height[stk.top()] <= height[i]) {
            int t = stk.top();
            stk.pop();
            // 当前层的雨水
            res += (height[t] - last) * (i - t - 1);
            last = height[t];  // 之前的高度更新为当前高度
        }
        // 右边墙低于左边墙的情况
        if (stk.size()) res += (height[i] - last) * (i - stk.top() - 1);
        stk.push(i);
    }
    return res;
}

// 双指针
int trap(vector<int>& height) {
    if (height.size() < 2) return 0;
    int res = 0, l = 0, r = height.size() - 1, ml = 0, mr = 0;
    while (l < r) {
        if (height[l] < height[r]) { // 当右侧高于左侧，则储水量由左侧的最大值和当前值决定
            if (height[l] >= ml)  // 如果当前值大于左侧的最大值，则没有存储到水，更新左侧最大值
                ml = height[l];
            else // 否则，计算当前墙的储水量
                res += ml - height[l];
            l++;
        } else { // 若果左墙高于右墙，则储水量由右侧最大值和当前墙的高度决定
            if (height[r] >= mr) // 如果当前墙的高度大于右侧最大值，说明当前无储水，更新右侧最大值
                mr = height[r];
            else // 否则利用最大值和当前墙的高度计算当前储水量
                res += mr - height[r];
            r--;
        }
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> res;
vector<bool> st;
vector<vector<int>> permute(vector<int>& nums) {
    vector<int> path;
    st = vector<bool>(nums.size());
    dfs(nums, 0, path);
    return res;
}

void dfs(vector<int>& nums, int idx, vector<int>& path) {
    if (idx == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (!st[i]) {
            path.push_back(nums[i]);
            st[i] = true;
            dfs(nums, idx + 1, path);
            path.pop_back();
            st[i] = false;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void rotate(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    // 对角翻转
    for (int i = 0; i < m; i++) {
        for (int j = i; j < n; j++) {
            int t = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = t;
        }
    }
    // 水平翻转
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n / 2; j++) {
            int t = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1] = t;
        }
    }
}

void rotate(vector<vector<int>>& matrix) {
    if (matrix.size() == 0) {
        return;
    }
    // start 和 end 界定当前圈一行的起始和终止位置
    for (int start = 0, end = matrix.size() - 1; start < end;
            start++, end--) {
        // s,e 用于旋转四个坐标，旋转的次数小于当前圈的长度end
        for (int s = start, e = end; s < end; s++, e--) {
            int temp = matrix[start][s];
            matrix[start][s] = matrix[e][start];
            matrix[e][start] = matrix[end][e];
            matrix[end][e] = matrix[s][end];
            matrix[s][end] = temp;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> hash;
    for (auto s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        hash[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto item : hash) res.push_back(item.second);
    return res;
}

1
2
3
4
5
6
7
8
9
int maxSubArray(vector<int>& nums) {
    int res = INT_MIN, last = 0;
    for (auto n : nums) {
        int t = max(last, 0) + n;
        res = max(res, t);
        last = t;
    }
    return res;
}

1
2
3
4
5
6
7
8
bool canJump(vector<int>& nums) {
    int maxPos = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i > maxPos) return false;
        maxPos = max(maxPos, nums[i] + i);
    }
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static bool cmp(vector<int> a, vector<int> b) { return a[0] < b[0]; }

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> res;
    if (!intervals.size()) return res;
    sort(intervals.begin(), intervals.end(), cmp); // 先排序
    res.push_back(intervals[0]);
    int idx = 0;
    for (int i = 1; i < intervals.size(); i++) {
        if (res[idx][1] >= intervals[i][0])
            res[idx][1] = max(res[idx][1], intervals[i][1]);
        else {
            res.push_back(intervals[i]);
            idx++;
        }
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
int uniquePaths(int m, int n) {
    // 动态规划：状态表示：dp[i][j]表示到达i，j这个位置的所有路径
    vector<vector<int>> dp(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!i || !j)
                dp[i][j] = 1; // base case
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 状态计算
        }
    }
    return dp[m - 1][n - 1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n)); // 表示到达位置i，j的最小路径和
    dp[0][0] = grid[0][0]; // base case
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; // 状态转移
        }
    }
    return dp[m - 1][n - 1];
}

1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2, res;
    for (int i = 3; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
int minDistance(string w1, string w2) {
    int m = w1.size(), n = w2.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 = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; // 插入、删除
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (w1[i - 1] != w2[j - 1])); // 替换
        }
    }
    return dp[m][n];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
void sortColors(vector<int>& nums) {
    int l = 0, r = nums.size() - 1, cur = 0;
    while (cur <= r) {
        if (nums[cur] == 0) {
            swap(nums[cur], nums[l]);
            l++, cur++;
        } else if (nums[cur] == 2) {
            swap(nums[cur], nums[r]);
            r--;
        } else
            cur++;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
string minWindow(string s, string t) {
    unordered_map<char, int> need, window; // 分别记录需要的字符及次数，窗口的字符及次数
    for (auto c : t) need[c]++; // 统计需要的字符
    int l = 0, r = 0, idx = 0; // 左指针，右指针，记录最左侧的索引
    int matched = 0, minLen = INT_MAX; // 匹配的字符数目，最小长度
    while (r < s.size()) {
        auto c = s[r];
        if (need.count(c)) { // 如果需要的字符串中包含c
            window[c]++;
            if (window[c] == need[c]) matched++; // 如果数量相同，说明匹配了一个字符
        }
        r++;
        while(matched== need.size()) { // 如果已经匹配，则缩小窗口
            if (r - l < minLen) { // 更新长度
                minLen = r - l;
                idx = l;
            }
            auto c = s[l];
            if(need.count(c)) { // 缩小窗口
                window[c]--;
                if (window[c] < need[c]) matched--;
            }
            l++;

        }
    }
    return minLen == INT_MAX ? "" : s.substr(idx, minLen);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> path;
    dfs(nums, 0, path);
    return res;
}

void dfs(vector<int>& nums, int idx, vector<int>& path) {
    res.push_back(path);
    for (int i = idx; i < nums.size(); i++) {
        path.push_back(nums[i]);
        dfs(nums, i + 1, path);
        path.pop_back();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
bool exist(vector<vector<char>>& board, string word) {
    if (!board.size() || !board[0].size()) return false;
    m = board.size(), n = board[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == word[0] && dfs(board, i, j, 0, word))
                return true;
        }
    }
    return false;
}

bool dfs(vector<vector<char>>& board, int x, int y, int idx, string& word) {
    if (board[x][y] != word[idx]) return false;
    if (idx == word.size() - 1) return true;
    board[x][y] = '.';
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n)
            if (dfs(board, a, b, idx + 1, word)) return true;
    }
    board[x][y] = word[idx];
    return false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n), right(n);
    stack<int> stk;
    for (int i = 0; i < n; i++) { // 找左边最近的小于当前柱子的位置
        while (stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
        if (stk.empty())
            left[i] = -1;
        else
            left[i] = stk.top();
        stk.push(i);
    }
    while (stk.size()) stk.pop();
    for (int i = n - 1; i >= 0; i--) { // 找右边最近的小于当前柱子的位置
        while (stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
        if (stk.empty())
            right[i] = n;
        else
            right[i] = stk.top();
        stk.push(i);
    }
    int res = 0;
    for (int i = 0; i < n; i++) { // 寻找最大值
        res = max(res, heights[i] * (right[i] - left[i] - 1));
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int maximalRectangle(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<int> dp(n);
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
        }
        res = max(res, largestRectangleArea(dp));
    }
    return res;
}

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n), right(n);
    stack<int> stk;
    for (int i = 0; i < n; i++) {
        while (stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
        if (stk.empty())
            left[i] = -1;
        else
            left[i] = stk.top();
        stk.push(i);
    }
    while (stk.size()) stk.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
        if (stk.empty())
            right[i] = n;
        else
            right[i] = stk.top();
        stk.push(i);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = max(res, heights[i] * (right[i] - left[i] - 1));
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
   public:
    vector<int> res;
    // 递归版本
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }

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

    // 非递归版
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
   public:
    /**
     * 思路：假设n个节点存在二叉搜索树的个数是G(n)，令f(i)表示以i为根节点的二叉搜索树，则：
     * G(n) = f(1) + f(2) + ... + f(n)
     * 当以i为根节点时：f(i) = G(i-1) * G(n-i),左子树有i-1个结点，右子树有n-i个结点
     * 综上有：G(n) = G(0)*G*(n-1) + G(1)*G(n-2) + ... + G(n-1)*G(0) 卡特兰数 
     * 通过dp来实现
     */
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
   public:
    typedef long long LL;
    // 判断当前结点是否在正确的区间
    bool isValidBST(TreeNode* root) { return dfs(root, INT_MIN, INT_MAX); }

    bool dfs(TreeNode* root, LL minV, LL maxV) {
        if (!root) return true;
        if (root->val < minV || root->val > maxV) return false; // 不在正确的区间，返回false
        // 缩小区间 dfs左右子树
        return dfs(root->left, minV, root->val - 1ll) &&
               dfs(root->right, root->val + 1ll, maxV);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
       return dfs(root, root);
    }

    bool dfs(TreeNode* r1, TreeNode* r2) {
        if (!r1 && !r2) return true;
        if (!r1 || !r2) return false;
        if (r1->val != r2->val) return false;
        return dfs(r1->left, r2->right) && dfs(r1->right, r2->left);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            int len = q.size();
            vector<int> t;
            for (int i = 0; i < len; i++) {
                auto node = q.front();
                q.pop();
                t.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(t);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        return max(l, r) + 1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++) pos[inorder[i]] = i;
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) {
        if (pl > pr) return nullptr;
        int val = preorder[pl];
        int k = pos[val];
        int len = k - il;
        auto root = new TreeNode(val);
        root->left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);
        root->right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* pre = nullptr;
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->right);
        flatten(root->left);
        root->right = pre;
        root->left = nullptr;
        pre = root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp_i_0 = 0, dp_i_1 = INT_MIN;
        for (auto p : prices) {
            dp_i_0 = max(dp_i_0, dp_i_1 + p);
            dp_i_1 = max(dp_i_1, -p);
        }
        return dp_i_0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int res = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }
    // 枚举所有的顶点
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int l = dfs(root->left); // 计算左子树最大和
        int r = dfs(root->right); // 计算右子树最大和
        res = max(res, l + r + root->val); //更新答案
        return max(0, max(l, r) + root->val);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
   public:
    /**
     * 使用哈希表
     * 时间复杂度：O(n)
     */
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        for (auto n : nums) hash.insert(n);
        int res = 0;
        for (auto n : hash) { // 注意这儿需要从set中枚举
            if (!hash.count(n - 1)) {  // 从没有比当前数小一的数开始
                int len = 0;
                // 统计以当前数字开始的连续序列长度
                while (hash.count(n)) {
                    len++, n++;
                }
                res = max(res, len);
            }
        }
        return res;
    }

    // 并查集
    unordered_map<int, int> p;
    int longestConsecutive(vector<int>& nums) {
        for (auto n : nums) p[n] = n + 1;
        int res = 0;
        for (auto n : nums) {
            int r = find(n + 1);
            res = max(res, r - n);
        }
        return res;
    }

    int find(int x) {
        return p.count(x) ? p[x] = find(p[x]) : x;
    }
}

1
2
3
4
5
6
7
8
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto n : nums) res ^= n;
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
   public:
    /**
     * 动态规划
     * 状态表示：dp[i]表示字符串前i个字符能否由单词表中的单词表示
     * 状态计算：dp[i] = true 如果前i个字符中从后面拆出来一个单词表中的单词，
     * 并且剩余的字符串dp[i-len(单词)]可以用单词表中单词表示时。
     * 时间复杂度：O(n^2)
     */
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        for (auto d : wordDict) dict.insert(d);
        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.count(s.substr(j, i - j))) { // 满足条件说明，可以表示，设置为true后直接跳出循环。
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto s = head;
        auto f = head;
        while(f && f->next) {
            f = f->next->next;
            s = s->next;
            if (s == f) return true;
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto s = head;
        auto f = head;
        while (f && f->next) {
            f = f->next->next;
            s = s->next;
            if (s == f) break;
        }
        if (!f || !f->next) return nullptr;
        s = head;
        while (s != f) {
            s = s->next;
            f = f->next;
        }
        return s;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class LRUCache {
public:
    typedef pair<int, int> PII;
    unordered_map<int, list<PII>::iterator> m; // 哈希表
    list<PII> cache; // 双向链表
    int cap = 0;

    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        if (m.count(key)) {
            auto t = *m[key]; // 找到双向链表中的结点
            cache.erase(m[key]); // 先删除该节点
            cache.push_front(t);  // 再把节点放在链表头
            m[key] = cache.begin(); // 把哈希表中的值更新为链接头
            return t.second;
        } else return -1;
    }

    void put(int key, int value) {
        if (m.count(key)) { // 如果包含键，则直接删除链表结点
            cache.erase(m[key]);
        } else {
            if (cache.size() == cap) {
                auto last = cache.back(); // 记录最后一个结点的值
                cache.pop_back(); // 删除最后一个结点
                m.erase(last.first); // 删除最后一个结点在哈希表中的键
            }
        }
        cache.push_front({key, value});
        m[key] = cache.begin();
    }
};