---
# System prepended metadata

title: algo - hw4
tags: [Algorithm]

---

# 演算法作業四

## 觀念題
### 第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畫成二元樹
            ![image](https://hackmd.io/_uploads/HkAEvMxAp.png)
        - 以分割後的array畫成二元樹
            ![image](https://hackmd.io/_uploads/rkSvvzeA6.png)
2. Worst Case
    - 每次選擇的pivot要是最小值
        - 以每次的pivot畫成二元樹
            ![image](https://hackmd.io/_uploads/r1W5wflCa.png)
        - 以分割後的array畫成二元樹
            ![image](https://hackmd.io/_uploads/SyicvMe0p.png)



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

![image](https://raw.githubusercontent.com/kevin0920911/myWebsite/main/algo%20-%20hw4%20-%20animate.gif)

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

### 第四題：兩數之和
- 程式碼
    - 解法一：Hash Table
        :::spoiler rust
        ```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
        ```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();
            }
        }
        ```
        :::
- 執行結果
    ![image](https://hackmd.io/_uploads/BJXA7TTpp.png)

- 解題時間
    - 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的資料結構，其運作原理如下
    ![image](https://hackmd.io/_uploads/S1_QITTpp.png)
    
    - 他的查詢時間複雜度只有$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
    ```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;
        }
    }
    ```
    :::
    - 執行結果
        ![image](https://hackmd.io/_uploads/Sk1coTTTp.png)
    - 解題時間：5分鐘
    - 完成時間：完全靠自己
    - 思路
        1. 簡單版的Two Pointer吧
        2. 一樣有兩個指示器：left, right
        3. 當配對成功那繼續
            - left++
            - right--
        4. 失敗則跳出

### 第6題：Linked List是否存在Cycle
- 程式碼
    ~~這題不能用Rust哭哭~~
    :::spoiler C++
    ```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;
        }
    };
    ```
    :::
    
- 執行結果
    ![image](https://hackmd.io/_uploads/rJq9pTa6a.png)
- 解題時間：5分鐘
- 完成程度：靠自己
- 思路
    1. 解法就是龜兔賽跑法
    2. 我一個比較慢(一次一步)，一個比較快(一次兩步)
        - 如果是無循環，一定會遇到null，因此遇到直接傳false即可
        - 如果是有循環，slow和fast一定會碰到，因此當碰到直接傳true即可
        - [證明](https://hackmd.io/_uploads/rJmMwCpp6.png)
            
## 心得
這周學了LowerBound問題，還有Heap Sort，有了上次的數學大轟炸後覺得這周沒那麼可怕了。

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