# 2024 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2024/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FH1-4KbanC)」HW1
> 貢獻者: 菜就多練-Rookie
## [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/)
> [面試影片(漢)](https://youtu.be/7r467Q1RbvU)
### 題目描述
給定一檔股票，其每日的價格變動資訊儲存在`prices`陣列中，其中`prices[i]`表示第`i`天的股票價格，我們可以選擇在某日買入股票，並於而後的某日賣出股票，請回傳這次交易所能獲得的最大收益，若無法獲得收益，則回傳`0`。
### 程式碼解說
#### *解法一：窮舉法*
直接使用兩層for迴圈，窮舉股票<買入,賣出>的所有可能，若找到更大的獲利且符合先買再賣順序，則更新`max_profit`，最後回傳`max_profit`即可。
##### 時間複雜度：$O(N^2)$
```c++=
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int max_profit = 0;
for (int i=0; i<prices.size(); i++){
for (int j=0; j<prices.size(); j++){
if(prices[j] - prices[i] > max_profit && j>i) max_profit = prices[j] - prices[i];
}
}
return max_profit;
}
};
```
#### *解法二：貪婪法*
首先紀錄股票的買價`buy_price`(初始化為第一天股票的價格`prices[0]`)。接著用一個for迴圈去掃每天股價，每當遇到更低的股票價格時，將`buy_price`更新為該價格。此外，每天都用當天的價格扣掉目前股票的買價來計算潛在的收益`potential_profit`，若潛在收益大於我們儲存的最大收益`max_profit`，則更新`max_profit`。最後同樣回傳`max_profit`即可。
##### 時間複雜度：$O(N)$
```c++=
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int max_profit = 0, buy_price = prices[0];
for (int i=0; i<prices.size(); i++){
if (buy_price > prices[i]) buy_price = prices[i];
int potential_profit = prices[i] - buy_price;
if (potential_profit > max_profit) max_profit = potential_profit;
}
return max_profit;
}
};
```
### 面試過程檢討
#### 整體
- 太常講口頭禪了，面試過程中不斷地說"好"、"然後"、"這樣"、"那" 等等字眼，讓人聽的有點煩躁。
#### Interviewer
- [00:25](https://www.youtube.com/watch?v=7r467Q1RbvU#t=0m25s): 題目該解釋清楚，而不是說詳細的內容你自己看，這樣挺不負責任的。
- [08:30](https://www.youtube.com/watch?v=7r467Q1RbvU#t=8m30s): 口吃了，身為面試官不用緊張吧，口吃是怎樣。
- [13:52](https://www.youtube.com/watch?v=7r467Q1RbvU#t=13m52s): 一直抖是怎樣，好好坐端正說話可以嗎，這是視訊面試餒。
- [14:18](https://www.youtube.com/watch?v=7r467Q1RbvU#t=14m18s): 面試者用了一個貪婪演算法，但是沒有講出"貪婪"這個關鍵字，面試官應該可以在面試者做完後和面試者聊一下這部分。
- [14:21](https://www.youtube.com/watch?v=7r467Q1RbvU#t=14m21s): 這一題還有DP的做法，面試官應該再次詢問面試者有沒有其他想法，而非直接結束。
#### Interviewee
- [04:19](https://www.youtube.com/watch?v=7r467Q1RbvU#t=4m19s): 話講太急了，感覺很想表達但表達不清，導致發出一堆沒必要的聲音，應該要先想好怎麼講再開始說。
- [04:43](https://www.youtube.com/watch?v=7r467Q1RbvU#t=4m43s): 口誤，不是`prices[a]`是`prices[j]`，a跟j的發音念清楚。
- [04:48](https://www.youtube.com/watch?v=7r467Q1RbvU#t=4m48s): code打到一半就開始test了，但依照REACTO，應該把code打完再開始test。
- [06:43](https://www.youtube.com/watch?v=7r467Q1RbvU#t=6m43s): `i=j`又是什麼，同樣講太急，請組織好語言再講。
- [10:54](https://www.youtube.com/watch?v=7r467Q1RbvU#t=10m54s): 這裡應該補充說我們股票買入的價格`buy_price`會時時更新成目前出現過最低的價格，論述會比較完整。
## [400. Nth Digit](https://leetcode.com/problems/nth-digit/description/)
> [面試影片(漢)](https://www.youtube.com/watch?v=3NaAHZwjTVI)
### 題目描述
給一個數字`n`，在從`1`開始的升冪序列中(`[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]`)，請回傳第`n`個digit。
### 程式碼解說
#### *解法一：暴力法*
直接把`[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]`這個數字序列建出來`sequence`，接著題目querry第`n`個，就回傳`sequence[n-1]`即可。
要回傳`n-1`項是因為`sequence`是從`1`開始，但index是從`0`開始，所以`sequence`的第`n-1`項才是答案。
##### 時間複雜度：$O(N)$
```c++=
class Solution {
public:
int findNthDigit(int n) {
string seqence;
for(int i=1;i<=n;i++){
seqence.append(to_string(i));
}
return (seqence[n-1] - '0');
}
};
```
#### *解法二：分析digit規率*
透過觀察得知：
個位數從1\~9(共9個數，每個數佔1 digit)，
十位數從10\~99(共90個數，每個數佔2 digit)，
百位數從100\~999(共900個數，每個數佔3 digit)...以此類推。
因此，我們可以用該位數的個數\*digit來得出該位數在序列中總共佔幾個digit。像是個位數總共佔了9\*1個digit，十位數總共佔了90\*2個digit，百位數總共佔了900\*3個digit...等等。
所以，若`n`大於`9*1`，就代表`n`超過了個位數的範疇(至少是十位數)，若`n`**又**大於`90*2`就代表`n`超過了十位數的範疇(至少是百位數)...一直到n沒有大於該位數的總數\*digit時，即代表n在的那個數屬於這個位數。
因此，我們用`digit`來記錄現在是幾位數(例：個位數digit=1，十位數digit=2)，用`count`來記錄這個位數的數總共有幾個(例：個位數count=9，十位數count=90)，再用`start`來記錄該位數下要從哪裡開始算(例如個位數從1開始算，十位數從10開始算)。
接著用一個while迴圈，依次判斷n有沒有超過個位數、十位數、百位數...的範疇，若超過，則將n減掉該位數所佔的總digit數，再更新`digit`、`count`、`start`成下一位數的資訊。如此一來，就能得知`n`是幾位數。
接著，我們要找`n`是該位數中的哪個數。由於我們得知現在的digit數，因此我們用`n`除以`digit`，再加上`start`，即可得知n屬於哪個數。
接著要找`n`是該數中的哪個數(例如是12中的1 or 2)，因此我們先將該數轉換成字串`num`，接著用`n`對`digit`取餘數即可得知他在`num`中的位置，因此`num[n%digit]`即為序列中第`n`位digit的數字(字元型態)，將其轉回int再回傳即可。
**但如同前面所說，由於序列由1開始，index由0開始，因此我們要用`n-1`去操作才會是對的。**
例如`n=14`，經過前面的while後，各變數情況為`n=5, digit=2, count=90, start=10`，接著用`start`加上`(n-1)/digit`後，得到`start=12`，代表此sequence中第14個digit屬於12這個數，接著先將其轉換成字串`"12"`，又因為`(n-1)%digit = 0`，代表它是在`"12"`這個字串的第0個位置`"1"`，將其轉回int即為答案。
##### 時間複雜度：$O(log_{10}N)$
```c++=
class Solution {
public:
int findNthDigit(int n) {
long long count = 9, digit = 1, start = 1;
// 看n是幾位數
while (n > count * digit) {
n -= count * digit;
digit++;
count *= 10;
start *= 10;
}
// 看n屬於哪個數字
start += (n - 1) / digit;
// 看n在該數字的哪個位置
string num = to_string(start);
return num[(n - 1) % digit] - '0';
}
};
```
### 面試過程檢討
#### 整體
- 和前面一樣，口頭禪有點多，待改進。
#### Interviewer
- [03:50](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=3m50s): 有些code很明確真的可行，建議用肯定一點的語氣，不要說聽起來是可行的這種很不確定的回答。
- [03:52](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=3m52s): 面試者使用了一個需要開額外空間的方法，但面試官卻只問了時間複雜度，理應也要問空間複雜度才合理。
- [06:04](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=6m04s): 面試者只說可以用這樣的思路去思考，並沒有提出具體的方法，但面試官直接說是個不錯的方法，不夠嚴謹。
- [06:06](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=6m06s): 在面試者只有思路的情況下，面試官下一步該問有沒有想到策略去執行該思路，而不該直接叫他去寫code。
- [11:45](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=11m45s): 面試者提出要把`n`減1，但這裡其實沒有那麼直觀，感覺面試官這裡可以提出一些問題來問面試者是怎麼知道，或者怎麼觀察到的，去避免面試者可能不求甚解，只知道這樣做會對，而不知道為什麼會對。
- [14:16](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=14m16s): 面試官不要口吃，你的你的什麼啦。
#### Interviewee
- [01:35](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=1m35s): 請組織語言，想好再講。
- [03:21](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=3m21s): 它會回傳到4還是會爆掉，想好再講。
- [05:05](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=5m05s): digit 2的數字有90個，因為10-99，這聽起來很讓人覺得你背答案，理應是要先講10-99是digit 2的數字，才算出總共有90個，而非直接講有90個再補充說是10-99。
- [05:33](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=5m33s): digit 1明明只有9個而非90，請組織好語言再講，一直口誤很扣分。
- [05:52](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=5m52s): 同樣，請把邏輯先打理好再講，不然一直口誤再修正感覺很差。
- [06:38](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=6m38s): 先理清思緒再打code，把變數寫出來但卻講不出代表什麼，只會讓別人覺得你背答案。
- [06:50](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=6m50s): 不該先打while迴圈才講原因，應該先把原因講清楚再開始打code。
- [08:12](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=8m12s): 同樣，邏輯想好再打code，不要打了要解釋又卡很久才想到怎麼解釋。
- [09:26](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=9m26s): 應該在講while迴圈時就講這是在判斷位數，而非舉完小例子後才補上。
- [09:48](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=9m48s): 面試者把code打上去後發現還沒解釋，又把code刪掉，這個做法又更容易讓面試官認為你在背code。
- [13:18](https://www.youtube.com/watch?v=3NaAHZwjTVI#t=13m18s): 該先解釋會什麼它會是答案，而非直接說我們return這個，因為它是答案。
## [83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/)
> [面試影片(英)](https://www.youtube.com/watch?v=WpSe3hZwCwM)
### 題目描述
給定一個排序好的linked list的head，請把該linked list中val重複的node刪除，讓所有node的val皆只出現過一次，最後回傳處理完的linked list的head。
### 程式碼解說
#### *解法一：使用set*
由於要刪除重複的val，因此我先想到開一個set`myset`，將linked list中各node的val放進`myset` 裡，每當拜訪node時，就用`myset`判斷該node的val是否已經存在，若不存在，就代表該Node要保留，此時就先將該node的val紀錄進`myset`，並繼續前進下一個node；但若該node的val已經存在於`myset`，代表這個node該被刪掉，此時我們就將我們原本的`next`指標改成再下一個node即可。拜訪完整條linked list後，再回傳head即可。
##### 時間複雜度：$O(NlogN)$
```c++=
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *now = head;
set<int> myset;
// 看head是否存在
if (now != NULL) myset.insert(now->val);
else return head;
while(now->next != NULL){
// 沒看過的val，保留node
if( myset.find(now->next->val) == myset.end() ){
myset.insert(now->next->val);
now = now->next;
}
// 有看過的val，刪除node
else{
ListNode *del = now->next;
now->next = now->next->next;
delete(del);
}
}
return head;
}
};
```
#### *解法二：直接比較*
由於題目給的linked list是排序過的，因此其實不用使用set來判斷該val是否出現過，反而可以直接拿現在的node和下一個node來比較他們的val，若不重複則都保留，若有重複則刪除後面的node，同樣拜訪完整條linked list，最後回傳head即可。
##### 時間複雜度：$O(N)$
```c++=
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *now = head;
while(now!=NULL && now->next!=NULL){
// 若後面node的val和前面node的val相同，則刪除後面的node
if(now->val == now->next->val) {
ListNode *del = now->next;
now->next = now->next->next;
delete(del);
}
else now = now->next;
}
return head;
}
};
```
### 面試過程檢討
#### 整體
- 英文口說要練，有些地方文法講錯。
- 一樣有些英文的口頭禪，請不要過度的講，聽了有些煩。
#### Interviewer
- [02:17](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=2m17s): 面試者提出一個可行的方法，那個嘆息聲也太大聲，不應該如此否定面試者。
- [02:20](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=2m20s): 什麼是maybe is can work，請組織一下語言再講。
- [11:10](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=11m10s): 使用者將node從linked list上移除後，並沒有`delete`它(還是有占用memory)，這裡面試官應該問一下使用者是不是還有什麼是忘記做之類的。
- [11:18](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=11m18s): 不要講的卡卡的，想過再講。
- [12:32](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=12m32s): 面試官問面試者有沒有其他想法，但下一秒直接說give you a hint，應該要讓使用者想，若使用者想不到，再給hint。
- [18:08](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=18m08s): 面試者只有改pointer，沒有將node給真正刪掉，這會造成memory leak，面試官該和面試者聊聊這塊。
#### Interviewee
- [00:15](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=0m15s): 這裡該和面試官打聲招呼。
- [01:50](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=1m50s): 想好再講。
- [03:00](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=3m00s): struct結構尾巴沒有";"，這樣會compile error，請熟悉語言。
- [04:18](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=4m18s): temporal不是變數，變數叫做variable，請記熟。
- [05:00](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=5m00s): 想好再講。
- [07:20](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=7m20s): 這裡講的有點饒口，請先整理好思緒。
- [08:05](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=8m05s): we will go this else是啥，應該說we will go this branch，然後鼠標停else那邊。
- [08:20](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=8m20s): 這裡並沒有真的把這個node給刪掉，只是把線給拆掉罷了，講的不嚴謹，應該要在寫code時把它`delete`掉。
- [08:27](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=8m27s): 想好再講。
- [08:58](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=8m58s): 在上一個例子中就會碰到while condition的問題了，但現在才發現，會讓人覺得你剛剛test程式沒有很認真照著程式邏輯走。
- [12:50](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=12m50s): 請組織語言，練練文法。
- [13:07](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=13m07s): 不是比較previous跟next，是比較previous跟current(這裡我突然忘記current這個單字才講next)，請記熟，不要講錯。
- [16:45](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=16m45s): 請講this branch。
- [17:43](https://www.youtube.com/watch?v=WpSe3hZwCwM#t=17m43s): 什麼they are not correct，they are not the same才對，不要口誤。
Sign in with Wallet
Connect another wallet