268 篇文章 含有標籤「leetcode」

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        int n = nums.size();
        vector<int> res;
        deque<int> q;

        for (int i = 0; i < n; ++i)
        {
            // 因為滑動視窗會向前移動
            // 當 q.front() 的元素離開視窗的時候
            // 1 [3  -1  -3]
            // ^          ^
            //   <- k ->  i
            if (!q.empty() && q.front() + k == i)
            {
                q.pop_front();
            }

            // 當發現 deque 尾端的元素比目前的 nums[i] 小的時候
            // pop 掉，因為不可能成為最大值
            // 所以 deque 裡面會存有潛力成為最大值數字的 index
            while (!q.empty() && nums[q.back()] < nums[i])
            {
                q.pop_back();
            }

            // 將 index push 到 queue
            q.push_back(i);

            // 當發現 i + 1 >= k 的時候
            // 代表滑動視窗的大小 k 已經形成
            // 則將最大值 nums[q.front()] 推到 res
            if (i + 1 >= k)
            {
                res.push_back(nums[q.front()]);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        vector<int> res;

        // 預設由大排到小
        priority_queue<pair<int, int>> q;

        for (int i = 0; i < nums.size(); ++i)
        {
            while (!q.empty() && q.top().second <= i - k)
            {
                q.pop();
            }

            // {存數字, 存 index}
            q.push({nums[i], i});

            // 如果滑動視窗形成
            // 將最大值 push 到 res
            if (i >= k - 1)
            {
                res.push_back(q.top().first);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        // Initialize a vector to store the products of elements to the left of each index
        // Initialize a vector to store the products of elements to the right of each index
        // Initialize a vector to store the final result

        // Compute the products of all elements to the left of each index
        for ()
        {
            // Each element in arr1[i+1] is the product of all elements before nums[i+1]
        }

        // Compute the products of all elements to the right of each index
        for ()
        {
            // Each element in arr2[i-1] is the product of all elements after nums[i-1]
        }

        // Compute the final result by multiplying the corresponding elements of arr1 and arr2
        for ()
        {
            // The product of all elements except nums[i] is arr1[i] * arr2[i]
        }
        // Return the result vector
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        vector<int> res(n);

        for (int i = 0; i < n - 1; ++i)
        {
            left[i + 1] = left[i] * nums[i];
        }

        for (int i = n - 1; i > 0; --i)
        {
            right[i - 1] = right[i] * nums[i];
        }

        for (int i = 0; i < n; ++i)
        {
            res[i] = left[i] * right[i];
        }
        return res;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        // Initialize the result array with 1s, as we will be using multiplication.

        // First pass: calculate the product of all elements to the left of each index.
        for ()
        {
            // res[i] will be the product of all elements to the left of i.
        }

        // Variable to store the product of all elements to the right of the current index.
        // Second pass: calculate the product of all elements to the right of each index and
        // multiply it with the product from the first pass.
        for ()
        {
            // Multiply with the product of elements to the right.
            // Update the right product for the next iteration (one index to the left).
        }
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> res(n, 1);

        for (int i = 1; i < n; ++i)
        {
            res[i] = nums[i - 1] * res[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; --i)
        {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // If the current node is null, or if it is either p or q, return the current node

        // Recur for the left subtree
        // Recur for the right subtree

        // If both left and right are non-null, it means p and q are found in different subtrees
        // Hence, the current node is their lowest common ancestor

        // If one of the left or right is non-null, return the non-null value
        // This means either one of p or q is found and we are returning up the recursive call stack
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (!root || root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left && right) return root;
        return left ? left : right;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        // If both p and q are less than root's value, then LCA must be in the left subtree

        // If both p and q are greater than root's value, then LCA must be in the right subtree

        // If p and q are on different sides of root, or one of them is the root, then root is the LCA
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (p->val < root->val && q->val < root->val)
        {
            return lowestCommonAncestor(root->left, p, q);
        }

        if (p->val > root->val && q->val > root->val)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        // Start with the root node

        // Loop until we find the lowest common ancestor
        while ()
        {
            // Get the value of the current node

            // If both p and q are greater than parentVal, LCA must be in the right subtree
            if ()
            {
            }
            // If both p and q are less than parentVal, LCA must be in the left subtree
            else if ()
            {
            }
            // If p and q are on different sides of the current node, or one of them is the current node,
            // then the current node is the lowest common ancestor
            else
            {
            }
        }
        // This line is never reached because the loop always returns a node
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        TreeNode* node = root;
        while (true)
        {
            int parentVal = node->val;
            if (parentVal < p->val && parentVal < q->val)
            {
                node = node->right;
            }
            else if (parentVal > p->val && parentVal > q->val)
            {
                node = node->left;
            }
            else
            {
                return node;
            }
        }
        return node;
    }
};

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        ListNode* cur = head;
        return helper(head, cur);
    }
    bool helper(ListNode* head, ListNode*& cur) {
        if (!head) return true;
        bool res = helper(head->next, cur) && (cur->val == head->val);
        cur = cur->next;
        return res;
    }
};

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        stack<int> stk;
        stk.push(head->val);
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            stk.push(slow->val);
        }
        if (!fast->next) stk.pop();

        while (slow && slow->next) {
            slow = slow->next;
            int tmp = stk.top(); stk.pop();
            if (tmp != slow->val) return false;
        }
        return true;
    }
};

class MyQueue {
public:
    MyQueue() {}

    void push(int x) {
        // 後進來的會維持在最上層
        // 如果 s1 推了 1, 2, 3，3 會在最上面
        s1.push(x);
    }

    int pop() {
        peek();
        int temp = s2.top(); s2.pop();
        return temp;
    }

    int peek() {
        // s2 用來儲存 s1 的反轉順序，如果 s2 裡面有值，直接回傳 s2.top();
        if(!s2.empty()) return s2.top();
        // 如果 s1 還有值，將元素丟到 s2 儲存，反轉順序
        while(!s1.empty()) {
            s2.push(s1.top()); s1.pop();
        }
        return s2.top();
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
private:
    stack<int> s1; // push 進去的元素先裝在這，最後一個元素會維持在最上層
    stack<int> s2; // 將 s1 的元素 pop() 到 s2，反轉順序
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

/**
 * 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 {
vector<int> v;
public:
    int kthSmallest(TreeNode* root, int k)
    {
        dfs(root);
        return v[k - 1];
    }
    void dfs(TreeNode* root)
    {
        if (!root) return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
};

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int n = nums.size();
        vector<string> ranges;

        for(int i = 0; i < n; i++) {
            // 將 nums[i] 當作起始點 start
            int start = nums[i];
            // 如果跟下一個數字比，是連續遞增序列的話，i++
            while(i < n - 1 && nums[i] + 1 == nums[i + 1]) {
                i++;
            }

            if (start != nums[i]) {
                // 像是 [0, 2] 這種情況
                ranges.push_back(to_string(start) + "->" + to_string(nums[i]));
            } else {
                // 像是 [7, 7] 這種情況
                ranges.push_back(to_string(start));
            }
        }
        return ranges;
    }
};

/*
 * @lc app=leetcode id=226 lang=cpp
 *
 * [226] Invert Binary Tree
 *
 * https://leetcode.com/problems/invert-binary-tree/description/
 *
 * algorithms
 * Easy (78.10%)
 * Likes:    14546
 * Dislikes: 241
 * Total Accepted:    2.6M
 * Total Submissions: 3.2M
 * Testcase Example:  '[4,2,7,1,3,6,9]'
 *
 * Given the root of a binary tree, invert the tree, and return its root.
 *
 *
 * Example 1:
 *
 *
 * Input: root = [4,2,7,1,3,6,9]
 * Output: [4,7,2,9,6,3,1]
 *
 *
 * Example 2:
 *
 *
 * Input: root = [2,1,3]
 * Output: [2,3,1]
 *
 *
 * Example 3:
 *
 *
 * Input: root = []
 * Output: []
 *
 *
 *
 * Constraints:
 *
 *
 * The number of nodes in the tree is in the range [0, 100].
 * -100 <= Node.val <= 100
 *
 *
 */

// @lc code=start
/**
 * 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* invertTree(TreeNode* root)
    {
        if (!root) return NULL;

        swap(root->left, root->right);

        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
// @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* invertTree(TreeNode* root)
    {
        if (!root) return NULL;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();

            swap(node->left, node->right);

            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        return root;
    }
};