---
# System prepended metadata

title: Leetcode Top In 150 1/2

---

---
title: Leetcode Top In 150 1/2
autoHeadingNumber: true
---
[TOC]
<!-- 按 Ctrl+Shift+P → Markdown: Create Table of Contents-->

# Leetcode Top Interview 150 1/2
## Array / String
### 88. Merge Sorted Array
- Given two sorted integer arrays `nums1` of length `m`and `nums2` of length `n`.
- merge `nums2` into `nums1` so that `nums1` becomes a single sorted array.
- Solution：將兩個list除了0之外的地方合併，題目給的list剛好0都會在最後，利用提供的整數數量m、n寫迴圈將整數都加入到list b，最後再全部複製到nums1

```python
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        b = []
        for i in range(m):
            b.append(nums1[i])
        for j in range(n):
            b.append(nums2[j])
        b.sort()
        nums1[:] = b
        return nums1
        '''
        # 快速解法
        nums1[:] = nums1[:m] + nums2[:n]
        nums1.sort()  # 排序
        '''
```
### 27. Remove Element
- 回傳`nums`裡面不是`val`的數量`k`
- `nums`不用回傳，但會檢查`nums`裡面的前`k`項不能有`val`
- 強調使用`in-place`的技巧
```python
class Solution(object):
    def removeElement(self, nums, val):
        k = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]  # 將「不等於 val」的值移動到 nums[k]
                k += 1
        return k
```
### 26. Remove Duplicates from Sorted Array
- 給一個遞增排序的`nums`
- 把一樣`value`的項目刪掉
- 輸出不重複的數字數量`k`，且`nums`的前`k`項不能重複
- Solution：不能連續兩個一樣 = 跟前面第一個(k-1)不一樣即可
```python
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0

        k = 1  # 下一個不重複數字要放的位置
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]  # in-place 覆寫
                k += 1

        return k
```
```cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int k = 1;  // 下個不重複數字要放的位置
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k] = nums[i];  // in-place 覆寫
                k++;
            }
        }
        return k;
    }
};
```
### 80. Remove Duplicates from Sorted Array II
- 給一個遞增排序的`nums`
- 把連續三個以上一樣`value`的項目刪掉
- 輸出不超過連續三個以上一樣的數字數量`k`，且`nums`的前`k`項不能重複三個以上
- Solution：不能連續三個一樣 = 跟前面第二個(k-2)不一樣即可
```python
class Solution(object):
    def removeDuplicates(self, nums):
        if len(nums) < 2: return len(nums)
        k = 2  # 下一個能放的位置
        for i in range(2, len(nums)):
            if nums[i] != nums[k - 2]:
                nums[k] = nums[i]
                k += 1

        return k
```
### 169. Majority Element
- 給一個長度為`n`的`nums`
- 輸出超過`n/2`數量的元素element
```python
class Solution(object):
    def majorityElement(self, nums):
        nums.sort()
        count = 0
        max_count = 0
        max_number = nums[0]
        for i in range(len(nums)-1):
            if nums[i]==nums[i+1]:
                count += 1
                if count > max_count:
                    max_number = nums[i]
                max_count = max(max_count,count)
            else:
                count = 0
        return max_number
```
### 189. Rotate Array
- Input: nums = [1,2,3,4,5,6,7], k = 3
- Output: [5,6,7,1,2,3,4]
- Explanation:
    - rotate 1 steps to the right: [7,1,2,3,4,5,6]
    - rotate 2 steps to the right: [6,7,1,2,3,4,5]
    - rotate 3 steps to the right: [5,6,7,1,2,3,4]
```python
class Solution(object):
    def rotate(self, nums, k):
        n = len(nums)
        k %= n # 處理 k > n 的情況

        nums.reverse()
        nums[:k] = reversed(nums[:k]) # 0~k
        nums[k:] = reversed(nums[k:]) # k~最後
```
```c
void reverse(int* nums, int left, int right) {
    while (left < right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}

void rotate(int* nums, int numsSize, int k) {
    if (numsSize <= 1 || k == numsSize) return;
    
    k = k % numsSize;   // 處理 k > n 的情況
    reverse(nums, 0, numsSize - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, numsSize - 1);
}
```
### 121. Best Time to Buy and Sell Stock
- You are given an array `prices` where `prices[i]` is the price of a given stock on the ith day.
- 哪天買哪天賣可以賺最多錢，return 可以賺的最高金額
```python
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        '''
        # 這個方法會超時
        max_profit = 0
        for i in range(len(prices) - 1, 0, -1):
            for j in range(i - 1, -1, -1):
                now_profit = prices[i] - prices[j]
                max_profit = max(max_profit, now_profit)
        '''
        # O(n)，邏輯是有更低的價格再更新就好，否則一路往下更新max_profit
        min_price = prices[0]
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            else:
                max_profit = max(max_profit, price - min_price)

        return max_profit
```
### 122. Best Time to Buy and Sell Stock II
- You are given an array `prices` where `prices[i]` is the price of a given stock on the ith day.
- 買賣不限一次，return 可以賺的最高金額
- Solution：只要明天比今天高，那就今天買明天賣
- 我原本想從右邊到左邊，有更大值才更新基準值，但這樣測資`[1,81,1,101]`只有賺100元，其實可以賺180元
```python
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 只要明天的價格比今天高，就今天買明天賣
        # GPT說這是Greedy
        max_profit = 0
        for i in range(0, len(prices) - 1):
            if prices[i]<prices[i+1]:
                max_profit = max_profit+(prices[i+1]-prices[i])
        return max_profit
print(Solution.maxProfit(Solution,[7,1,5,3,6,4]))
```
```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        for (int i=0; i < prices.size()-1;i++){
            if (prices[i]<prices[i+1]){
                max_profit = max_profit+(prices[i+1]-prices[i]);
            }
        }
        return max_profit;
    }
};
```
### 55. Jump Game
- You are given an integer array `nums`. You are initially positioned at the array's first index,
- and each element in the array represents your maximum jump length at that position.
- Return `true` if you can reach the last index, or `false` otherwise.
```python
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # 假如第一個數字是0就不用跳了
        # 同理nums[n]如果n-1項是0且n-1前面其他項都跳不過來，那n就是死路
        # GPT說這是Greedy
        max_range = nums[0]
        for i in range(len(nums)):
            if i<=max_range:
                max_range = max(max_range, i+nums[i])
            else:
                return False
        return True
```
```cpp
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_range = nums[0];
        for (int i = 0; i <nums.size(); i++){
            if (i<=max_range){
                max_range = max(max_range, i+nums[i]);
            }
            else{
                return false;
            }
        }
        return true;
    }
};
```
### 45. Jump Game II
- Input: nums = [2,3,1,1,4]
- Output: 2
- Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
- Solution：
    - for-if-if結構，我覺得超難
    - 不能無腦擴張領土就+1，因為array的值都至少有1
    - 要有一個邊界max_line，那個邊界內的都是step多少以內能到的
    - nums[0]是step0
    - 其中step0最遠能到的區域都是step1
    - 假如step0最遠能到nums[3]，那nums[1:3] = step1
    - 再看step1最遠能到多少
    - 假如step1最遠到nums[10]，那nums[4:10] = step2
```python
class Solution(object):
    def jump(self, nums):
        max_range = 0
        step = 0
        last_step_line = 0
        max_line = len(nums) - 1
        for i in range(len(nums)):
            if last_step_line >= max_line:
                return step
            max_range = max(max_range, i + nums[i])
            if i == last_step_line:  # 當i = last_step_line = 0時，進入step1
                step += 1
                last_step_line = max_range  # step1的範圍是1~0+nums[0]
```
```cpp
class Solution {
public:
    int jump(vector<int>& nums) {
        int max_range = 0;
        int step = 0;
        int last_step_line = 0;
        int max_line = nums.size()-1;

        for (int i = 0; i < nums.size();i++){
            if (last_step_line >= max_line){
                return step; // return沒有寫在函式最後，隨便return一個0就好
            }
            max_range = max(max_range, i + nums[i]);
            if (i==last_step_line){
                step++;
                last_step_line = max_range;
            }
        }
        return 0;
    }
};
```
### 274. H-Index
- `citations[i]` is the number of citations a researcher received for their ith paper, return h-index.
- h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
- 最多有H篇論文至少被引用H次
- Input：citations = [3, 0, 6, 1, 5], n = 5
- Output：h = 3 
- Solution：
    - (最多有H篇論文)>=(至少)被引用H次
    - 論文被引用的次數統整在`count[]`裡面，這是一種bucket(分類)
        - index:  0 1 2 3 4 5
        - count: [1, 1, 0, 1, 0, 2]
    - 最多n篇論文往下找，當n-k>=被引用的次數總和時，輸出那次的次數

```python
class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        # 最多有H篇論文至少被引用H次
        h_score = 0
        for i in range(1, len(citations) + 1): # 窮舉法，從h=1~n逐步檢查
            count = 0
            for j in citations:
                if j >= i:
                    count += 1
                if count >= i:
                    h_score = max(h_score, i)
        return h_score
# print(Solution.hIndex(Solution,[1]))

    def hIndex2(self, citations): # 建立count[]後從高往下推，直到>=為止
        n = len(citations)
        count = [0] * (n + 1)

        for c in citations:
            if c >= n:
                count[n] += 1
            else:
                count[c] += 1

        total = 0
        for h in range(n, -1, -1):
            total += count[h]
            if total >= h:
                return h
```
```c
int hIndex(int* citations, int citationsSize) {
    int n = citationsSize;
    int count[n + 1];
    for (int i = 0; i <= n; i++) {
        count[i] = 0;
    }
    
    for (int i = 0; i < n; i++) { // bucket分類
        int c = citations[i];
        if (c >= n) {
            count[n]++;
        } else {
            count[c]++;
        }
    }
    
    int total = 0;
    for (int h = n; h >= 0; h--) {
        total += count[h];  // 被引用 >= h 的論文數
        if (total >= h) {
            return h;
        }
    }
    return 0;
}
```
### 380. Insert Delete GetRandom O(1)
- 要求三個操作都要平均 O(1)： insert(val) → 插入 O(1)， remove(val) → 刪除 O(1)， getRandom() → 隨機取值 O(1)
- 如果只有 list： 插入 O(1)， 刪除 O(n)（因為要找元素在哪個 index）， getRandom O(1)
- 如果只有 dict： 插入 O(1)， 刪除 O(1)， getRandom 沒辦法做到，因為 dict 沒有隨機取「第幾個」的功能
- 所以才要 list + dict 搭配： list 用來隨機抽取， dict 用來快速找到元素的位置
- Solutionn：
    - insert / remove → 主要靠 dict，加上 list 做同步更新
    - getRandom → 只用 list
    - list 與 dict 雙結構同時維護，各自負責不同需求

```python
import random

class RandomizedSet(object):

    def __init__(self):
        self.nums = []
        self.nums_dict = {}

    def insert(self, val):
        """
        :type val: int
        :rtype: bool
        """
        if val in self.nums_dict:
            return False
        else:
            self.nums.append(val) # list
            self.nums_dict[val] = len(self.nums) - 1 # dict
            return True

    def remove(self, val):
        """
        :type val: int
        :rtype: bool
        """
        if val not in self.nums_dict:
            return False
        else:
            exchange_place = self.nums_dict[val] # dict
            self.nums_dict[self.nums[-1]] = exchange_place # dict
            self.nums[exchange_place], self.nums[exchange_place] = self.nums[len(self.nums) - 1], self.nums[
                len(self.nums) - 1] # list
            self.nums.pop() # list
            del self.nums_dict[val] # dict
            return True

    def getRandom(self):
        """
        :rtype: int
        """
        if len(self.nums) == 0:
            return False
        else:
            return random.choice(self.nums)

# ===================== 測資 =====================
inputs = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
params = [[], [1], [2], [2], [], [1], [2], []]

obj = None
output = []

for cmd, param in zip(inputs, params):
    if cmd == "RandomizedSet":
        obj = RandomizedSet()
        output.append(None)   # 對應 LeetCode 的 null
    elif cmd == "insert":
        output.append(obj.insert(param[0]))
    elif cmd == "remove":
        output.append(obj.remove(param[0]))
    elif cmd == "getRandom":
        output.append(obj.getRandom())

print("Input:")
print(inputs)
print(params)
print("Output:")
print(output)

# Output = [null, true, false, true, 2, true, false, 2]

'''
# dict{x, y}：x對y可以一對一、多對一，不能一對多
# 舉例刪除掉3
# list = [1, 2, 3, 4, 5]
# dict = {1:0, 2:1, 3:2, 4:3, 5:4}

# step1:
exchange_place = self.nums_dict[val]
self.nums_dict[self.nums[-1]] = exchange_place # -> dict = {1:0, 2:1, 3:2, 4:3, 5:2}

# step2:
self.nums[exchange_place], self.nums[exchange_place] = self.nums[len(self.nums) - 1], self.nums[len(self.nums) - 1]
# -> list = [1, 2, 5, 4, 3]

# step3:
self.nums.pop() # -> list = [1, 2, 5, 4]
del self.nums_dict[val] # -> dict = {1:0, 2:1, 4:3, 5:2}
所以刪除後會引響list的順序，dict的value也會同步更新位子

# 比對時間複雜度
leetcode_380_dict的學號對應list的位子
if val in dict:  O(1)
if val in list:  O(n)
'''
```
### 238. Product of Array Except Self
- 給一個`nums`，全部相乘是某個整數，輸出`answer`，`answer[i]`是該整數中，因數不包含`nums[i]`的積
- Input: nums = [1,2,3,4]
- Output: [24,12,8,6]
- Solution：`answer[i]`其實就是左邊跟右邊所有元素相乘
- prefix
- suffix
```python
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        answer = [1] * n
        left = 1
        for i in range(0, n - 1, 1):
            left *= nums[i] # 因為你要累乘
            answer[i + 1] *= left
        right = 1
        for i in range(n - 1, 0, -1):
            right *= nums[i]
            answer[i - 1] *= right
        return answer
```
```c
int* productExceptSelf(int* nums, int n, int* returnSize){
    *returnSize = n;

    int* answer = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        answer[i] = 1;
    }

    int left = 1;
    for (int i = 0; i < n - 1; i++) {
        left *= nums[i];
        answer[i + 1] *= left;
    }

    int right = 1;
    for (int i = n - 1; i > 0; i--) {
        right *= nums[i];
        answer[i - 1] *= right;
    }
    return answer;
}
```
```cpp
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) { // vector不用指標
        int n = nums.size();
        vector<int> answer(n, 1);

        int left = 1;
        for (int i = 0; i < n - 1; ++i) {
            left *= nums[i];
            answer[i + 1] *= left;
        }

        int right = 1;
        for (int i = n - 1; i > 0; --i) {
            right *= nums[i];
            answer[i - 1] *= right;
        }
        return answer;
    }
};
```
### 134. Gas Station
- gas[i]是抵達該加油站後可以加的油
- cost[i]是從這邊離開時要扣掉的油
- return從gas多少開始可以走完整一圈
- Solution：
    - 只要total_gas >= total_cost 就一定有解
    - +gas-cost可以想成新的diff
    - 正+負定理：
        - 能走到3，那1一定是正的，同理1+2也必定正，卡在3表示3是一個超大負
        - 如果1 ->2 ->3不行，那從2、3當起點也一定不行
        - 直接測試從4當起點的情況
```python
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        # gas是你抵達時得到的gas
        # cost是你離開時消耗的gas
        # 只要total_gas >= total_cost 就一定有解
        total_tank = 0
        current_tank = 0
        start_index = 0

        for i in range(len(gas)):
            total_tank += gas[i] - cost[i]
            current_tank += gas[i] - cost[i]

            # 若目前的油量不足，重新選擇起點
            if current_tank < 0:
                start_index = i + 1
                current_tank = 0  # 重置當前油量 # 不用重置total

        if total_tank >= 0:
            return start_index
        else:
            return -1
```
### 135. Candy
- arrays `ratings` of length `n`, rating[i]是小孩的價值
- 每個小孩至少一個糖果
- 小孩一定要比自己鄰居ratings更低的小孩拿更多糖
- 輸出至少需要多少糖果
- Solution：
![image](https://hackmd.io/_uploads/HkWqNESX-g.png =80%x)
```python
class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        n = len(ratings)
        candy_L2R = [1]*n
        candy_R2L = [1]*n
        candy_result = [1]*n
        sum = 0
        for i in range(1, n):
            if ratings[i]>ratings[i-1]: candy_L2R[i] = candy_L2R[i-1]+1
        for j in range(n-2, -1, -1):
            if ratings[j]>ratings[j+1]: candy_R2L[j] = candy_R2L[j+1]+1
        for k in range(n):
            candy_result[k] = max(candy_L2R[k], candy_R2L[k])
            
            sum += candy_result[k]
        return sum
```
### 42. Trapping Rain Water
- arrays `height` of length `n`, `height[i]`是牆壁的高度，輸出最多可以搜集多少雨水
- Solution：
![image](https://hackmd.io/_uploads/rJq3V4HX-g.png =80%x)
```python
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        L2R_up = 0
        R2L_up = 0
        L2R_line = [0]*n
        R2L_line = [0]*n
        result = 0
        result2 = 0

        for i in range(n):
            L2R_up = max(L2R_up, height[i])
            L2R_line[i] = L2R_up
        
        for i in range(n-1,-1,-1):
            R2L_up = max(R2L_up, height[i])
            R2L_line[i] = R2L_up

            result = min(R2L_line[i], L2R_line[i])
            result = result - height[i]
            if result > 0:
                result2 += result
        return result2
```
```c
int trap(int* height, int heightSize) {
    int n = heightSize;
    int L2R_up = 0;
    int R2L_up = 0;
    int L2R_line[n]; // C創建list比C++簡單
    int R2L_line[n];
    int result = 0;
    int result2 = 0;

    for (int i = 0; i < n; i++) {
        L2R_up = (L2R_up > height[i]) ? L2R_up : height[i];
        L2R_line[i] = L2R_up;
    }

    for (int i = n - 1; i >= 0; i--) {
        R2L_up = (R2L_up > height[i]) ? R2L_up : height[i];
        R2L_line[i] = R2L_up;

        result = (R2L_line[i] < L2R_line[i]) ? R2L_line[i] : L2R_line[i];
        result = result - height[i];

        if (result > 0) result2 += result;
    }
    return result2;
}
```

### 13. Roman to Integer
|Symbol|Value|
|-|-|
|I|1|
|IV|4|
|V|5|
|VI|6|
|X|10|
|L|50|
|C|100|
|D|500|
|M|1000|

- input是string的羅馬數字，output數字
```python
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        s_dict = {
                'I': 1,
                'V': 5,
                'X': 10,
                'L': 50,
                'C': 100,
                'D': 500,
                'M': 1000,
        }
        sum = s_dict[s[len(s)-1]]
        for i in range(len(s)-1):
            if s_dict[s[i]]< s_dict[s[i+1]]:
                sum -= s_dict[s[i]]
            else:
                sum += s_dict[s[i]]
        return sum
```
### 12. Integer to Roman
- input數字，output是string的羅馬數字
```python
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        roman_dict = {
        1: 'I',
        4: 'IV',
        5: 'V',
        9: 'IX',
        10: 'X',
        40: 'XL',
        50: 'L',
        90: 'XC',
        100: 'C',
        400: 'CD',
        500: 'D',
        900: 'CM',
        1000: 'M',
        }
        roman_list = sorted(roman_dict.keys()) # leetcode的dict沒有照上面的順序排
        roman_number = ''
        for i in list(roman_list)[::-1]:  # 從大到小 # 讓迴圈發生在roman_list
            roman_number += roman_dict[i] * (num // i)
            num -= (num // i) * i
        return roman_number
```
### 58. Length of Last Word
- input一個string，每個單字會用空格隔開，輸出最後一個單字的長度
- Python Solution：
    - 有可能最後一個元素是空格，所以設定一個spare，遇到空格就把result複製到spare
    - 最後如果是空格，result就會是0，輸出spare
    - 最後如果不是空格，就輸出result
- C++ Solution：
    - 從後面往前，如果不是空格就+1
    - 如果是空格且count不是0就直接輸出count
```python
class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = 0
        spare = 0
        for i in range(len(s)):
            if s[i] == ' ':
                if result != 0:
                    spare = result
                result = 0
            else:
                result += 1
        
        if result == 0:
            return spare
        else:
            return result
```
### 14. Longest Common Prefix
- 找共同的前綴詞
- Input: strs = `["flower","flow","flight"]`
- Output: "fl"
- Solution：
    - 每個詞的第一個單字開始比，如果不一樣就輸出答案
```python
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        ans = ""

        for i, char in enumerate(strs[0]):  # 以第一個flower為基準
            for word in strs:  # 依序比對所有字元的i=1、i=2、i=3等
                # 超出字串範圍，或字串不同，直接結束返回結果
                if i >= len(word) or word[i] != char:
                    return ans
            ans += char  # 整個for word迴圈都沒return就把該char加入ans

        return ans  # 所有字串都遍歷完後，返回完整的共同前綴
```
### 151. Reverse Words in a String
- Input: s = "a good   example"
- Output: "example good a"
- Python Solution：
    - 從前面開始遇到空格的話再把前面的詞放到後面
    - `result[position-length+j] = s[i-length+j]`
- C Solution：
    - 從後面開始統計不是空格的數量放到result
```python
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        result = [""] * (n+1) # list of string # n+1因為可能多一個空格
        count = 0
        position = n
        for i in range(n+1):
            if i == n or s[i] == " ":
                length = count
                if length > 0:
                    for j in range(length):
                        result[position-length+j] = s[i-length+j] # 把最前面的You放到最後面
                    position -= length
                    position -= 1
                    if position >= 0:
                        result[position] = " " # 在You的前面補一個空格
                    count = 0
            else:
                count += 1 # 沒遇到空格就一直+1
        return "".join(result).strip() # 把list裡面的子string都合起來 # .strip()會刪掉頭尾空格

#solution = Solution()
#print(solution.reverseWords("You are very smart"))
```
```c
char* reverseWords(char* s) {
    int n = strlen(s);
    char* result = (char*)malloc(n + 1);
    int pos = 0;

    int i = n - 1;
    while (i >= 0) {
        while (i >= 0 && s[i] == ' ') i--; // 跳過空格
        if (i < 0) break;

        int end = i;
        while (i >= 0 && s[i] != ' ') i--; // 找單字結尾
        int start = i + 1;

        if (pos > 0) result[pos++] = ' '; // 補空格（不是第一個單字)

        for (int k = start; k <= end; k++) result[pos++] = s[k]; // 複製單字
    }

    result[pos] = '\0'; 
    // C 語言中的字串結尾的標記 
    // char s[] = {'H','i','\0'}; 等價 char s[] = "Hi";
    return result;
}
```
### 6. Zigzag Conversion
- input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
- output = [1, 5, 9, 13, 2, 4, 6, 8, 10, 12, 14, 3, 7, 11]
![image](https://hackmd.io/_uploads/B1mqCSqNWe.png)
- Solution
    - 剛好會是numRows +numRows -2的循環
    - 用找餘數的方式分類，餘數是1的是第一row，餘數是2的是第二row
    - 其中5跟3同一組、6跟2同組，所以`if x >= row: x = cycle - x`
    - 從小到大，把元素加入到不同string的分類裡

```python
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        row = numRows
        n = len(s)
        ans = [""] * row  # 可以把值存到ans_[0]、ans_[1] ...
        cycle = row + row - 2
        if cycle == 0:
            return s

        for i in range(n):
            x = i % cycle
            if x >= row:
                x = cycle - x # 以N=4為例，6跟2同組，5跟3同組
            ans[x] += s[i] if 0 <= x < numRows else ""

        return "".join(ans)

'''
N = 3, 1個穿插：
1   5   9     13
2 4 6 8 10 12 14
3   7   11

1   1   1   
2 4 2 4 2 4
3   3   3

N = 4, 2個穿插：

1     7      13
2   6 8   12 14
3 5   9 11   
4     10     

1     1    1    1
2   6 2  6 2  6 2
3 5   3 5  3 5 
4     4    4
'''
```
### 28. Find the Index of the First Occurrence in a String
- Input: haystack = "absadbutsad", needle = "sad"
- Output: 2
- Solution：
    - 寫兩個迴圈逐一深入比對，把所有答案加入到list最後輸出最小的值
    - 建立LPS表看有多少前綴詞重複，就不用重頭比對
    - ![image](https://hackmd.io/_uploads/HkVPrN7HZx.png =45%x)

```python
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        answer = []
        for i in range(0, len(haystack)):
            count = 0
            for j in range(i, len(haystack)):
                if haystack[j] == needle[count]:
                    count += 1
                elif haystack[j] != needle[count]:
                    count = 0
                if count == len(needle):
                    x = j-count+1
                    answer.append(x)
                    count = 0
        if answer != []:
            return min(answer)
        return -1
```
```python
class Solution(object):
    def strStr(self, haystack, needle):
        if needle == "":
            return 0

        # ---------- build lps ----------
        lps = [0] * len(needle) 
        # 控制j的list，告訴你哪些前綴一樣
        # needed = [a, b, c, a, b, c, d],  lps = [0, 0, 0, 1, 2, 3, 0]
        j = 0 
        # j是你正在跟哪個index的元素比 
        # j-1是哪些index的元素已經一樣了

        for i in range(1, len(needle)):
            while j > 0 and needle[i] != needle[j]:
                j = lps[j - 1]

            if needle[i] == needle[j]:
                j += 1

            lps[i] = j

        # ---------- KMP search ----------
        j = 0
        for i in range(len(haystack)):
            while j > 0 and haystack[i] != needle[j]:
                j = lps[j - 1]

            if haystack[i] == needle[j]:
                j += 1

            if j == len(needle):
                return i - j + 1

        return -1
'''
haystack = "mississippi"
needle   = "issip"
lps = [0, 0, 0, 1, 0]
當比到hystack[5]、j=3不一樣時，j不會直接歸0，根據lps j會變成1，直接跟needle[1]繼續比
'''
```
### 68. Text Justification
-
- Solution：
    - 
```python

```
```c

```
## Two Pointers
### 125. Valid Palindrome
- 給一個字串`s`，忽略標點符號英文大小寫，看是不是回文(正讀反讀都一樣)
```python
class Solution:
    def isPalindrome(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            # 如果是非英數就額外+1 # not .sialnum 是 not False = True 就會跳過(+1)
            while left < right and not s[left].isalnum(): left += 1
            while left < right and not s[right].isalnum(): right -= 1
            if s[left].lower() != s[right].lower(): return False
            left += 1
            right -= 1
        return True

'''
'a'.isalnum()   # True
'7'.isalnum()   # True
' '.isalnum()   # False
','.isalnum()   # False
'''
```
### 392. Is Subsequence
- 給兩個字串`s` `t`，如果s是t的 subsequence (子序列)就return True
- 子序列可以不用相連但順序要對，如s = abc，t = ....a....b....c...
```python
class Solution(object):
    def isSubsequence(self, s, t):
        n = len(s)
        m = len(t)
        if n == 0: return True
        t_l = 0
        s_l = 0
        while t_l < m:
            if s[s_l] == t[t_l]:
                s_l += 1
                if s_l == n: return True
            t_l += 1
        return False
```
### 167. Two Sum II - Input Array Is Sorted
- 給排序的數列，找兩數相加等於target
- Solution：
    - 用`while`縮小範圍，我原本以為`leetcode1`就是有排序的
```python
class Solution(object):
    def twoSum(self, numbers, target):
        left = 0
        right = len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            # LeetCode 167 題目規定：回傳的是「1-based index」
            if s == target: return [left + 1, right + 1]
            elif s < target: left += 1
            else: right -= 1
```
### 11. Container With Most Water
- 給你一個陣列 `height`，`height[i]` = 第 i 條直線的高度
- 每兩條線可以和 x 軸圍成一個容器
- 容器能裝的水量是：寬度 × 高度 = (右 index - 左 index) × min(左高, 右高)
- 回傳最大能裝多少水？
- Solution：
    - 區域：`area = width × min(height[left], height[right])`
    - 雙指標：只移比較矮的那邊，如果移動高的，容量只會被矮的那端限制住
    - `if height[left] < height[right]: left += 1`
    - `else: right -= 1`
```python
class Solution(object):
    def maxArea(self, height):
        left = 0
        right = len(height) - 1
        ans = 0
        while left < right:
            area = (right - left) * min(height[left], height[right])
            ans = max(ans, area)
            # 只移比較矮的那邊一定是對的
            # 如果移動高的，容量只會被矮的那端限制住
            if height[left] < height[right]: left += 1
            else: right -= 1
        return ans
```
### 15. 3Sum
- 給一個list，輸出list of list，哪三個數字加起來等於0，不能重複
- Solution：
    - 先排序，再用雙指標右邊的最右邊跟最左邊依序縮短距離
    - 過程中只要跟下一個狀態重複就要跳過
    - C的`malloc`語法補充在`python c c++.md`的`malloc`篇中
    - C的`result`是2D array，`returnColumnSizes`是1D array
```python
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        n = len(nums)
        ans = []
        Target = 0

        for i in range(n):  # 以第i個數字為主角，再去看右邊的範圍有沒有可以配合的兩個數字
            if i > 0 and nums[i] == nums[i-1]:  # 如果跟上一個數字一樣，就跳過不重複做
                continue
            left = i + 1
            right = n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == Target:
                    ans.append([nums[i], nums[left], nums[right]]) # List[List[int]]的方法
                    while left < right and nums[left] == nums[left+1]:
                        left += 1 # 避免重複算
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1 # 避免重複算

                    left += 1
                    right -= 1

                elif total < Target:
                    left += 1 # 如果太小就左邊+1，因為有sort過左邊是小的
                else:
                    right -= 1 # 如果太大就右邊-1，因為sort過右邊是大的
        return ans

solution = Solution()
print(solution.threeSum([-1,0,1,2,-1,-4]))
```
```c
// qsort 用的
int cmp(const void* a, const void* b) { // void表示不知道什麼類別
    return (*(int*)a - *(int*)b); 
    // 一開始宣告void，類別轉型(int*)a, 假設a是int整數
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 指標符號 * 有兩種用途 1.解參考 2.宣告指標回傳值
    // int* returnSize是指向int的指標
    // Q: 為什麼這邊要int **returnColumnSizes才代表array，但void sort(int*arr)就代表array？
    // 怎麼知道int*arr是指向int的指標還是array退化成指標？
    // A: 一開始有宣告過arr是array就是後者，沒有宣告過的話就要用int**
    
    *returnSize = 0;
    if (numsSize < 3) return NULL;
    qsort(nums, numsSize, sizeof(int), cmp);

    // 最多不會超過 n^2 組
    int capacity = numsSize * numsSize;
    int** result = (int**)malloc(sizeof(int*) * capacity);
    // int**是double pointer，宣告array of array
    // int**是指向int*的指標
    // sizeof(int*)是指標的長度
    *returnColumnSizes = (int*)malloc(sizeof(int) * capacity);
    // 因為returnColumnSizes不會被return，所以要用*A = size(int)的方式malloc

    for (int i = 0; i < numsSize - 2; i++) {

        if (i > 0 && nums[i] == nums[i - 1]) continue; // 重複不用算
        int left = i + 1;
        int right = numsSize - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum == 0) {
                result[*returnSize] = (int*)malloc(sizeof(int) * 3);
                result[*returnSize][0] = nums[i];
                result[*returnSize][1] = nums[left];
                result[*returnSize][2] = nums[right];
                (*returnColumnSizes)[*returnSize] = 3;
                // (*returnColumnSizes)[i]  == *(*returnColumnSizes + i)
                (*returnSize)++;

                // 重複不用算
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;
                right--;
            }
            else if (sum < 0) left++;
            else right--;
        }
    }
    return result;
}
```

## Sliding Window 兩個指標維持一個連續區間，邊移動邊更新答案
### 209. Minimum Size Subarray Sum
- 給一個array跟target，找連續的子陣列（subarray），子陣列的總和 ≥ target，return子陣列最短長度
```python
class Solution(object):
    def minSubArrayLen(self, target, nums):
        left = 0
        curr_sum = 0
        res = float('inf') # 無限大

        for right in range(len(nums)): 
            curr_sum += nums[right]
            while curr_sum >= target:
                res = min(res, right - left + 1)
                curr_sum -= nums[left]
                left += 1

        return 0 if res == float('inf') else res
```
```c
int minSubArrayLen(int target, int* nums, int numsSize) {
    int left = 0;
    int sum = 0;
    int minLen = numsSize + 1;

    for (int right = 0; right < numsSize; right++) {
        sum += nums[right];

        while (sum >= target) {
            int len = right - left + 1;
            if (len < minLen) minLen = len;
            sum -= nums[left];
            left++;
        }
    }
    return minLen == numsSize + 1 ? 0 : minLen;
}
```
### 3. Longest Substring Without Repeating Characters
- input一個string，output最長不重複的字母數量
- Python Solution：
    - 把string的字母加到key、第i個加到value
    - for迴圈一開始更新left邊界
- C Solution1：
    - 類似python，建立char_last_position的list當dict用
    - `list['a']++` 等價 `freq[97]++`，freq的第97個位子會++
    - list每個值預設是-1，因為python一開始就沒有值，C的list的128個位子一開始都要設定值
    - for迴圈一開始更新left邊界
    - 如果前面有出現過這個字母，left = 第一次出現該字母+1
- 補充 `list[s[right]] >= left` 的意思是：
    - list[s[right]]本來應該要沒有值或-1
    - 如果有值且>=left，表示在原本left~right之間有重複的s[right]
    - left = 第一次出現該字母的位子+1
    - 如abcdeabc，`s[5]`出現第二次b，則left邊界從`s[2]`開始
    - ![image](https://hackmd.io/_uploads/H1TCbVmSZe.png =50%x)
- C Solution2：
    - 建立list，如果有重複的如`freq['a']=2`，就照string的順序把前面都--，直到`freq['a']=1`為止就是left的邊界
    - 跟查字典char_last_postion的位子+1更新left不同
```python
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        seen = {}
        start = 0
        count = 0
        max_len = 0

        for i in range(n):
            # 更新left邊界
            if s[i] in seen and seen[s[i]] >= start:
                start = seen[s[i]] + 1 # 如dvdf，遇到第二個d起點從v開始
                count = i - start # count不見得會直接歸0，
                # 例如dvdf，遇到第二個d時，count = 2-1 = 1，
                # 後面馬上count += 1，count = 2，count會從v開始算
            seen[s[i]] = i 
            # 字串的字母加到key
            # 第i個加到value
            # seen[s[0]] = 0 →seen = {'a': 0}
            count += 1
            if count > max_len:
                max_len = count
                results = s[start:i+1] # 字串切割範圍從start到i+1-1
        return results

solution = Solution()
print(solution.lengthOfLongestSubstring("abbcdef"))
```
```c
int lengthOfLongestSubstring(char* s) {
    int char_last_position[128];
    for (int i = 0; i < 128; i++) char_last_position[i] = -1;
    int left = 0;
    int maxLen = 0;

    for (int right = 0; s[right]; right++) {  // 同for ( ; s[right] != '\0'; ) 
        // 更新left邊界
        if (char_last_position[s[right]] >= left) left = char_last_position[s[right]] + 1;
        char_last_position[s[right]] = right;
        int len = right - left + 1;
        if (len > maxLen) maxLen = len;
    }
    return maxLen;
}
```
```c
int lengthOfLongestSubstring(char* s) {
    int freq[128] = {0};   // 128是所有字元
    int left = 0;
    int maxLen = 0;

    for (int right = 0; s[right] != '\0'; right++) {
        freq[s[right]]++;  // freq['a']++ 等價 freq[97]++ // freq的第97個位子會++

        // 如果有重複，就縮小左邊邊界
        while (freq[s[right]] > 1) {
            freq[s[left]]--;
            left++;  
            // left會一直+到當left == right為止
            // 此時再freq[s[left]]-- 才會停止迴圈
            // 這段同python, start = seen[s[i]] + 1
        }

        int currLen = right - left + 1;
        if (currLen > maxLen)
            maxLen = currLen;
    }

    return maxLen;
}
```
### 30. Substring with Concatenation of All Words
### 76. Minimum Window Substring

## Matrix
### 36. Valid Sudoku
- 看數獨是否符合邏輯，row, column, 3x3區域內不能有重複的值
- Solution：
    - python建立2D array
    - C 的2D array column是實際value值-1
```python
class Solution(object):
    def isValidSudoku(self, board):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val == '.': continue # leetcode題目規定的無值
                box_id = (r // 3) * 3 + (c // 3) # 把box變成9個區間：(0,3,6)+(0,1,2)
                if val in rows[r] or val in cols[c] or val in boxes[box_id]: return False
                rows[r].add(val)
                cols[c].add(val)
                boxes[box_id].add(val)
        return True
```
```c
bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
    bool row[9][10] = {false};
    bool col[9][10] = {false};
    bool box[9][10] = {false};
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char num = board[r][c];
            if (num == '.') continue;
            int num2 =  num - '0'; // 因為char的1是int的49，1-'0'同49-48
            int box_id = (r / 3) * 3 + (c / 3);
            if (row[r][num2] || col[c][num2] || box[box_id][num2]) return false;
            row[r][num2] = true;
            col[c][num2] = true;
            box[box_id][num2] = true;
        }
    }
    return true;
}
```
### 54. Spiral Matrix
- 給一個mn矩陣，回傳沿著邊邊往內走順序(spiral order)的list
- Solution：
     - 右往左跟下往上要多寫一個if，不然走到終點後還會繼續計算重複的點
```python
class Solution(object):
    def spiralOrder(self, matrix): # mn matrix
        if not matrix: return []
        res = []
        top, bottom = 0, len(matrix) - 1 # m, row, y-axis
        left, right = 0, len(matrix[0]) - 1 # n, column, x-axis

        while top <= bottom and left <= right:
            
            for c in range(left, right + 1): res.append(matrix[top][c]) # left → right
            top += 1 # 縮小範圍，top起點是0、bottom起點是m-1
        
            for r in range(top, bottom + 1): res.append(matrix[r][right]) # top → bottom
            right -= 1

            if top <= bottom: # right → left
                for c in range(right, left - 1, -1): res.append(matrix[bottom][c])
                bottom -= 1

            if left <= right: # bottom → top
                for r in range(bottom, top - 1, -1): res.append(matrix[r][left])
                left += 1

        return res
```
```c
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0) {
        *returnSize = 0;
        return NULL;
    }

    int m = matrixSize;
    int n = matrixColSize[0];
    int total = m * n;
    int* res = (int*)malloc(sizeof(int) * total);
    int idx = 0;

    int top = 0, bottom = m - 1;
    int left = 0, right = n - 1;

    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) res[idx++] = matrix[top][c];
        top++;
        for (int r = top; r <= bottom; r++) res[idx++] = matrix[r][right];
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) res[idx++] = matrix[bottom][c];
            bottom--;
            }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) res[idx++] = matrix[r][left];
            left++;
            }
    }
    *returnSize = idx;
    return res;
}
```
### 48. Rotate Image
- 給nn矩陣，順時針轉90度
- Solution：
    - 順時針轉90度：ij交換+反轉row
    - 逆時針轉90度：ij交換+反轉column
    - 轉180度：上下反轉+左右反轉
```python
class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(i+1, n):  matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 轉置
        for i in range(n): matrix[i].reverse() # 反轉每一row
```
```c
void rotate(int** matrix, int matrixSize, int* matrixColSize){
    int n = matrixSize;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n/2; j++){
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][n-1-j];
            matrix[i][n-1-j] = tmp;
        }
    }
}
```
### 73. Set Matrix Zeroes
- 給mn矩陣，0的同一row跟同一column都變成0
- Solution：
    - 把0所在的row, column紀錄起來，再一次把所有row, column變成0，O(2mn)
    - 有更快的方法，但我覺得面試不會考這題，就不研究了
```python
class Solution(object):
    def setZeroes(self, matrix):
        m, n = len(matrix), len(matrix[0])
        row = [False] * m
        col = [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = True
                    col[j] = True

        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0
```
```c
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
    int m = matrixSize;
    int n = matrixColSize[0];
    int row[m], col[n];
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(matrix[i][j] == 0){
                row[i] = 1;
                col[j] = 1;
            }
        }
    }

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(row[i] || col[j]){
                matrix[i][j] = 0;
            }
        }
    }
}
```
### 289. Game of Life
- 給一個 0/1 矩陣（死/活），同時依照規則更新成下一代
- 4條規則，對每一格，看 8 個鄰居：
    - 活細胞，活鄰居 < 2 → 死
    - 活細胞，活鄰居 2 或 3 → 活
    - 活細胞，活鄰居 > 3 → 死
    - 死細胞，活鄰居 = 3 → 活
- 全部是同時發生，不能邊更新邊看下一個，類似non-blocking的效果，但不是non-blocking的機制
- Solution：
    - 讓存的值有四種狀態
    - cell > 0 → 1
    - cell <= 0 → 0
    - 這題沒認真刻，很類似電腦視覺的作業

|原本|後來|value|
|-|-|-|
|0|0|0|
|1|1|1|
|1|0|-1|
|0|1|2|


```python
class Solution:
    def gameOfLife(self, board):
        m, n = len(board), len(board[0])
        dirs = [(-1,-1), (-1,0), (-1,1),
                (0,-1),          (0,1),
                (1,-1),  (1,0),  (1,1)]

        # 第一次遍歷：標記狀態
        for i in range(m):
            for j in range(n):
                live = 0
                for dx, dy in dirs:
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n and abs(board[x][y]) == 1:
                        live += 1

                if board[i][j] == 1 and (live < 2 or live > 3):
                    board[i][j] = -1      # 活 → 死
                elif board[i][j] == 0 and live == 3:
                    board[i][j] = 2       # 死 → 活

        # 第二次遍歷：還原成 0 / 1
        for i in range(m):
            for j in range(n):
                if board[i][j] > 0:
                    board[i][j] = 1
                else:
                    board[i][j] = 0
```
```c
void gameOfLife(int** board, int boardSize, int* boardColSize) {
    int m = boardSize;
    int n = boardColSize[0];

    int dirs[8][2] = {
        {-1,-1}, {-1,0}, {-1,1},
        {0,-1},          {0,1},
        {1,-1},  {1,0},  {1,1}
    };

    // 第一輪：標記暫態
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int live = 0;
            for (int d = 0; d < 8; d++) {
                int x = i + dirs[d][0];
                int y = j + dirs[d][1];
                if (x >= 0 && x < m && y >= 0 && y < n &&
                    abs(board[x][y]) == 1) {
                    live++;
                }
            }

            if (board[i][j] == 1 && (live < 2 || live > 3)) {
                board[i][j] = -1;   // 活 → 死
            } else if (board[i][j] == 0 && live == 3) {
                board[i][j] = 2;    // 死 → 活
            }
        }
    }

    // 第二輪：轉回 0 / 1
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = board[i][j] > 0 ? 1 : 0;
        }
    }
}
```
## Hashmap
### 383. Ransom Note
-
- Solution：
    - 5
```python

```
```c

```
### 205. Isomorphic Strings
-
- Solution：
    - 5
```python

```
```c

```

### 290. Word Pattern
-
- Solution：
    - 5
```python

```
```c

```

### 242. Valid Anagram
-
- Solution：
    - 5
```python

```
```c

```

### 49. Group Anagrams
- Input: strs = ["eat","tea","tan","ate","nat","bat"]
- Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
- Solution：
    - 用`defaultdict` value設定list
    - `sorted_str = "".join(sorted(s))` 排序詞彙
    - `ans[sorted_str].append(s)` 排序一樣的詞彙放在同一個key的list裡面
```python
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        from collections import defaultdict
        ans = defaultdict(list)
        for s in strs:
            sorted_str = "".join(sorted(s))
            ans[sorted_str].append(s)
        return list(ans.values())
```

### 1. Two Sum
- 給你一個整數陣列 nums 和一個目標 target
- 找出兩個不同 index，使得 nums[i] + nums[j] == target
- 回傳這兩個 index，保證一定有解，只有一組解
- Solution：
    - 可以用雙迴圈O(n*2)、while雙指標縮小範圍、dict
```python
class Solution(object):
    def twoSum(self, nums, target):
        # dict的key放nums的value,
        # key的value放nums的index
        # dict[key] -> value
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen: return [seen[complement], i]
            seen[num] = i
        return []
```

### 202. Happy Number
-
- Solution：
    - 5
```python

```
```c

```

### 219. Contains Duplicate II
-
- Solution：
    - 5
```python

```
```c

```

### 128. Longest Consecutive Sequence
-
- Solution：
    - 5
```python

```
```c

```

## Intervals 一堆區間 [start, end] 的演算法
### 228. Summary Ranges
- 給一個sorted num，有連續的區間用5->9表示，其他用單獨的數字表示
- Solution：
    - `if i == n or nums[i] != nums[i - 1] + 1:` 到尾巴或發現不連續
    - 再看是重複的還是連續的
```python
class Solution(object):
    def summaryRanges(self, nums):
        res = []
        n = len(nums)
        if n == 0: return res
        start = nums[0]
        for i in range(1, n + 1):
            if i == n or nums[i] != nums[i - 1] + 1: # 到尾巴 或 發現不連續
                if start == nums[i - 1]: res.append(str(start)) 
                else:  res.append(str(start) + "->" + str(nums[i - 1]))
                if i < n: start = nums[i]
        return res
```
```c
char** summaryRanges(int* nums, int numsSize, int* returnSize) {
    char** res = (char**)malloc(sizeof(char*) * numsSize);
    *returnSize = 0;
    if (numsSize == 0) return res;
    int start = nums[0];
    for (int i = 1; i <= numsSize; i++) {
        if (i == numsSize || nums[i] != nums[i - 1] + 1) {
            char* buf = (char*)malloc(25);
            if (start == nums[i - 1]) sprintf(buf, "%d", start); // 存成字串
            else sprintf(buf, "%d->%d", start, nums[i - 1]);
            res[(*returnSize)++] = buf;
            if (i < numsSize) start = nums[i];
        }
    }
    return res;
}
```

### 56. Merge Intervals
-
- Solution：
    - 5
```python

```
```c

```

### 57. Insert Interval
-
- Solution：
    - 5
```python

```
```c

```

### 452. Minimum Number of Arrows to Burst Balloons
-
- Solution：
    - 5
```python

```
```c

```

## Stack
### 20. Valid Parentheses
-
- Solution：
    - 5
```python

```
```c

```

### 71. Simplify Path
-
- Solution：
    - 5
```python

```
```c

```

### 155. Min Stack
-
- Solution：
    - 5
```python

```
```c

```

### 150. Evaluate Reverse Polish Notation
-
- Solution：
    - 5
```python

```
```c

```

### 224. Basic Calculator
-
- Solution：
    - 5
```python

```
```c

```

## Linked List
### 141. Linked List Cycle
- Given head, the head of a linked list, determine if the linked list has a cycle in it.
- Solution: 給一個盲Linked List判斷是否為迴圈，同時一次只走一步跟一次走兩步，如果有迴圈遲早兩個人會重疊
```python
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow = head   # 慢指針，每次走一步
        fast = head   # 快指針，每次走兩步

        while fast and fast.next: # fast.next有東西的話，fast.next.next才有意義
            slow = slow.next
            fast = fast.next.next
            if slow == fast: return True # 相遇表示有 cycle
        return False
```
```c
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *slow = head;  // 慢指針，一次走一步
    struct ListNode *fast = head;  // 快指針，一次走兩步

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // 相遇表示有 cycle
    }
    return false;  // 都沒相遇
}
```
### 2. Add Two Numbers
- 給兩個linklist，return相加後的linklist，但個十百千萬都是相反的
- Input: l1 = [2,4,3], l2 = [5,6,4]
- Output: [7,0,8]
- Explanation: 342 + 465 = 807
- Solution：
    - 位數相反是好事，第一個就是個位數相加，第二個是十位數相加
    - carry是看有沒有進位
    - `while carry` `v1 = l1.val if l1 else 0` 都是怕最後一位相加後要進位
    - 每建立新的點都要在heap上配置空間
        - C宣告curr的方式 `struct ListNode* curr  = l3;`；對比python `curr = l3`
        - C要多一個變數`node`做malloc；python會自動建立空間才不用多一個變數malloc
```python
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        carry = 0
        l3 = ListNode(0)
        curr = l3 # current用來借位
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            total = v1 + v2 + carry
            carry = total // 10
            curr.next = ListNode(total % 10)
            curr = curr.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return l3.next
```
```c
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int carry = 0;
    struct ListNode* l3 =
        (struct ListNode*)malloc(sizeof(struct ListNode));
    l3->val = 0;
    l3->next = NULL;
    struct ListNode* curr = l3; // curr借位不要影響到l3
    while (l1 != NULL || l2 != NULL || carry != 0) {
        int v1 = (l1 != NULL) ? l1->val : 0;
        int v2 = (l2 != NULL) ? l2->val : 0;
        int total = v1 + v2 + carry;
        carry = total / 10;
        // 每創建一個點就要多一次malloc
        // C要多一個node變數做malloc
        // python會自動建立空間才不用多一個變數malloc
        struct ListNode* node =
            (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = total % 10;
        node->next = NULL;
        curr->next = node;
        curr = curr->next;
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }
    return l3->next;
}
```
### 21. Merge Two Sorted Lists
- 給兩個排序的linklist，將兩個linklist合併，每個node由小到大
- Solution：
    - 建立dummy當開頭，不用建立新的linklist
    - C在stack建立dummy node作為開頭，後面都是更改l1, l2的排序
    - python無論如何都會在heap建立空間，dummy node建立在heap
```python
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0) # python不管怎樣都會在heap建立空間
        curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 if l1 else l2
        return dummy.next
```
```c
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy; // 不用在heap配置linklist空間，所以不用malloc
    struct ListNode* curr = &dummy;
    dummy.next = NULL;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } 
        else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    curr->next = (l1 != NULL) ? l1 : l2; // 最後會剩下l1或l2最後一個node
    return dummy.next;
}
```
### 138. Copy List with Random Pointer
- 特殊的 linked list有val, next, random，random是指向其中一個點或null
- 完整複製一份新的 linked list，不能用到舊的點
- random 不是線性的，你在複製 A 時，A.random 可能指到還沒被複製的 C
- Solution：
    - 在原本的linklist每個node後面都接新的node 
        - `new.next = cur.next ` 
        - `cur.next = new`
    - 新node的random也要接到新的node 
        - `cur.next.random = cur.random.next`
    - 1,3,5,7是舊點；2,4,6,8是新點，最後分解成兩個linklist
        - `copy_cur.next = copy`
        - `cur.next = copy.next`
```python
class Solution(object):
    def copyRandomList(self, head):
        # 如果原本 list 為空，直接回傳 None
        if not head: return None

        '''
        1 -> 2 -> 3 -> None
        |    |    |
        v    v    v
        3    1   None
        '''

        cur = head
        while cur:
            new = Node(cur.val)
            new.next = cur.next # 標準插入node的兩行
            cur.next = new
            cur = new.next

        '''
        1 -> 1' -> 2 -> 2' -> 3 -> 3' -> None
        |         |         |
        v         v         v
        3         1        None
        '''

        cur = head
        while cur:
            if cur.random: cur.next.random = cur.random.next # random是舊點，再next是新點
            cur = cur.next.next # 去下一個舊點

        '''
        1 -> 1' -> 2 -> 2' -> 3 -> 3'
        |    |     |    |     |
        v    v     v    v     v
        3    3'    1    1'   None
        '''

        new_head = Node(0)  # 新 list 的假頭
        copy_cur = new_head  # 用來走訪新 list
        cur = head  # 重新從舊 list 的頭開始
        while cur:
            copy = cur.next 
            # cur的第一個是舊點
            # cur從下一個新點開始run
            
            copy_cur.next = copy # 接上copy的新點
            copy_cur = copy      # 移到剛接上的點
            
            cur.next = copy.next # 接上copy的舊點
            cur = cur.next       # 移到剛接上的點

        '''
        1 -> 2 -> 3 -> None
        |    |    |
        v    v    v
        3    1   None

        1' -> 2' -> 3' -> None
        |     |      |
        v     v      v
        3'    1'    None
        '''
        return new_head.next
```
```c
struct Node* copyRandomList(struct Node* head){
    if (!head) return NULL;

    struct Node* cur = head;
    while (cur) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = cur->val;
        newNode->next = cur->next;
        newNode->random = NULL;
        cur->next = newNode;
        cur = newNode->next;
    }

    cur = head;
    while (cur) {
        if (cur->random)  cur->next->random = cur->random->next;
        cur = cur->next->next;
    }

    //struct Node* dummy = (struct Node*)malloc(sizeof(struct Node));
    //dummy->next = NULL;
    //struct Node* copy_cur = dummy;

    struct Node dummy;
    dummy.next = NULL; // 只有指標的子項目用 ->
    struct Node* copy_cur = &dummy;
    cur = head;

    while (cur) {
        struct Node* copy = cur->next;

        copy_cur->next = copy;
        copy_cur = copy;

        cur->next = copy->next;
        cur = cur->next;
    }

    //return dummy->next;
    return dummy.next;
}
```
### 92. Reverse Linked List II
- 給一個linklist，指定範圍反轉
- linklist的輸出就是一個點，每個點都有`next`所以會無限延伸
- Solution：
    - 變數很多，沒有好的命名方法，設定變數就是一直在縮短範圍
    - 中間反轉同單向 Linked List 反轉
```python
class Solution:
    def reverseBetween(self, head, m, n):
        if not head or m == n: return head
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy # 頭多一個0
        for _ in range(m - 1): prev = prev.next # prev 移到 m-1
        cur = prev.next
        tail = cur # 第m個之後會是尾巴
        rev_prev = None

        # 反轉 m~n 節點 # 同單向 Linked List 反轉
        for _ in range(n - m + 1):
            next_node = cur.next
            cur.next = rev_prev
            rev_prev = cur
            cur = next_node

        # 接回原 list
        prev.next = rev_prev # 上面prev在m-1，後面接反轉後的linklist
        tail.next = cur

        return dummy.next
```
```c
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if (!head || m == n) return head;

    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* prev = &dummy;  // prev 最終指向 m 前一個節點
    for (int i = 1; i < m; i++) prev = prev->next; // 移動 prev 到第 m-1 個節點
    struct ListNode* cur = prev->next; // m 節點
    struct ListNode* next;
    struct ListNode* tail = cur; // 反轉後的尾巴是 cur
    struct ListNode* rev_prev = NULL;
    // 反轉 m ~ n 節點
    for (int i = 0; i <= n - m; i++) {
        next = cur->next;
        cur->next = rev_prev;
        rev_prev = cur;
        cur = next;
    }
    
    // 接回原鏈表
    prev->next = rev_prev; // m-1 節點接反轉後的頭
    tail->next = cur;      // 反轉後尾巴接 n+1 節點

    return dummy.next;
}
```
### 25. Reverse Nodes in k-Group
- 給定一個 單向鏈結串列 `head`，每 `k` 個節點反轉一次，並返回修改後的鏈表
- Solution：
    - 用`while curr:`計算長度
    - 當`while count >= k:`成立
    - 執行子迴圈`for i in range(1, k):`標準單向linklist轉向
    - 直到count < k
```python
class Solution:
    def reverseKGroup(self, head, k):
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        curr = head
        count = 0
        while curr:
            count += 1
            curr = curr.next
        
        while count >= k:
            curr = prev.next  # 第 1 個節點
            next = curr.next
            # 反轉 k 個節點 # 同單向 Linked List 反轉
            for i in range(1, k):
                curr.next = next.next
                next.next = prev.next
                prev.next = next
                next = curr.next
            prev = curr
            count -= k
        
        return dummy.next
```
```c
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    if (!head || k == 1) return head;
    
    struct ListNode dummy;
    dummy.val = 0;
    dummy.next = head;
    struct ListNode *prev = &dummy, *curr, *next; // 同時宣告*prev, *curr, *next;
    
    // 計算長度
    int count = 0;
    curr = head;
    while (curr) {
        count++;
        curr = curr->next;
    }
    
    while (count >= k) {
        curr = prev->next;  // 第 1 個節點
        next = curr->next;
        for (int i = 1; i < k; i++) {
            curr->next = next->next;
            next->next = prev->next;
            prev->next = next;
            next = curr->next;
        }
        prev = curr;
        count -= k;
    }
    
    return dummy.next;
}
```
### 19. Remove Nth Node From End of List
- 給定一個 單向鏈結串列 `head`，刪掉倒數第`n`個元素，並返回修改後的鏈表
- Solution：
    - 
```python
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        dummy = ListNode(0)
        dummy.next = head
        curr = dummy.next
        count=0
        while curr:
           count+=1
           curr=curr.next

        curr = dummy # 一定要從dummy開始，不然linklist只有一項會錯
        for _ in range(count - n): curr = curr.next
        curr.next = curr.next.next
        return dummy.next
```
```c
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode dummy;
    dummy.val = 0;
    dummy.next = head;

    struct ListNode* curr = dummy.next;
    int count = 0;
    while (curr) {
        count++;
        curr = curr->next;
    }
    
    curr = &dummy;
    for (int i = 0; i < count - n; i++) curr = curr->next;

    struct ListNode* temp = curr->next;
    curr->next = curr->next->next;
    free(temp); // C要釋放記憶體
    return dummy.next;
}
```
### 82. Remove Duplicates from Sorted List II
- 給一個已排序的 linked list，刪除所有出現超過一次的數字，只留下「完全沒重複過」的節點
- Solution：
    - 用`dup`紀錄重複的值，用`while`將該值都刪掉
```python
class Solution(object):
    def deleteDuplicates(self, head):
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        cur = head
        while cur:
            if cur.next and cur.val == cur.next.val:
                dup = cur.val
                while cur and cur.val == dup:
                    cur = cur.next
                prev.next = cur
            else:
                prev = cur
                cur = cur.next

        return dummy.next
```
```c
struct ListNode* deleteDuplicates(struct ListNode* head) {
    struct ListNode dummy;
    dummy.next = head;

    struct ListNode* prev = &dummy;  // record
    struct ListNode* cur = head; // process

    while (cur) {
        if (cur->next && cur->val == cur->next->val) {
            int dup = cur->val;
            while (cur && cur->val == dup) { // 同一個值都要刪掉
                struct ListNode* tmp = cur;
                cur = cur->next;
                free(tmp);
            }
            prev->next = cur;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy.next;
}
```
### 61. Rotate List
- 給一個已排序的 linked list，跟數字`k`，把最後一個元素放到第一個元素`k`次
- Solution：
    - 把linklist變成環狀，再找新的頭跟新的尾巴
    - `while curr.next:` 計算linklist長度
    - 從第一個元素走`長度-k-1`是新的尾巴，`.next`是新的頭
```python
class Solution(object):
    def rotateRight(self, head, k):
        if not head or not head.next: return head
        dummy = ListNode(0)
        dummy.next = head
        curr = head
        count = 1
        while curr.next:
            curr = curr.next
            count += 1
        k %= count
        if k == 0: return head
        curr.next = head # 接成環
        curr = head
        # 找新尾巴：走 count - k - 1 步
        for _ in range(count - k - 1): curr = curr.next
        dummy.next = curr.next
        curr.next = None

        return dummy.next
```
```c
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (head == NULL || head->next == NULL) return head;
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* curr = head;
    int count = 1;
    while (curr->next != NULL) {
        curr = curr->next;
        count++;
    }
    k %= count;
    if (k == 0) return head;
    curr->next = head;
    // 找新尾巴：走 count - k - 1 步
    curr = head;
    for (int i = 0; i < count - k - 1; i++) {
        curr = curr->next;
    }
    dummy.next = curr->next;
    curr->next = NULL;
    return dummy.next;
}
```
### 86. Partition List
- 給你一個 linked list head，還有一個整數 x，重新排列 linked list，使得：
    - 所有 < x 的節點在前面
    - 所有 >= x 的節點在後面
    - 重點：相對順序要保持（stable）
- Solution：
    - 開兩條 `list`，一條裝 `< x`，一條裝 `>= x`，最後接起來
```python
class Solution(object):
    def partition(self, head, x):
        small_dummy = ListNode(0)
        large_dummy = ListNode(0)
        small = small_dummy
        large = large_dummy
        curr = head
        while curr:
            if curr.val < x:
                small.next = curr
                small = small.next
            else:
                large.next = curr
                large = large.next
            curr = curr.next
        large.next = None
        small.next = large_dummy.next
        return small_dummy.next
```
```c
struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode small_dummy, large_dummy;
    small_dummy.next = NULL;
    large_dummy.next = NULL;
    struct ListNode* small = &small_dummy;
    struct ListNode* large = &large_dummy;
    struct ListNode* curr = head;
    while (curr != NULL) {
        if (curr->val < x) {
            small->next = curr;
            small = small->next;
        } else {
            large->next = curr;
            large = large->next;
        }
        curr = curr->next;
    }
    large->next = NULL;
    small->next = large_dummy.next;
    return small_dummy.next;
}
```
### 146. LRU Cache
- Least Recently Used
- 實作一個快取系統，支援兩個操作：
    - `get(key)`    → O(1)
    - `put(key, value)` → O(1)，當容量滿了，要刪掉「最久沒被使用的」資料
- 正解只能是：Hash Table + Doubly Linked List
    - 只用 array / list → `get(key)`無法 O(1)
    - 只用 hash table → 不知道誰最久沒用
- Solution：
    - Hash Map：key → node，O(1) 找到資料
    - Doubly Linked List：記錄使用順序，最近用的放前面，最久沒用的在後面（尾巴）
    - `get(key)`
        - key 不存在 → return -1
        - key 存在：把該 node 移到最前面(因為最近使用) return value
    - `put(key, value)`
        - key 已存在：更新 value，把 node 移到最前面
        - key 不存在：如果容量滿了：刪掉尾巴（LRU），hash 也要刪，插新 node 到最前面，hash 記錄 key → node
    - 把node移到最前面都是先刪掉node`_remove`，再插入最前面`_add_to_head`
```python
class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node

        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_head(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_head(node)
        else:
            if len(self.cache) == self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
```
# Reference
- [Hello Algo](https://www.hello-algo.com/zh-hant/)
- [GeeksforGeeks](https://www.geeksforgeeks.org/)
- [Leetcode](https://leetcode.com/)
- [Collegiate Programming Examination](https://cpe.mcu.edu.tw/)
- [HackerRank](https://www.hackerrank.com/)