serenata: 12月 2023

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

訂閱：文章 (Atom)

2023年12月27日 星期三

2023年12月26日 星期二

2023年12月12日 星期二

2023年12月10日 星期日

2023年12月27日星期三

2023年12月26日星期二

2023年12月12日星期二

2023年12月10日星期日