268 篇文章 含有標籤「leetcode」

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        int sum = 0;
        unordered_map<int, int> m{{0, -1}};
        for (int i = 0; i < n; ++i) {
            // 遇到 1 就 +1，遇到 0 就 -1
            sum += (nums[i] == 1) ? 1 : -1;
            // 如果加起來的總和不等於 0 的話
            // 目前的長度為目前的 index i 減掉 m[sum]
            if (m.count(sum)) {
                res = max(res, i - m[sum]);
            } else {
                // 如果加起來的總和等於 0 的話，其值為目前的 index
                m[sum] = i;
            }
        }
        // nums = [0,1,0]
        // m = {{-1: 0}, {0: -1}}

        // nums = [0, 0, 0, 1, 1, 1]
        // m = {{-2: 1}, {-1: 0}, {-3: 2}, {0: -1}}
        return res;
    }
};

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)$

/*
 * @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

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];
    }
};

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

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

/*
 * @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

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];
    }
};

/*
 * @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

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

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