# 資訊科技產業專案設計作業二
泰迪熊 Teddy
## 為他人評分內容簡述
優點:
1.舉例詳細，很好看懂。
2.有加入情境，並且有變化或延伸leetcode題目
3.有討論程式用途
4.面試者說話有語調變化。
可改進的地方:
1.REACTO中的REAT常常漏掉。
2.縮排時連續按鍵盤聲音太大。
3.程式碼錯誤糾正。
4.不要直接使用Leetcode的編輯器面試，因為讓面試者自己找出例子驗證程式正確性也可以做為面試評分的標準。
## 學習到的東西
1.發現REACTO中example和approach的重要，同學影片中有些會略過這兩個步驟，特別是略過approach，直接打程式碼，我從面試官的角度來看會非常混亂，程式碼也變得不好理解，就算有錯，也不一定有辦法立即發現。
2.可以試著說明自己將要用什麼程式語言實作，感覺會讓面試官更好理解，也能大概預期將會用到那些語法或函式庫。
3.使用STL需要先詢問面試官能否使用並且需要了解底層實作方式。
## 作業二
🥸：interviewer 🙂：interviewee
🥸：泰迪熊先生你好，我是Tim，歡迎你參加我們的面試，請您打開剛剛寄給您的面試題目。
## [198.House Robber](https://leetcode.com/problems/house-robber/)
[video](https://youtu.be/TZTy5xcm53I)
🥸：我先說明一下題目，假設我們要建設一條新鐵道，而已經有幾個車站預定地，每站都有估計出預期的每日運輸人次，所以希望你能設計一個程式，找出能夠運輸最多人次的組合，但是考量到車站相鄰太近會造成運輸速度及效益下降，且還有多出的建設成本，所以希望選擇出來的地點彼此不相鄰。那示意圖也在文件中了。程式輸入的部分是一個紀錄運輸量的陣列nums，並且會提供陣列大小，以及一個紀錄選擇地點的陣列station，這個陣列初始都是0，希望你能把選中的車站標示為1，陣列中的元素順序是依照車站的順序排列的。請你回傳這條鐵路的最大運輸量以及選出的車站有哪些。
🙂：那我想請問一下這條鐵路有說最少需要多少站嗎?
🥸：最少需要設定一站，並且可以排除起點和終點兩站，只要把輸入想為鐵路中途的停靠站即可。
🙂：那假設最好的建站方法有兩種以上呢?
🥸：只要輸出其中一種就可以了。
### Repeat
🙂：那這題是要依據最大的鐵路運輸量來建設車站，並且不可以選擇相鄰的兩個地點，要找出最大運輸量以及要建設的地點。
### Examples
🙂：那我舉個例子
```
假設輸入為[3,5,10,11,6,8]單位為萬人次，那我們應該選擇第2、4、6站，並且最大運輸量為24萬人次
輸出的station陣列為[0,1,0,1,0,1]
```
🙂：我這樣的理解是正確的嗎?
🥸：沒錯，請繼續。
### Approach
🙂：那這題因為是一個最佳化問題，而且還會有一些重複計算的部分，所以我想可以用動態規劃來求解。那我直接用上方的例子舉例說明我的作法。
```
[2,7,9,3,1]
題目要考量的是從1~5這些地點中，找出最大的運輸量設站，會發現
說最佳解可以分為兩種情況:也就是考量目前地點有沒有在最佳解中
，以第5個地點為例:
max(5+1~3的最佳解,5不選的解(1~4的最佳解))
```
🙂：所以我們可以發現拆分出了子問題1 ~ 3的最佳解和1~4的最佳解，並且這兩個子問題是有可能出現重複計算的部分，因此我們只需要不斷拆分出子問題，並紀錄子問題的答案，再迭代計算，就可以得到全部的最佳解。至於怎麼看會選到那些車站，我們可以再另外建立一個全部為0的陣列aux記錄max函數比較的結果，如果說目前最佳解需要有第5個地點，就在該陣列中把他對應的位置另為1，否則為0，最後再從陣列回推那些是真正有在最佳解中的地點，更新在station陣列上。
🥸：聽起來還可以，那請你實做看看。
### Code
```clike
int max(int a,int b,int i,int*aux){
if(a>b){
aux[i]=1;
return a;
}else{
aux[i]=0;
return b;
}
}
int FindBestPos(int* nums, int numsSize,int* station){
int*arr=malloc((numsSize+1)*sizeof(int));
int*aux=malloc((numsSize+1)*sizeof(int));
arr[0]=0;aux[0]=-1;
if(numsSize==1){
ans[0]=1;
return nums[0];
}
arr[1]=nums[0];
aux[1]=1;
for(int i=2;i<=numsSize;i++)
arr[i]=max(nums[i-1]+arr[i-2],arr[i-1],i,aux);
int i =numsSize;
while(aux[i]!=-1&&i>=0){
if(aux[i]==1){
station[i-1]=1;
i=i-2;
}
else
i=i-1;
}
return arr[numsSize];
}
```
🙂：時間複雜度是O(n)並且空間複雜度也是O(n)
### Test
🙂：接著我舉個例子驗證
```
nums=[1,7,10,15,2,4]
station=[0,0,0,0,0,0]
arr =[0 ]
aux =[-1 ]
1~1的最佳解是1必選=>arr =[0 1 ],aux=[-1,1]
1~2的最佳解是1、2的最大值=>arr =[0 1 7 ],aux=[1,1]
1~3的最佳解是1+10和7比較=>arr =[0 1 7 11 ],aux=[-1,1,1,1]
1~4的最佳解是7+15和11比較=>arr=[0 1 7 11 22 ],aux=[-1,1,1,1,1]
1~5的最佳解是2+11和22比較=>arr=[0 1 7 11 22 22 ],aux=[-1,1,1,1,1,0]
1~6的最佳解是4+22和22比較=>arr=[0 1 7 11 22 22 26],aux=[-1,1,1,1,1,0,1]
所以我們的最大運輸量是26萬人次
從aux尾端回推那些站被選擇:
aux[6]=1=>代表1~6最佳解是nums[6]+1~4的最佳解(=aux[4]),station[6-1]=1
aux[4]=1=>代表1~4最佳解是nums[4]+1~2的最佳解(=aux[2]),station[3-1]=1
aux[2]=1=>代表最佳解是nums[2]+0的最佳解(=aux[0]),station[2-1]=1
aux[0]=-1代表超出aux陣列前端了，結束while迴圈
最後station=[0,1,0,1,0,1]所以我們需要選擇第2、4、6站。
```
### Optimization
🥸：你的程式碼看起來是可以正確運作的，但是還能不能更降低記憶體使用呢?請說說看你的想法。
🙂：好的，那我發現說我們在找最佳解的時候其實只有在不斷使用上一個最佳解和上上一個最佳解，也就是arr[i]=max(nums[i-1]+arr[i-2],arr[i-1],i,aux);得部分所以我想可以改為只用兩個變數來記錄這兩個值，之後不斷更新，就可以減少一個陣列的使用。
🥸：OK，聽起來不錯，那我們今天的面試就到這邊。
## 自我檢討
1.說話不順，停頓時會發出呃的聲音。
2.測試例子的時間有點太長，
Sign in with Wallet
Connect another wallet