[toc]
# Info2023-homework 1
## 740. Delete and Earn
==Interviewer：==
這個題目會給你一個存整數的array叫做nums[]。
你必須根據以下規則來獲取最多的分數：
選擇任意nums[i]並刪除，就可以獲得nums[i]的分數。
然後，必須刪除等於nums[i]-1的每一項以及等於nums[i]+1的每一項。
重複以上操作，最後獲得並回傳可獲得的最高分數。
==Interviewee：==
好的，那我舉個例子確認一下我的理解是否正確
假設輸入的陣列nums = [3,4,2]，
首先可以取出4並獲得4分，然後陣列中的3會被刪除，此時陣列中剩下[2]。
再來可以取出剩下的2並獲得2分。
所以我們能獲得的最高分是6分。
再一個較複雜的例子，假設輸入的陣列nums = [2,2,3,3,3,4]，
首先可以取出3並獲得3分，然後陣列中的所有2和4會被刪除，此時陣列中剩下[3,3]。
再來可以取出剩下的其中一個3並獲得3分，
然後再取出最後一個3，獲得3分，
這個例子我們能獲得的最高分是9分。
==Interviewer：==
你的範例沒有錯，
另外，這個題目的限制是：
1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4
如果沒問題的話，可以開始實作你的方法。
==Interviewee：==
我的想法是，先找出輸入陣列的最大整數max_num，
然後再使用另一個陣列accu_num[max_num+1]來儲存輸入陣列不同數字的累加值。
最後，使用Dynamic Programming的方式，從accu_num的index=0到index=max_num，算出能獲得的最高分數。
### Solution
```
int deleteAndEarn(int* nums, int numsSize){
int max_num=0;
for(int i=0;i<numsSize;i++){ //先找出最大整數
max_num=fmax(max_num,nums[i]);
}
printf("max_num=%d\n",max_num);
int accu_num[max_num+1]; //建立array儲存每個number可獲得的pts總和，最小數字為1，但還是從0到n+1來index。
for(int i=0;i<max_num+1;i++) // init
accu_num[i]=0;
for(int i=0;i<numsSize;i++){
accu_num[nums[i]]=accu_num[nums[i]]+nums[i];
}
/*
//print array accu_num[];
printf("accu_num[]:\n");
for(int i=0;i<max_num+1;i++){
printf("%d ",accu_num[i]);
}
*/
//accu_num[]:取了[n]，就要刪除[n-1]、[n+1]。
//DP:先確定長度0、長度1能取得的最高分
int opt_pts[max_num+1];//計算可獲得最多的pts
opt_pts[0]=0;
opt_pts[1]=accu_num[1];
for(int i=2;i<max_num+1;i++){
opt_pts[i]=fmax(opt_pts[i-1],opt_pts[i-2]+accu_num[i]);
}
return opt_pts[max_num];
}
```
==Interviewer：==
能分析你的程式的時間複雜度嗎？
==Interviewee：==
好，從最一開始先找出max_num，到計算accu_num，時間複雜度都是O(n)。
最後使用DP來計算最佳解也是，但需要額外的陣列來儲存DP方法所需的資訊。
## 746. Min Cost Climbing Stairs
==Interviewer：==
題目會輸入一個儲存整數的array叫做cost[]，其中cost[i]是樓梯第i階的成本。
付出第i階的成本，就可以選擇往上爬一階或兩階。
最一開始，可以選擇從第0階開始，也可以從第1階開始爬樓梯。
最後要回傳爬到樓梯頂端消耗的最低成本。
==Interviewee：==
好的，那我舉個例子確認一下我的理解是否正確。
假設輸入陣列是[10,15,20]，
我會選擇從第1階開始爬，然後爬2階到樓梯頂部。
最後花費的最低成本就是15。
再一個較複雜的例子，假設輸入的陣列是[1,100,1,1,1,100,1,1,100,1]，
我選擇從第0階開始爬，付出的成本是1，
往上爬2階到第2階，付出的成本是1，
再往上爬2階到第4階，付出的成本是1，
再往上爬2階到第6階，付出的成本是1，
再往上爬1階到第7階，付出的成本是1，
再往上爬2階到第9階，付出的成本是1。
最後到達樓梯頂部，總共花費的成本是6。
==Interviewer：==
你的範例沒有錯，
另外，這個題目的限制是：
2 <= cost.length <= 1000
0 <= cost[i] <= 999
如果沒問題的話，可以開始實作你的方法。
==Interviewee：==
這題我想可以用DP的方式解決，使用額外的陣列來在計算爬樓梯的途中，每一階累計的最低成本。
給定第0階和第1階的初始條件，計算第2階到第n-1階的最低成本。
最後回傳第n-2階和第n-1階兩者的較小值作為最低成本。
### Solution
```
int minCostClimbingStairs(int* cost, int costSize){
int dp_a[costSize];
//int dp_b[costSize];
dp_a[0]=cost[0];
dp_a[1]=cost[1];
for(int i=2;i<costSize;i++)
dp_a[i]=fmin(dp_a[i-1],dp_a[i-2])+cost[i];
/*
for(int i=0;i<costSize;i++)
printf("%d ",dp_a[i]);
*/
return fmin(dp_a[costSize-1],dp_a[costSize-2]);
}
```
==Interviewer：==
能分析你的程式的時間複雜度嗎？
==Interviewee：==
好，我們使用DP來計算最佳解，從第2階到第n-1階，時間複雜度是O(n)。
不過需要花費額外的空間來儲存DP方法所需的資訊。
## 278. First Bad Version
==Interviewer：==
The problem is that you are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check.
Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad.
Implement a function to find the first bad version.
You should minimize the number of calls to the API.
==Interviewee：==
For example, suppose that Input: n = 5, bad = 4
We can check the version is bad or not ,by calling API as below：
call isBadVersion(3) return false
call isBadVersion(5) return true
call isBadVersion(4) return true
Then 4 is the first bad version.
==Interviewer：==
Your example is correct,
In addition, the constraints of this question are:
1 <= bad <= n <= 231 - 1
If there is no problem, you can start implementing your program.
==Interviewee：==
Because the description of this problem has said that all the versions after a bad version are also bad.
So, we can use binary search to solve this problem.
We declare two variable "top" and "bottom", for calculating the variable "next" indicate the next version we are going to check.
### Solution
```
int firstBadVersion(int n) {
long int next=n/2;
long int top=n;
long int bottom=0;
while(top-bottom>1){
if(isBadVersion(next)==true)
top=next;
else
bottom=next;
next=round((bottom+top)/2);
}
return top;
}
```
==Interviewer：==
Can you analyze the time complexity of your program?
==Interviewee：==
Sure, because we are using binary search method.
For the common cases, we will have time complexity in O(log n).
# Info2023-homework 2
>[video](https://youtu.be/gsvRDImYZ7o)
## 977. Squares of a Sorted Array
==Interviewer：==
同學你好，我是你今天的面試官。
接下來的問題是，你會得到一個排序後的陣列，陣列裡面儲存的是遞增的整數，包含正數、負數、零都有可能，
你必須將陣列內元素做平方後，將重新排序後的陣列回傳。
==Interviewee：==
好的，我初步的想法是，可以將陣列內的元素分別作平方後，再使用排序演算法將陣列做排序，
這個方法的時間複雜度應該會是O(n log n)。
==Interviewer：==
這方法聽起來可行，不過是否有更快的方法，可以在O(n)的時間複雜度內解決？
==Interviewee：==
可以，我們可以使用兩個pointer，分別指向陣列的頭和尾，
先將所有元素做平方之後，我們可以觀察到，因為原始陣列是排序過的陣列，正整數和負整數都有可能存在，平方之後的陣列兩端的元素，會比中間的元素還要大。
我們可以利用這個特性，將兩端的元素比大小，將較大的元素存進要回傳的陣列的最尾端，然後將該較大元素pointer往陣列中間移一格，最後就能得到要回傳的陣列，也已經是遞增的排序。
因為不用另外使用排序演算法來對陣列做重新排序，只需移動兩個pointer，直到做完n次，
所以這個方法的時間複雜度就會是O(n)。
### Solution
```
int* sortedsquares(int* nums,int numssize,int* returnsize){
int *new=(int*)malloc(sizeof(int)*numssize);
*returnsize=numssize;
int top=numssize-1;
int bottom=0;
int insert=numssize-1;
for(int i=0;i<numssize;i++)
nums[i]=nums[i]*nums[i];
while(insert>=0){
if(nums[top]>=nums[bottom]){
new[insert]=nums[top];
top--;
}
else{
new[insert]=nums[bottom];
bottom++;
}
insert--;
}
return new;
}
```
### 同儕互評
### 優點
* 口齒清晰。
### 可改進的地方
* [6:30](https://youtu.be/gsvRDImYZ7o?si=Rm4Sa6oerT_-G1mE&t=390): 根本不需要returnSize，看起來是抄LeetCode的答案。
* [12:30](https://youtu.be/gsvRDImYZ7o?si=Rm4Sa6oerT_-G1mE&t=750): Test的部分應該由interviewee執行。
Sign in with Wallet
Connect another wallet