268 篇文章 含有標籤「leetcode」

/*
 * @lc app=leetcode id=3175 lang=cpp
 *
 * [3175] Find The First Player to win K Games in a Row
 *
 * https://leetcode.com/problems/find-the-first-player-to-win-k-games-in-a-row/description/
 *
 * algorithms
 * Medium (39.39%)
 * Likes:    127
 * Dislikes: 15
 * Total Accepted:    33.6K
 * Total Submissions: 85.4K
 * Testcase Example:  '[4,2,6,3,9]\n2'
 *
 * A competition consists of n players numbered from 0 to n - 1.
 *
 * You are given an integer array skills of size n and a positive integer k,
 * where skills[i] is the skill level of player i. All integers in skills are
 * unique.
 *
 * All players are standing in a queue in order from player 0 to player n - 1.
 *
 * The competition process is as follows:
 *
 *
 * The first two players in the queue play a game, and the player with the
 * higher skill level wins.
 * After the game, the winner stays at the beginning of the queue, and the
 * loser goes to the end of it.
 *
 *
 * The winner of the competition is the first player who wins k games in a
 * row.
 *
 * Return the initial index of the winning player.
 *
 *
 * Example 1:
 *
 *
 * Input: skills = [4,2,6,3,9], k = 2
 *
 * Output: 2
 *
 * Explanation:
 *
 * Initially, the queue of players is [0,1,2,3,4]. The following process
 * happens:
 *
 *
 * Players 0 and 1 play a game, since the skill of player 0 is higher than that
 * of player 1, player 0 wins. The resulting queue is [0,2,3,4,1].
 * Players 0 and 2 play a game, since the skill of player 2 is higher than that
 * of player 0, player 2 wins. The resulting queue is [2,3,4,1,0].
 * Players 2 and 3 play a game, since the skill of player 2 is higher than that
 * of player 3, player 2 wins. The resulting queue is [2,4,1,0,3].
 *
 *
 * Player 2 won k = 2 games in a row, so the winner is player 2.
 *
 *
 * Example 2:
 *
 *
 * Input: skills = [2,5,4], k = 3
 *
 * Output: 1
 *
 * Explanation:
 *
 * Initially, the queue of players is [0,1,2]. The following process
 * happens:
 *
 *
 * Players 0 and 1 play a game, since the skill of player 1 is higher than that
 * of player 0, player 1 wins. The resulting queue is [1,2,0].
 * Players 1 and 2 play a game, since the skill of player 1 is higher than that
 * of player 2, player 1 wins. The resulting queue is [1,0,2].
 * Players 1 and 0 play a game, since the skill of player 1 is higher than that
 * of player 0, player 1 wins. The resulting queue is [1,2,0].
 *
 *
 * Player 1 won k = 3 games in a row, so the winner is player 1.
 *
 *
 *
 * Constraints:
 *
 *
 * n == skills.length
 * 2 <= n <= 10^5
 * 1 <= k <= 10^9
 * 1 <= skills[i] <= 10^6
 * All integers in skills are unique.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int findWinningPlayer(vector<int>& skills, int k) {
        int winner = 0, winCount = 0;
        for (int i = 1; i < skills.size(); i++) {
            if (skills[winner] > skills[i]) {
                winCount++;
            } else {
                winner = i;
                winCount = 1;
            }
            if (winCount == k) return winner;
        }
        return winner;
    }
};
// @lc code=end

/**
 * 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* insertGreatestCommonDivisors(ListNode* head)
    {
        if (!head->next) return head;

        ListNode* node1 = head;
        ListNode* node2 = head->next;
        while (node2)
        {
            int gcdVal = gcd(node1->val, node2->val);
            ListNode* gcdNode = new ListNode(gcdVal);

            node1->next = gcdNode;
            gcdNode->next = node2;

            node1 = node2;
            node2 = node2->next;
        }
        return head;
    }
};

class Solution {
public:
    int countSeniors(vector<string>& details)
    {
        int cnt = 0;
        for (const auto& s : details)
        {
            int age = (s[11] - '0') * 10 + (s[12] - '0');
            if (age > 60) ++cnt;
        }
        return cnt;
    }
};

/*
 * @lc app=leetcode id=2658 lang=cpp
 *
 * [2658] Maximum Number of Fish in a Grid
 *
 * https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/
 *
 * algorithms
 * Medium (60.32%)
 * Likes:    915
 * Dislikes: 63
 * Total Accepted:    150K
 * Total Submissions: 213.4K
 * Testcase Example:  '[[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]'
 *
 * You are given a 0-indexed 2D matrix grid of size m x n, where (r, c)
 * represents:
 *
 *
 * A land cell if grid[r][c] = 0, or
 * A water cell containing grid[r][c] fish, if grid[r][c] > 0.
 *
 *
 * A fisher can start at any water cell (r, c) and can do the following
 * operations any number of times:
 *
 *
 * Catch all the fish at cell (r, c), or
 * Move to any adjacent water cell.
 *
 *
 * Return the maximum number of fish the fisher can catch if he chooses his
 * starting cell optimally, or 0 if no water cell exists.
 *
 * An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c -
 * 1), (r + 1, c) or (r - 1, c) if it exists.
 *
 *
 * Example 1:
 *
 *
 * Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
 * Output: 7
 * Explanation: The fisher can start at cell (1,3) and collect 3 fish, then
 * move to cell (2,3) and collect 4 fish.
 *
 *
 * Example 2:
 *
 *
 * Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
 * Output: 1
 * Explanation: The fisher can start at cells (0,0) or (3,3) and collect a
 * single fish.
 *
 *
 *
 * Constraints:
 *
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 10
 * 0 <= grid[i][j] <= 10
 *
 *
 */

// @lc code=start
class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int maxFish = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxFish = max(maxFish, dfs(grid, i, j));
                }
            }
        }
        return maxFish;
    }
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
            return 0;
        }
        int numberOfFish = grid[i][j];
        grid[i][j] = 0;

        vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        for (const auto& dir : directions) {
            numberOfFish += dfs(grid, i + dir[0], j + dir[1]);
        }
        return numberOfFish;
    }
};
// @lc code=end

class Solution {
public:
    int passThePillow(int n, int time)
    {
        int rounds = time / (n - 1);
        int steps = time % (n - 1);

        if (rounds % 2 == 0) return steps + 1;
        return n - steps;
    }
};

#define ll long long
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        ll res = 0, sum = 0;
        unordered_map<int, int> freq;
        for(int i = 0; i < k; i++) {
            ++freq[nums[i]];
            sum += nums[i];
        }

        // base case
        if(freq.size() == k)
            res = sum;

        int i = k;
        for(int i = k; i < n; i++) {
            ++freq[nums[i]];
            --freq[nums[i - k]];

            if(freq[nums[i - k]] == 0)
                freq.erase(nums[i - k]);

            sum += nums[i];
            sum -= nums[i - k];
            // 維持 freq 的長度要等於 3
            // 也就是 distinct element = 3
            if(freq.size() == k)
                res = max(res, sum);
        }
        return res;
    }
};

/*
 * @lc app=leetcode id=2390 lang=cpp
 *
 * [2390] Removing Stars From a String
 *
 * https://leetcode.com/problems/removing-stars-from-a-string/description/
 *
 * algorithms
 * Medium (76.60%)
 * Likes:    3086
 * Dislikes: 224
 * Total Accepted:    505.4K
 * Total Submissions: 648.5K
 * Testcase Example:  '"leet**cod*e"'
 *
 * You are given a string s, which contains stars *.
 *
 * In one operation, you can:
 *
 *
 * Choose a star in s.
 * Remove the closest non-star character to its left, as well as remove the
 * star itself.
 *
 *
 * Return the string after all stars have been removed.
 *
 * Note:
 *
 *
 * The input will be generated such that the operation is always possible.
 * It can be shown that the resulting string will always be unique.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: s = "leet**cod*e"
 * Output: "lecoe"
 * Explanation: Performing the removals from left to right:
 * - The closest character to the 1^st star is 't' in "leet**cod*e". s becomes
 * "lee*cod*e".
 * - The closest character to the 2^nd star is 'e' in "lee*cod*e". s becomes
 * "lecod*e".
 * - The closest character to the 3^rd star is 'd' in "lecod*e". s becomes
 * "lecoe".
 * There are no more stars, so we return "lecoe".
 *
 * Example 2:
 *
 *
 * Input: s = "erase*****"
 * Output: ""
 * Explanation: The entire string is removed, so we return an empty string.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= s.length <= 10^5
 * s consists of lowercase English letters and stars *.
 * The operation above can be performed on s.
 *
 *
 */

// @lc code=start
class Solution {
public:
    string removeStars(string s) {
        int cnt = 0;
        string res = "";
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == '*') {
                cnt++;
            } else if (cnt != 0 && s[i] != '*') {
                cnt--; continue;
            } else {
                res += s[i];
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
// @lc code=end

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold)
    {
        nums.push_back(0);
        int n = nums.size();
        stack<int> stk;
        for (int i = 0; i < n; ++i)
        {
            while (!stk.empty() && nums[stk.top()] > nums[i])
            {
                int h = nums[stk.top()]; stk.pop();
                int w = stk.empty() ? i : i - stk.top() - 1;
                if (h * w > threshold)
                {
                    return w;
                }
            }
            stk.push(i);
        }
        return -1;
    }
};

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold)
    {
        nums.push_back(0);
        int n = nums.size();
        stack<int> stk;
        int i = 0;
        while (i < n)
        {
            if (stk.empty() || nums[i] >= nums[stk.top()])
            {
                stk.push(i);
                ++i;
            }
            else
            {
                int h = nums[stk.top()]; stk.pop();
                int w = stk.empty() ? i : i - stk.top() - 1;
                if (h * w > threshold)
                {
                    return w;
                }
            }
        }
        return -1;
    }
};

/**
 * 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:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head)
    {
        int i = 0, j = 0, dir = 0;

        int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        vector<vector<int>> res(m, vector<int>(n, -1));

        while (head)
        {
            res[i][j] = head->val;
            int new_i = i + directions[dir][0];
            int new_j = j + directions[dir][1];

            if (new_i < 0 || new_j < 0 || new_i >= m || new_j >= n || res[new_i][new_j] != -1)
            {
                dir = (dir + 1) % 4;
            }
            i += directions[dir][0];
            j += directions[dir][1];
            head = head->next;
        }

        return res;
    }
};