138. Copy List with Random Pointer

解題思路

要 deep copy 一個 linked list，而且該 linked list 有名為 random 的屬性，會隨機指到 list 中其他 node。

用 two pass 的方式解題，第一次單純把 node 與 val 弄好，第二次則根據對照把 random 補上去。

程式碼

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *dummy = new Node(0);
        Node *newHead = dummy, *p = head;
        unordered_map<Node*, Node*> mp; // old, new

        while(p != nullptr)
        {
            newHead->next = new Node(p->val);
            newHead = newHead->next;
            mp[p] = newHead;
            p = p->next;
        }

        newHead = dummy->next, p = head;
        while(newHead != nullptr)
        {
            newHead->random = mp[p->random];
            newHead = newHead->next;
            p = p->next;
        }
        return dummy->next;
    }
};

143. Reorder List

解題思路

可以把步驟拆分為三大項：

1. 把 list 分為左右半，用 slow-fast pointer 即可求得

2. 把右半 list 給 reverse，這題同樣寫過

3. 兩個 list merge，這題同樣也寫過

程式碼 

class Solution {
public:
    void reorderList(ListNode* head) {
        // find the mid point and split the list to two
        ListNode *slow = head, *fast = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        
        // reverse the second part of the list
        ListNode* prev = nullptr, *second = slow->next;
        ListNode* next;
        slow->next = nullptr;
        while(second != nullptr)
        {
            next = second->next;
            second->next = prev;
            prev = second;
            second = next;
        }
        
        // merge two list
        ListNode *firstHead = head, *secondHead = prev, *next1, *next2;
        while(secondHead != nullptr)
        {
            next1 = firstHead->next;
            next2 = secondHead->next;
            firstHead->next = secondHead;
            secondHead->next = next1;
            firstHead = next1;
            secondHead = next2;
        }
    }
};

153. Find Minimum in Rotated Sorted Array

解題思路

要找斷裂處的右側值。又根據特性，斷裂處右側的數字都會比 index 0 來的小，所以可以用二分搜尋來縮小與排除。

程式碼

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid;
        if(nums.size() == 1 || nums[0] < nums[nums.size() - 1])
            return nums[0];

        while(left <= right)
        {
            mid = (left + right) / 2;
            if(nums[0] <= nums[mid])
                left = mid + 1;
            else
                right = mid - 1;
        }
        return nums[left];
    }
};

875. Koko Eating Bananas

解題思路

直覺想到這題是在解等式，假設答案為 x，那該等式為 ceil(piles[i]/i) 的 sum 要小於等於 h，找出最小的 x。

只是要怎麼求 x？很酷的方法是想成 x 的所有可能範圍值介在 1 ~ max(piles)，然後用 binary search 的方式縮小範圍。如果 mid 是可以的，那就再往左邊試看看更小的還有無機會(right shift)；如果不行代表 left 要往右移一點。

程式碼

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxPile = 0;
        for(int i=0; i<piles.size(); i++)
            maxPile = max(maxPile, piles[i]);

        int left = 1, right = maxPile, mid;
        while(left <= right)
        {
            mid = (left + right) / 2;
            long long int hour = 0;
            for(int i=0; i<piles.size(); i++)
                hour += ceil((double)piles[i] / mid);
            if(hour > h)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
};

74. Search a 2D Matrix

解題思路

先找 row 再找 column 的 binary search 版本

明明題目本身很簡單，卻卡在某些 edge case 上面好久.....

程式碼

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int left = 0, right = matrix.size() - 1, mid = 0;
        // find which row
        while (left <= right) {
            mid = (left + right) / 2;
            if (matrix[mid][0] <= target && (mid == matrix.size()-1 || target < matrix[mid+1][0]))
                break;
            if (matrix[mid][0] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        // find which column
        left = 0, right = matrix[0].size() - 1;
        int row = mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (matrix[row][mid] == target)
                return true;
            if (matrix[row][mid] > target)
                right = mid - 1;
            else
                left = mid + 1; 
        }
        return false;
    }
};

853. Car Fleet

解題思路

第一步是想要怎麼找出最後速度會相等的車？速度最後會相等，代表出發位置靠後的車會趕上前面的車，也表示靠後的車原本到達目的地的時間會比較短。

時間的計算則是 (目的地位置 - 出發位置) / 車速。

又因為兩車相遇後，快車速度變慢，所以用stack紀錄有哪些車，而快車就不放進去。最後stack長度即為解。

程式碼

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<int, int>> cars;
        for(int i=0; i<position.size(); i++)
            cars.push_back(make_pair(position[i], speed[i]));
        sort(cars.begin(), cars.end());

        stack<pair<int, int>> st;
        st.push(cars.back());
        double currentTime = (target - cars.back().first) / (double)cars.back().second;
        for(int i=cars.size() - 2; i>=0; i--)
        {
            if((target - cars[i].first)/(double)cars[i].second > currentTime)
            {
                st.push(cars[i]);
                currentTime = (target - cars[i].first)/(double)cars[i].second;
            }
        }
        return st.size();
    }
};

22. Generate Parentheses

解題思路

很明顯需要用到遞迴的方式來解。只是要加 ( 或 ) 的條件不一樣。

( 的話，只要數量還沒到 n ，就可以加。

) 的話，除了數量到 n 了沒外，還要看 ( 的數量夠不夠，不然亂加就是 invalid。

終止條件自然是 ( 跟 ) 都夠了。

程式碼

class Solution {
public:
    void helper(string s, int open, int close, int n, vector<string>& v)
    {
        if(open == n && close == n)
            v.push_back(s);
        if(open < n)
            helper(s + "(", open + 1, close, n, v);
        if(open > close)
            helper(s + ")", open, close + 1, n, v);
    }
    vector<string> generateParenthesis(int n) {
        vector<string> v;
        helper("", 0, 0, n, v);
        return v;
    }
};

239. Sliding Window Maximum

解題思路

看 neetcode 的方法來解這題。

btw 問了 chatGPT 發現我寫的程式碼還是太醜了XD

程式碼

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        for(int i=0; i<k; i++)
        {
            while(!dq.empty() && nums[i] > dq.back())
                dq.pop_back();
            dq.push_back(nums[i]);
        }
        ans.push_back(dq.front());
        for(int i=1; i<(nums.size() - k + 1); i++)
        {
            if(dq.front() == nums[i-1])
            {
                dq.pop_front();
            }
            while(!dq.empty() && nums[i+k-1] > dq.back())
                dq.pop_back();
            dq.push_back(nums[i+k-1]);
            ans.push_back(dq.front());
        }
        return ans;
    }
};

76. Minimum Window Substring

解題思路

很容易聯想到 sliding window，若該 window 中所有字母出現次數與希望的一樣，就看長度決定是否更新。

比對的方式則是該兩個 index  array 以及 have 跟 need 兩個 int。index array 用來記錄該字母的出現次數，need 表示需要幾個「字母」種類(不考慮次數)，have 表示現階段的 sliding window 有幾個「字母」(同樣不考慮次數)。

那要怎麼移動 sliding window？暴力解是 O(n^2) 的方法，也就是每個字母依序當開頭，然後每次就開頭 + 1、開頭 + 2的一路看到最後。但有時若已經 valid ，那就可以提前結束。

至此還可以進一步優化。當找到新的 valid window，可以回過頭把 left 往右移，一直到 invalid 為止，這麼做是因為可能前面包含到多餘的子字串。記得這個 pop 的動作也要檢查 have 是否要減少。

程式碼 

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

        int countS[128] = {0}, countT[128] = {0}, left = 0, right = 0;
        int have = 0, need = 0, minLen = s.size()+1, minL = 0, minR = 0;
        bool isFind = false;
        for(int i=0; i<t.size(); i++)
        {
            countT[t[i]]++;
            if(countT[t[i]] == 1) // meet first time
                need++;
        }

        while(right < s.size())
        {
            // add right element into countS
            countS[s[right]]++;
            // check countS[i] == countT[i] ?
                // if true, have++
            if(countS[s[right]] == countT[s[right]])
                have++;
            // check have == need?
                // if true, update window len if needed
                // pop from front until have != need
            while(have == need)
            {
                if((right - left + 1) < minLen)
                {
                    minLen = right - left + 1;
                    minL = left;
                    minR = right;
                    isFind = true;
                }
                countS[s[left]]--;
                if(countS[s[left]] < countT[s[left]])
                    have--;
                left++;
            }
            right++;
        }
        if(!isFind) return "";
        return s.substr(minL, minLen);
    }
};

567. Permutation in String

解題思路

要找 s2 中存不存在 s1 的排列組合，又排列組合肯定是長度為 len(s1) 的，所以就想到用 sliding window，接下來就每次比較出現的字母數量就好。

程式碼

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.size() > s2.size()) return false;
        int countS1[26] = {0};
        for(int i=0; i<s1.size(); i++)
            countS1[s1[i] - 'a']++;

        for(int i=0; i<(s2.size() - s1.size() + 1); i++)
        {
            int countS2[26] = {0};
            for(int j=i; j<(i+s1.size()); j++)
            {
                countS2[s2[j] - 'a']++;
            }
            bool isSame = true;
            for(int j=0; j<26; j++)
            {
                if(countS1[j] != countS2[j])
                {
                    isSame = false;
                    break;
                }
                
            }
            if(isSame)
                return true;
        }
        return false;
    }
};

424. Longest Repeating Character Replacement

解題思路

首先，要找到「valid substring」的條件是：

substring length - max frequency letter count in substring <= k

因為最常出現的肯定是主體，剩下不常見的是要被替換的，那這些被替換的字母數量一定要小於題目規定的數字 k。

接著 substring 又是怎麼產生的？概念是 sliding window，所以就會有 left 跟 right pointer。

每次更新完 sliding window 中字母出現次數，都看該 sliding window 是 valid 的嗎？如果是，那就把 right 往右移，以及看看 ans 有無變化；如果不是，那就要把 left 往右移，以及把 count 也更新。

程式碼

class Solution {
public:
    int characterReplacement(string s, int k) {
        int count[26] = {0}, left = 0, right = 0, maxF = 0;
        int ans = 0;
        while(right < s.size())
        {
            count[s[right] - 'A']++;
            maxF = max(maxF, count[s[right] - 'A']);
            
            if((right - left + 1) - maxF > k)
            {
                count[s[left] - 'A']--;
                left++;
            }
            
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};