serenata

2023年12月26日星期二

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

2023年10月7日星期六

202. Happy Number

202. Happy Number ( https://leetcode.com/problems/happy-number/ )

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19

Output: true

Explanation:

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2

Output: false

Constraints:

1 <= n <= 2^31 - 1

思路筆記：
首先要能求各位數的平方和
就是要 mod 10 平方
然後除 10，再mod 10 平方....
全部加起來

如果加起來的數字是 1 ，就 return true
要用 Set 記住加起來的數字 sum
如果 sum 曾經出現過，那就是繞回原點了
繼續往下走，也會再繞到這個數字，這樣就 return false

class Solution {
public:
    bool isHappy(int n) {
        set<int> numSet;
        int sum = 0;

        while (numSet.count(sum) == 0)
        {
            numSet.insert(sum);
            sum = 0;
            while (n != 0)
            {
                sum += pow(n % 10, 2) ;
                n /= 10;
            }

            n = sum;
            if (n == 1)
                return true;
        }

        return false;
    }
};

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

136. Single Number

( https://leetcode.com/problems/single-number/description/ )

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

1 <= nums.length <= 3 * 104

-3 * 104 <= nums[i] <= 3 * 104

Each element in the array appears twice except for one element which appears only once.

思路筆記:
任何數字 XOR 自己，會等於 0

任何數字 XOR 0 會等於自己

所以你只要把陣列裡面所有的數字 XOR 起來

出現兩次的數字就會變成 0

出現一次的數字跟其他的 0，XOR 起來還是原本的數字

那我們就得到答案了

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = nums[0];
        for(vector<int>::iterator it = nums.begin() + 1; it != nums.end(); it++)
        {
            ans ^= *it;
        }
        return ans;
    }
};

參考：

https://www.youtube.com/watch?v=Hy1hE0HBR3U&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=1

訂閱：文章 (Atom)

2023年12月26日 星期二

2023年12月12日 星期二

2023年12月10日 星期日

2023年10月19日 星期四

2023年10月14日 星期六

2023年10月12日 星期四

2023年10月7日 星期六

2023年12月26日星期二

2023年12月12日星期二

2023年12月10日星期日

2023年10月19日星期四

2023年10月14日星期六

2023年10月12日星期四

2023年10月7日星期六