---
# System prepended metadata

title: Top interview 150

---

# Top interview 150 

## 88. Merge Sorted Array
```c=
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m-1;
        int j = n-1;
        int insert_index = m+n-1;
        while(i>=0 && j>=0){
            if(nums2[j]>=nums1[i]){
                nums1[insert_index] = nums2[j];
                j--;
            }
            else{
                nums1[insert_index] = nums1[i];
                i--;
            }
            insert_index--;
            //cout<<i<<" "<<j<<" "<<insert_index<<endl;
        }
        while(j>=0){
            nums1[insert_index] = nums2[j];
            insert_index--;
            j--;
        }
    }
};
```
### Notes:
1. 用two-pointers來解
2. 兩個指標都先指向vector內的最後一個元素(Maxima)
3. 比較大的那個就放在nums1的最後一個，重複此步驟一直比大小
4
--- 

## 121. Best Time to Buy and Sell Stock
```c=
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0; 
        int buy_index = 0, sell_index = 1;
        int temp = 0;
        for(sell_index=1; sell_index<prices.size(); sell_index++){
            temp = prices[sell_index] - prices[buy_index];
            if(temp>max_profit)
                max_profit = temp;
            if(temp<0){
                buy_index = sell_index;
            }
        }
        return max_profit;
    }
};
```
### Notes: 
1. 用two-pointers計算獲利，sell_index是主要在變動的
2. 唯有當temp_profit < 0，才會改變buy_index(代表當下這個index便宜，更適合當buy_index)

---

## 122. Best Time to Buy and Sell Stock II
```c=
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int b_index = 0, s_index = 1; 
        int max_profit = 0, sum = 0, temp = 0, pre_max = 0;
        for(s_index = 1; s_index < prices.size(); s_index++){
            temp = prices[s_index] - prices[b_index];
            if(temp > max_profit){
                sum-=pre_max;
                max_profit = temp;
                sum+=max_profit;
                pre_max = max_profit;
            }
            if(temp < 0 || temp<max_profit){
                b_index = s_index;
                max_profit = 0; pre_max = 0;
            }
        }
        return sum;
    }
};
```

### Notes:
1. 跟Best Time to Buy and Sell Stock差不多，先找出max_profit
2. 但因為可以重複買賣，所以若發現temp < 0，就可以再買賣一次，所以這題其實就是重複找很多次max_profit 


--- 
## 36. Valid Sudoku
```c=
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // check row 
        for(int i=0; i<9; i++){
            unordered_set<char> row_record;
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'&&row_record.find(board[i][j])!=row_record.end())
                    return false; 
                row_record.insert(board[i][j]);
            }
        }
        // check col 
        for(int i=0; i<9; i++){
            unordered_set<char> col_record;
            for(int j=0; j<9; j++){
                if(board[j][i]!='.'&&col_record.find(board[j][i])!=col_record.end())
                    return false; 
                col_record.insert(board[j][i]);
            }
        }
        // check 3x3 subboxes 
        vector<unordered_set<char>> record(9);
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                int number = 3*(int(i/3)) + int(j/3);
                if(board[i][j]!='.'&&record[number].find(board[i][j])!=record[number].end())
                    return false;
                record[number].insert(board[i][j]);
            }
        }
        return true;
    }
};
```
### Notes:
1. 這題只是要判斷是不是一個有效的數獨，只需要按照題目說的規則檢查即可，不需要考慮可能的解
2. 依序檢查每個row有無重複、每個col有無重複、每個3x3的box內有無重複。

---
## 12. Integer to Roman
```c=
class Solution {
public:
    string intToRoman(int num) {
        vector<int> nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        string ans = "";
        
        for(int i=0; i<nums.size(); i++){
            if(num>=nums[i]){
                for(int j=0; j<int(num/nums[i]); j++)
                    ans+=roman[i];
                num = num%nums[i];
            }
        }
        return ans;
        
    }
};
```

### Notes:
1. 因為題目說的特殊情況只有6種，所以先事先pre-define這幾個對應的roman即可

--- 
## 73. Set Matrix Zeroes
```c=
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int* r_record = new int[matrix.size()]{}; 
        int* c_record = new int[matrix[0].size()]{};
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[0].size(); j++){
                if(matrix[i][j] == 0){
                    r_record[i] = 1;
                    c_record[j] = 1;
                }
            }
        }
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[0].size(); j++){
                if(r_record[i] == 1 || c_record[j] == 1){
                    matrix[i][j] = 0;
                }
            }
        }
    }
};
```
### Notes:
1. 新增2個array，分別記錄第i-th個row是否全為0、第i-th個col是否全為0
2. 這個做法就不需要花費O(MxN)的space來儲存是否為0

---
## 61. Rotate List
```c=
/**
 * 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* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        ListNode* temp = head; 
        ListNode* pre = NULL;
        int length = 0;
        while(temp!=NULL){
            length++;
            pre = temp;
            temp = temp->next;
        }
        temp = head;
        if(k%length == 0)
            return head;
        int new_k = length - (k%length);
        for(int i=0; i<new_k-1; i++)
            temp = temp->next;
        ListNode* new_root = temp->next;
        pre->next = head;
        temp->next = NULL;
        return new_root;
    }
};
```

### Notes: 
1. 先count出整個List的長度
2. 這題其實不用step by step的插入，只需要找出"切斷的地方"，把整段list移動到head前面即可
3. 因為k可能遠大於list.length()，所以要取Mod 
4. Time complexity O(N)

---
## 219. Contains Duplicate II
```c=
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size() == 1)
            return false;
        map<int, vector<int>> loc; 
        for(int i=0; i<nums.size(); i++){
            loc[nums[i]].push_back(i);
        }
        for(auto it = loc.begin(); it!=loc.end(); it++){
            for(int i=0; i<loc[it->first].size()-1; i++){
                if(abs(loc[it->first][i] - loc[it->first][i+1])<=k)
                    return true;
            }
        }
        return false;
    }
};
```

### Notes: 
1. 用c++的stl來解，紀錄每個num出現的index

---
## 71. Simplify Path
```c=
class Solution {
public:
    string simplifyPath(string path) {
        vector<string> strs;
        stack<string> s;
        string ans = "";
        string temp = "";
        if(path[path.length()-1]!='/')
            path = path + "/";
        for(int i=0; i<path.length()-1; i++){   
            if (path[i]!='/'){
                temp = temp + path[i];
                if(path[i+1] == '/'){
                    strs.push_back(temp);
                    temp = "";
                }
            }
        }
        for(int i=0; i<strs.size(); i++){
            if(strs[i] == "."){
                continue;
            }
            else if(strs[i] == ".."){
                if(s.size()!=0)
                    s.pop();
            }
            else{
                s.push(strs[i]);
            }
        }
        while(s.size()!=0){
            ans = "/" + s.top() + ans;
            s.pop();
        }
        return ans.length()==0?"/":ans;
    }
};
```
### Notes:
1. 從題目可以發現，不論是幾個"/"都不影響，所以遇到"/"可以忽略
2. split path string by "/" 
3. 假設path = "/home/../file/", 那strs = {"home", "..", file"}
4. 建立一個stack，若遇到folder name就放入stack，遇到".."要特別注意，就把stack的top value移除即可。
---
## 933. Number of Recent Calls
```c=
class RecentCounter {
public:
    queue<int> q;
    RecentCounter() {
        q = queue<int>();
    }
    
    int ping(int t) {
        int retv = 0;
        q.push(t);
        while(true){
            if(q.front() >= t-3000){
                retv = q.size();
                break;
            }
            else{
                q.pop();
            }
        }
        return retv;
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */
```
### Notes:
1. 其實這題用brute force硬解也可以過 O(N)
2. 但因為他有告訴你t只會越來越大(等於queue是有排序)
3. 我們只要檢查q.front()有沒有大於t-3000即可，若沒有則pop出來
4. 最終的結果就是q.size()

---
## 649. Dota2 Senate
```c=
class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> radiant_queue, dire_queue;
        for(int i=0; i<senate.length(); i++){
            if(senate[i] == 'R')
                radiant_queue.push(i);
            else 
                dire_queue.push(i);
        }
        while(radiant_queue.size()!=0 && dire_queue.size()!=0){
            int r_index = radiant_queue.front();
            radiant_queue.pop();
            int d_index = dire_queue.front();
            dire_queue.pop();
            
            //代表D會被ban掉，把R重新丟回queue裡面
            if(r_index < d_index){
                radiant_queue.push(r_index + senate.length());
            }
            else{
                dire_queue.push(d_index + senate.length());
            }
        }
        return (radiant_queue.size()==0)?"Dire":"Radiant";
    }
    
};
```
### Notes:
1. 這題的解法很漂亮
2. 因為會有順序的關係，queue裡面存的是index
3. R_index < D_index，代表R一定可以把D給ban了
4. R_index因為還有下一輪，所以還要重新放回queue (line 19)