# 演算法作業04
## 第1題: Selection Sort
### 請使用Selection sort排序，6,4,1,3,5。在四個回合中，每回合的Change of Flag數量為何？總共的Change of Flag數量為何？
:::info
Change of Flag的定義(個人想法)：
從$a_0$開始往$a_{n-1}$走，如果遇到比較小的$a_i$就+1，
然後把$a_0$跟$a_i$交換，繼續比對
:::
:::info
初始陣列：
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 6 | 4 | 1 | 3 | 5 |
:::
:::info
第一回合
初始化：
`f`設為0
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| <font color="#f00">6</font> | 4 | 1 | 3 | 5 |
| j | f |
| --- | --- |
| 0 | 0 |
遇到4，$a_k<a_f$，
`Change_of_Flag++`
`f=j`
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 6 | <font color="#f00">4</font> | 1 | 3 | 5 |
| j | f |
| --- | --- |
| 0 | 1 |
遇到1，$a_k<a_f$，
`Change_of_Flag++`
`f=2`
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 6 | 4 | <font color="#f00">1</font> | 3 | 5 |
| j | f |
| --- | --- |
| 0 | 2 |
遇到3，$a_k\geq a_f$，不做事
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 6 | 4 | 1 | <font color="#f00">3</font> | 5 |
| j | f |
| --- | --- |
| 0 | 2 |
遇到5，$a_k\geq a_f$，不做事
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 6 | 4 | 1 | 3 | <font color="#f00">5</font> |
| j | f |
| --- | --- |
| 0 | 2 |
最後將$a_j$和$a_k$交換
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| <font color="#f00">1</font> | 4 | <font color="#f00">6</font> | 3 | 5 |
<font color="#f00">此回合的Change of Flag是$2$</font>
:::
:::info
第二回合
初始化
`f`設為1
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | <font color="#f00">4</font> | 6 | 3 | 5 |
| j | f |
| --- | --- |
| 1 | 1 |
遇到`6`，$a_k\geq a_f$，不做事
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | <font color="#f00">4</font> | 6 | 3 | 5 |
| j | f |
| --- | --- |
| 1 | 1 |
遇到3，$a_j<a_f$，
`Change_of_Flag++`
`f=3`
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 4 | 6 | <font color="#f00">3</font> | 5 |
| j | f |
| --- | --- |
| 1 | 3 |
遇到`5`，$a_k\geq a_f$，不做事
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 4 | 6 | <font color="#f00">3</font> | 5 |
| j | f |
| --- | --- |
| 1 | 3 |
最後將$a_j$和$a_k$交換
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | <font color="#f00">3</font> | 6 | <font color="#f00">4</font> | 5 |
<font color="#f00">此回合的Change of Flag是$1$</font>
:::
:::info
第三回合
初始化
`f`設為2
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 3 | <font color="#f00">6</font> | 4 | 5 |
| j | f |
| --- | --- |
| 2 | 2 |
遇到4，$a_k<a_f$，
`Change_of_Flag++`
`f=3`
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 3 | 6 | <font color="#f00">4</font> | 5 |
| j | f |
| --- | --- |
| 2 | 3 |
遇到`5`，$a_k\geq a_f$，不做事
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 3 | 6 | <font color="#f00">4</font> | 5 |
| j | f |
| --- | --- |
| 2 | 3 |
最後將$a_j$和$a_k$交換
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 3 | <font color="#f00">4</font> | <font color="#f00">6</font> | 5 |
<font color="#f00">此回合的Change of Flag是$1$</font>
:::
:::info
第四回合
初始化
`f`設為3
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 3 | 4 | <font color="#f00">6</font> | 5 |
| j | f |
| --- | --- |
| 3 | 3 |
遇到4，$a_k<a_f$，
`Change_of_Flag++`
`f=4`
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 3 | 4 | 6 | <font color="#f00">5</font> |
| j | f |
| --- | --- |
| 3 | 4 |
最後將$a_j$和$a_k$交換
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| 1 | 3 | 4 | <font color="#f00">5</font> | <font color="#f00">6</font> |
<font color="#f00">此回合的Change of Flag是$1$</font>
:::
:::success
第一回合:2
第二回合:1
第三回合:1
第四回合:1
總共:5
:::
## 第2題: Quick Sort
### 使用Quick排序7個數字，1,2,3,4,5,6,7，請說明每回合的pivot如何選擇，會有best case。請參考投影片33頁，畫出二元樹表示。
:::info
每次選擇的pivot都要對半切，這樣就會是best case
紅色是第一刀，藍色是第二刀
:::
:::success
第一回合要選擇4
第二回合要選擇2
第三回合要選擇6
best case會是: 4213657
:::
### 呈上題，請說明每回合的pivot如何選擇，會有worstcase。請參考投影片33頁，畫出二元樹表示。
:::info
每一刀都只把自己切掉，這樣就會跑$N$次
所以這棵二元樹會是歪斜的
:::
:::success
答案有兩個
一個左歪斜一個右歪斜
worst case: 1234567 or 7654321
:::
## 第3題: 2-D Ranking Finding
### 平面上四個點，(1,1),(2,2),(3,3),(4,4)。請依照課本的方法，說明如何找出四個點的Ranking。(可配合畫圖表示)
:::info
先把點排序好，再用中間值去切分
切到剩一個
再將左右邊合併
右邊每個點去加多少個`y`比他小的
:::
:::success
註：這邊以$(i,i)$的點以$i$表示
* 步驟一、排序
* 步驟二、遞迴切半
* $[1,2,3,4]$
* $[1,2]\ [3,4]$
* $[1]\ [2]\ [3]\ [4]$
* 步驟三、遞迴上來同時將左右邊做合併處理
0. $rank$初始狀態
| 1 | 2 | 3 | 4 |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 0 |
1. $[1]+[2] => [1,2]$
| <font color="#00f">1</font> | <font color="#00f">2</font> | 3 | 4 |
| --- | --- | --- | --- |
| 0 | 1 | 0 | 0 |
`y`比2小的有一個所以`rank[2]+=1`
2. $[3]+[4] => [3,4]$
| 1 | 2 | <font color="#00f">3</font> | <font color="#00f">4</font> |
| --- | --- | --- | --- |
| 0 | 1 | 0 | 1 |
`y`比4小的有一個所以`rank[4]+=1`
3. $[1,2]+[3,4] => [1,2,3,4]$
| <font color="#00f">1</font> | <font color="#00f">2</font> | <font color="#00f">3</font> | <font color="#00f">4</font> |
| --- | --- | --- | --- |
| 0 | 1 | 2 | 3 |
`y`比3小的有一個所以`rank[3]+=2`
`y`比4小的有一個所以`rank[4]+=2`
結果就是
| dots | 1 | 2 | 3 | 4 |
| ---- | --- | --- | --- | --- |
| rank | 0 | 1 | 2 | 3 |
:::
我自己畫ㄉGIF
## 第4題：兩數之和
### 解題思路1
枚舉每個$a_i$，然後設$tmp$為成為target的差
$tmp=target-a_i$
然後因為要避免重複搜尋到自己($a_i$)
所以把二分搜的左右界先用好
1. 如果$tmp \geq a_i$，則`l=i+1,r=numbers.size()-1`
2. 如果$tmp<a_i$，則`l=0,r=i-1`
這樣就可以很輕鬆的使用二分搜
還可以避免搜尋到自身
最後再回傳就可以了
這個方法是$O(nlogn)$
### 程式碼1
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i,l,r,mid;
vector<int> ans;
for(i=0;i<numbers.size();i++)
{
int tmp=target-numbers[i];
if(tmp>=numbers[i])
{
l=i+1;
r=numbers.size()-1;
}
else
{
l=0;
r=i-1;
}
while(l<=r)
{
mid=(l+r)>>1;
if(numbers[mid]>=tmp)
{
r=mid-1;
}
else
{
l=mid+1;
}
}
if(l<numbers.size()&&numbers[l]==tmp)
{
ans=vector<int>{min(i+1,l+1),max(i+1,l+1)};
break;
}
}
return ans;
}
};
```
#### 可以用也map解
時間複雜度一樣
如果改成unordered_map照理來說效果也會不錯
不過建雜湊的常數太高了，結果有點差
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
map<int,int> m;
for(int i=0;i<numbers.size();i++) m[numbers[i]]=i+1;
for(int i=0;i<numbers.size();i++)
{
auto p=m.find(target-numbers[i]);
if(p!=m.end()) return vector<int>{min(i+1,p->second),max(i+1,p->second)};
}
return vector<int>{0,0};
}
};
```
### 測試輸出輸入的畫面截圖1
7ms
### 解題思路2
`l=0,r=numbers.size()-1`
分成4個狀況
1. `numbers[l]+numbers[r]>target`
2. `numbers[l]+numbers[r]<target`
4. `numbers[l]+numbers[r]==target`
狀況1: 要把`numbers[l]+numbers[r]`變小，所以把`r-1`
狀況2: 要把`numbers[l]+numbers[r]`變大，所以把`l+1`
狀況3: 符合`target`，所以就可以return答案了
這個方法是$O(n)$
### 程式碼2
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l=0,r=numbers.size()-1;
int tmp=numbers[l]+numbers[r];
while(tmp!=target)
{
if(tmp>target)
{
r--;
}
else
{
l++;
}
tmp=numbers[l]+numbers[r];
}
return vector<int>{l+1,r+1};
}
};
```
### 測試輸出輸入的畫面截圖2
10ms
### 解題思路3
把上面的`l+1`跟`r-1`改成用二分搜
時間一樣是$O(N)$，可是常數低很多
### 程式碼3
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int ll,rr,l=0,r=numbers.size()-1,tmp,mid;
while(numbers[l]+numbers[r]!=target&&l<=r)
{
cout<<l<<' '<<r<<endl;
cout<<numbers[l]<<' '<<numbers[r]<<endl;
if(numbers[l]+numbers[r]<target)
{
ll=l;
rr=r-1;
while(ll<=rr)
{
mid=(ll+rr)>>1;
tmp=numbers[r]+numbers[mid];
if(tmp==target)
{
return vector<int>{mid+1,r+1};
}
else if(target < tmp)
{
rr=mid-1;
}
else
{
ll=mid+1;
}
}
l=ll;
}
else if(numbers[l]+numbers[r]>target)
{
ll=l+1;
rr=r;
while(ll<=rr)
{
mid=(ll+rr)>>1;
tmp=numbers[l]+numbers[mid];
if(tmp==target)
{
return vector<int>{l+1,mid+1};
}
else if(target < tmp)
{
rr=mid-1;
}
else
{
ll=mid+1;
}
}
r=ll-1;
}
}
return vector<int>{l+1,r+1};
}
};
```
### 測試輸出輸入的畫面截圖3
3ms超讚
### 解題時間
12分鐘(如果不算後面幾個的時間的話)
### 完成程度
完全自己解出
## 第5題：回文Palindrome
### 解題思路
`tolow()`是在做把大寫轉小寫，其他照樣傳
`isAaOR19()`是判斷是不是大小寫字母跟數字
一個指針放左邊
一個指針放右邊
過程中如果不符合`isAaOR19()`就跳下一個字
一直往中間跑
在跑之前先設一個`bool f=1`
如果有不同的字就把`f`改成0
最後再回傳`f`就好了
### 程式碼
```cpp=
class Solution {
public:
char tolow(char ch)
{
return ch>='A'&&ch<='Z'?ch-'A'+'a':ch;
}
bool isAaOR19(char ch)
{
return ch>='a'&&ch<='z' || ch>='A'&&ch<='Z' || ch>='0'&&ch<='9';
}
bool isPalindrome(string s) {
int l=0,r=s.size()-1;
bool f=1;
while(l<r)
{
while(l<r&&!isAaOR19(s[l]))
{
l++;
}
while(l<r&&!isAaOR19(s[r]))
{
r--;
}
if(tolow(s[l])!=tolow(s[r]))
{
f=0;
break;
}
l++;
r--;
}
return f;
}
};
```
### 測試輸出輸入的畫面截圖
### 解題時間
10分鐘
### 完成程度
完全自己解出
## 第6題：Linked List是否存在Cycle
### 解題思路
直覺(?)
龜兔賽跑:D，看到判圈就想到歐拉迴圈，就用上去了
簡單來說就是
`r`是兔子一次跑兩步
`t`是烏龜一次跑一步
如果有環最終一定會撞到一起
### 程式碼
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *r=head;
ListNode *t=head;
while(t!=NULL&&r!=NULL&&r->next!=NULL)
{
r=r->next->next;
t=t->next;
if(r==t)
{
return 1;
}
}
return 0;
}
};
```
### 測試輸出輸入的畫面截圖
### 解題時間
8分鐘
### 完成程度
完全自己解出
## 第7題：心得
已填
Sign in with Wallet
Connect another wallet