268 篇文章 含有標籤「leetcode」

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        // base case
        // 如果 k == n，回傳原數列
        if(k == n) return nums;

        // {數字, 出現的頻率}
        unordered_map<int, int> freq;
        priority_queue<pair<int, int>> q;
        vector<int> res;

        // 算數字出現的頻率
        for(auto num : nums) ++freq[num];

        // 將出現頻率的推到 priority queue 排列
        // 預設是 max heap，由大排到小
        for(auto it : freq) {
            q.push({it.second, it.first});
        }

        for(int i = 0; i < k; i++) {
            // 將出現頻率前 k 的數字推到 res
            res.push_back(q.top().second); q.pop();
        }
        return res;
    }
};

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int size)
    {
        parent.resize(size);
        rank.resize(size, 1);
        for (int i = 0; i < size; ++i)
        {
            parent[i] = i;
        }
    }

    int find(int node)
    {
        if (parent[node] != node)
        {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    void unionNodes(int node1, int node2)
    {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) return;
        if (rank[root1] < rank[root2])
        {
            parent[root1] = root2;
        }
        else if (rank[root1] > rank[root2])
        {
            parent[root2] = root1;
        }
        else
        {
            parent[root2] = root1;
            rank[root1]++;
        }
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges)
    {
        UnionFind uf(n);

        for (const auto& edge : edges)
        {
            uf.unionNodes(edge[0], edge[1]);
        }

        int count = 0;

        for (int i = 0; i < n; ++i)
        {
            if (uf.find(i) == i)
            {
                ++count;
            }
        }
        return count;
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges)
    {
        int count = 0;
        vector<bool> seen(n);
        vector<vector<int>> graph(n);

        for (auto edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        for (int i = 0; i < n; ++i)
        {
            if (!seen[i])
            {
                ++count;
                dfs(graph, seen, i);
            }
        }
        return count;
    }
    void dfs(vector<vector<int>>& graph, vector<bool>& seen, int node)
    {
        if (seen[node]) return;

        seen[node] = true;
        for (int i = 0; i < graph[node].size(); ++i)
        {
            dfs(graph, seen, graph[node][i]);
        }
    }
};

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