268 篇文章 含有標籤「leetcode」

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> st;
        vector<int> res(n);
        for(int i = 0; i < n; i++) {
            // 當遇到溫度是比較高的時候
            while(!st.empty() && temperatures[i] > temperatures[st.top()]) {
                // 拿到前一天的 index
                int previousDay = st.top(); st.pop();

                // 計算 index 差，也就是差幾天
                int dayDiff = i - previousDay;

                // 將結果存到 res
                res[previousDay] = dayDiff;
            }
            // 將 index 存到 stack
            st.push(i);
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        int originalColor = image[sr][sc];
        if (color == originalColor) return image;
        dfs(image, sr, sc, color, originalColor);
        return image;
    }

    void dfs(vector<vector<int>>& image, int i, int j, int color, int originalColor)
    {
        if (i < 0 || j < 0 || i >= image.size() || j >= image[0].size() || image[i][j] == color || image[i][j] != originalColor)
            return;

        image[i][j] = color;

        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (const auto& dir : directions)
        {
            dfs(image, i + dir[0], j + dir[1], color, originalColor);
        }
    }
};

/**
 * 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<ListNode*> splitListToParts(ListNode* head, int k)
    {
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            n++;
            cur = cur->next;
        }

        int splitSize = n / k;
        int remaining = n % k;

        vector<ListNode*> res(k);
        cur = head;
        for (int i = 0; i < k; i++)
        {
            ListNode* partHead = cur;
            int partSize = splitSize + (remaining > 0 ? 1 : 0);
            remaining--;

            for (int j = 0; j < partSize - 1 && cur; j++)
            {
                cur = cur->next;
            }

            if (cur) {
                ListNode* nextPart = cur->next;
                cur->next = nullptr;
                cur = nextPart;
            }
            res[i] = (partHead);
        }
        return res;
    }
};

class UnionFind {
private:
    // Stores the parent of each node
    // Stores the rank (or depth) of each node

public:
    // Constructor: Initialize parent and rank vectors
    UnionFind()
    {
        // Resize parent vector to hold n elements
        // Initialize rank vector with 1 for all elements
        // Set each node to be its own parent
    }

    // Find the root of the set containing x, with path compression
    int find()
    {
    }

    // Union the sets containing n1 and n2
    void unionNodes()
    {
        // Find the root of the set containing n1
        // Find the root of the set containing n2
        // If they are already in the same set, do nothing

        // Union by rank
        if ()
        {
            // Attach smaller tree to larger tree
        }
        else if ()
        {
            // Attach smaller tree to larger tree
        }
        else
        {
            // Attach second tree to first and increase rank
        }
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts)
    {
        // Number of accounts
        // Create UnionFind instance with n nodes
        // Maps email to account index

        // Iterate through each account
        for ()
        {
            // Iterate through each email in the account
            for ()
            {
                if ()
                {
                    // Union the current account with the account that already has this email
                }
                else
                {
                    // Map the email to the current account index
                }
            }
        }

        // Maps root account index to list of emails
        // Collect emails for each connected component
        for ()
        {
        }

        // Result vector to store merged accounts
        // Prepare the final result
        for ()
        {
            // Get the username
            // Initialize group with the username
            // Sort emails in lexicographical order
            // Add emails to group
            // Add group to result
        }
        // Return the merged accounts
    }
};

class UnionFind {
private:
    vector<int> parent; // Stores the parent of each node
    vector<int> rank;   // Stores the rank (or depth) of each node

public:
    // Constructor: Initialize parent and rank vectors
    UnionFind(int n)
    {
        parent.resize(n); // Resize parent vector to hold n elements
        rank.resize(n, 1); // Initialize rank vector with 1 for all elements
        for (int i = 0; i < n; i++) parent[i] = i; // Set each node to be its own parent
    }

    // Find the root of the set containing x, with path compression
    int find(int x)
    {
        if (x != parent[x])
        {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    // Union the sets containing n1 and n2
    void unionNodes(int n1, int n2)
    {
        int p1 = find(n1); // Find the root of the set containing n1
        int p2 = find(n2); // Find the root of the set containing n2
        if (p1 == p2) return; // If they are already in the same set, do nothing

        // Union by rank
        if (rank[p1] > rank[p2])
        {
            parent[p2] = p1; // Attach smaller tree to larger tree
        }
        else if (rank[p1] < rank[p2])
        {
            parent[p1] = p2; // Attach smaller tree to larger tree
        }
        else
        {
            parent[p2] = p1; // Attach second tree to first and increase rank
            rank[p1]++;
        }
    }
};

class Solution {
public:
    // Merge accounts with the same email
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts)
    {
        int n = accounts.size(); // Number of accounts
        UnionFind uf(n); // Create UnionFind instance with n nodes
        unordered_map<string, int> emailMap; // Maps email to account index

        // Iterate through each account
        for (int i = 0; i < n; i++)
        {
            // Iterate through each email in the account
            for (int j = 1; j < accounts[i].size(); j++)
            {
                string email = accounts[i][j];
                if (emailMap.count(email))
                {
                    // Union the current account with the account that already has this email
                    uf.unionNodes(emailMap[email], i);
                }
                else
                {
                    // Map the email to the current account index
                    emailMap[email] = i;
                }
            }
        }

        unordered_map<int, vector<string>> mergeMap; // Maps root account index to list of emails
        // Collect emails for each connected component
        for (auto& [email, accountIdx] : emailMap)
        {
            mergeMap[uf.find(accountIdx)].push_back(email);
        }

        vector<vector<string>> res; // Result vector to store merged accounts
        // Prepare the final result
        for (auto& [accountIndex, emails] : mergeMap)
        {
            string user = accounts[accountIndex][0]; // Get the username
            vector<string> group = {user}; // Initialize group with the username
            sort(emails.begin(), emails.end()); // Sort emails in lexicographical order
            group.insert(group.end(), emails.begin(), emails.end()); // Add emails to group
            res.push_back(group); // Add group to result
        }

        return res; // Return the merged accounts
    }
};

/*
 * @lc app=leetcode id=704 lang=cpp
 *
 * [704] Binary Search
 *
 * https://leetcode.com/problems/binary-search/description/
 *
 * algorithms
 * Easy (58.66%)
 * Likes:    12543
 * Dislikes: 272
 * Total Accepted:    3.1M
 * Total Submissions: 5.3M
 * Testcase Example:  '[-1,0,3,5,9,12]\n9'
 *
 * Given an array of integers nums which is sorted in ascending order, and an
 * integer target, write a function to search target in nums. If target exists,
 * then return its index. Otherwise, return -1.
 *
 * You must write an algorithm with O(log n) runtime complexity.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [-1,0,3,5,9,12], target = 9
 * Output: 4
 * Explanation: 9 exists in nums and its index is 4
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [-1,0,3,5,9,12], target = 2
 * Output: -1
 * Explanation: 2 does not exist in nums so return -1
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 10^4
 * -10^4 < nums[i], target < 10^4
 * All the integers in nums are unique.
 * nums is sorted in ascending order.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                ++left;
            } else {
                --right;
            }
        }
        return -1;
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=695 lang=cpp
 *
 * [695] Max Area of Island
 *
 * https://leetcode.com/problems/max-area-of-island/description/
 *
 * algorithms
 * Medium (72.62%)
 * Likes:    10244
 * Dislikes: 212
 * Total Accepted:    1M
 * Total Submissions: 1.4M
 * Testcase Example:  '[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]'
 *
 * You are given an m x n binary matrix grid. An island is a group of 1's
 * (representing land) connected 4-directionally (horizontal or vertical.) You
 * may assume all four edges of the grid are surrounded by water.
 *
 * The area of an island is the number of cells with a value 1 in the island.
 *
 * Return the maximum area of an island in grid. If there is no island, return
 * 0.
 *
 *
 * Example 1:
 *
 *
 * Input: grid =
 * [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * Output: 6
 * Explanation: The answer is not 11, because the island must be connected
 * 4-directionally.
 *
 *
 * Example 2:
 *
 *
 * Input: grid = [[0,0,0,0,0,0,0,0]]
 * Output: 0
 *
 *
 *
 * Constraints:
 *
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * grid[i][j] is either 0 or 1.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        int maxArea = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                maxArea = max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }

    int dfs(vector<vector<int>>& grid, int i, int j)
    {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0)
        {
            return 0;
        }

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

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        int maxArea = 0;
        vector<vector<int>> directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == 0) continue;
                int area = 1;
                queue<vector<int>> q;
                q.push({i, j});
                grid[i][j] = 0;
                while (!q.empty())
                {
                    auto node = q.front(); q.pop();
                    for (const auto& dir : directions)
                    {
                        int new_i = node[0] + dir[0];
                        int new_j = node[1] + dir[1];
                        if (new_i < 0 || new_j < 0 || new_i >= grid.size() || new_j >= grid[0].size() || grid[new_i][new_j] == 0)
                            continue;

                        grid[new_i][new_j] = 0;
                        area++;
                        q.push({new_i, new_j});
                    }
                }
                maxArea = max(maxArea, area);
            }
        }
        return maxArea;
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // res 最多就 k 的長度
        vector<string> res(k);

        // 計算每個單字的頻率
        unordered_map<string, int> freq;
        for (auto word : words) ++freq[word];

        auto cmp = [](pair<string, int>& a, pair<string, int>& b) {
            // a.second > b.second 比較頻率
            // priority_queue 和 sort custom compare 的順序相反
            // 如果頻率是由小排到大的話，會是 a.second > b.second

            // 如果出現頻率一樣的話，a.second == b.second && a.first < b.first
            // 比較字串
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> pq(cmp);

        for (auto f : freq) {
            pq.push(f);
            // 維持 k 的長度，如果太長就 pop 掉，從頻率少的開始 popup
            if (pq.size() > k) pq.pop();
        }

        // 因為這時候的 priority queue 是從小排到大
        // 所以從 res 的最後面開始裝
        for (int i = res.size() - 1; i >= 0; --i) {
            res[i] = pq.top().first; pq.pop();
        }
        return res;
    }
};

/*
 * @lc app=leetcode id=684 lang=cpp
 *
 * [684] Redundant Connection
 *
 * https://leetcode.com/problems/redundant-connection/description/
 *
 * algorithms
 * Medium (63.65%)
 * Likes:    6822
 * Dislikes: 434
 * Total Accepted:    528K
 * Total Submissions: 798.6K
 * Testcase Example:  '[[1,2],[1,3],[2,3]]'
 *
 * In this problem, a tree is an undirected graph that is connected and has no
 * cycles.
 *
 * You are given a graph that started as a tree with n nodes labeled from 1 to
 * n, with one additional edge added. The added edge has two different vertices
 * chosen from 1 to n, and was not an edge that already existed. The graph is
 * represented as an array edges of length n where edges[i] = [ai, bi]
 * indicates that there is an edge between nodes ai and bi in the graph.
 *
 * Return an edge that can be removed so that the resulting graph is a tree of
 * n nodes. If there are multiple answers, return the answer that occurs last
 * in the input.
 *
 *
 * Example 1:
 *
 *
 * Input: edges = [[1,2],[1,3],[2,3]]
 * Output: [2,3]
 *
 *
 * Example 2:
 *
 *
 * Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
 * Output: [1,4]
 *
 *
 *
 * Constraints:
 *
 *
 * n == edges.length
 * 3 <= n <= 1000
 * edges[i].length == 2
 * 1 <= ai < bi <= edges.length
 * ai != bi
 * There are no repeated edges.
 * The given graph is connected.
 *
 *
 */

// @lc code=start
class UnionFind {
    private:
        vector<int> parent;
        vector<int> rank;
    public:
        UnionFind(int n) {
            parent.resize(n + 1);
            rank.resize(n + 1);
            for (int i = 0; i <= n; ++i) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

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

        void merge(int n1, int n2) {
            int p1 = find(n1);
            int p2 = find(n2);

            if(p1 == p2) return;

            if(rank[p1] > rank[p2]) {
                parent[p2] = p1;
                rank[p1] += rank[p2];
            } else {
                parent[p1] = p2;
                rank[p2] += rank[p1];
            }
        }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        UnionFind uf(n);
        for (const auto& edge : edges) {
            if (uf.find(edge[0]) == uf.find(edge[1])) {
                return edge;
            }
            uf.merge(edge[0], edge[1]);
        }
        return {};
    }
};
// @lc code=end

/**
 * 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) {}
 * };
 */
 #define ll long long

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        // 使用 pair 的結構 {目前的節點, 節點的 index}
        queue<pair<TreeNode*, ll>> q;
        q.push({root, 0});

        ll maxWidth = 0;
        while(!q.empty()) {
            ll qSize = q.size();
            // 最左邊 node 的 index
            ll left = q.front().second;
            // 最右邊 node 的 index
            ll right = q.back().second;

            // 寬度公式：右邊節點的 index - 左邊節點的 index + 1
            maxWidth = max(maxWidth, right - left + 1);

            // 走訪每一層
            for(int i = 0; i < qSize; i++) {
                auto node = q.front(); q.pop();
                // levelIndex = 目前節點的 index - 最左邊節點的 index
                ll levelIndex = node.second - left;
                if(node.first->left) {
                    // 將左邊節點推到 queue
                    q.push({node.first->left, 2 * levelIndex});
                }
                if(node.first->right) {
                    // 將右邊節點推到 queue
                    q.push({node.first->right, 2 * levelIndex + 1});
                }
            }
        }
        return maxWidth;
    }
};