serenata

2023年12月27日星期三

4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

思路：
比較差的做法是，使用額外的空間
把兩個 array merge 在一起，保持 sorted
如果兩個 array 都還有元素，就比大小，小的先 merge 進新 array
直到array 1 空了，就把 array 2 剩下的元素 merge 進新 array
最後回傳中位數

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> mergeArray;
        vector<int>::iterator it1 = nums1.begin();
        vector<int>::iterator it2 = nums2.begin();

        while(it1 != nums1.end()) {
            if (it2 != nums2.end()) {
                if (*it1 < *it2) {
                    mergeArray.push_back(*it1);
                    it1++;
                } else {
                    mergeArray.push_back(*it2);
                    it2++;
                }
            } else {
                mergeArray.push_back(*it1);
                it1++;
            }
        }

        // append rest of array 2 
        while(it2 != nums2.end()) {
            mergeArray.push_back(*it2);
            it2++;
        }

        int mid = mergeArray.size() / 2;
        if (mergeArray.size() % 2 == 0) {
            return (double)(mergeArray[mid] + mergeArray[mid-1]) / 2;
        } else {
            return mergeArray[mid];
        }
    }
};

比較好的做法，不需要使用額外空間
因為你知道兩個 array 相加的元素個素 totalSize
所以可以知道中位數是在第幾個元素 half
就一路找出位在中位數的元素值就好 mid
要記得記住前一個元素值 preMid，因為若元素個素是偶素
那中位數就是 (preMid + mid) / 2

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> mergeArray;
        vector<int>::iterator it1 = nums1.begin();
        vector<int>::iterator it2 = nums2.begin();
        int totalSize = nums1.size() + nums2.size();
        int half = totalSize / 2;
        double mid = 0;
        int preMid = 0;

        while(half >= 0) {
            preMid = mid;  // keep previous value of mid
            if (it1 != nums1.end() && it2 != nums2.end()) {
                if (*it1 < *it2) {
                    mid = *it1;
                    it1++;
                } else {
                    mid = *it2;
                    it2++;
                }
            } else if (it1 != nums1.end()) {
                mid = *it1;
                it1++;
            } else if (it2 != nums2.end()) {
                mid = *it2;
                it2++;
            }
            half--;
        }

        if (totalSize % 2 == 0) {
            return (double)(preMid + mid) / 2;
        } else {
            return mid;
        }

    }
};

當然也可以參考網路上的思路
https://www.youtube.com/watch?v=KB9IcSCDQ9k

2023年12月26日星期二

100. Same Tree

100. Same Tree ( https://leetcode.com/problems/same-tree/ )

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:
The number of nodes in both trees is in the range [0, 100].
-104 <= Node.val <= 104

思路
兩棵樹要一樣，代表著
中間節點的值一樣
左子樹一樣
右子樹一樣
然後 return 三個比較結果的 AND 值

所以要遞迴取得三者的比較結果
遞迴的終點條件就是樹葉節點
樹葉節點的特性是 NULL
所以兩棵樹只要有一個走到NULL
就是該位置走到樹葉了
若兩樹相同，就必須同為 NULL
若兩樹不同，就只有一者 NULL
所以遇到樹葉，就可直接比較兩個 pointer

/**
 * 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 isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL || q == NULL)
        {
            return p == q;
        }

        bool sameLeft = isSameTree(p->left, q->left);
        bool sameRight = isSameTree(p->right, q->right);
        bool sameVal = p->val == q->val;
        return sameLeft && sameRight && sameVal;
    }
};

844. Backspace String Compare

844. Backspace String Compare ( https://leetcode.com/problems/backspace-string-compare/ )

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.
Note that after backspacing an empty text, the text will continue empty.

Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:
1 <= s.length, t.length <= 200
s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

思路
輸入兩個字串，要先處理成真實要比較的字串，所以用一個 function realString 來處理
最後比較兩個經 realString 處理後的結果
realString 內就用 stack 的觀念去做 push 與 pop
幸運的是 C++ 的 string 就有這樣的功能，很方便，不用自己 maintain stack
要注意的是 pop 的時候，string 不能是空的

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return realString(s) == realString(t);
    }

    string realString(string strInput) {
        string strOutput = "";
        for(char c : strInput) {
            if (c == '#') {
                if (strOutput != "")
                    strOutput.pop_back();
            } else {
                strOutput.push_back(c);
            }
            cout << strOutput << endl;
        }
        return strOutput;
    }
};

參考
https://www.youtube.com/watch?v=aILH2R7zjXg&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=9

2023年12月12日星期二

876. Middle of the Linked List

876. Middle of the Linked List ( https://leetcode.com/problems/middle-of-the-linked-list/ )

Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.

Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:
The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100

思路：
使用快慢雙指標
快的一次走兩步
慢的一次走一步
快的走到底時，慢的就是走到中間

slow 跟 fast 都從 1 開始走
若 fast 能夠前進兩步，那 slow 就前進一步
若 fast 只能前進一步，那 slow 停在原地

/**
 * 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* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != NULL)
        {
            fast = fast->next;
            if (fast != NULL)
            {
                fast = fast->next;
                slow = slow->next;
            }
        }

        return slow;
    }
};

參考：
https://www.youtube.com/watch?v=f4xocU8WIaU

2023年12月10日星期日

2. Add Two Numbers

2. Add Two Numbers ( https://leetcode.com/problems/add-two-numbers/description/ )

You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each of their nodes contains a single digit.
Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:
2->4->3
5->6->4
= 7->0->8
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

就模擬兩個數字相加的過程
從個位數開始相加，如果有進位，就把進位存起來
然後把 mod 10 的餘數弄成一個 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:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        int carry = 0;
        ListNode* curNode = dummy;
        while(l1 || l2 || carry)
        {
            int sum = 0;
            sum += l1? l1->val : 0;
            sum += l2? l2->val : 0;
            sum += carry;
            carry = sum / 10;
            ListNode* newNode = new ListNode();
            newNode->val = sum % 10;
            curNode->next = newNode;
            curNode = curNode->next;
            l1 = l1? l1->next : NULL;
            l2 = l2? l2->next : NULL;
        }
        return dummy->next;
    }
};

1426. Counting Elements

1426. Counting Elements ( https://leetcode.com/problems/counting-elements )

It's a premium problem, I'm not a suscriber....

Description

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there are duplicates in arr, count them separately.

Example 1:
Input: arr = [1,2,3]

Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:
Input: arr = [1,1,3,3,5,5,7,7]

Output: 0
Explanation: No numbers are counted, cause there is no 2, 4, 6, or 8 in arr.

Constraints:
1 <= arr.length <= 1000
0 <= arr[i] <= 1000

因為題目說，最大的數就是 1000 個

最直覺的解法就是，用 0~1001 的 int 陣列，去紀錄出現過的數字次數

有三個 1，就把 cnt[2] += 1 三次

最後把 cnt 的值加總就是答案了

class Solution {
public:
    int countElements(vector<int>& arr) {
        int cnt[1001]{};
        for (int x : arr) {
            ++cnt[x];
        }
        int ans = 0;
        for (int x = 0; x < 1000; ++x) {
            if (cnt[x + 1]) {
                ans += cnt[x];
            }
        }
        return ans;
    }
};

可以看以下影片，最後有個動態的解題法

只要排序加一次 for 迴圈

邊走邊計算符合條件的次數

參考
https://www.youtube.com/watch?v=HCFlfV1JJUw&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=7

https://github.com/doocs/leetcode/blob/main//solution/1400-1499/1426.Counting%20Elements/README_EN.md

49. Group Anagrams

49. Group Anagrams ( https://leetcode.com/problems/group-anagrams/ )

Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

1 <= strs.length <= 104

0 <= strs[i].length <= 100

strs[i] consists of lowercase English letters.

解答：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> sortedStrs(strs);
        vector<pair<string, string>> pairStrs;
        for(int i = 0; i < sortedStrs.size(); i++)
        {
            sort(sortedStrs[i].begin(), sortedStrs[i].end());
            pair<string, string> p(sortedStrs[i], strs[i]);
            pairStrs.push_back(p);
        }
        sort(pairStrs.begin(), pairStrs.end());
        for(vector<pair<string, string>>::iterator i = pairStrs.begin(); i != pairStrs.end(); i++)
        {
            cout << i->first << " | " << i->second << endl;
        }

        vector<string> initGroup;
        initGroup.push_back(pairStrs[0].second);
        vector<vector<string>> result;
        result.push_back(initGroup);
        for(int i = 1; i < strs.size(); i++)
        {
            if (pairStrs[i].first == pairStrs[i-1].first)
            {
                result[result.size()-1].push_back(pairStrs[i].second);
            } else {
                vector<string> newGroup;
                newGroup.push_back(pairStrs[i].second);
                result.push_back(newGroup);
            }
        }

        return result;
    }
};

參考：https://www.youtube.com/watch?v=1zU77mcQJ-U&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=6

2023年10月19日星期四

122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II ( https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ )

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]

Output: 7

Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.

Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]

Output: 4

Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.

Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

1 <= prices.length <= 3 * 10^4

0 <= prices[i] <= 10^4

因為你有上帝視角，你知道兩天之間是賺還是賠
你就把任兩天之間有賺錢的加起來，就是最大獲利

假設 profit(b, s) 代表 b 這天買，s 這天賣的獲利
如果 profit(1~n) 天的獲利會比 profit(1~n-1) 好
那profit(n-1~n)一定是正的
所以把所有可能 profit(n-1~n) 加起來，就一定會是最佳獲利

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        if (prices.size() <= 1)
        {
            return profit;
        }
        for (int i=1; i<prices.size(); i++)
        {
            int thisProfit = prices[i] - prices[i-1];
            if (thisProfit > 0)
            {
                profit += thisProfit;
            }
        }
        return profit;
    }
};

參考：https://www.youtube.com/watch?v=akTjUKEP7Co&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=5

2023年10月14日星期六

283. Move Zeroes

283. Move Zeroes (https://leetcode.com/problems/move-zeroes/)

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:
Input: nums = [0]
Output: [0]

Constraints:
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

Follow up: Could you minimize the total number of operations done?

用雙指標
快指標去找出所有非零的元素
逐一的排列到慢指標的位置
最後再從慢指標的位置，把之後的所有元素都設為零
這樣就可以依序保存所有非零的元素
並且把零都挪到陣列末端

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if (nums.size() == 1)
            return;

        int i = 0;
        int j = 0;
        while (j < nums.size())
        {
            if (nums[j] != 0)
            {
                nums[i] = nums[j];
                i++;
            }
            j++;
        }

        while(i < nums.size())
        {
            nums[i] = 0;
            i++;
        }
    }
};

參考: https://www.youtube.com/watch?v=vy9QG75U77g&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=4

2023年10月12日星期四

53. Maximum Subarray

53. Maximum Subarray ( https://leetcode.com/problems/maximum-subarray/ )

Given an integer array nums, find the subarray

with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

你可以用兩個迴圈 i 代表起點，j 代表終點
求得 i~j 的總和，保留最大的總和
i~j 的總和，可以用 i~(j-1) 的總和 + j
不需要每次都重新算 i+.....+j
這樣時間複雜度約 O(n^2)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max = INT_MIN;
        for (int i=0; i<nums.size(); i++)
        {
            int sum = 0;
            for (int j=i; j<nums.size(); j++)
            {
                sum += nums[j];
                if (sum > max)
                {
                    max = sum;
                }
            }
        }
        return max;
    }
};

有更快的 O(n) 解法
從第一個元素一路往後逐一加總
如果最大值的序列出現在 i~nums.size()
那就表示 0~(i-1) 的總和是負數
那最大值總和就不需要加上 0~(i-1) 的和
所以當 sum < 0 的時候，就重設 sum = 0
繼續求接下來 i~nums.size() 的總和即可

如果最大值的序列不包含最後一個元素
那表示最後一個元素是負數
i~ (nums.size()-1) 的總和，會 keep 在 max 之中
i~nums.size() 的總和，不會取代成為新的 max
同樣的如果最後 n 個元素的總和是負數
i~ (nums.size()-n) 的總和，會 keep 在 max 之中
i~nums.size() 的總和，不會取代成為新的 max

依此邏輯，只需要依序加總每個元素
當 sum >max，就更新 max
當 sum <0，就設 sum=0
這樣執行一次 for 迴圈，就可以得到最大的子序列和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max = INT_MIN;
        int sum = 0;
        for (int i=0; i<nums.size(); i++)
        {
            if (sum < 0)
            {
                sum = 0;
            }
            sum += nums[i];

            if (sum > max)
            {
                max = sum;
            }
        }
        return max;
    }
};

這邊要注意一下的是 sum 用 int 即可
因為 nums 內最大值是 10000，最多 100000 個，總和不會超過 1000000000
int 的最大值是2147483647，不會破表，所以用 int 就好

參考:
https://www.youtube.com/watch?v=cL5tRclvvCI&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=3

訂閱：文章 (Atom)

2023年12月27日 星期三

2023年12月26日 星期二

2023年12月12日 星期二

2023年12月10日 星期日

2023年10月19日 星期四

2023年10月14日 星期六

2023年10月12日 星期四

2023年12月27日星期三

2023年12月26日星期二

2023年12月12日星期二

2023年12月10日星期日

2023年10月19日星期四

2023年10月14日星期六

2023年10月12日星期四