# 演算法 HW4

## :book: 觀念題

### 第一題 Selection Sort
* 請使用Selection sort排序，6,4,1,3,5。在四個回合中，每回合的Change of Flag數量為何？總共的Change of Flag數量為何？
* **第一回合** ==6,4,1,3,5==
flag change : 6->4->1 : 2次
-> 1,4,6,3,5
* **第二回合** ==1,4,6,3,5==
flag change : 4->3 : 1次
-> 1,3,6,4,5
* **第三回合** ==1,3,6,4,5==
flag change : 6->4 : 1次
-> 1,3,4,6,5
* **第四回合** ==1,3,4,6,5==
flag change : 6->5 : 1次
-> 1,3,4,5,6
**共 2+1+1+1=5 次**
### 第二題 Quick Sort
:::info
左邊(i)找比基準點(pivot)大，右邊(j)找比基準點小。
若 i<j ，則 a~i~ ⇿ a~j~
若 i>j ，則 a~pivot~ ⇿ a~j~
:::
* 使用Quick排序7個數字，1,2,3,4,5,6,7，請說明每回合的pivot如何選擇，會有best case。請參考投影片33頁，畫出二元樹表示。

* 呈上題，請說明每回合的pivot如何選擇，會有worstcase。請參考投影片33頁，畫出二元樹表示。

### 第三題 2-D Ranking Finding
* 平面上四個點，(1,1),(2,2),(3,3),(4,4)。請依照課本的方法，說明如何找出四個點的Ranking。(可配合畫圖表示)

* A(1,1) isn't dominated by any point -> rank(A)=0
* B(2,2) is dominated by A -> rank(B)=1
* C(3,3) is dominated by A,B -> rank\(C\)=2
* D(4,4) is dominated by A,B,C -> rank(D)=3

## :desktop_computer: 程式題 Two Pointers類型 (使用語言 : C++)

### 第四題 回文Palindrome

* leetcode 125
* 時間:30分鐘
* 自己完成的程度 : 完全靠自己
* 思路 :
:::success
==i -> 由前往後
j -> 由後往前==

因為只需要判斷英文字母或是數字，所以利用isalnum()函式判斷是否為英文字母或數字，若不是則i++或j--。
當s[i]和s[j]都是數字或字母時判斷是否相同
* 若是，則重複上述動作。
* 若否，則直接回傳false。
:::
* 程式碼 :

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.size()==1)
            return true;
        int j=s.size()-1;
        for(int i=0;i<s.size() && i<=j;i++)
        {
            while(!isalnum(s[i]) && i<j)
                i++;
            while(!isalnum(s[j]) && i<j)
                j--;
            if(tolower(s[i])!=tolower(s[j]))
                return false;

            else
                j--;
        }
        return true;
}
};

* 通過截圖

### 第五題 Linked List是否存在Cycle

* leetcode 141
* 時間:25分鐘
* 自己完成的程度：完全靠自己+老師給的提示
* 思路 :
:::success
同老師給的提示，給定兩個指標，一快(前進2格)一慢(前進1格)，
判斷:
若有NULL出現，則表示沒有Cycle。
若快指標==慢指標，則表示有Cycle。
:::
* 程式碼:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *list1=head;
        ListNode *list2=head;
        if(head==NULL)
            return false;
        else if(head->next!=NULL)
            list2=head->next;
        else
            return false;
        while(list1)
        {
            if(list1==list2)
                return true;
            if(list1->next==NULL || list2->next==NULL)
                return false;
            else if(list2->next->next==NULL)
                return false;
            list1=list1->next;
            list2=list2->next->next;
        }
        return false;
    }
};

* 通過截圖

## :pushpin:心得

### 第六題 本週心得
本周影片，quick sort的二元樹表示的部分，覺得老師講的挺清楚的，也覺得好像懂了。但寫作業時卻又突然不知道要如何下手，因此有找了一下實際例子參考，發現其實不是不會，也不是聽不懂老師說的，只是第一次使用二元樹表示quick sort有點陌生。
這次作業跟以往不同的是，老師給了很多提示，當作業不知道如何下手時，這些提示真的幫助很大。

###### tags: `演算法`