/*
 * @lc app=leetcode id=322 lang=cpp
 *
 * [322] Coin Change
 *
 * https://leetcode.com/problems/coin-change/description/
 *
 * algorithms
 * Medium (45.14%)
 * Likes:    19407
 * Dislikes: 479
 * Total Accepted:    2.1M
 * Total Submissions: 4.6M
 * Testcase Example:  '[1,2,5]\n11'
 *
 * You are given an integer array coins representing coins of different
 * denominations and an integer amount representing a total amount of money.
 *
 * Return the fewest number of coins that you need to make up that amount. If
 * that amount of money cannot be made up by any combination of the coins,
 * return -1.
 *
 * You may assume that you have an infinite number of each kind of coin.
 *
 *
 * Example 1:
 *
 *
 * Input: coins = [1,2,5], amount = 11
 * Output: 3
 * Explanation: 11 = 5 + 5 + 1
 *
 *
 * Example 2:
 *
 *
 * Input: coins = [2], amount = 3
 * Output: -1
 *
 *
 * Example 3:
 *
 *
 * Input: coins = [1], amount = 0
 * Output: 0
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= coins.length <= 12
 * 1 <= coins[i] <= 2^31 - 1
 * 0 <= amount <= 10^4
 *
 *
 */

// @lc code=start
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (const auto& coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};
// @lc code=end

class Solution {
public:
    int coinChange(vector<int>& coins, int amount)
    {
        vector<int> dp(amount + 1, amount + 1);

        dp[0] = 0;
        for (auto& coin : coins)
        {
            for (int i = coin; i <= amount; i++)
            {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

/*
 * @lc app=leetcode id=300 lang=cpp
 *
 * [300] Longest Increasing Subsequence
 *
 * https://leetcode.com/problems/longest-increasing-subsequence/description/
 *
 * algorithms
 * Medium (56.61%)
 * Likes:    21409
 * Dislikes: 467
 * Total Accepted:    2M
 * Total Submissions: 3.5M
 * Testcase Example:  '[10,9,2,5,3,7,101,18]'
 *
 * Given an integer array nums, return the length of the longest strictly
 * increasing subsequence.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [10,9,2,5,3,7,101,18]
 * Output: 4
 * Explanation: The longest increasing subsequence is [2,3,7,101], therefore
 * the length is 4.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [0,1,0,3,2,3]
 * Output: 4
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [7,7,7,7,7,7,7]
 * Output: 1
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 2500
 * -10^4 <= nums[i] <= 10^4
 *
 *
 *
 * Follow up: Can you come up with an algorithm that runs in O(n log(n)) time
 * complexity?
 *
 */

// @lc code=start
class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n, 1);
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};
// @lc code=end

class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> pq;
        pq.push_back(nums[0]);
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > pq.back())
            {
                pq.push_back(nums[i]);
            }
            else
            {
                int j = lower_bound(pq.begin(), pq.end(), nums[i]) - pq.begin();
                pq[j] = nums[i];
            }
        }
        return pq.size();
    }
};

/*
 * @lc app=leetcode id=299 lang=cpp
 *
 * [299] Bulls and Cows
 *
 * https://leetcode.com/problems/bulls-and-cows/description/
 *
 * algorithms
 * Medium (50.76%)
 * Likes:    2549
 * Dislikes: 1804
 * Total Accepted:    412.4K
 * Total Submissions: 802.4K
 * Testcase Example:  '"1807"\n"7810"'
 *
 * You are playing the Bulls and Cows game with your friend.
 *
 * You write down a secret number and ask your friend to guess what the number
 * is. When your friend makes a guess, you provide a hint with the following
 * info:
 *
 *
 * The number of "bulls", which are digits in the guess that are in the correct
 * position.
 * The number of "cows", which are digits in the guess that are in your secret
 * number but are located in the wrong position. Specifically, the non-bull
 * digits in the guess that could be rearranged such that they become bulls.
 *
 *
 * Given the secret number secret and your friend's guess guess, return the
 * hint for your friend's guess.
 *
 * The hint should be formatted as "xAyB", where x is the number of bulls and y
 * is the number of cows. Note that both secret and guess may contain duplicate
 * digits.
 *
 *
 * Example 1:
 *
 *
 * Input: secret = "1807", guess = "7810"
 * Output: "1A3B"
 * Explanation: Bulls are connected with a '|' and cows are underlined:
 * "1807"
 * ⁠ |
 * "7810"
 *
 * Example 2:
 *
 *
 * Input: secret = "1123", guess = "0111"
 * Output: "1A1B"
 * Explanation: Bulls are connected with a '|' and cows are underlined:
 * "1123"        "1123"
 * ⁠ |      or     |
 * "0111"        "0111"
 * Note that only one of the two unmatched 1s is counted as a cow since the
 * non-bull digits can only be rearranged to allow one 1 to be a bull.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= secret.length, guess.length <= 1000
 * secret.length == guess.length
 * secret and guess consist of digits only.
 *
 *
 */

// @lc code=start
class Solution {
public:
    string getHint(string secret, string guess) {
        int n = secret.size();
        int bulls = 0;
        unordered_map<char, int> secret_count, guess_count;
        for (int i = 0; i < n; i++) {
            if (secret[i] == guess[i]) bulls++;
            else {
                secret_count[secret[i]]++;
                guess_count[guess[i]]++;
            }
        }
        int cows = 0;
        for (const auto& [k, v] : guess_count) {
            if (secret_count.count(k)) {
                cows += min(secret_count[k], v);
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};
// @lc code=end

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, int> m1;
        unordered_map<string, int> m2;

        stringstream ss(s);
        int i = 0;
        int n = pattern.size();
        for (string word; ss >> word; ++i) {
            // 如果遇到 i == n 的情況，代表 pattern 已經先到終點了
            // 但 word 還有單字
            if (i == n || m1[pattern[i]] != m2[word]) {
                return false;
            }
            // 更新 index + 1
            m1[pattern[i]] = i + 1;
            m2[word] = i + 1;
        }
        // 最後比較 i 有沒有到達終點
        return i == n;
    }
};

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board)
    {
        int m = board.size(), n = board[0].size();

        // 狀態：
        // 0 -> 目前死的細胞
        // 1 -> 目前活的細胞
        // 2 -> 目前活的，但即將死亡的細胞
        // 3 -> 目前死的，但即將復活的細胞

        // 周圍八個格子
        vector<vector<int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                // 計算活細胞的數量
                int cnt = 0;

                // 走訪目標格子的周圍八個格子
                for (int k = 0; k < 8; ++k)
                {
                    // 新的 x, y
                    int x = i + directions[k][0], y = j + directions[k][1];

                    // 計算活細胞（值為1或2）的數量並存儲在 cnt 中。
                    if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2))
                    {
                        ++cnt;
                    }
                }

                // 如果細胞目前是活的（board[i][j] == 1）且活鄰居數少於2或多於3，則該細胞將變為死（標記為2）。
                if (board[i][j] && (cnt < 2 || cnt > 3))
                {
                    board[i][j] = 2;
                }
                // 如果細胞目前是死的（board[i][j] == 0）且有正好3個活鄰居，則該細胞將變為活（標記為3）。
                else if (!board[i][j] && cnt == 3)
                {
                    board[i][j] = 3;
                }
            }
        }

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                // 標記為2的細胞（原本活的，但應變為死的）會被設置為0。
                if (board[i][j] == 2)
                {
                    board[i][j] = 0;
                }
                // 標記為3的細胞（原本死的，但應變為活的）會被設置為1。
                else if (board[i][j] == 3)
                {
                    board[i][j] = 1;
                }
            }
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                nums[k] = nums[i];
                k++;
            }
        }
        for (int i = k; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

/*
 * @lc app=leetcode id=279 lang=cpp
 *
 * [279] Perfect Squares
 *
 * https://leetcode.com/problems/perfect-squares/description/
 *
 * algorithms
 * Medium (55.19%)
 * Likes:    11357
 * Dislikes: 478
 * Total Accepted:    909.5K
 * Total Submissions: 1.6M
 * Testcase Example:  '12'
 *
 * Given an integer n, return the least number of perfect square numbers that
 * sum to n.
 *
 * A perfect square is an integer that is the square of an integer; in other
 * words, it is the product of some integer with itself. For example, 1, 4, 9,
 * and 16 are perfect squares while 3 and 11 are not.
 *
 *
 * Example 1:
 *
 *
 * Input: n = 12
 * Output: 3
 * Explanation: 12 = 4 + 4 + 4.
 *
 *
 * Example 2:
 *
 *
 * Input: n = 13
 * Output: 2
 * Explanation: 13 = 4 + 9.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= n <= 10^4
 *
 *
 */

// @lc code=start
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};
// @lc code=end

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        // Sort the citations in descending order

        // Initialize the index variable

        // Loop through the sorted citations array
        // Check if the citation count is greater than the current index
            // Increment the index
        // Return the H-Index
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        sort(citations.rbegin(), citations.rend());
        int i = 0;
        while (i < citations.size() && citations[i] > i) ++i;
        return i;
    }
};

class Solution {
public:
    // Function to calculate the H-Index given a list of citation counts
    int hIndex(vector<int>& citations)
    {
        // Map to store the frequency of each citation count

        // Populate the map with citation counts and their frequencies

        // Convert the map to a vector of pairs and sort it in descending order of citation counts
        // m.rbegin() and m.rend() reverse the order of the map

        // Initialize the count of papers that have at least 'cnt' citations

        // Iterate through the sorted list of citation counts and their frequencies
        for ()
        {
            // If the current citation count is greater than the current count plus the number of papers with this citation count
            if ()
            {
                // Increase the count by the number of papers with this citation count
            }
            // If the current citation count is equal to the current count plus the number of papers with this citation count
            else if ()
            {
                // Return the current citation count as the H-Index
            }
            // If the current citation count is less than the current count plus the number of papers with this citation count
            else
            {
                // Return the maximum of the current citation count and the current count as the H-Index
            }
        }
        // If we have iterated through all the citation counts and not returned, return the count as the H-Index
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations)
    {
        map<int, int> m;
        for (int i = 0; i < citations.size(); ++i) ++m[citations[i]];

        vector<pair<int, int>> q(m.rbegin(), m.rend());

        int cnt = 0;
        for (int i = 0; i < q.size(); ++i)
        {
            if (q[i].first > cnt + q[i].second)
            {
                cnt += q[i].second;
            }
            else if (q[i].first == cnt + q[i].second)
            {
                return q[i].first;
            }
            else
            {
                return max(q[i].first, cnt);
            }
        }
        return cnt;
    }
};

/*
 * @lc app=leetcode id=273 lang=cpp
 *
 * [273] Integer to English Words
 *
 * https://leetcode.com/problems/integer-to-english-words/description/
 *
 * algorithms
 * Hard (34.09%)
 * Likes:    3738
 * Dislikes: 6794
 * Total Accepted:    544.8K
 * Total Submissions: 1.6M
 * Testcase Example:  '123'
 *
 * Convert a non-negative integer num to its English words representation.
 *
 *
 * Example 1:
 *
 *
 * Input: num = 123
 * Output: "One Hundred Twenty Three"
 *
 *
 * Example 2:
 *
 *
 * Input: num = 12345
 * Output: "Twelve Thousand Three Hundred Forty Five"
 *
 *
 * Example 3:
 *
 *
 * Input: num = 1234567
 * Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty
 * Seven"
 *
 *
 *
 * Constraints:
 *
 *
 * 0 <= num <= 2^31 - 1
 *
 *
 */

// @lc code=start
class Solution {
public:
    string numberToWords(int num) {
       if (num == 0) return "Zero";

        vector<pair<int, string>> units = {
            {1000000000, "Billion"},
            {1000000, "Million"},
            {1000, "Thousand"},
            {1, ""}
        };

        string res;
        for (auto& [val, name] : units) {
            if (num >= val) {
                string segment = helper(num / val);
                res += segment + (name.empty() ? "" : " " + name) + " ";
                num %= val;
            }
        }
        while (!res.empty() && res.back() == ' ') res.pop_back();
        return res;
    }
    string helper(int num) {
        vector<string> below_20 = {
            "", "One", "Two", "Three", "Four", "Five", "Six", "Seven",
            "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",
            "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"
        };
        vector<string> tens = {
            "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
        };
        string res;
        if (num < 20) {
            res = below_20[num];
        } else if (num < 100) {
            res = tens[num / 10];
            if (num % 10 != 0) {
                res += " " + helper(num % 10);
            }
            return res;
        } else {
            res = below_20[num / 100] + " Hundred";
            if (num % 100 != 0) {
                res += " " + helper(num % 100);
            }
        }
        return res;
    }
};
// @lc code=end