力扣Hot100

哈希

两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> st;
        for (int i = 0; i < nums.size(); i++) {
            if (st.find(target - nums[i]) != st.end()) {
                return {i, st[target - nums[i]]};
            } else {
                st[nums[i]] = i;
            }
        }
        return {};
    }
};

字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string> > st;
        for (int i = 0; i < strs.size(); i++) {
            string t = strs[i];
            sort(strs[i].begin(), strs[i].end());
            st[strs[i]].push_back(t);
        }
        vector<vector<string>> res;
        for (auto it: st) {
            res.push_back(it.second);
        }
        return res;
    }
};

最长连续序列

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < nums.size();) {
            int t = 1;
            while (i < nums.size() - 1) {
                if (nums[i] == nums[i + 1]) i++;
                else if (nums[i] == nums[i + 1] - 1) {
                    t++;
                    i++;
                } else break;
            }
            if (t == 1) i++;
            res = max(res, t);
        }
        return res;
    }
};

哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> sets;
        for (auto num: nums) sets.insert(num);
        int res = 0;
        for (auto num: sets) {
            if (!sets.count(num - 1)) {
                int cur = num, t = 1;
                while (sets.count(cur + 1)) {
                    cur++;
                    t++;
                }
                res = max(res, t);
            }
        }
        return res;
    }
};

双指针

移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l = 0, r = 0, n = nums.size();
        while (r < n) {
            if (nums[r]) {
                swap(nums[l], nums[r]);
                l++;
            }
            r++;
        }
    }
};

盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size()-1;
        int res = 0;
        while (l < r) {
            int t = min(height[l], height[r]) * (r - l);
            res = max(res, t);
            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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, int> st;
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) st[nums[i]] = i;
        for (int i = 0; i < nums.size(); i++) {
            if (i != 0 && nums[i] == nums[i-1]) continue;
            for (int j = i + 1; j < nums.size(); j++) {
                if (j != i + 1 && nums[j] == nums[j-1]) continue;
                if (st[-nums[i] - nums[j]] > i && st[-nums[i] - nums[j]] > j) 
                    res.push_back({nums[i], nums[j], -nums[i] - nums[j]});
            }
        }
        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:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        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 j = i + 1, k = n - 1;
            while (j < k) {
                int s = nums[i] + nums[j] + nums[k];
                if (s > 0) k--;
                else if (s < 0) j++;
                else {
                    res.push_back({nums[i], nums[j++], nums[k--]});
                    while(j < k && nums[j] == nums[j - 1]) j++;
                    while(j < k && nums[k] == nums[k + 1]) k--;
                }
            }
        }
        return res;
    }
};

滑动窗口

无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int nums[128];
        int i = 0, j = 0, res = 0;
        while (j < s.size()) {
            nums[s[j]]++;
            while (nums[s[j]] > 1) nums[s[i++]]--;
            res = max(res, j - i + 1);
            j++;
        }
        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:
    vector<int> findAnagrams(string s, string p) {
        int l = 0, r = 0, valid = 0;
        unordered_map<char, int> need, window;
        vector<int> res;
        for (char ch: p) need[ch]++;
        while (r < s.size()) {
            char c = s[r++];
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) valid++;
            }
            while (r - l >= p.size()) {
                if (valid == need.size()) res.push_back(l);
                char d = s[l++];
                if (need.count(d)) {
                    if (window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        return res;
    }
};

字串

和为 K 的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0, s[20005];
        for (int i = 0; i < nums.size(); i++)
            s[i + 1] = s[i] + nums[i];
        unordered_map<int, int> cnt;
        for (int i = 0; i <= nums.size(); i++) {
            if (cnt.contains(s[i] - k)) res += cnt[s[i] - k];
            cnt[s[i]]++;
        }
        return res;
    }
};

滑动窗口最大值

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; i++) q.push({nums[i], i});
        vector<int> res = {q.top().first};
        for (int i = k; i < n; i++) {
            q.push({nums[i], i});
            while (q.top().second <= i - k) 
                q.pop();
            res.push_back(q.top().first);
        }
        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
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        vector<int> res;
        int l = 0;
        for (int i = 0; i < k; i++) {
            while (!q.empty() && nums[i] >= nums[q.back()])
                q.pop_back();
            q.push_back(i);
        }
        res.push_back(nums[q.front()]);
        for (int i = k; i < n; i++) {
            while (!q.empty() && nums[i] >= nums[q.back()])
                q.pop_back();
            q.push_back(i);
            while (q.front() <= i - k)
                q.pop_front();
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};

普通数组

最大子数组和

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp[100005], res = -0x3f3f3f3f;
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) 
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        for (int i = 0; i < nums.size(); i++) 
            res = max(res, dp[i]);
        return res;
    }
};

合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        for (int i = 0; i < intervals.size();) {
            int t = intervals[i][1];
            int j = i + 1;
            while (j < intervals.size() && intervals[j][0] <= t) {
                t = max(t, intervals[j][1]);
                j++;
            }
            res.push_back({intervals[i][0], t});
            i = j;
        };
        return res;
    }
};

轮转数组

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int t[100005], size = nums.size();
        for (int i = 0; i < size; i++) 
            t[(i + k) % size] = nums[i];
        for (int i = 0; i < size; i++) 
            nums[i] = t[i];
    }
};

矩阵

矩阵置零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int row[205], col[205], n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (row[i] || col[j]) matrix[i][j] = 0;
            }
        }
    }
};

螺旋矩阵

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = m - 1, u = 0, d = n - 1;
        vector<int> res;
        while (true) {
            for (int i = l; i <= r; i++) 
                res.push_back(matrix[u][i]);
            u++;
            if (u > d) break;
            for (int i = u; i <= d; i++) 
                res.push_back(matrix[i][r]);
            r--;
            if (l > r) break;
            for (int i = r; i >= l; i--) 
                res.push_back(matrix[d][i]);
            d--;
            if (u > d) break;
            for (int i = d; i >= u; i--) 
                res.push_back(matrix[i][l]);
            l++;
            if (l > r) break;
        }
        return res;
    }
};

链表

二叉树

图论

回溯

二分查找

35. 搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        if (l == nums.size() - 1 && nums[l] < target) return l + 1;
        else return l;
    }
};

74. 搜索二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid].back() < target) l = mid + 1;
            else r = mid;
        }
        int t = l;
        l = 0, r = m - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[t][mid] < target) l = mid + 1;
            else r = mid;
        }
        return matrix[t][l] == target;
    }
};

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

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.empty()) {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        if (nums[l] == target) res.push_back(l);
        else res.push_back(-1);
        l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > target) r = mid - 1;
            else l = mid;
        }
        if (nums[r] == target) res.push_back(l);
        else res.push_back(-1);
        return res;
    }
};

33. 搜索旋转排序数组

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

栈

堆

贪心算法

121. 买卖股票的最佳时机

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int t = prices[0], res = 0;
        for (int i = 0; i < prices.size(); i++) {
            t = min(t, prices[i]);
            res = max(res, prices[i] - t);
        }
        return res;
    }
};

55. 跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int dp[10005] = {0};
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (dp[i - 1] <= 0) return false;
            dp[i] = max(dp[i - 1] - 1, nums[i]); 
        }
        return true;
    }
};

45. 跳跃游戏 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, end = 0, maxa = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            maxa = max(nums[i] + i, maxa);
            if (i == end) {
                end = maxa;
                res++;
            }
        }
        return res;
    }
};

763. 划分字母区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26], n = s.size();
        for (int i = 0; i < n; i++) last[s[i] - 'a'] = i;
        vector<int> res;
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                res.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
};

动态规划

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int climbStairs(int n) {
        int dp[50];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) 
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};

118. 杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        int dp[31][31];
        dp[1][1] = 1;
        for (int i = 2; i <= numRows; i++) {
            for (int j = 1; j <= i; j++) 
                dp[i][j] = dp[i-1][j - 1] + dp[i-1][j];
        }
        for (int i = 1; i <= numRows; i++) {
            vector<int> t;
            for (int j = 1; j <= i; j++) 
                t.push_back(dp[i][j]);
            res.push_back(t);
        }
        return res;
    }
};

198. 打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[105], res;
        if (nums.size() == 1) res = nums[0];
        else if (nums.size() == 2) res = max(nums[0], nums[1]);
        else {
            dp[0] = nums[0];
            dp[1] = max(nums[0], nums[1]);
            for (int i = 2; i < nums.size(); i++) {
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            res = dp[nums.size() - 1];
        }
        return res;
    }
};

279. 完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                minn = min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
};

322. 零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[10005];
        fill(dp, dp + amount + 1, 10005);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i - coins[j] >= 0) dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        if (dp[amount] == 10005) return -1;
        else return dp[amount];
    }
};

139. 单词拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (auto & word: wordDict) {
                int sz = word.size();
                if (i - sz >= 0 && s.substr(i - sz, sz) == word)
                    dp[i] = dp[i] || dp[i - sz];
            }
        }
        return dp[s.size()];
    }
};

多维动态规划

62. 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

64. 最小路径和 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int dp[205][205], n = grid.size(), m = grid[0].size();
        for (int i = 1; i <= m; i++) dp[1][i] = dp[1][i - 1] + grid[0][i - 1];
        for (int i = 1; i <= n; i++) dp[i][1] = dp[i - 1][1] + grid[i - 1][0];
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }
};

技巧

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~