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