# 演算法導論 HW4
https://hackmd.io/@wang1234/BJu0tDNZq
## 第1題: Selection Sort
<font color="DarkGray" class="small">* 請使用Selection sort排序，6,4,1,3,5。在四個回合中，每回合的Change of Flag數量為何？總共的Change of Flag數量為何？</font>
| j | 排序情況 | change of flag數量 |
| -------- | -------- | -------- |
| | 6,4,1,3,5 | |
| 1 | <font color="LimeGreen">1</font>,<font color="Magenta">4</font>,<font color="Magenta">6</font>,3,5 |<font color="DeepSkyBlue">2</font> |
| 2 | <font color="LimeGreen">1,3</font>,6,<font color="Magenta">4</font>,5 | <font color="DeepSkyBlue">1</font> |
| 3 | <font color="LimeGreen">1,3,4</font>,<font color="Magenta">6</font>,5 | <font color="DeepSkyBlue">1</font> |
| 4 | <font color="LimeGreen">1,3,4,5</font>,<font color="Magenta">6</font> | <font color="DeepSkyBlue">1</font> |
| | <font color="LimeGreen">1,3,4,5,6</font> | (加總)<font color="DeepSkyBlue">5</font> |
## 第2題: Quick Sort
<font color="DarkGray" class="small">* 使用Quick排序7個數字，1,2,3,4,5,6,7，請說明每回合的pivot如何選擇，會有best case。請參考投影片33頁，畫出二元樹表示。</font>
best case的pivot : 每回合都可以選到中位數作為pivot，讓數字能分成大小差不多的兩區塊
<font color="DarkGray" class="small">* 呈上題，請說明每回合的pivot如何選擇，會有worst case。請參考投影片33頁，畫出二元樹表示。</font>
worst case的pivot : 每回合選到的pivot都是最大值或最小值，以至於某一每次只分出去一個數字
## 第3題: 2-D Ranking Finding
<font color="DarkGray" class="small">* 平面上四個點，(1,1),(2,2),(3,3),(4,4)。請依照課本的方法，說明如何找出四個點的Ranking。(可配合畫圖表示)</font>
A(1,1) <font color="DeepSkyBlue">rank(A)=0</font> ⇒ { }       B(2,2) <font color="DeepSkyBlue">rank(B)=1</font> ⇒ {A}
C(3,3) <font color="DeepSkyBlue">rank( C)=2</font> ⇒ {A,B}     D(4,4) <font color="DeepSkyBlue">rank(D)=3</font> ⇒ {A,B,C}
## 第4題：兩數之和
[167. Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)
<font color="Black">
解題思路:
> finger_st和finger_nd初始時指向list的頭尾兩端,
> 如果指向的兩數加起來大過target,表示finger_nd所指向的數太大,
> 因為此時finger_st指向的值在數列中已經找不到比它更小的了,所以應該將finger_nd移往小一點的數,
> 反之,兩數加起來比target小,就把finger_st往更大的數挪動
</font>
```python=
class Solution(object):
def twoSum(self, numbers, target):
finger_st,finger_nd=0,len(numbers)-1
while numbers[finger_st]+numbers[finger_nd]!=target:
if numbers[finger_st]+numbers[finger_nd]>target:
finger_nd-=1
elif numbers[finger_st]+numbers[finger_nd]<target:
finger_st+=1
else:
break
return [finger_st+1,finger_nd+1]
```
花30分鐘，完全靠自己
但有參考老師給的資源 [Leetcode 刷題 pattern - Two Pointer](https://blog.techbridge.cc/2019/08/30/leetcode-pattern-two-pointer/)
## 第5題：回文Palindrome
[121. Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)
<font color="Black">
解題思路:
> 如過去除無關字元後的字串長度小於等於1,那此字串一定是回文
> 若是大於1,從字串的頭和尾開始個抓一個字元,一一比較,但凡有一對不相等,就直接輸出False
> 同時,判斷比較的次數是否已經過字串長度的一半,如果是,就可以確定輸出True
</font>
```python=
class Solution(object):
def isPalindrome(self,s):
s=s.lower()
for i in range(len(s)):
if s[i]<'a' or s[i]>'z':
if s[i]<'0' or s[i]>'9':
s=s.replace(s[i],' ')
s=s.replace(' ','')
if len(s)>1:
for i in range(len(s)):
if s[i]!=s[len(s)-1-i]:
return False
if i>=(len(s)+1)//2:
return True
else:
return True
```
花60分鐘，完全靠自己
## 第6題：Linked List是否存在Cycle
[141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
<font color="Black">
解題思路:
> (sorry,沒有思路,這不是我想出來的答案)
</font>
```python=
class Solution(object):
def hasCycle(self, head):
slow=head
fast=head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
return True
return False
```
花30分鐘，有答案但仍不太懂
答案來源 [Python3 Slow and Fast Pointer Easy Solution](https://leetcode.com/problems/linked-list-cycle/solutions/3274406/python3-slow-and-fast-pointer-easy-solution/?page=3)
## 心得
第6題,我對python中的Linked List完全不了解,也不知道要怎麼使用,只好先去solutions中觀摩別人的解法,此外,這題的題目也看得似懂非懂
Sign in with Wallet
Connect another wallet