268 篇文章 含有標籤「leetcode」

/*
 * @lc app=leetcode id=34 lang=cpp
 *
 * [34] Find First and Last Position of Element in Sorted Array
 *
 * https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 *
 * algorithms
 * Medium (45.48%)
 * Likes:    21764
 * Dislikes: 573
 * Total Accepted:    2.6M
 * Total Submissions: 5.7M
 * Testcase Example:  '[5,7,7,8,8,10]\n8'
 *
 * Given an array of integers nums sorted in non-decreasing order, find the
 * starting and ending position of a given target value.
 *
 * If target is not found in the array, return [-1, -1].
 *
 * You must write an algorithm with O(log n) runtime complexity.
 *
 *
 * Example 1:
 * Input: nums = [5,7,7,8,8,10], target = 8
 * Output: [3,4]
 * Example 2:
 * Input: nums = [5,7,7,8,8,10], target = 6
 * Output: [-1,-1]
 * Example 3:
 * Input: nums = [], target = 0
 * Output: [-1,-1]
 *
 *
 * Constraints:
 *
 *
 * 0 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * nums is a non-decreasing array.
 * -10^9 <= target <= 10^9
 *
 *
 */

// @lc code=start
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int n = nums.size();
        vector<int> res(2, -1);

        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (right == n || nums[right] != target) {
            return res;
        }
        res[0] = right;
        right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        res[1] = right - 1;

        return res;
    }
};
// @lc code=end

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int left = n - 2, right = n - 1;
        while(left >= 0 && nums[left] >= nums[left + 1]) {
            --left;
        }
        if(left >= 0) {
            while(nums[left] >= nums[right]) {
                --right;
            }
            swap(nums[left], nums[right]);
        }
        reverse(nums.begin() + left + 1, nums.end());
    }
};

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        // 每個單字的長度都相同，為 n
        int n = words[0].size();

        // 計算總共有幾個單字
        int wordCounts = words.size();

        unordered_map<string,int> freq;

        // 計算每個單字出現的頻率
        for (int i = 0; i < wordCounts; i++)
        {
            freq[words[i]]++;
        }

        vector<int> res;

        // 一個指標 start 走訪一個單字的長度 n
        for (int start = 0; start < n; ++start)
        {
            // 兩個指標 i, j
            // i 為右邊界
            // j 為左邊界
            int i = start;
            int j = i;
            int cnt = 0;

            // 記錄目前的子串中每個單字的出現次數
            unordered_map<string, int> m;

            // 走訪字串 s
            while (j < s.size())
            {
                // 如果子串中出現了一個不在 words 中的單字，清空 m，並且將指針 i 和 j 向前移動一個單字的長度。
                if (!freq.count(s.substr(j, n)))
                {
                    // 清空 m
                    m.clear();
                    // 清空 cnt
                    cnt = 0;
                    // i, j 跳到下一個起始點
                    j += n;
                    i = j;
                }
                // 如果子串中所有單字的出現次數均不超過 words 中該單字的出現次數，我們將指針 j 向前移動一個單字的長度，同時增加相應的計數。
                else if (m[s.substr(j, n)] < freq[s.substr(j, n)])
                {
                    m[s.substr(j, n)]++;
                    cnt++;
                    j += n;
                }
                // 如果子串中某個單字的出現次數超過了 words 中該單字的出現次數，我們將指針 i 向前移動一個單字的長度，同時將相應的計數減少。
                else if (m[s.substr(j, n)] == m[s.substr(j, n)])
                {
                    m[s.substr(i, n)]--;
                    i += n;
                    cnt--;
                }

                // 當找到一個包含 words 中所有單字的子串時，將其起始 index 加入結果 res 中。
                if (cnt == wordCounts)
                {
                    res.push_back(i);
                    m[s.substr(i, n)]--;
                    // i 向前移動 n 的距離
                    i += n;
                    cnt--;
                }
            }
        }

        return res;
    }
};

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        // Iterate through 'haystack' from the start to the point where 'needle' can fit
        for ()
        {
            // Iterate through each character in 'needle'
            for ()
            {
                // If the characters don't match, break out of the inner loop

                // If we reach the end of 'needle' and all characters have matched
                if ()
                {
                    // Return the starting index of the first occurrence of 'needle' in 'haystack'
                }
            }
        }
        // If 'needle' is not found in 'haystack', return -1
    }
};

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        for (int i = 0; i <= haystack.size() - needle.size(); ++i)
        {
            for (int j = 0; j < needle.size(); ++j)
            {
                if (needle[j] != haystack[i + j]) break;
                if (j == needle.size() - 1)
                {
                    return i;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        // Initialize a counter to keep track of the new length of the array
        // Iterate through each element of the array
        for ()
        {
            // If the current element is not equal to the value to be removed
            if ()
            {
                // Assign the current element to the position indicated by cnt and increment cnt
            }
        }
        // Return the new length of the array, which is the count of elements not equal to val
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        int cnt = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != val)
            {
                nums[cnt++] = nums[i];
            }
        }
        return cnt;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        // Initialize a counter to keep track of the unique elements' length

        // Iterate through the array starting from the second element
        for ()
        {
            // If the current element is different from the previous element
            if ()
            {
                // Assign the current element to the position indicated by cnt and increment cnt
            }
        }
        // Return the count of unique elements in the array
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        int cnt = 1;
        for (int i = 1; i < nums.size(); ++i)
        {
            if (nums[i - 1] != nums[i])
            {
                nums[cnt++] = nums[i];
            }
        }
        return cnt;
    }
};

/**
 * 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* reverseKGroup(ListNode* head, int k)
    {
        // cnt 計算需要反轉的 node 的數量
        int cnt = 0;
        ListNode* cur = head;
        // 當需要反轉的 node 的數量小於 k 的時候
        // 指標前進
        while (cur && cnt < k)
        {
            cur = cur->next;
            cnt++;
        }

        // 當需要反轉的 node 數量達到 k 時
        if (cnt == k)
        {
            // 呼叫 reverseLinkedList，反轉 linked list
            ListNode* reversedHead = reverseLinkedList(head, k);

            // 遞迴反轉剩餘的 node
            head->next = reverseKGroup(cur, k);
            return reversedHead;
        }
        return head;
    }

    ListNode* reverseLinkedList(ListNode* head, int k)
    {
        ListNode* dummy = new ListNode();
        ListNode* cur = head;
        for (int i = 0; i < k; ++i)
        {
            ListNode* next_node = cur->next;
            cur->next = dummy;
            dummy = cur;
            cur = next_node;
        }
        return dummy;
    }
};

/**
 * 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* swapPairs(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* first = head;
        ListNode* second = head->next;

        first->next = swapPairs(second->next);

        second->next = first;
        return second;
    }
};

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        if (!list1) return list2;
        if (!list2) return list1;
        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
    }
};

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;

        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                cur->next = list1;

                list1 = list1->next;
            }
            else
            {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        if (!list1) cur->next = list2;
        if (!list2) cur->next = list1;
        return dummy->next;
    }
};