684. Redundant Connection

解題思路

用 union find 來解這題。

如果 edge 的兩個 node 已屬於同個 union，即可知該 edge 為多餘的。

程式碼

class Solution {
public:
    int *dsu, *rank;
    int size;

    int find_set(int v)
    {
        if(dsu[v] == v) return v;
        return dsu[v] = find_set(dsu[v]);
    }
    void make_union(int u, int v)
    {
        u = find_set(u), v = find_set(v);
        if(u != v)
        {
            if(rank[u] > rank[v])
            {
                dsu[v] = u;
                rank[u] += rank[v]; 
            }
            else
            {
                dsu[u] = v;
                rank[v] += rank[u]; 
            }
        }
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        this->size = edges.size() + 1;
        this->dsu = new int[size];
        this->rank = new int[size];

        for(int i=0; i<size; i++)
        {
            dsu[i] = i;
            rank[i] = 1;
        }

        for(int i=0; i<edges.size(); i++)
        {
            if(find_set(edges[i][0]) == find_set(edges[i][1]))
                return edges[i];
            make_union(edges[i][0], edges[i][1]);
        }    
        return edges[0];
    }
};

130. Surrounded Regions

解題心得

從邊緣的 O 往內走訪，最後再回頭重新檢視誰要被翻過去。

程式碼

class Solution {
public:
    void helper(vector<vector<char>>& board, vector<vector<bool>>& notFlip, int x, int y)
    {
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
            return;
        if(board[x][y] == 'X' || notFlip[x][y])
            return;

        int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
        notFlip[x][y] = true;
        for(int i=0; i<4; i++)
        {
            helper(board, notFlip, x+dx[i], y+dy[i]);
        }
    }
    void solve(vector<vector<char>>& board) {
        vector<vector<bool>> notFlip(board.size(), vector<bool>(board[0].size(), false));
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(board[i][j] == 'O' && (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1))
                {
                    helper(board, notFlip, i, j);
                }
            }
        }
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(board[i][j] == 'O' && !notFlip[i][j])
                    board[i][j] = 'X';
            }
        }
    }
};

90. Subsets II

解題思路

因為有重複的數字，所以可能會有重複的組合出現。

要避免這種情況，那麼就要知道，這個求解的過程就是每次都在選或不選當下的數字。如果不選，就代表該數字未來也不會選，所以要把 i 往後推。

程式碼

class Solution {
public:
    void helper(vector<int>& nums, vector<vector<int>>& ans, vector<int> current, int start)
    {
        ans.push_back(current);
        for(int i=start; i<nums.size(); i++)
        {
            
            current.push_back(nums[i]);
            helper(nums, ans, current, i+1);
            current.pop_back();
            int next = i+1;
            while(next <nums.size() &&nums[next] == nums[i])
                next++;
            i = next-1;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> current;
        sort(nums.begin(), nums.end());
        helper(nums, ans, current, 0);
        return ans;
    }
};

215. Kth Largest Element in an Array

解題思路

覺得這題跟 703. Kth Largest Element in a Stream 非常像，甚至還比這題簡單，但兩個題目的難度標示卻不是這樣，不懂。

程式碼

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i=0; i<nums.size(); i++)
        {
            pq.push(nums[i]);
            if(pq.size() > k)
                pq.pop();
        }
        return pq.top();
    }
};

1046. Last Stone Weight

解題思路

每次要找出最大與次大，最方便的方法是用 max heap。

程式碼

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for(int i=0; i<stones.size(); i++)
            pq.push(stones[i]);
        while(pq.size() != 1)
        {
            int first = pq.top(); pq.pop();
            int second = pq.top(); pq.pop();
            pq.push(first - second);
        }
        return pq.top();
    }
};

703. Kth Largest Element in a Stream

解題思路

minHeap 以 priority queue 的實作練習。

程式碼

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> pq;
    int size;

    KthLargest(int k, vector<int>& nums) {
        size = k;
        for(int i=0; i<nums.size(); i++)
        {
            pq.push(nums[i]);
            if(pq.size() > size)
                pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if(pq.size() > size)
            pq.pop();
        return pq.top();
    }
};

關於 vscode 調整 interpreter 之後炸掉的那回事

 vscode 底下那條藍色的 bar 偏右側有一個地方，點擊後可選擇 interpreter。隨便選了一個後，莫名的用 vscode terminal 做某些操作就會出現問題，把 python 與 vscode 刪掉重裝仍然沒有解決。

後來是把 default 的 interpreter 改到新安裝的 python 的路徑就正常了，但是執行指令要打 py 而不 python，例如：py -m venv myenv。這個部分感覺跟這個有關，先存著以後有需要再來看。

1472. Design Browser History

解題思路

其實就照題目敘述實作即可。

只是 back() 的部分要注意，如果 stack 裡面只剩一個就不要 pop 了，不然連首頁都會不見。

程式碼

class BrowserHistory {
public:
    stack<string> backHistory;
    stack<string> forwardHistory;
    
    BrowserHistory(string homepage) {
        backHistory.push(homepage);
    }
    
    void visit(string url) {
        while (!forwardHistory.empty())
            forwardHistory.pop();
        backHistory.push(url);
    }
    
    string back(int steps) {
        while (steps  && backHistory.size() > 1) {
            forwardHistory.push(backHistory.top());
            backHistory.pop();
            steps--;
        }
        return backHistory.top();
    }
    
    string forward(int steps) {
        while (steps && !forwardHistory.empty()) {
            backHistory.push(forwardHistory.top());
            forwardHistory.pop();
            steps--;
        }
        return backHistory.top();
    }
};

1448. Count Good Nodes in Binary Tree

解題思路

基本上就是 traverse 整棵樹，然後不斷紀錄這條 path 的最大值，以及更新 count 的次數。

程式碼

class Solution {
public:
    void helper(TreeNode* root, int curMax, int& count)
    {
        if(root == nullptr)
            return;
        if(root->val >= curMax)
            count++;
        curMax = max(curMax, root->val);
        helper(root->left, curMax, count);
        helper(root->right, curMax, count);

    }
    int goodNodes(TreeNode* root) {
        int count = 0;
        helper(root, root->val, count);
        return count;
    }
};

572. Subtree of Another Tree

解題思路

直覺反應是 same tree 的延伸題。

程式碼

class Solution {
public:
    bool isSame(TreeNode* root, TreeNode* subRoot)
    {
        if(root == nullptr && subRoot == nullptr)
            return true;
        if(root == nullptr || subRoot == nullptr)
            return false;
        return root->val == subRoot->val && isSame(root->left, subRoot->left)
        && isSame(root->right, subRoot->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root == nullptr)
            return false;
        return isSame(root, subRoot) || isSubtree(root->left, subRoot) ||
            isSubtree(root->right, subRoot);
    }
};

958. Check Completeness of a Binary Tree

解題思路

所謂 complete 的意思是，node 盡可能地滿，只會在最右下方有 null。這代表一旦有 null 出現，後面一定都不會再有 node。利用這樣的特性去 traverse 整棵樹。

程式碼

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        bool flag = false;
        while(!q.empty())
        {
            TreeNode* node = q.front();
            q.pop();

            if(node == nullptr)
                flag = true;
            else if(flag)
                return false;
            else
            {
                q.push(node->left);
                q.push(node->right);
            }
            
        }
        return true;
    }
};

23. Merge k Sorted Lists

解題思路

如果考慮一次 merge k 的太麻煩，就兩兩 merge 來簡化問題。

merge 的部分偷懶用遞迴，有機會的話改成非遞迴的版本。

程式碼

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        while(lists.size() > 1)
        {
            lists.push_back(merge2Lists(lists[0], lists[1]));
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        return lists[0];
    }
    ListNode* merge2Lists(ListNode* l1, ListNode* l2)
    {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val <= l2->val)
        {
            l1->next = merge2Lists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

129. Sum Root to Leaf Numbers

解題心得

把 tree 給走訪一遍。若走到 left node 就把累計的加起來。

程式碼

class Solution {
public:
    void helper(TreeNode* root, int& sum, int current)
    {
        current = current * 10 + root->val;
        if(root->left == nullptr && root->right == nullptr)
        {
            sum += current;
            cout << current << endl;
            return;
        }
        else
        {
            if(root->left) helper(root->left, sum, current);
            if(root->right) helper(root->right, sum, current);
        }
    }
    int sumNumbers(TreeNode* root) {
        int sum = 0;
        helper(root, sum, 0);
        return sum;
    }
};

2. Add Two Numbers

解題思路

很基本的大數加法，只是用 linked list 來做而已。

程式碼

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode *head = dummy;

        int add = 0;
        while(l1 && l2)
        {
            int sum = 0;
            if(l1)
                sum += l1->val;
            if(l2)
                sum += l2->val;

            sum += add;
            head->next = new ListNode(sum % 10);
            add = sum / 10;
            head = head->next;
            l1 = l1->next;
            l2 = l2->next;
        }
         while(l1)
        {
            head->next = new ListNode((l1->val + add) % 10);
            add = (l1->val + add) / 10;
            head = head->next;
            l1 = l1->next;
        }
         while(l2)
        {
            head->next = new ListNode((l2->val + add) % 10);
            add = (l2->val + add) / 10;
            head = head->next;
            l2 = l2->next;
        }
        if(add != 0)
            head->next = new ListNode(add);
        return dummy->next;
    }
};

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;
    }
};