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

#define ll long long

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads)
    {
        vector<ll> city(n);
        // 計算與多少城市相連
        for(auto road : roads)
        {
            city[road[0]]++;
            city[road[1]]++;
        }

        sort(city.begin(), city.end());

        ll res = 0;
        // city = [1, 2, 2, 3, 4]
        //         1, 2, 3, 4, 5
        //         1 + 4 + 6 + 12 + 20 = 43
        // res += 與多少城市相連 * 城市的數目加權
        for (int i = 0; i < n; ++i)
        {
            res += (i + 1) * city[i];
        }
        return res;
    }
};

class Solution {
public:
    string removeDigit(string number, char digit)
    {
        string res;
        for (int i = 0; i < number.size(); i++)
        {
            if (number[i] == digit)
            {
                string temp = number.substr(0, i) + number.substr(i + 1, number.size());
                res = max(res, temp);
            }
        }
        return res;
    }
};