---
# System prepended metadata

title: 演算法導論 HW4

---

# 演算法導論 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，讓數字能分成大小差不多的兩區塊
![](https://i.imgur.com/syizcqi.png)

<font color="DarkGray" class="small">* 呈上題，請說明每回合的pivot如何選擇，會有worst case。請參考投影片33頁，畫出二元樹表示。</font>
worst case的pivot : 每回合選到的pivot都是最大值或最小值，以至於某一每次只分出去一個數字
![](https://i.imgur.com/TkUQ5np.png)

## 第3題: 2-D Ranking Finding
<font color="DarkGray" class="small">* 平面上四個點，(1,1),(2,2),(3,3),(4,4)。請依照課本的方法，說明如何找出四個點的Ranking。(可配合畫圖表示)</font>
![](https://i.imgur.com/3AIT8eF.png)
A(1,1)&emsp;<font color="DeepSkyBlue">rank(A)=0</font> ⇒ { } &emsp;&emsp;&emsp;&emsp;&emsp; B(2,2)&emsp;<font color="DeepSkyBlue">rank(B)=1</font> ⇒ {A}
C(3,3)&emsp;<font color="DeepSkyBlue">rank( C)=2</font> ⇒ {A,B} &emsp;&emsp;&emsp; D(4,4)&emsp;<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]
```
![](https://i.imgur.com/1lCVrWW.png)
花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
```
![](https://i.imgur.com/CDXacqi.png)
花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
```
![](https://i.imgur.com/BohGBLa.png)
花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中觀摩別人的解法,此外,這題的題目也看得似懂非懂
