268 篇文章 含有標籤「leetcode」

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        while (arr.size() > k) {
            if (x - arr.front() > arr.back() - x) {
                // 如果 x - arr.front() 的差大於 arr.back() - x 的話
                // 代表 arr.front() 離中心點 x 比較遠
                // 這時候就 erase 前面
                arr.erase(arr.begin());
            } else {
                // 如果 arr.back() - x 的差大於 x - arr.front() 的話
                // 代表 arr.back() 離中心點 x 比較遠
                // 這時候就 pop_back() 後面
                arr.pop_back();
            }
        }
        return arr;
    }
};

/*
 * @lc app=leetcode id=650 lang=cpp
 *
 * [650] 2 Keys Keyboard
 *
 * https://leetcode.com/problems/2-keys-keyboard/description/
 *
 * algorithms
 * Medium (59.60%)
 * Likes:    4264
 * Dislikes: 243
 * Total Accepted:    270.7K
 * Total Submissions: 454.1K
 * Testcase Example:  '3'
 *
 * There is only one character 'A' on the screen of a notepad. You can perform
 * one of two operations on this notepad for each step:
 *
 *
 * Copy All: You can copy all the characters present on the screen (a partial
 * copy is not allowed).
 * Paste: You can paste the characters which are copied last time.
 *
 *
 * Given an integer n, return the minimum number of operations to get the
 * character 'A' exactly n times on the screen.
 *
 *
 * Example 1:
 *
 *
 * Input: n = 3
 * Output: 3
 * Explanation: Initially, we have one character 'A'.
 * In step 1, we use Copy All operation.
 * In step 2, we use Paste operation to get 'AA'.
 * In step 3, we use Paste operation to get 'AAA'.
 *
 *
 * Example 2:
 *
 *
 * Input: n = 1
 * Output: 0
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= n <= 1000
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minSteps(int n)
    {
        int count = 0;
        for (int i = 2; i <= n; i++)
        {
            while (n % i == 0)
            {
                count += i;
                n /= i;
            }
        }
        return count;
    }
};
// @lc code=end

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord = false;
    TrieNode() {
        for(int i = 0; i < 26; i++) {
            child[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for(auto c : word) {
            if(!node->child[c - 'a']) {
                node->child[c - 'a'] = new TrieNode();
            }
            node = node->child[c - 'a'];
        }
        node->isWord = true;
    }

    string searchShortestRoot(string word) {
        TrieNode* node = root;
        // 用一個 prefix 字串儲存最短 root
        string prefix = "";
        for (char c : word) {
            // 當發現沒有在字典樹內的時候，break，並且返回 word
            if (!node->child[c - 'a']) break;
            prefix.push_back(c);
            node = node->child[c - 'a'];
            // 輸入的 word 已經是最短 root 的狀況
            if (node->isWord) return prefix;
        }
        return word;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        stringstream ss(sentence);
        Trie t;
        // 將 root push 到 trie
        for(auto word : dictionary) {
            t.insert(word);
        }
        string token;
        string res;
        // 用 string stream 的方式尋找 word
        // 如果找到的話，replace word with root
        while (getline(ss, token, ' ')) {
            res += t.searchShortestRoot(token) + " ";
        }
        res.pop_back();
        return res;
    }
};

/**
 * 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:
    vector<double> averageOfLevels(TreeNode* root)
    {
        vector<double> res;
        queue<TreeNode*> q{{root}};
        while (!q.empty())
        {
            int qSize = q.size();
            double sum = 0;
            for (int i = 0; i < qSize; ++i)
            {
                TreeNode* node = q.front(); q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(sum / qSize);
        }
        return res;
    }
};

/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        // base case
        if (!subRoot) return true;
        if (!root) return false;

        // 如果相符就 return true
        if (isSame(root, subRoot)) return true;

        // 檢查左邊、檢查右邊，只要其中一邊有 subtree 就 return true
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);

    }
    bool isSame(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        if (t1->val != t2->val) return false;
        return isSame(t1->left, t2->left) && isSame(t1->right, t2->right);
    }
};

/*
 * @lc app=leetcode id=547 lang=cpp
 *
 * [547] Number of Provinces
 *
 * https://leetcode.com/problems/number-of-provinces/description/
 *
 * algorithms
 * Medium (67.05%)
 * Likes:    9841
 * Dislikes: 367
 * Total Accepted:    981.9K
 * Total Submissions: 1.5M
 * Testcase Example:  '[[1,1,0],[1,1,0],[0,0,1]]'
 *
 * There are n cities. Some of them are connected, while some are not. If city
 * a is connected directly with city b, and city b is connected directly with
 * city c, then city a is connected indirectly with city c.
 *
 * A province is a group of directly or indirectly connected cities and no
 * other cities outside of the group.
 *
 * You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the
 * i^th city and the j^th city are directly connected, and isConnected[i][j] =
 * 0 otherwise.
 *
 * Return the total number of provinces.
 *
 *
 * Example 1:
 *
 *
 * Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
 * Output: 2
 *
 *
 * Example 2:
 *
 *
 * Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
 * Output: 3
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= n <= 200
 * n == isConnected.length
 * n == isConnected[i].length
 * isConnected[i][j] is 1 or 0.
 * isConnected[i][i] == 1
 * isConnected[i][j] == isConnected[j][i]
 *
 *
 */

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

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

    void unionNodes(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:
    int findCircleNum(vector<vector<int>>& isConnected)
    {
        int n = isConnected.size();
        UnionFind uf(n);

        int cnt = n;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (isConnected[i][j] && uf.find(i) != uf.find(j))
                {
                    cnt--;
                    uf.unionNodes(i, j);
                }
            }
        }
        return cnt;
    }
};
// @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) {}
 * };
 */
class Solution {
private:
    int diameter = 0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return diameter;
    }

    int dfs(TreeNode* root) {
        if(!root) return 0;
        // 走訪左邊的 tree
        int left = dfs(root->left);

        // 走訪右邊的 tree
        int right = dfs(root->right);

        // 算最大的直徑
        diameter = max(diameter, left + right);

        // 每次遞迴，要記得直徑 + 1
        return 1 + max(left, right);
    }
};

/*
 * @lc app=leetcode id=542 lang=cpp
 *
 * [542] 01 Matrix
 *
 * https://leetcode.com/problems/01-matrix/description/
 *
 * algorithms
 * Medium (49.81%)
 * Likes:    9993
 * Dislikes: 434
 * Total Accepted:    696.7K
 * Total Submissions: 1.4M
 * Testcase Example:  '[[0,0,0],[0,1,0],[0,0,0]]'
 *
 * Given an m x n binary matrix mat, return the distance of the nearest 0 for
 * each cell.
 *
 * The distance between two cells sharing a common edge is 1.
 *
 *
 * Example 1:
 *
 *
 * Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
 * Output: [[0,0,0],[0,1,0],[0,0,0]]
 *
 *
 * Example 2:
 *
 *
 * Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
 * Output: [[0,0,0],[0,1,0],[1,2,1]]
 *
 *
 *
 * Constraints:
 *
 *
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 10^4
 * 1 <= m * n <= 10^4
 * mat[i][j] is either 0 or 1.
 * There is at least one 0 in mat.
 *
 *
 *
 * Note: This question is the same as 1765:
 * https://leetcode.com/problems/map-of-highest-peak/
 *
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
    {
        int m = mat.size(), n = mat[0].size();
        queue<vector<int>> q;
        set<pair<int, int>> used;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j] == 0)
                {
                    q.push({i, j, 0});
                    used.insert({i, j});
                }
            }
        }

        vector<vector<int>> res = mat;
        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 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];
                int dist = node[2] + 1;

                if (new_i < 0 || new_j < 0 || new_i >= m || new_j >= n || used.count({new_i, new_j})) continue;
                q.push({new_i, new_j, dist});
                used.insert({new_i, new_j});
                res[new_i][new_j] = dist;
            }
        }
        return res;
    }
};
// @lc code=end

class Solution {
public:
    int findMinDifference(vector<string>& timePoints)
    {
        int n = timePoints.size();
        vector<int> minutes(n);
        for (int i = 0; i < n; i++)
        {
            int h = stoi(timePoints[i].substr(0, 2));
            int m = stoi(timePoints[i].substr(3));
            minutes[i] = (h * 60 + m);
        }

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

        int res = 1440;
        for (int i = 0; i < n - 1; i++)
        {
            res = min(res, minutes[i + 1] - minutes[i]);
        }
        return min(res, 24 * 60 - (minutes[n - 1] - minutes[0]));
    }
};