268 篇文章 含有標籤「leetcode」

/**
 * 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) {}
 * };
 */
/**
 * 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 isSubPath(ListNode* head, TreeNode* root)
    {
        if (!root) return false;
        return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
    }
    bool dfs(ListNode* head, TreeNode* node)
    {
        if (!head) return true;
        if (!node) return false;
        if (node->val != head->val) return false;
        return dfs(head->next, node->left) || dfs(head->next, node->right);
    }
};

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold)
    {
        // Initialize the distance matrix with a large number

        // Distance from each city to itself is zero

        // Set the distance for each edge in the graph

        // Floyd-Warshall algorithm to find shortest paths between all pairs of cities

        // To store the city with the minimum count of reachable cities
        // To store the minimum number of reachable cities

        // Iterate over each city to find the one with the fewest reachable cities within the threshold
        for ()
        {

            // Count how many cities are reachable within the distance threshold

            // Update the result if this city has fewer reachable cities
        }
        // Return the city with the fewest reachable cities
    }
};

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold)
    {
        vector<vector<int>> dist(n, vector<int>(n, 1e9 + 7));

        for (int i = 0; i < n; i++) dist[i][i] = 0;

        for (const auto& edge : edges)
        {
            int start = edge[0];
            int end = edge[1];
            int weight = edge[2];
            dist[start][end] = weight;
            dist[end][start] = weight;
        }

        for (int k = 0; k < n; ++k)
        {
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int cities = -1;
        int record = n + 1;
        for (int i = 0; i < n; ++i)
        {
            int count = 0;

            for (int j = 0; j < n; ++j)
            {
                if (dist[i][j] <= distanceThreshold) count++;
            }

            if (count <= record)
            {
                record = count;
                cities = i;
            }
        }
        return cities;
    }
};

class Solution {
public:
    string breakPalindrome(string palindrome)
    {
        int n = palindrome.size();
        if (n == 1)
        {
            return "";
        }

        for (int i = 0; i < n / 2; ++i)
        {
            if (palindrome[i] != 'a')
            {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        palindrome.back() = 'b';
        return palindrome;
    }
};

class Solution {
public:
    string reverseParentheses(string s)
    {
        // Stack to keep track of the positions of '('

        // Result string to build the final output

        // Iterate through each character in the input string
        for ()
        {
            if ()
            {
                // When encountering '(', push the current size of res onto the stack
                // This marks the position to start reversing later

            }
            else if ()
            {
                // When encountering ')', get the position of the matching '('

                // Reverse the substring within the parentheses

            }
            else
            {
                // For any other character, append it to the result string

            }
        }
        // Return the final modified string

    }
};

class Solution {
public:
    string reverseParentheses(string s)
    {
        stack<int> stk;
        string res;

        for (char c : s)
        {
            if (c == '(')
            {
                stk.push(res.size());
            }
            else if (c == ')')
            {
                int start = stk.top(); stk.pop();
                reverse(res.begin() + start, res.end());
            }
            else
            {
                res += c;
            }
        }
        return res;
    }
};

/*
 * @lc app=leetcode id=1143 lang=cpp
 *
 * [1143] Longest Common Subsequence
 *
 * https://leetcode.com/problems/longest-common-subsequence/description/
 *
 * algorithms
 * Medium (57.74%)
 * Likes:    13643
 * Dislikes: 199
 * Total Accepted:    1.2M
 * Total Submissions: 2.1M
 * Testcase Example:  '"abcde"\n"ace"'
 *
 * Given two strings text1 and text2, return the length of their longest common
 * subsequence. If there is no common subsequence, return 0.
 *
 * A subsequence of a string is a new string generated from the original string
 * with some characters (can be none) deleted without changing the relative
 * order of the remaining characters.
 *
 *
 * For example, "ace" is a subsequence of "abcde".
 *
 *
 * A common subsequence of two strings is a subsequence that is common to both
 * strings.
 *
 *
 * Example 1:
 *
 *
 * Input: text1 = "abcde", text2 = "ace"
 * Output: 3
 * Explanation: The longest common subsequence is "ace" and its length is 3.
 *
 *
 * Example 2:
 *
 *
 * Input: text1 = "abc", text2 = "abc"
 * Output: 3
 * Explanation: The longest common subsequence is "abc" and its length is 3.
 *
 *
 * Example 3:
 *
 *
 * Input: text1 = "abc", text2 = "def"
 * Output: 0
 * Explanation: There is no such common subsequence, so the result is 0.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= text1.length, text2.length <= 1000
 * text1 and text2 consist of only lowercase English characters.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i < m + 1; ++i)
        {
            for (int j = 1; j < n + 1; ++j)
            {
                if (text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};
// @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 {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        // If the tree is empty, return nullptr

        // Get the depth of the left and right subtrees

        // If the depths are equal, the current node is the LCA of the deepest leaves

        // If the left subtree is deeper, continue the search in the left subtree

        // Otherwise, continue the search in the right subtree
    }

    // This method calculates the depth of a given node
    int getDepth(TreeNode* node)
    {
        // If the node is null, return 0 as the depth
        // Recursively get the depth of the left and right subtrees and add 1 for the current node
    }
};

/**
 * 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:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        if (!root) return nullptr;

        int left = getDepth(root->left);
        int right = getDepth(root->right);

        if (left == right) return root;
        return (left > right) ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);
    }

    int getDepth(TreeNode* node)
    {
        if (!node) return 0;
        return 1 + max(getDepth(node->left), getDepth(node->right));
    }
};

/**
 * 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:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        // Start the depth-first search from the root
    }

    // This method performs a depth-first search and returns a pair containing the LCA and the depth
    pair<TreeNode*, int> dfs(TreeNode* node)
    {
        // If the node is null, return {nullptr, 0} indicating a depth of 0

        // Recursively perform DFS on the left and right subtrees

        // If the left subtree is deeper, return the left LCA and increase the depth by 1
        // If the right subtree is deeper, return the right LCA and increase the depth by 1
        // If both subtrees have the same depth, the current node is the LCA
    }
};

/**
 * 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:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        return dfs(root).first;
    }
    pair<TreeNode*, int> dfs(TreeNode* node)
    {
        if (!node) return {nullptr, 0};

        auto left = dfs(node->left);
        auto right = dfs(node->right);

        if (left.second > right.second) return {left.first, left.second + 1};
        if (left.second < right.second) return {right.first, right.second + 1};
        return {node, left.second + 1};
    }
};

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2)
    {
        map<int, int> countMap;
        for (int num : arr1) ++countMap[num];

        vector<int> res;
        for (int num : arr2)
        {
            for (int i = 0; i < countMap[num]; ++i)
            {
                res.push_back(num);
            }
            countMap.erase(num);
        }

        for (auto a : countMap)
        {
            for (int i = 0; i < a.second; ++i)
            {
                res.push_back(a.first);
            }
        }
        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:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete)
    {
        // Vector to store the resulting forest of trees
        // Convert the list of nodes to delete into a set for faster lookup
        // Call the helper function to process the tree
        // If the root is not deleted, add it to the forest
        // Return the forest
    }

    // Helper function to process each node
    helper()
    {
        // If the node is null, return null

        // Recursively process the left and right subtrees

        // If the current node is not in the set of nodes to delete, return it

        // If the current node is to be deleted, add its children to the forest if they exist

        // Delete the current node
        // Return null to indicate the node has been deleted
    }
};

/**
 * 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:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete)
    {
        vector<TreeNode*> forest;
        unordered_set<int> st(to_delete.begin(), to_delete.end());
        root = helper(root, st, forest);
        if (root) forest.push_back(root);
        return forest;
    }

    TreeNode* helper(TreeNode* node, unordered_set<int>& st, vector<TreeNode*>& forest)
    {
        if (!node) return nullptr;

        node->left = helper(node->left, st, forest);
        node->right = helper(node->right, st, forest);

        if (!st.count(node->val)) return node;

        if (node->left) forest.push_back(node->left);
        if (node->right) forest.push_back(node->right);
        delete node;
        return nullptr;
    }
};

/**
 * 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 sum = 0;
public:
    TreeNode* bstToGst(TreeNode* root)
    {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root)
    {
        if (!root) return;
        dfs(root->right);
        root->val += sum;
        sum = root->val;
        dfs(root->left);
    }
};

/**
 * 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:
    TreeNode* bstToGst(TreeNode* root)
    {
        int sum = 0;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (node || !stk.empty())
        {
            while (node)
            {
                stk.push(node);
                node = node->right;
            }
            node = stk.top(); stk.pop();
            sum += node->val;
            node->val = sum;
            node = node->left;
        }
        return root;
    }
};