268 篇文章 含有標籤「leetcode」

/**
 * 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* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

class Solution {
public:
    bool lemonadeChange(vector<int>& bills)
    {
        int coin5 = 0;
        int coin10 = 0;

        for (const auto& b : bills)
        {
            if (b == 5)
            {
                coin5++;
            }
            else if (b == 10)
            {
                if (coin5 > 0)
                {
                    coin5--;
                    coin10++;
                }
                else return false;
            }
            else if (b == 20)
            {
                if (coin10 > 0 && coin5 > 0)
                {
                    coin5--;
                    coin10--;
                }
                else if (coin5 >= 3)
                {
                    coin5 -= 3;
                }
                else return false;
            }
        }
        return true;
    }
};

/*
 * @lc app=leetcode id=856 lang=cpp
 *
 * [856] Score of Parentheses
 *
 * https://leetcode.com/problems/score-of-parentheses/description/
 *
 * algorithms
 * Medium (63.90%)
 * Likes:    5526
 * Dislikes: 229
 * Total Accepted:    205.7K
 * Total Submissions: 322.7K
 * Testcase Example:  '"()"'
 *
 * Given a balanced parentheses string s, return the score of the string.
 *
 * The score of a balanced parentheses string is based on the following
 * rule:
 *
 *
 * "()" has score 1.
 * AB has score A + B, where A and B are balanced parentheses strings.
 * (A) has score 2 * A, where A is a balanced parentheses string.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: s = "()"
 * Output: 1
 *
 *
 * Example 2:
 *
 *
 * Input: s = "(())"
 * Output: 2
 *
 *
 * Example 3:
 *
 *
 * Input: s = "()()"
 * Output: 2
 *
 *
 *
 * Constraints:
 *
 *
 * 2 <= s.length <= 50
 * s consists of only '(' and ')'.
 * s is a balanced parentheses string.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int scoreOfParentheses(string s) {
        int res = 0;
        stack<int> stk;
        for (auto c : s) {
            if(c == '(') {
                stk.push(res);
                res = 0;
            } else {
                if (res == 0) {
                    res = 1 + stk.top();
                } else {
                    res = res * 2 + stk.top();
                }
                stk.pop();
            }
        }
        return res;
    }
};
// @lc code=end

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        int n = hand.size();
        if(n % groupSize) return false;

        // 使用 TreeMap 計算每個數字的頻率
        // TreeMap 裡面的 key 會從小到大排列
        map<int, int> freq;
        for(auto h : hand) ++freq[h];

        while(!freq.empty()) {
            // TreeMap 的第一個數字，也就是陣列裡最小的數字
            int first = freq.begin()->first;

            // 從 first 當作起始點，遞增到 < first + groupSize
            // 也就是遞增到每個 group 的最大值
            for(int i = first; i < first + groupSize; ++i){

                // 如果 i 不存在 freq 裡的話，代表這個數字已經被其他 group 用完了
                if(!freq.count(i)) {
                    return false;
                }

                // 如果 i 存在在 freq 裡的話，頻率減一
                --freq[i];

                // 頻率扣到為 0 的話，刪除這個 key
                if(freq[i] == 0) {
                    freq.erase(i);
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1;
        int j = t.size() - 1;

        int s_backspace_count = 0;
        int t_backspace_count = 0;

        // 只要其中一個字串沒有掃完，就繼續掃
        while(i >= 0 || j >= 0) {
            while(i >= 0) {
                if(s[i] == '#') {
                    --i;
                    // 要扣掉的數量 + 1
                    ++s_backspace_count;
                } else if(s_backspace_count > 0) {
                    --i;
                    --s_backspace_count;
                } else break;
            }
            while(j >= 0) {
                if(t[j] == '#') {
                    --j;
                    ++t_backspace_count;
                } else if(t_backspace_count > 0) {
                    --j;
                    --t_backspace_count;
                } else break;
            }
            // 如果發現 char 不一樣，直接 return false
            if (i >= 0 && j >= 0 && s[i] != t[j])
                return false;

            // 如果都被扣光光了，檢查 i 跟 j 是否相等
            // 這行可以讓程式 early return
            if(i < 0 || j < 0) return i == j;
            --i; --j;
        }
        return i == j;
    }
};

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        int res = 0;
        for (int i = 0; i < m - 2; i++)
        {
            for (int j = 0; j < n - 2; j++)
            {
                if (isMagicSqures(grid, i, j)) res++;
            }
        }
        return res;
    }

    bool isMagicSqures(vector<vector<int>>& grid, int r, int c)
    {
        vector<bool> seen(10);
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                int num = grid[r + i][c + j];
                if (num < 1 || num > 9) return false;
                if (seen[num]) return false;
                seen[num] = true;
            }
        }

        int postiveDiag = grid[r + 2][c] + grid[r + 1][c + 1] + grid[r][c + 2];
        int negativeDiag = grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2];

        if (postiveDiag != negativeDiag) return false;

        int r1 = grid[r][c] + grid[r + 1][c] + grid[r + 2][c];
        int r2 = grid[r][c + 1] + grid[r + 1][c + 1] + grid[r + 2][c + 1];
        int r3 = grid[r][c + 2] + grid[r + 1][c + 2] + grid[r + 2][c + 2];

        if (r1 != postiveDiag || r2 != postiveDiag || r3 != postiveDiag) return false;

        int c1 = grid[r][c] + grid[r][c + 1] + grid[r][c + 2];
        int c2 = grid[r + 1][c] + grid[r + 1][c + 1] + grid[r + 1][c + 2];
        int c3 = grid[r + 2][c] + grid[r + 2][c + 1] + grid[r + 2][c + 2];

        if (c1 != postiveDiag || c2 != postiveDiag || c3 != postiveDiag) return false;

        return true;
    }
};

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker)
    {
        int n = difficulty.size();

        // {difficulty, profit} pair
        vector<pair<int, int>> jobs;

        for (int i = 0; i < n; ++i)
        {
            jobs.push_back({difficulty[i], profit[i]});
        }

        sort(jobs.begin(), jobs.end());
        sort(worker.begin(), worker.end());

        // 雙指針法
        int res = 0;
        int i = 0;
        int cur = 0;
        for (auto w : worker)
        {
            while (i < n && w >= jobs[i].first)
            {
                cur = max(cur, jobs[i++].second);
            }
            res += cur;
        }
        return res;
    }
};

/**
 * 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 {
    vector<int> v;
public:
    int minDiffInBST(TreeNode* root)
    {
        dfs(root);
        sort(v.begin(), v.end());
        int minDiff = INT_MAX;
        for (int i = 1; i < v.size(); i++)
        {
            minDiff = min(minDiff, v[i] - v[i - 1]);
        }
        return minDiff;
    }
    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
};

/*
 * @lc app=leetcode id=746 lang=cpp
 *
 * [746] Min Cost Climbing Stairs
 *
 * https://leetcode.com/problems/min-cost-climbing-stairs/description/
 *
 * algorithms
 * Easy (66.19%)
 * Likes:    11495
 * Dislikes: 1777
 * Total Accepted:    1.3M
 * Total Submissions: 1.9M
 * Testcase Example:  '[10,15,20]'
 *
 * You are given an integer array cost where cost[i] is the cost of i^th step
 * on a staircase. Once you pay the cost, you can either climb one or two
 * steps.
 *
 * You can either start from the step with index 0, or the step with index 1.
 *
 * Return the minimum cost to reach the top of the floor.
 *
 *
 * Example 1:
 *
 *
 * Input: cost = [10,15,20]
 * Output: 15
 * Explanation: You will start at index 1.
 * - Pay 15 and climb two steps to reach the top.
 * The total cost is 15.
 *
 *
 * Example 2:
 *
 *
 * Input: cost = [1,100,1,1,1,100,1,1,100,1]
 * Output: 6
 * Explanation: You will start at index 0.
 * - Pay 1 and climb two steps to reach index 2.
 * - Pay 1 and climb two steps to reach index 4.
 * - Pay 1 and climb two steps to reach index 6.
 * - Pay 1 and climb one step to reach index 7.
 * - Pay 1 and climb two steps to reach index 9.
 * - Pay 1 and climb one step to reach the top.
 * The total cost is 6.
 *
 *
 *
 * Constraints:
 *
 *
 * 2 <= cost.length <= 1000
 * 0 <= cost[i] <= 999
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        vector<int> dp(cost.size() + 1);
        for (int i = 2; i < cost.size() + 1; ++i)
        {
            int one = dp[i - 1] + cost[i - 1];
            int two = dp[i - 2] + cost[i - 2];
            dp[i] = min(one, two);
        }
        return dp.back();
    }
};
// @lc code=end

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        int one = 0, two = 0;
        for (int i = 2; i <= cost.size(); i++)
        {
            int temp = one;
            one = min(one + cost[i - 1], two + cost[i - 2]);
            two = temp;
        }
        return one;
    }
};