# 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)
Sign in with Wallet
Connect another wallet