---
# System prepended metadata

title: info2023-homework1

---

#  info2023-homework1
> 貢獻者: 托爾-Thor
> > ==[video1]()==,==[[video2]]()==, ==[video(英)]()==

> > 
> 🧔：interviewer    👶：interviewee

## [[268. Missing number]](https://leetcode.com/problems/missing-number/)

### 題目描述
給定一個數組nums,有0到n,種共有n+1個數
同時給一個數組裡面有n個數,找出缺少的那一個數(也就是missing number)

![](https://hackmd.io/_uploads/ByB7RBdka.png)
### 程式碼解說
#### 方案一 : ***利用等差,相減,求出missing number***
```cpp
int numssum=0;
int numstotal = 0;
    for(i=0;i<nums.size();i++){
        //numssum=nussum+nums[i];
    }
    for(...){
        //numstotal=totoalsum+i;
    }
    return numstotal-numssum;
```
##### 方案一(較優的寫法) : ***利用高斯等差求和公式:n(n+1)/2***
```cpp
int missingnumber(vector<int>& nums){
    int sum = 0;
    int n=nums.size();
    for(auto &a :nums){
        sum+ =a;
    }//nums累加
    return n*(n+1)*0.5-sum;
}
```
#### 方案二 : ***利用邏輯運算XOR特性求解***
XOR真值表
![](https://hackmd.io/_uploads/Byc6xIukT.png)
```cpp
int missingnumber(vector<int>& nums){
    int res =0;
    int n=nums.size();
    for(int i=0;i<n;i++){
        res ^=(i+1)^nums[i];
    }
    return res;
}
```
#### 方案三 : ***index sort求解***
```cpp
int missingnumber(vector<int>& nums){
    int n=nums.size();
    nums.push_back(INT_MAX);
    for(int i=0;i<=n;i++){
        while(nums[i]!=i && nums[i]<=n){
            swap(nums[i],nums[nums[i]]);
        }
    }
    for(int i=0;i<=n;i++){
        if(nums[i]!=i)
            retur i;
    }
}
```

## [[9.Palindrome Number]](https://leetcode.com/problems/palindrome-number/)
### 題目描述
![](https://hackmd.io/_uploads/rkU9wUu16.png)
### 程式碼解說
#### 方案一 : ***轉換為字串進行比對***
將整數 x 轉換為字串表示形式。
設定一個 for循環，從字串的開頭（索引 0）迭代到字串的中間（長度/2）。
在循環內，將目前位置的字元(number[i]) 與字串末尾對應位置的字元(number[length - i - 1])進行比較。
如果字元不符（即從中心向外不是回文數），則立即傳回false，表示不是回文數。
如果循環 完成後沒有發現任何不匹配（所有數字都匹配），則傳回true，表示該整數是回文。
```cpp
bool isPalindrome(int x) {
        string number = to_string(x) ;
        int length = number.size() ;
        for(int i = 0 ; i < length / 2 ; i ++){
            if(number[i] != number[length - i - 1])
                return false ;
        }
        return true;
    }
```
#### 方案二 : ***10進位反轉一半的數字***
以只反轉數字的後半部分，而不是反轉整個數字。這種方法很棘手，因為當我們反轉數字的後半部時，我們不希望中間的數字反轉回其原始值。如果數字的位數為奇數，就會發生這種情況。為了解決這個問題，我們可以將數字的前半部分與相反的後半部分進行比較。

解釋：
我們首先進行初步檢查以處理特殊情況：

在循環內部，我們x使用模運算子提取最後一位數字%，並將其乘以 10 後加到reversed變數中（將現有數字左移）。
// string = 1 2 3 2 1		reverse = 1
mod =1 

然後我們除以x10 以刪除最後一位數字並將其移向數字的中心。
循環完成後，我們反轉了後半部的數字。現在，我們將數字的前半部 ( x) 與反轉的後半部 ( reversed) 進行比較，以確定數字是否為回文：

對於偶數位，如果x等於reversed，則該數字是回文數。我們回來了true。
對於奇數個數字，如果x等於reversed / 10（忽略中間數字），則該數字是回文數。我們回來了true。
如果以上條件都不滿足，則表示該數不是回文數，因此傳回false。
程式碼僅比較必要的部分，從而避免了反轉整個數字的需要。這種方法降低了時間複雜度和記憶體使用量，從而產生更有效的解決方案
```cpp
    bool isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        int reversed = 0;
        while (x > reversed) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }
        return (x == reversed) || (x == reversed / 10);
    }
```
### 對話內容
🧔:好的,托爾,那現在我們進到第二題
我將會給你整數x,想請你判斷是否為回文數,如果是的話回傳true,否則回傳false
而所謂的回文數也就是正著讀跟反著讀會是一樣的,這邊先舉幾個例子
![](https://hackmd.io/_uploads/S1d_T6YkT.png)
👶：想請問x是否有範圍限制
🧔:有的,我們的x範圍界在-2^31 < X <(2 ^ 31) -1
👶：了解,那我這邊想到可以先將整數 x 轉換為字串表示形式
接著設定for循環從字串的開頭,也就是index為0開始每次都往後一格直到字串的中間(長度/2)的位置
並將目前位置的字元(number[i]),與字串對應位置的字元(number[length - i - 1])進行比較(舉例)
![](https://hackmd.io/_uploads/S1d_T6YkT.png)
如果數值不同代表不為回文數,(return false)
若逐一比較後皆為相同的代表是回文數,回傳true
👶：(coding ...方案一 : 轉換為字串進行比對)
🧔:那是否可以不藉由轉換成字串的方式也能夠判斷是否為回文數呢??
👶：以整數的型態翻轉其中一半去跟另一半比較,如果一樣那就是回文數
因為無法使用字串的形式所以我想可以使用10進位的規則,如果對input的輸入數值每次都除以十並把餘數留存在進行,進位的排序就可以得到反轉的數值(舉例)
![](https://hackmd.io/_uploads/BJrsRaty6.png)
這邊可能得先排除掉幾種特例
首先第一種
avoid
1. x < 0 (x=-123)
	reverse x=321-
2. x = 10*n倍 (x=10,20,30....
	reverse x=01,02,03 
    
👶：(coding ...方案二 : 10進位反轉一半的數字)
🧔:比較一下兩種方式的哪種比較好以及解釋原因
👶：值觀為第一種,但第二種較優(解釋原因...)


## [[189.Rotate Array]](https://leetcode.com/problems/rotate-array/)
### 題目描述
![](https://hackmd.io/_uploads/Hyf4YUdyT.png)
### 程式碼解說
#### 方案一 : ***以矩陣存儲並使用for迴圈逐一走訪執行翻轉***
```cpp
void rotate(vector<int>& nums,int k){
    vector<int> newArray =nums;
    for(int i=0;i<nums.size();i++){
        nums[(i+k)%nums.size()]=newArray[i];
    }
}
```
#### 方案二 : ***以reverse翻轉指定區域***
```cpp
void retate(vector<int>&nums ,int k ){
    if (k> nums.size()) k% =nums.size();
    reverse(nums.begin(),nums.end());
    reverse(nums.begin(),nums.begin()+k);
    reverse(nums.begin()+k,nums.end());
}
```
### 對話內容
🧔:hi torr I am todays interviewer
I well give you a question and we are going to discuss how to get the sloution 
so if you are already that's getting started
🧔:In this question
 first  I well given an array.
 rotate the array to the right by k steps where k is non-negative for example  1 2 3 4 5 6 7 and K is 3 the final output is 5 6 7 and then 1 2 3 4 because we rotate this array to the right by 3 staps so first rotate one step it becomes 7 1 2 3 4 5 6 because every single number moves towards the right by one step and the last number that on the very right end moves towards the beginning. so that where 7 moves becames to one position and then we continue to do this for the second step. then everything like 1 2 3 4 5 6 7 move towards the right .
so the 6 becomes to 7 position right? so we continue to do that. For the third time  all of these move towards the right and then 5 well come to the first position that's how it end. 

👶：ok,let me give an example to verify whether my understanding of this question is correct.
so for example,if input is  [-1 -100 3 99] and K is 2
that means we rotate this array to the right by 2
so after rotate 2 stepts the output is [3 99 -1 -100] we just shift the array to the right repeate two times right?
🧔:yes
👶：ok,so I think the first we can use the brute-force , ues for loop to rotate every single element out of the n element towards the right one at a time and do this K times ,so the time complexity of that is going to be n times K,in this way not efficient  to slove this problem,
to optimize this solution,I think we can 
''use an extra array which means we can copy the entire original input array into the second array so basically we put we assign we can pre calculate every single element that should be rotated into its correct position as an extra array so that later on we can just basically copy the actual array into the original array so then every element in the original array is at its final rotated position how can we do that let's take a look at here so 1 2 3 4 5 6 7''
![](https://hackmd.io/_uploads/BkBgGCKkT.png)

the i equals 0 is move to i equals 3
and i equals 1 is becomes to the index iequals 4
(coding ...)
🧔:sounds a good way ,but could you give me the way ,can reduce the space complexity is O(1)??
👶：let me think,...
the 2 way I well use reverse function to revers the array and restrict the range to reach the same answer
let me take the example![](https://hackmd.io/_uploads/HkR2ZCKJp.png)
so  the code is like (coding ...)
🧔:ok,good I think we are finish ,thank for coming this interview
### 面試過程檢討(初步自評)
#### **優點**
* 再給出想到的做法實作程式碼前有先解釋自己的想法,並舉案例,較易於理解
#### **缺點**
* 面試官這個說詞可以改成另一個名稱取代,儘量不要有上對下的關係存在
* 錄製的音訊會有回音需要想辦法避免
* 英文口說需要加強,段句需要清楚,不然會聽不懂
* 可以更深入對演算法的時間複雜度和空間複雜度做討論
---------------------------
#  info2023-homework2
## [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

> [video](https://youtu.be/8sw8CuywsbE)
### 題目描述
希望可以讓在校住宿生參與的活動,但是由於場地受限,目前開放三個梯次
每位學生最多只能報名一個場次,如果重複報名到其他場次將會刪除報名資格
![](https://hackmd.io/_uploads/By00vccWp.png)
如何將重複報名得學生刪除於已報名學生的名單中?
### 程式碼
```cpp
//input =[0,1,3,4,7,9,10]
Listnode* deleteRep(Listnode* head){
    Listnode* dummy =new Listnode(0,head);
    Listnode *cur =dummy;
    while(cur->next && cur->next->next){
        if(cur->next->val == cur->next->next->val){
            int x = cur->next->val;
        }
        while(cur->next->val && cur->next->next->val == x){
            cur->next = cur->next->next;
        }
    }
    else{
        cur = cur->next;
    }
    return dummy->next;     
}
```
### 對話內容
需考慮:
1.如何把當前的節點刪除
2.頭節點重複需要刪除時該如何
所以可以先假設在頭節點前其實還有一個節點

------------------------------------
解釋過程...

------------------------------------
程式實作:
所以回到程式碼的部分首先創立一個節點存儲最剛開始的head
這樣dummy這個list node就會取代第一個頭節點
接著用cur保存原來head節點(可理解為當前指向的節點
所以接下來可以用來比較next跟n.n是否為相同

### 面試過程檢討(初步自評)
#### **優點**
改寫leetcode題目,結合於生活上,(舉例:學生報名通識活動)
解釋理解舉例,並於最後再舉實例對應情況
#### **缺點**
中間過程,while打錯,在debug舉例時才發現