# 演算法作業四

## 觀念題
### 第1題: Selection Sort
| **round** | **a1** | **a2** | **a3** | **a4** | **a5** | **Change of Flag** |
|:---------:|:------:|:------:|:------:|:------:|:------:|:------------------:|
| 0 | 6 | 4 | 1 | 3 | 5 | X |
| 1 | 1 | 4 | 6 | 3 | 5 | 2 |
| 2 | 1 | 3 | 6 | 4 | 5 | 1 |
| 3 | 1 | 3 | 4 | 6 | 5 | 1 |
| 4 | 1 | 3 | 4 | 5 | 6 | 1 |

> 總共：5
### 第2題: Quick Sort
1. Best Case
- 每次選擇的pivot要是中位數
- 以每次的pivot畫成二元樹
- 以分割後的array畫成二元樹
2. Worst Case
- 每次選擇的pivot要是最小值
- 以每次的pivot畫成二元樹
- 以分割後的array畫成二元樹

### 第3題: 2-D Ranking Finding


> Rank( A ) = 0
> Rank( B ) = 1
> Rank( C ) = 2
> Rank( D ) = 3
## 程式題

### 第四題：兩數之和
- 程式碼
- 解法一：Hash Table
:::spoiler rust

        use std::collections::HashMap;

        impl Solution {
            pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
                let mut hashTable =  HashMap::new();
                let mut index = 0;
                for i in numbers.iter(){
                    hashTable.insert(i,index);
                    index+=1;
                }        

                index = 0; 
                for i in numbers.iter(){
                    let j = hashTable.get(&(target-i));
                    if let Some(val) = j{
                        return vec![index+1,val.clone()+1];
                    }
                    else{
                        index+=1;
                    }
                }
                return vec![0 as i32,0 as i32];

            }
        }

:::
- 解法二：Two Pointer
:::spoiler rust

        impl Solution {
            pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
                let mut left:i32   = 0;
                let mut right:i32  = numbers.len() as i32 - 1;
                while left <= right{
                    let sum = numbers[left as usize] + numbers[right as usize];

                    if sum == target{
                        return vec![left + 1,right+1];
                    }
                    else if sum > target{
                        right -= 1;
                    }
                    else{
                        left += 1;
                    }
                }
                return [].to_vec();
            }
        }

:::
- 執行結果

- 解題時間
- Hash Table：10分鐘
- Two Pointer：15分鐘

- 完成程度
- Hash Table：完全靠自己
- Two Pointer：觀摩網路
- [ref1](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/solutions/2130327/c-rust-o-n-time-0-1-extra-space/)
- [ref2](https://blog.techbridge.cc/2019/08/30/leetcode-pattern-two-pointer/)

- 思路(Hash Table)
~~我就問誰一開始會想到Two Pointer拉討厭~~
**前言：** Hash Table是我一看到這題的想法
:::spoiler Hash Table 複習
###### Hash Table
Hash Table 是用來儲存Key-Value的資料結構，其運作原理如下

- 他的查詢時間複雜度只有$O(1)$
- 但但但，需要考慮碰撞問題
~~還好有一堆程式語言都有實作出來，所以快跟我說謝謝電神orz~~

:::info
- C++：用unordered_map
- map是用紅黑樹實作喔，時間複雜度是O(logn)，好處是key有排序
- Python：用字典
- Rust：用HashMap
:::
:::

1. 首先，將key當成array中的值，value當成array的index進行插入
2. 最後，我就只要對hash_table查詢target - key即可
- 兩個情形
- Not Found => 繼續找
- Found => 直接查詢

- 複雜度分析：O(n)，但是常數極高，畢竟多了插入與查詢的時間
- 思路(Two Pointer)
1. 其實想法超簡單，我只要把自己可愛的小手手當成left跟right就可以查詢了阿
2. 所以這樣就產生三種狀況
- 當[left] + [right] > target
- 一定是right太大 => 向左搜尋 right--
- 當[left] + [right] < target
- 一定是left太小 => 向右搜尋 left++
- 當[left] + [right] = target
- 答案

- 複雜度分析：O(n)

### 第五題：回文Palindrome
- 程式碼
:::spoiler rust

    impl Solution {
        pub fn is_palindrome(s: String) -> bool {

            let simplify = {
                let mut S:String = "".to_string();
                for i in s.chars(){
                    if (i>='A' && i<='Z') || (i>='a' && i<='z') || (i>='0' && i<='9'){
                        S = S + &(i.to_ascii_lowercase().to_string());
                    }
                }
                S
            };
            if (simplify=="".to_string()){
                return true;
            }
            println!("{}",simplify);

            let mut left:usize  = 0;
            let mut right:usize = simplify.len() - 1;

            while left < right {
                if simplify.chars().nth(left).unwrap() != simplify.chars().nth(right).unwrap(){
                    return false;
                }
                left+=1;
                right-=1;
            }
            return true;
        }
    }

:::
- 執行結果
- 解題時間：5分鐘
- 完成時間：完全靠自己
- 思路
1. 簡單版的Two Pointer吧
2. 一樣有兩個指示器：left, right
3. 當配對成功那繼續
- left++
- right--
4. 失敗則跳出

### 第6題：Linked List是否存在Cycle
- 程式碼
~~這題不能用Rust哭哭~~
:::spoiler C++

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            typedef ListNode* nodeptr;
            nodeptr slow = head;
            if (!slow) return false;
            nodeptr fast = head->next;

            if (!fast) return false;

            while (slow != fast){
                if (!fast || !fast->next) return false;
                slow = slow->next;
                fast = fast->next->next;
            }
            return true;
        }
    };

:::

- 執行結果
- 解題時間：5分鐘
- 完成程度：靠自己
- 思路
1. 解法就是龜兔賽跑法
2. 我一個比較慢(一次一步)，一個比較快(一次兩步)
- 如果是無循環，一定會遇到null，因此遇到直接傳false即可
- 如果是有循環，slow和fast一定會碰到，因此當碰到直接傳true即可
- [證明](https://hackmd.io/_uploads/rJmMwCpp6.png)

## 心得
這周學了LowerBound問題，還有Heap Sort，有了上次的數學大轟炸後覺得這周沒那麼可怕了。

作業的部分都是雙指針，我印象比較深的是第一題，我當時使用的是hash table法，但後來跟朋友互相討論時才發現原來雙指針真的可行，大家好聰明orz。