# Leetcode Notes

---

[TOC]

## 34. Find First and Last Position of Element in Sorted Array
- 難度：medium
- 題意：給一遞增陣列，再給一數字，找出該數字們所在陣列中的開始與結束位置
- 範例：
- Input: `[5, 7, 7, 8, 8, 10], target = 8`
- Output: [3, 4]
- Input: `[5, 7, 7, 8, 8, 10], target = 6`
- Output: [-1, -1]
- - Input: `[], target = 8`
- Output: [-1, -1]
- 限制：
- 演算法要求 O(log n)
- 陣列長度 0 ~ ${10}^5$
- 想法：
- 因為題目要求 O(log n)，大概只剩 Binary search 可行
- Tree search methods 因為還要建樹 O(n)，時間也會超過
- 程式碼

vector<int> searchRange(vector<int>& nums, int target)
{
    int f = BinarySearch(nums, target);
    return (f >= nums.size() || nums[f] != target) ? vector<int>(2, -1) : vector<int>{f, BinarySearch(nums, target+1)-1};
}

int BinarySearch(vector<int>& nums, int target)
{
    int min = 0;
    int max = nums.size();

    while ( min < max )
    {
        int middle = ( max + min ) / 2;
        (nums[middle] < target) ? min = middle + 1 : max = middle;
    }

    return max;
}

- 分析:
- 2 次的 binary search
- Time: c * log n --> 2 * log n --> O(log n)
- 解釋:
- 利用第一次 binary search 找 target 的開頭
- 利用開頭判斷條件是否符合 (數字是否存在 或 為空陣列)
- 符合後，再進入 binary search 找 target + 1 的開頭
- 此時 target + 1 的開頭 -1 就會是 target 的結尾
- NOTE:
- 一般的 binary search 不一定找得到最左邊的 target
- 因此要在條件上處理
- `if (arr[middle] < target) { min = middle + 1 }`
- `else { max = middle }`
- 意思就是每次找到的 target，只縮右邊一半，保證 **開頭** 一定會被 [min, max] 包住
- 同理，演算法也可以改成 找結尾的 binary search

## 53. Maximum Subarray
- 難度：medium
- 題意：給一串陣列，找出一連續子陣列，其和最大
- 範例：
- Input: `[-2, 1, -3, 4, -1, 2, 1, -5, 4]`
- Output: 6
- Explanation: `[4, -1, 2, 1]`
- 限制：
- 數字 ${-10}^4$ ~ ${10}^4$
- 陣列長度 1 ~ ${10}^5$
- 想法：
- 子陣列什麼時候到達最大值
- 當新增的數字加進來使得總和變小
- `[4, -1, 2, -1]` + `[-5]` --> smaller
- 如何確保子陣列增長 --> Dynamic programming
- 每次都把加到前一個數，其最大的值存起來，確保下次新增的數字使用前一次加到的最大值
- 舉例
- 加到 index 0 --> 子陣列 == `[-2]` 最大值 == -2
- 加到 index 1 --> 子陣列 == `[-2, 1]` 最大值 == 1
- 解釋: (-2 + 1) < 1，代表**子陣列的頭**從 1 開始往後加 比 從 -2 開始還來的大，因此可以捨去 -2
- 加到 index 2 --> 子陣列 == `[1, -3]` 最大值 == -2
- 加到 index 3 --> 子陣列 == `[1, -3, 4]` 最大值 == 4
- 解釋: (1 + -3 + 4) < 4，代表**子陣列的頭**從 4 開始往後加 比 從 1 + -3 開始還來的大，因此可以捨去 1, -3
- 加到 index 4 --> 子陣列 == `[4, -1]` 最大值 == 3
- 加到 index 5 --> 子陣列 == `[4, -1, 2]` 最大值 == 5
- 加到 index 6 --> 子陣列 == `[4, -1, 2, 1]` 最大值 == 6
- 加到 index 7 --> 子陣列 == `[4, -1, 2, 1, -5]` 最大值 == -1
- 加到 index 8 --> 子陣列 == `[4, -1 ,2, 1, -5, 4]` 最大值 == 3
- 程式碼

int maxSubArray(vector<int>& nums)
{
    int size = nums.size();
    int max = nums[0];

    for (int i = 1; i < size; i++)
    {
        int temp = nums[i-1] + nums[i];
        nums[i] = temp > nums[i] ? temp : nums[i];
        max = nums[i] > max ? nums[i] : max;
    }

    return max;
}

- 分析:
- time O(n) --> for loop 1 to n
- space O(1) --> constant space
- 目前沒有想到其他解法，我有看到別人使用 [Kadane's algorithm](https://en.wikipedia.org/wiki/Maximum_subarray_problem)，他的概念是
- 假設最大子陣列 `[a, y, b]`
- 則陣列 `[a, y, b, x]` 之最大子陣列，必為包含或不包含 `[a, y, b]` 之陣列，即 不可能發生 `[y, b, x]` > `[a, y, b, x]`

## 69. Sqrt(x)
- 難度：easy
- 題意：給一數，求其平方根; 若有小數捨去至整數位
- 範例：
- Input: `8`
- Output: 2
- Explanation: `2.82842`
- 限制：
- 不能使用內建函數 pow, sqrt
- n: 1 ~ $2^{31}-1$ (2147483647)
- 想法：
- for 一個一個慢慢找
- Binary search
- [直立開方法](https://highscope.ch.ntu.edu.tw/wordpress/?p=51628)
- 程式碼

// for 一個一個慢慢找
int mySqrt(int x)
{
    for (int i = 1; i <= (x / 2) + 1; i++)
    {
        if (x / i == i) return i;
        if (x / i < i) return i - 1;
    }
    return 0;
}

// Binary search
int mySqrt(int x)
{
    if(x == 0) return 0;
    int left = 1, right = x;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(mid == x / mid)
            return mid;
        else if(mid > x / mid)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return right;
}

## 70. Climbing Stairs
- 難度：easy
- 題意：給 n 階樓梯，一次走一步或兩步，問幾種方法恰好走完樓梯
- 範例：
- Input: `3`
- Output: 3
- Explanation: `1 + 1 + 1` OR `1 + 2` OR `2 + 1`
- 限制：
- n: 1 ~ 45
- 想法：
- 費氏數列 遞迴 (x) --> 儘量不用
- 公式解
- 建表法
- 程式碼

// 建表法
int climbStairs(int n)
{
    uint stairs[50] = {0, 1, 2};
    for(int i = 3; i < 50; i++)
    {
        stairs[i] = stairs[i-1] + stairs[i-2];
    }
    return stairs[n];
}

// 公式解 
int climbStairs(int n)
{
    double coeff = sqrt(5.0);
    double left = pow((1 + coeff) / 2, n + 1);
    double right = pow((1 - coeff) / 2, n + 1);
    return (int)((double)(left - right) / coeff);
}

- 公式解可以考慮背一下

## 74. Search a 2D Matrix
- 難度：medium
- 題意：給一二維陣列，確認當中是否存某數，要求 algorithm O(log mn)
- 範例：
- Input: `[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3`
- Output: true
- 限制：
- 陣列大小: m 列 n 行
- m, n: 1 ~ 100
- matrix[i][j], target: $-10^{4}$ ~ $10^{4}$
- 想法：
- 暴力解，肯定行不通，不考慮
- Binary Search
- 程式碼

// Binary Search
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
    int m = matrix.size();
    int n = matrix[0].size();
    return binary_search(matrix, 0, m*n-1, target);
}

bool binary_search(vector<vector<int>>& matrix, int start, int end, int target)
{
    if (start > end)
        return false;

    int n = matrix[0].size();
    int middle = (start + end) / 2;

    int i = middle / n;
    int j = middle % n;

    if (matrix[i][j] > target)
        return binary_search(matrix, start, middle-1, target);
    else if (matrix[i][j] < target)
        return binary_search(matrix, middle+1, end, target);
    else
        return true;
    return false;
}

- 基本上就把 matrix 攤平做 binary search 而已，沒什麼
- 搜尋過其他人解答，大部分都是 binary search，大同小異

## 1346. Check if N and its double exist
- 難度：easy
- 題意：給一陣列，確認當中是否存在二數，其一數為另一數的兩倍
- 範例：
- Input: `[10, 2, 5, 3]`
- Output: true
- Explanation: `arr[0] = arr[2] * 2`
- 限制：
- 陣列長度: 2 ~ 500
- arr[i]: $-10^{3}$ ~ $10^{3}$
- 想法：
- 暴力解，此題並無限制時間複雜度，且出現 worst case 的機率並不高(猜測)
- Binary Search，可善用 algorithm library
- Hash table (STL)
- 程式碼

// 暴力解
bool checkIfExist(vector<int>& arr)
{
    for (int i = 0; i < arr.size(); i++)
    {
        for (int j = 0; j < arr.size(); j++)
        {
            if (i != j && (arr[i] == 2 * arr[j] || arr[j] == 2 * arr[i]))
            {
                return true;
            }
        }
    }
    return false;
}

// Binary Search
bool checkIfExist(vector<int>& arr)
{
    sort(arr.begin() , arr.end());
    int countZero = 0;
    for(int i = 0; i < arr.size(); i++)
    {
        if(arr[i] == 0) countZero++;
        if(binary_search(arr.begin(), arr.end(), 2*arr[i]))
        {
            if(arr[i] == 0 and countZero > 1) return true;
            if(arr[i] != 0) return true;
        } 
    }
    return false;
}

// Hash table
bool checkIfExist(vector<int>& arr)
{
    map<int, int> hash;
    for (int i = 0; i < arr.size(); i++)
        hash[arr[i]]++;
    
    for (int i = 0; i < arr.size(); i++)
    {
        if (arr[i] == 0)
        {
            if (hash[0] > 1) return true;
        }
        else
        {
            if (arr[i] % 2 == 0 && hash.count(arr[i] / 2))
                return true;
            if (hash.count(arr[i] + arr[i]))
                return true;
        }
    }
    return false;
}

:::info
其中，0 至少要出現兩次，才算存在其倍數，因此可以把 0 當 special case 處理
:::

- 解釋 Hash table
- 第一個 for 先將，所有數字存進 map 中，相當於建一棵樹 O(n)
- 第二個 for 把每個數字遍歷，一一確認自己是否為 map 中某數的兩倍，或 map 存在其兩倍的數
- 因為 map.count 為 O(log n)，因此相當於 binary search

## 141. Linked List Cycle
1. 找 singly linked list 中是否存在 cycle
2. 快慢指標？ two pointers
- 如果有 cycle，fast 會在 loop 中遇到 slow，how ?
- 
Assume time: T
Distance of Fast pointer: ==$m + nx + k = 2T$==
Distance of slow pointer: ==$m + ny + k = T$==
$\Rightarrow m + nx + k = 2(m + ny + k)$
$\Rightarrow n(x - 2y) = m + k$
帶回 T 等式中
$\Rightarrow T = ny + n(x - 2y) = n(x - y)$
$\Rightarrow$ slow pointer 走完 (x - y) 個 cycle 後會遇到 fast pointer
$\Rightarrow$ 在 $O(x - y) == O(n)$ 的時間內，可停止循環
- 停止條件
- fast 碰到 slow
- fast 走到最底
- edge cases
- head == NULL
- length == 1
- analysis
- time: 如上 $O(n)$
- space: 只要 handle 兩個指標 $O(1)$
3. 使用 hash table 記錄所有節點，看是否出現兩次
- 用 C++ STL 較方便，以資料結構為單位，不要用 value 當作 key，因為有可能 value 會重複但沒有 cycle
- 最多 loop $n + 1$ 次即可確定是否含 cycle
- 實作 hash table，collision 策略？
- closed addressing / chaining
- 允許 table 大小(m) 比資料筆數少，代價就是要 handle 額外空間(array / linked list) 來儲存 collision data
- best time: $O(1)$
- worst time: $O(n)$
- space: $O(m + n)$
- open addressing
- 簡單來說，就是找方法 1 to 1 mapping 進 table
- probing(linear / quadratic)
- double hashing
- space: $O(n)$
:::info
C++ STL
`std::map` internally is a Red-Black tree.
`std::unordered_map` is a Hash Table.
Find times are O(log N) vs O(1) respectively.
:::

## 142. Linked List Cycle II
1. 記得考慮 Initial Condition for ==no node or no cycle==
1. 方法參考 141，取 $n(x - 2y) = m + k$
- $m + k$ 是 cycle 的倍數，又 k 與 一部份的 n 重疊，即 $m = ni - k$
- $\Rightarrow$ 也就是 $m \rightarrow -k$ 的中點即是 cycle 的起點（該點被兩個 next 所指到）
- $-k$ 指從 cycle 起點==反方向==到==相遇點==的距離（經過 $i$ 圈）
- time: $O(n)$
- space: $O(1)$
2. 用 set 紀錄 visit 過的 node
- 如果找到重複的值，該值便是 cycle 起點
- time: $O(n)$
- space: $O(n)$

## 83. Remove Duplicates from Sorted List