跳至主要内容

523. Continuous Subarray Sum

· 閱讀時間約 1 分鐘
  • 如果子數列各個元素除以 k 的餘數和，可以被 k 整除的話，則連續子數列的總和必定可以被 k 整除。
  • 初始化一個 Map modSeen 儲存 {餘數: index}。
  • edge case: modSeen[0] = -1
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k)
    {
        int n = nums.size();
        int prefixMod = 0;
        unordered_map<int, int> modSeen;

        modSeen[0] = -1;

        for (int i = 0; i < n; ++i)
        {
            prefixMod = (prefixMod + nums[i]) % k;
            if (modSeen.count(prefixMod))
            {
                if (i - modSeen[prefixMod] > 1)
                {
                    return true;
                }
            }
            else
            {
                modSeen[prefixMod] = i;
            }
        }
        return false;
    }
};```


- T: $O(n)$
- S: $O(n)$

509. Fibonacci Number

· 閱讀時間約 2 分鐘

Recursion

/*
 * @lc app=leetcode id=509 lang=cpp
 *
 * [509] Fibonacci Number
 *
 * https://leetcode.com/problems/fibonacci-number/description/
 *
 * algorithms
 * Easy (72.00%)
 * Likes:    8563
 * Dislikes: 381
 * Total Accepted:    2.3M
 * Total Submissions: 3.1M
 * Testcase Example:  '2'
 *
 * The Fibonacci numbers, commonly denoted F(n) form a sequence, called the
 * Fibonacci sequence, such that each number is the sum of the two preceding
 * ones, starting from 0 and 1. That is,
 *
 *
 * F(0) = 0, F(1) = 1
 * F(n) = F(n - 1) + F(n - 2), for n > 1.
 *
 *
 * Given n, calculate F(n).
 *
 *
 * Example 1:
 *
 *
 * Input: n = 2
 * Output: 1
 * Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
 *
 *
 * Example 2:
 *
 *
 * Input: n = 3
 * Output: 2
 * Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
 *
 *
 * Example 3:
 *
 *
 * Input: n = 4
 * Output: 3
 * Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
 *
 *
 *
 * Constraints:
 *
 *
 * 0 <= n <= 30
 *
 *
 */

// @lc code=start
class Solution {
public:
    int fib(int n)
    {
        if(n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }
};
// @lc code=end
  • T: $O(2^N)$
  • S: $O(N)$

DP

class Solution {
public:
    int fib(int n)
    {
        if(n < 2) return n;
        vector<int> dp(n + 1);
        dp[0] = 0, dp[1] = 1;
        for(int i = 2; i < n + 1; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
  • T: $O(N)$
  • S: $O(N)$

DP improved

class Solution {
public:
    int fib(int n)
    {
        if(n < 2) return n;
        int first = 1, second = 1;
        for(int i = 2; i < n; i++)
        {
            int temp = first;
            first = first + second;
            second = temp;
        }
        return first;
    }
};
  • T: $O(N)$
  • S: $O(1)$

502. IPO

· 閱讀時間約 1 分鐘
class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();

        // 將 {capital, profits} pair 在一起比較好處理 (排序)
        vector<pair<int, int>> projects;

        for (int i = 0; i < n; i++)
        {
            projects.push_back({capital[i], profits[i]});
        }

        // 排序後，capital 小的會放前面
        sort(projects.begin(), projects.end());

        priority_queue<int> q;

        int j = 0;

        // 最多 k 個專案
        for (int i = 0; i < k; i++)
        {
            // 當啟動 project 的成本 projects[ptr].first 小於等於 w 的時候
            while (j < n && projects[j].first <= w)
            {
                // 將獲得的利潤推到 queue
                q.push(projects[j].second);
                // 指標++，移動到下一個 project
                j++;
            }
            // 直到 queue 裡面沒有 project
            if (q.empty()) break;

            // 將獲得的利潤加到 w
            w += q.top(); q.pop();
        }
        // 最後 return 總共獲得多少的資金 w
        return w;
    }
};
  • T: $O(n \cdot \log n)$
  • S: $O(n)$

494. Target Sum

· 閱讀時間約 2 分鐘

2-D DP

/*
 * @lc app=leetcode id=494 lang=cpp
 *
 * [494] Target Sum
 *
 * https://leetcode.com/problems/target-sum/description/
 *
 * algorithms
 * Medium (47.77%)
 * Likes:    11630
 * Dislikes: 387
 * Total Accepted:    813.1K
 * Total Submissions: 1.6M
 * Testcase Example:  '[1,1,1,1,1]\n3'
 *
 * You are given an integer array nums and an integer target.
 *
 * You want to build an expression out of nums by adding one of the symbols '+'
 * and '-' before each integer in nums and then concatenate all the
 * integers.
 *
 *
 * For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1
 * and concatenate them to build the expression "+2-1".
 *
 *
 * Return the number of different expressions that you can build, which
 * evaluates to target.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,1,1,1,1], target = 3
 * Output: 5
 * Explanation: There are 5 ways to assign symbols to make the sum of nums be
 * target 3.
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1], target = 1
 * Output: 1
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 20
 * 0 <= nums[i] <= 1000
 * 0 <= sum(nums[i]) <= 1000
 * -1000 <= target <= 1000
 *
 *
 */

// @lc code=start
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        int n = nums.size();
        vector<unordered_map<int, int>> dp(n + 1);

        dp[0][0] = 1;

        for(int i = 0; i < n; ++i)
        {

            for(auto a : dp[i])
            {
                int sum = a.first, count = a.second;
                dp[i + 1][sum + nums[i]] += count;
                dp[i + 1][sum - nums[i]] += count;
            }
        }
        return dp[n][target];
    }
};
// @lc code=end
  • T: $O(T \cdot N)$
  • S: $O(T \cdot N)$

Space improved

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        dp[0] = 1;

        for (int num : nums) {
            unordered_map<int, int> next_dp;
            for (const auto& [s, cnt] : dp) {
                next_dp[s + num] += cnt;
                next_dp[s - num] += cnt;
            }
            dp = move(next_dp);
        }
        return dp[target];
    }
};
  • T: $O(T \cdot N)$
  • S: $O(T)$

474. Ones and Zeroes

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=474 lang=cpp
 *
 * [474] Ones and Zeroes
 *
 * https://leetcode.com/problems/ones-and-zeroes/description/
 *
 * algorithms
 * Medium (48.13%)
 * Likes:    5530
 * Dislikes: 469
 * Total Accepted:    226.2K
 * Total Submissions: 468K
 * Testcase Example:  '["10","0001","111001","1","0"]\n5\n3'
 *
 * You are given an array of binary strings strs and two integers m and n.
 *
 * Return the size of the largest subset of strs such that there are at most m
 * 0's and n 1's in the subset.
 *
 * A set x is a subset of a set y if all elements of x are also elements of
 * y.
 *
 *
 * Example 1:
 *
 *
 * Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
 * Output: 4
 * Explanation: The largest subset with at most 5 0's and 3 1's is {"10",
 * "0001", "1", "0"}, so the answer is 4.
 * Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
 * {"111001"} is an invalid subset because it contains 4 1's, greater than the
 * maximum of 3.
 *
 *
 * Example 2:
 *
 *
 * Input: strs = ["10","0","1"], m = 1, n = 1
 * Output: 2
 * Explanation: The largest subset is {"0", "1"}, so the answer is 2.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= strs.length <= 600
 * 1 <= strs[i].length <= 100
 * strs[i] consists only of digits '0' and '1'.
 * 1 <= m, n <= 100
 *
 *
 */

// @lc code=start
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (const auto& s : strs)
        {
            int zeros = 0, ones = 0;
            for (const auto& c : s)
            {
                c == '0' ? ++zeros : ++ones;
            }
            for (int i = m; i >= zeros; --i)
            {
                for (int j = n; j >= ones; --j)
                {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
};
// @lc code=end
  • T: $O(L \cdot M \cdot N)$
  • S: $O(M \cdot N)$

452. Minimum Number of Arrows to Burst Balloons

· 閱讀時間約 2 分鐘

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6]. - Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]] Output: 4 Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3]. - Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

  • 1 <= points.length <= 105
  • points[i].length == 2
  • -231 <= xstart < xend <= 231 - 1
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;

        // 排序氣球
        sort(points.begin(), points.end());

        int res = 1; // 最少需要一個飛鏢
        int lastEnd = points[0][1];

        for (int i = 1; i < points.size(); ++i) {
            // 如果發現當前的區間的起始點比 end 小的話
            // 代表有 overlap
            if (points[i][0] <= lastEnd) {
                // 更新 last end，找到比較小的那個 last end
                lastEnd = min(lastEnd, points[i][1]);
            } else {
                // 如果發現當前的區間的起始點比 end 大的話
                // 需要再多一個飛鏢
                ++res;
                // 更新 last end
                lastEnd = points[i][1];
            }
        }
        return res;
    }
};
  • T: $O(n \cdot \log n)$
  • S: $O(n)$

435. Non-overlapping Intervals

· 閱讀時間約 1 分鐘

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 先進行排序
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        int res = 0;
        int lastEnd = intervals[0][1];
        for(int i = 1; i < n; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if(start >= lastEnd) {
                lastEnd = end;
            } else {
                ++res;
                lastEnd = min(lastEnd, end);
            }
        }
        return res;
    }
};
  • T: $O(N \cdot \log N)$
  • S: $O(1)$

424. Longest Repeating Character Replacement

· 閱讀時間約 1 分鐘
  • 求最長的重複子字串，可替換 k 次。
  • 初始化兩個指標 i 和 j 分別作為滑動視窗的左右邊界，初始時都指向字串的起始位置。
  • 初始化一個 unordered_map<char, int> charCount。
  • maxCnt 變數為當前滑動視窗中出現次數最多的字元的次數，要不斷更新 maxCnt 的值。
  • 什麼情況滑動視窗的左邊界要往右移呢？當發現滑動視窗的長度 - 出現最多頻率的字母 > 可以替換的字母 k 的時候
class Solution {
public:
    int characterReplacement(string s, int k)
    {
        int n = s.size();
        int longest = 0, maxCnt = 0;
        unordered_map<char, int> charCount;

        // i, j 分別是滑動視窗的左右邊界
        int i = 0;
        for (int j = 0; j < n; ++j)
        {
            // 右邊界的 freq + 1
            ++charCount[s[j]];

            // 更新 maxCnt 變數為當前滑動視窗中出現次數最多的字元的次數
            maxCnt = max(maxCnt, charCount[s[j]]);

            while (j - i + 1 - maxCnt > k)
            {
                // 移動左邊界
                // 左邊界字母的頻率 - 1
                --charCount[s[i]];
                ++i;
            }
            longest = max(longest, j - i + 1);
        }
        return longest;
    }
};
  • T: $O(n)$
  • S: $O(n)$

417. Pacific Atlantic Water Flow

· 閱讀時間約 3 分鐘

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

image

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below: [0,4]: [0,4] -> Pacific Ocean   [0,4] -> Atlantic Ocean [1,3]: [1,3] -> [0,3] -> Pacific Ocean   [1,3] -> [1,4] -> Atlantic Ocean [1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean   [1,4] -> Atlantic Ocean [2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean   [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean [3,0]: [3,0] -> Pacific Ocean   [3,0] -> [4,0] -> Atlantic Ocean [3,1]: [3,1] -> [3,0] -> Pacific Ocean   [3,1] -> [4,1] -> Atlantic Ocean [4,0]: [4,0] -> Pacific Ocean [4,0] -> Atlantic Ocean Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]] Output: [[0,0]] Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints:

  • m == heights.length
  • n == heights[r].length
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 105
class Solution {
public:
    vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();
        if(rows == 0 || cols == 0) return {};

        vector<vector<int>> res;

        // 分別用兩個矩陣紀錄這個格子有沒有比其他格子高
        // 起始值都是 false
        vector<vector<bool>> pacific(rows, vector<bool>(cols));
        vector<vector<bool>> atlantic(rows, vector<bool>(cols));

        // by rows 開始搜索，如果發現這個格子比周圍的格子高，就標記 true
        // 因為要找比周圍格子高的值，起始值用 INT_MIN
        for(int i = 0; i < rows; ++i) {
            dfs(heights, pacific, INT_MIN, i, 0);
            dfs(heights, atlantic, INT_MIN, i, cols - 1);
        }

        // by cols 開始搜索，如果發現這個格子比周圍的格子高，就標記 true
        // 因為要找比周圍格子高的值，起始值用 INT_MIN
        for(int j = 0; j < cols; ++j) {
            dfs(heights, pacific, INT_MIN, 0, j);
            dfs(heights, atlantic, INT_MIN, rows - 1, j);
        }

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(pacific[i][j] && atlantic[i][j]) {
                    res.push_back({i, j});
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& seen, int previous, int i, int j) {
        int rows = heights.size(), cols = heights[0].size();
        if(i < 0 || j < 0 || i >= rows || j >= cols || seen[i][j] || heights[i][j] < previous)
            return;

        // 標記這個格子比其他人高
        seen[i][j] = true;

        // 四個方向深度搜索
        for(auto& dir : directions)
            dfs(heights, seen, heights[i][j], i + dir[0], j + dir[1]);
    }
};
  • T: $O(M \cdot N)$
  • S: $O(M \cdot N)$