268 篇文章 含有標籤「leetcode」

/*
 * @lc app=leetcode id=84 lang=cpp
 *
 * [84] Largest Rectangle in Histogram
 *
 * https://leetcode.com/problems/largest-rectangle-in-histogram/description/
 *
 * algorithms
 * Hard (45.83%)
 * Likes:    18224
 * Dislikes: 326
 * Total Accepted:    1.2M
 * Total Submissions: 2.5M
 * Testcase Example:  '[2,1,5,6,2,3]'
 *
 * Given an array of integers heights representing the histogram's bar height
 * where the width of each bar is 1, return the area of the largest rectangle
 * in the histogram.
 *
 *
 * Example 1:
 *
 *
 * Input: heights = [2,1,5,6,2,3]
 * Output: 10
 * Explanation: The above is a histogram where width of each bar is 1.
 * The largest rectangle is shown in the red area, which has an area = 10
 * units.
 *
 *
 * Example 2:
 *
 *
 * Input: heights = [2,4]
 * Output: 4
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= heights.length <= 10^5
 * 0 <= heights[i] <= 10^4
 *
 *
 */

// @lc code=start
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        int n = heights.size();
        stack<int> stk;
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && heights[stk.top()] > heights[i]) {
                int h = heights[stk.top()]; stk.pop();
                int w = stk.empty() ? i : i - stk.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            stk.push(i);
        }
        return maxArea;
    }
};
// @lc code=end

/**
 * 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:
    ListNode* deleteDuplicates(ListNode* head)
    {
        ListNode* cur = head;
        while (cur && cur->next)
        {
            if (cur->val == cur->next->val)
            {
                cur->next = cur->next->next;
            }
            else
            {
                cur = cur->next;
            }
        }
        return head;

    }
};

/**
 * 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:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if (!head || !head->next) return head;

        // 因為 head 有可能會有重複項
        // 如果刪掉就沒有了
        // 所以這裡定義一個新的節點 dummy
        ListNode* dummy = new ListNode(-1);
        // 用一個 prev 指標指到這個 pseudo node
        ListNode* prev = dummy;

        // 然後這個 dummy node 接到 head
        // 以避免 head 被刪掉的情況
        dummy->next = head;

        // 從下個位置開始走訪節點
        while (prev->next)
        {
            ListNode* cur = prev->next;
            // 跳過所有重複的節點
            while (cur->next && cur->val == cur->next->val)
            {
                cur = cur->next;
            }

            if (cur != prev->next)
            {
                // 略過重複的節點
                prev->next = cur->next;
            }
            else
            {
                // 移到下一個節點
                prev = prev->next;
            }
        }
        return dummy->next;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        // Initialize the index to insert the next valid element
        // Initialize the count of the current element to 1 (the first element is always counted once)

        // Iterate through the array starting from the second element
        for ()
        {
            // If the current element is the same as the previous element, increment the count
            if ()
            {
            }
            else // If the current element is different from the previous element, reset the count to 1
            {
            }

            // If the count is less than or equal to 2, we can keep this element
            if ()
            {
                // Place the current element at the insertIndex and increment insertIndex
            }
        }
        // Return the index where the next element would be inserted, which is the new length of the array
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        int insertIndex = 1;
        int cnt = 1;

        for (int i = 1; i < nums.size(); ++i)
        {
            if (nums[i] == nums[i - 1]) ++cnt;
            else cnt = 1;
            if (cnt <= 2) nums[insertIndex++] = nums[i];
        }
        return insertIndex;
    }
};

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word)
    {
        int m = board.size(), n = board[0].size();

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (board[i][j] == word[0] && backtracking(board, word, i, j, 0))
                {
                    return true;
                }
            }
        }
        return false;

    }

    bool backtracking(vector<vector<char>>& board, string word, int i, int j, int start)
    {
        int m = board.size(), n = board[0].size();

        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[start])
        {
            return false;
        }

        if (start == word.size() - 1) return true;

        char temp = board[i][j];

        board[i][j] = '#';

        bool res = backtracking(board, word, i + 1, j, start + 1) || \
                   backtracking(board, word, i - 1, j, start + 1) || \
                   backtracking(board, word, i, j + 1, start + 1) || \
                   backtracking(board, word, i, j - 1, start + 1);

        board[i][j] = temp;
        return res;
    }
};

class Solution {
private:
    vector<vector<int>> res;
    vector<int> comb;
public:
    vector<vector<int>> combine(int n, int k)
    {
        backtracking(n, k, 1);
        return res;
    }

    void backtracking(int n, int k, int start)
    {
        if (comb.size() == k) res.push_back(comb);
        if (comb.size() > k) return;
        for (int i = start; i <= n; ++i)
        {
            comb.push_back(i);
            backtracking(n, k, i + 1);
            comb.pop_back();
        }
    }
};

class Solution {
public:
    string minWindow(string s, string t)
    {
        if (s.size() == 0 || t.size() == 0) return "";

        int left = 0;

        // 當前窗口中已匹配的字元數量
        int cnt = 0;

        // 最小子字串的起始位置
        int minLeft = -1;

        // 最小子字串的長度
        int minLen = INT_MAX;

        // 計算字元出現的頻率
        unordered_map<char, int> m;
        for (auto& c : t) ++m[c];

        for (int right = 0; right < s.size(); ++right)
        {
            // 如果 --m[s[right]] >= 0
            // 代表是目標字元，則 ++cnt
            if (--m[s[right]] >= 0)
            {
                ++cnt;
            }

            // 當 cnt == t.size() 的時候，代表子字串都有覆蓋到 t 的字母了
            while (cnt == t.size())
            {
                // 則計算當前的長度
                int curLen = right - left + 1;

                // 如果發現當前的長度更小，則
                if (minLen > curLen)
                {
                    // 更新 minLen 的值
                    minLen = curLen;

                    // 最小左邊界等於 left
                    minLeft = left;
                }

                // 如果發現左邊界是 t 其中一個字母
                // 則頻率 + 1 回來，且計數 cnt - 1
                if (++m[s[left]] > 0) --cnt;

                // 最後更新左邊界
                ++left;
            }
        }
        return minLeft == -1 ? "" : s.substr(minLeft, minLen);
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        quickSort(nums, 0, nums.size() - 1);
    }

    void quickSort(vector<int>& nums, int left, int right)
    {
        if (left < right)
        {
            int pivot = partition(nums, left, right);
            quickSort(nums, 0, pivot - 1);
            quickSort(nums, pivot + 1, right);
        }
    }

    int partition(vector<int>& nums, int left, int right)
    {
        int pivot = nums[right];
        int pointer = left;
        for (int i = left; i < right; ++i)
        {
            if (nums[i] <= pivot)
            {
                swap(nums[i], nums[pointer]);
                ++pointer;
            }
        }
        swap(nums[pointer], nums[right]);
        return pointer;
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int n = nums.size();
        bool swapped = false;
        for (int i = 0; i < n; ++i)
        {
            swapped = false;
            for (int j = 0; j < n - 1 - i; ++j)
            {
                if (nums[j] > nums[j + 1])
                {
                    swap(nums[j], nums[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        mergeSort(nums, 0, nums.size() - 1);
    }

    void merge(vector<int>& nums, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        vector<int> l1(n1);
        vector<int> l2(n2);

        // 將 nums 數列左側的數字填入 l1
        for (int i = 0; i < n1; ++i) l1[i] = nums[left + i];
        // 將 nums 數列右側的數字填入 l2
        for (int i = 0; i < n2; ++i) l2[i] = nums[mid + 1 + i];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2)
        {
            if (l1[i] <= l2[j])
            {
                nums[k] = l1[i++];
            }
            else
            {
                nums[k] = l2[j++];
            }
            ++k;
        }
        while (i < n1)
        {
            nums[k] = l1[i];
            ++i; ++k;
        }
        while (j < n2)
        {
            nums[k] = l2[j];
            ++j; ++k;
        }
    }
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();

        bool firstRow = false, firstCol = false;

        for (int i = 0; i < m; ++i)
        {
            if (matrix[i][0] == 0) firstCol = true;
        }

        for (int j = 0; j < n; ++j)
        {
            if (matrix[0][j] == 0) firstRow = true;
        }

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                if (matrix[i][j] == 0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                {
                    matrix[i][j] = 0;
                }
            }
        }

        if (firstRow)
        {
            for (int j = 0; j < n; ++j)
            {
                matrix[0][j] = 0;
            }
        }

        if (firstCol)
        {
            for (int i = 0; i < m; ++i)
            {
                matrix[i][0] = 0;
            }
        }
    }
};