---
# System prepended metadata

title: LeetCode Everyday for Beginner 2
tags: [LeetCode]

---

# LeetCode Everyday for Beginner 2

contributed by <`Charlie-Tsai1123`> , <`xiusobeee`>


| <font color="#46c6c2">**Easy 14**</font> | <font color="#fac31d">**Medium 36**</font> | <font color="#f8615c">**Hard 7**</font> | (7/19)

>[!Note] reference
>[代碼隨想錄 - 教材](https://gitee.com/programmercarl/leetcode-master#/programmercarl/leetcode-master/blob/master/./problems/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.md)
>[代碼隨想錄 - 題目](https://github.com/youngyangyang04/leetcode-master/tree/master/problems)

## 7/19


### [131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `String` `Dynamic Programming` `Backtracking`

* <font color="#2DB55D">**AC** (66ms) | **Beats** 26.54%</font>
* $O(n \times 2 ^n)$

```cpp
class Solution {
public:
    vector<vector<string>> ans;
    vector<string> ans_element;
    bool isPalindrome(string s) {
        int left = 0, right = s.length() - 1;
        while (right > left) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    void backTracing(string s) {
        if (s == "") {
            ans.push_back(ans_element);
        }
        string tmp = "";
        for (int i = 0; i < s.length(); i++) {
            tmp.push_back(s[i]);
            if (isPalindrome(tmp)) {
                ans_element.push_back(tmp);
                backTracing(s.substr(i + 1, s.length() - i - 1));
                ans_element.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        backTracing(s);
        return ans;
    }
};
```

---
>[!Note]優化兩個地方
>1. 判斷 palindrome 原本的 code 會重複判斷到
>2. function 傳入改成 const string& s 可以不用複製整個 s 到 function
* <font color="#2DB55D">**AC** (50ms) | **Beats** 56.70%</font>
* $O(n \times 2 ^n)$

```cpp
class Solution {
public:
    vector<vector<string>> ans;
    vector<string> ans_element;
    vector<vector<bool>> isPalindrome;
    void computePalindrome(const string& s) {
        isPalindrome.resize(s.length(), vector<bool>(s.length(), false));
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j) {
                    isPalindrome[i][j] = true;
                } else if (j - i == 1) {
                    isPalindrome[i][j] = (s[i] == s[j]);
                } else {
                    isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i + 1][j - 1]);
                }
            }
        }
    }
    void backTracing(const string& s, int startIndex) {
        if (startIndex == s.length()) {
            ans.push_back(ans_element);
            return;
        }
        
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome[startIndex][i]) {
                ans_element.push_back(s.substr(startIndex, i - startIndex + 1));
                backTracing(s, i + 1);
                ans_element.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        computePalindrome(s);
        backTracing(s, 0);
        return ans;
    }
};
```
---

### [647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Two Pointers` `String` `Dynamic Programming`

* <font color="#2DB55D">**AC** (31ms) | **Beats** 30.42%</font>
* $O(n^2)$

```cpp
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.length(), vector<bool>(s.length(), false));
        int ans = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                dp[i][j] = (i == j) || ((j - i == 1) && s[i] == s[j]) || ((j - i > 1) && s[i] == s[j] && dp[i + 1][j - 1]);
                if (dp[i][j]) ans++;
            }
        }
        return ans;
    }
};
```

## 7/20


### [132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/description/)

<font color="#f8615c">**Hard**</font>
==Topics== : `String` `Dynamic Programming` 

* <font color="#2DB55D">**AC** (52ms) | **Beats** 77.74%</font>
* $O(n^2)$

```cpp
class Solution {
public:
    int minCut(string s) {
        vector<vector<bool>> isPalindrome(s.length(), vector<bool>(s.length(), false));
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (j - i <= 1) isPalindrome[i][j] = (s[i] == s[j]);
                else isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i + 1][j - 1]);
            }
        }

        vector<int> cut(s.length(), 0);
        for (int i = 0; i < s.length(); i++) cut[i] = i;
        for (int i = 1; i < s.length(); i++) {
            if (isPalindrome[0][i]) {
                cut[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j + 1][i]) {
                    cut[i] = min(cut[i], cut[j] + 1);
                }
            }
        }
        return cut[s.length() - 1];
    }
};
```

### [134. Gas Station](https://leetcode.com/problems/gas-station/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Greedy` 

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $O(n)$


#### Method 1
```cpp
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0, min = INT_MAX;
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }

        if (min > 0) return 0;
        if (curSum < 0) return -1;
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) return i;
        }
        return -1;
    }
};
```



#### Method 2
---
>[!Caution]錯誤沒檢查 total sum 是否小於 0

```cpp
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0, startIndex = 0;
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < 0) {
                curSum = 0;
                startIndex = i + 1;
            }
        }
        return (startIndex == gas.size()) ? -1 : startIndex;
    }
};
```

修正版
```cpp
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0, startIndex = 0, totalSum = 0;
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            totalSum += rest;
            if (curSum < 0) {
                curSum = 0;
                startIndex = i + 1;
            }
        }
        return (totalSum < 0) ? -1 : startIndex;
    }
};
```
---
## 7/22


### [135. Candy](https://leetcode.com/problems/candy/description/)

<font color="#f8615c">**Hard**</font>
==Topics== : `Array` `Greedy` 

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $O(n)$

---
錯誤作法一次考慮
```cpp
class Solution {
public:
    int candy(vector<int>& ratings) {
        int last_candy = 1, sum = 1, min = 1;
        for (int i = 1; i < ratings.size(); i++) {
            cout << last_candy << " ";
            if (ratings[i] <= ratings[i - 1]) {
                last_candy--;
            } else {
                last_candy++;
            }
            sum += last_candy;
            if (last_candy < min) min = last_candy;
        }
        cout << last_candy << endl;
        sum += (1 - min) * ratings.size();
        return sum;
    }
};
```

```tex
ratings =[1,3,2,2,1]
stdout = 1 2 1 0 -1
```
---
正確做法 : 分成兩邊考慮

```cpp
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        int sum;
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        }
        sum = candies[ratings.size() - 1];
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) candies[i] = max(candies[i + 1] + 1, candies[i]);
            sum += candies[i];
        }
        return sum;
    }
};
```

## 8/5
### [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/description/)

<font color="#46c6c2">**Easy**</font>
==Topics== : `Math` `Dynamic Programming` `Recursion` `Memoization` 

#### Method 1
* <font color="#2DB55D">**AC** (3ms) | **Beats** 66.48%</font>
* $Time: O(n)$
* $Space: O(n)$
```cpp
class Solution {
public:
    int fib(int n) {
        vector<int> dp(max(n + 1, 2));
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
```

#### Method 2
* <font color="#2DB55D">**AC** (2ms) | **Beats** 77.67%</font>
* $Time: O(n)$
* $Space: O(1)$
```cpp
class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};
```

### [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)

<font color="#46c6c2">**Easy**</font>
==Topics== : `Math` `Dynamic Programming` `Memoization` 
* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(n)$


```cpp
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(max(n, 2));
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
};
```

### [746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/description/)

<font color="#46c6c2">**Easy**</font>
==Topics== : `Math` `Dynamic Programming` `Memoization` 

#### Method 1
* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(n)$
```cpp
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i < dp.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[dp.size() - 1];
    }
};
```

#### Method 2
* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(1)$
```cpp
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp[2];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int sum = min(dp[0] + cost[i - 2], dp[1] + cost[i - 1]);
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};
```

## 8/6


### [343. Integer Break](https://leetcode.com/problems/integer-break/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Math` `Dynamic Programming`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n^2)$
* $Space: O(n)$

>[!Note]思考為什麼 iterate 的範圍可以是 i / 2

```cpp
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = max({dp[i], dp[i - j] * j, j * (i - j)});
            }
        }
        return dp[n];
    }
};
```



### [416. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (63ms) | **Beats** 89.84%</font>
* $Time: O(n^2)$
* $Space: O(n)$

```cpp
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int space = 0;
        for (int a: nums) space += a;
        if (space % 2 == 1) return false;
        space /= 2;
        vector<int> dp(space + 1);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = space; j >= nums[i]; j--) {
                dp[j] = max(dp[j], nums[i] + dp[j - nums[i]]);
            }
        }
        return dp[space] == space;
    }
};
```

### [1049. Last Stone Weight II](https://leetcode.com/problems/last-stone-weight-ii/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming` `Weekly Contest 137`

* <font color="#2DB55D">**AC** (2ms) | **Beats** 59.13%</font>
* $Time: O(n^2)$
* $Space: O(n)$

```cpp
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int a: stones) sum += a;
        vector<int> dp(sum / 2 + 1, 0);
        for (int i = 0; i < stones.size(); i++) {
            for (int j = sum / 2; j >= stones[i]; j--) {
                dp[j] = max(dp[j], stones[i] + dp[j - stones[i]]);
            }
        }
        return sum - 2 * dp[sum / 2];
    }
};
```

## 8/7

### [494. Target Sum](https://leetcode.com/problems/target-sum/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming` `Backtracking`

* <font color="#2DB55D">**AC** (3ms) | **Beats** 87.76%</font>
* $Time: O(n^2)$
* $Space: O(n)$

>[!Note] 這題難點在初始化部分要想清楚

```cpp
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int capacity = target;
        for (int a: nums) capacity += a;
        if (capacity < 0) return 0;
        vector<int> dp(capacity + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = capacity; j >= 2 * nums[i]; j--) {
                dp[j] = dp[j] + dp[j - 2 * nums[i]];
            }
        }
        return dp[capacity];
    }
};
```

* <font color="#2DB55D">**AC** (2ms) | **Beats** 90.15%</font>
* $Time: O(n^2)$
* $Space: O(n)$

>[!Note] 可以想想看背包空間要如何解釋
```cpp
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int capacity = target;
        for (int a: nums) capacity += a;
        if (capacity < 0 || capacity % 2 == 1) return 0;
        capacity /= 2;

        vector<int> dp(capacity + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = capacity; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[capacity];
    }
};
```

### [474. Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `String` `Dynamic Programming`

* <font color="#2DB55D">**AC** (50ms) | **Beats** 85.49%</font>
* $Time: O(kmn)$
* $Space: O(mn)$

```cpp
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (string s: strs) {
            int numZero = 0, numOne = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '0') numZero++;
                else numOne++;
            }
            for (int i = m; i >= numZero; i--) {
                for (int j = n; j >= numOne; j--) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i - numZero][j - numOne]);
                }
            }
        }
        return dp[m][n];
    }
};
```

### [518. Coin Change II](https://leetcode.com/problems/coin-change-ii/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (3ms) | **Beats** 95.26%</font>
* $Time: O(n^2)$
* $Space: O(n)$

```cpp
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<uint64_t> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};
```

## 8/8
### [377. Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n^2)$
* $Space: O(n)$

---
>[!Warning] 錯誤作法: 先遍歷物品是組合

```cpp
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = nums[i]; j <= target; j++) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};
```
---
>[!Warning] 正確做法: 先遍歷背包式排列

```cpp
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<uint64_t> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (nums[j] > i) continue;
                dp[i] = dp[i] + dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};
```

## 8/9
### [322. Coin Change](https://leetcode.com/problems/coin-change/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming` `Breadth-First Search`

* <font color="#2DB55D">**AC** (19ms) | **Beats** 83.84%</font>
* $Time: O(n^2)$
* $Space: O(n)$


---
>[!Warning]錯誤作法
>1. 沒考慮若無法組成 amount 如何處理
>2. 因為一開始就初始化 dp 數組為 0 也沒考慮若 amount 就是 0 的情況
```cpp
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, 0);
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j >= amount; j++) {
                if (dp[j] == 0) {
                    dp[j] = 1 + dp[j - coins[i]];
                } else {
                    dp[j] = min(dp[j], 1 + dp[j - coins[i]]);
                }
            }
        }
        return dp[amount];
    }
};
```
---
```cpp
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        vector<int> dp(amount + 1, 0);
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j - coins[i]] == 0 && j - coins[i] != 0) continue;
                if (dp[j] == 0) {
                    dp[j] = 1 + dp[j - coins[i]];
                } else {
                    dp[j] = min(dp[j], 1 + dp[j - coins[i]]);
                }
            }
        }
        return (dp[amount] == 0) ? -1 : dp[amount];
    }
};
```

### [279. Perfect Squares](https://leetcode.com/problems/perfect-squares/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming` `Breadth-First Search`

* <font color="#2DB55D">**AC** (39ms) | **Beats** 85.65%</font>
* $Time: O(n^2)$
* $Space: O(n)$

```cpp
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= sqrt(n); i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = min(dp[j], 1 + dp[j - i * i]);
            }
        }
        return dp[n];
    }
};
```

## 8/10
### [377. Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Hash Table` `String` `Dynamic Programming` `Trie` `Memoization`

* <font color="#2DB55D">**AC** (15ms) | **Beats** 33.93%</font>
* $Time: O(n^3)$
* $Space: O(n)$

>[!Note] substr 本身的時間複雜度就是 O(n)
>這題值得再思考一次他的做法
```cpp
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.length() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                string str = s.substr(j, i - j);
                if (wordSet.find(str) != wordSet.end() && dp[j] == true) {
                    dp[i] = true;
                    continue;
                }
            }
        }
        return dp[s.length()];
    }
};
```

## 8/11

### [198. House Robber](https://leetcode.com/problems/house-robber/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(n)$

>[!Note] 注意 edge cases
```cpp
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[nums.size() - 1];
    }
};
```

### [213. House Robber II](https://leetcode.com/problems/house-robber-ii/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(n)$

>[!Note] 
>1. 思考題目不一定要直接思考，也可以想想可不可以轉換成已知的題目形式
>2. 注意 edge cases 本題還要多思考只有兩個元素的情況

```cpp
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);
        return max(robAction(nums, 0, nums.size() - 2), robAction(nums, 1, nums.size() - 1));
    }

    int robAction(vector<int>& nums, int start, int end) {
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
};
```

## 8/12

### [337. House Robber III](https://leetcode.com/problems/house-robber-iii/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Dynamic Programming` `Tree` `Depth-First Search` `Binary Tree`


#### Traversal
* <font color="#2DB55D">**AC** (11ms) | **Beats** 25.13%</font>
* $Time: O(n)$
* $Space: O(n)$


```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<TreeNode*, int> visitedNode;
    int rob(TreeNode* root) {
        if (visitedNode.find(root) != visitedNode.end()) return visitedNode[root];
        int valNotInclude = 0, valInclude = root->val;
        if (root->left != nullptr) {
            valNotInclude += rob(root->left);
            if (root->left->right != nullptr) valInclude += rob(root->left->right);
            if (root->left->left != nullptr) valInclude += rob(root->left->left);
        }
        if (root->right != nullptr) {
            valNotInclude += rob(root->right);
            if (root->right->right != nullptr) valInclude += rob(root->right->right);
            if (root->right->left != nullptr) valInclude += rob(root->right->left);
        }
        visitedNode[root] = max(valNotInclude, valInclude);
        return visitedNode[root];
    }
};
```


#### Dynamic programing
>[!Warning] Wrong
>注意不包括時應該思考的情況

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> dp = robTree(root);
        return max(dp[0], dp[1]);
    }

    vector<int> robTree(TreeNode* cur) {
        // dp[0] --> not include, dp[1] --> include
        if (cur == nullptr) return {0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        return {left[1] + right[1], left[0] + right[0] + cur->val};
    }
};
```
---
* <font color="#2DB55D">**AC** (13ms) | **Beats** 18.46%</font>
* $Time: O(n)$
* $Space: O(n)$

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> dp = robTree(root);
        return max(dp[0], dp[1]);
    }

    vector<int> robTree(TreeNode* cur) {
        // dp[0] --> not include, dp[1] --> include
        if (cur == nullptr) return {0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        int valNotInclude = max(left[0], left[1]) + max(right[0], right[1]);
        return {valNotInclude, left[0] + right[0] + cur->val};
    }
};
```

## 8/13

### [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?source=submission-noac)

<font color="#46c6c2">**Easy**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(1)$

```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = prices[0], sold = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] < buy) buy = prices[i];
            else sold = max(sold, prices[i] - buy);
        }
        return sold;
    }
};
```


## 8/14

### [123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/?source=submission-noac)

<font color="#f8615c">**Hard**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (139ms) | **Beats** 64.04%</font>
* $Time: O(n)$
* $Space: O(n)$


```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(4, 0));
        int max_profit = 0;
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = -prices[i];
            dp[i][1] = prices[i] + dp[i - 1][0];
            dp[i][2] = -prices[i] + dp[i - 1][1];
            dp[i][3] = prices[i] + dp[i - 1][2];
            max_profit = max({max_profit, dp[i][1], dp[i][3]});
        }
        return max_profit;
    }
};
```
>[1,2,3,4,5]
>output: 2
>expected: 4

```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(4, 0));
        int max_profit = 0;
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
            dp[i][2] = max(dp[i - 1][2], -prices[i] + dp[i - 1][1]);
            dp[i][3] = max(dp[i-  1][3], prices[i] + dp[i - 1][2]);
            max_profit = max({max_profit, dp[i][1], dp[i][3]});
        }
        return max_profit;
    }
};
```
>別忘記可以選擇什麼都不做

## 8/15

### [188. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/?source=submission-noac)

<font color="#f8615c">**Hard**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (3ms) | **Beats** 86.39%</font>
* $Time: O(n \times k)$
* $Space: O(n \times k)$

```cpp
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
        int max_profit = 0;
        for (int i = 1; i <= k; i++) {
            dp[0][2 * i - 1] = -prices[0];
        }

        for (int i = 1; i < prices.size(); i++) {
            for (int j = 1; j <= k; j++) {
                int id = 2 * j - 1;
                dp[i][id] = max(dp[i - 1][id], dp[i - 1][id - 1] - prices[i]);
                dp[i][id + 1] = max(dp[i - 1][id + 1], dp[i - 1][id] + prices[i]);
                max_profit = max(max_profit, dp[i][id + 1]);
            }
        }
        return max_profit;
    }
};
```

### [309. Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(3 \times n)$


```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(3, 0));
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            // dp[i][0] => no stock
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = dp[i - 1][1] + prices[i];
        }
        return max({dp[prices.size() - 1][0], dp[prices.size() - 1][1], dp[prices.size() - 1][2]});
    }
};
```

## 8/17

### [714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming` `Greedy`

* <font color="#2DB55D">**AC** (95ms) | **Beats** 55.17%</font>
* $Time: O(n)$
* $Space: O(2 \times n)$


```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<vector<int>> dp(prices.size(), vector<int>(2));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[prices.size() - 1][1];
    }
};
```


* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(1)$
>[!Note] 空間複雜度降低，少了初始化 vector 速度增加
```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int cur_buy = -prices[0], cur_sold = 0;
        for (int i = 1; i < prices.size(); i++) {
            int prev_buy = cur_buy, prev_sold = cur_sold;
            cur_buy = max(prev_buy, cur_sold - prices[i]);
            cur_sold = max(prev_sold, cur_buy + prices[i] - fee);
        }
        return cur_sold;
    }
};
```


## 8/18

### [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Binary Search` `Dynamic Programming`

* <font color="#2DB55D">**AC** (48ms) | **Beats** 74.75%</font>
* $Time: O(n^2)$
* $Space: O(n)$
```cpp
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int result = 1;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};
```
* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n \times log(n))$
* $Space: O(n)$

```cpp
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> subsequence;
        subsequence.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > subsequence[subsequence.size() - 1]) {
                subsequence.push_back(nums[i]);
                continue;
            }

            int left = 0, right = subsequence.size();
            while (right > left) {
                int middle = ((right - left) >> 1) + left;
                if (subsequence[middle] < nums[i]) {
                    left = middle + 1;
                } else if (subsequence[middle] > nums[i]) {
                    right = middle;
                } else {
                    left = middle;
                    break;
                }
            }
            subsequence[left] = nums[i];
        }
        return subsequence.size();
    }
};
```

### [674. Longest Continuous Increasing Subsequence](https://leetcode.com/problems/longest-continuous-increasing-subsequence/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(1)$
```cpp
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int cur_length = 1, max_length = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) cur_length++;
            else cur_length = 1;
            max_length = max(max_length, cur_length);
        }
        return max_length;
    }
};
```

### [718. Maximum Length of Repeated Subarray](https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Binary Search` `Dynamic Programming` `Sliding Window` `Rolling Hash` `Hash Function`

* <font color="#2DB55D">**AC** (103ms) | **Beats** 31.60%</font>
* $Time: O(n \times m)$
* $Space: O(n \times m)$

```cpp
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int max_length = 0;
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                max_length = max(max_length, dp[i][j]);
            }
        }
        return max_length;
    }
};
```

* <font color="#2DB55D">**AC** (47ms) | **Beats** 88.61%</font>
* $Time: O(n \times m)$
* $Space: O(n)$
>[!Note]使用滾動數組但要注意
>1. 遍歷順序
>2. 注意每次遍歷的狀態變化
```cpp
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<int> dp(nums2.size() + 1, 0);
        int result = 0;
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = nums2.size(); j > 0; j--) {
                if (nums1[i - 1] == nums2[j - 1]) dp[j] = dp[j - 1] + 1;
                else dp[j] = 0;
                result = max(result, dp[j]);
            }
        }
        return result;
    }
};
```


## 8/21

### [1143. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `String` `Dynamic Programming`

* <font color="#2DB55D">**AC** (27ms) | **Beats** 83.64%</font>
* $Time: O(n \times m)$
* $Space: O(n \times m)$


```cpp
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1));
        int result = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; 
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};
```
### [1035. Uncrossed Lines](https://leetcode.com/problems/uncrossed-lines/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Dynamic Programming` `Weekly Contest 134`

#### Writing Method (2D)
* <font color="#2DB55D">**AC** (5ms) | **Beats** 70.34%</font>
* $Time: O(n \times m)$
* $Space: O(n \times m)$


```cpp
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};
```

#### Writing Method (1D)
* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n \times m)$
* $Space: O(m)$

---
>[!Warning] 看看哪裡出錯

```cpp
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<int> dp(nums2.size() + 1, 0);
        for (int i = 1, prev = 0; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                int cur = dp[j];
                if (nums1[i - 1] == nums2[j - 1]) dp[j] = prev + 1;
                else dp[j] = max(dp[j], dp[j - 1]);
                prev = cur;
            }
        }
        return dp[nums2.size()];
    }
};
```

>注意初始化
```diff
- for (int i = 1, prev = 0; i <= nums1.size(); i++)
+ for (int i = 1, prev = 0; i <= nums1.size(); i++, prev = 0)
```
---
```cpp
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<int> dp(nums2.size() + 1, 0);
        for (int i = 1, prev = 0; i <= nums1.size(); i++, prev = 0) {
            for (int j = 1; j <= nums2.size(); j++) {
                int cur = dp[j];
                if (nums1[i - 1] == nums2[j - 1]) dp[j] = prev + 1;
                else dp[j] = max(dp[j], dp[j - 1]);
                prev = cur;
            }
        }
        return dp[nums2.size()];
    }
};
```

>[!Note] 動態規劃 2D 轉為 1D
>1. 如果要用到上一個的多個狀態可以善用 `%` 
>2. 如果是上一個的斜線 (i - 1, j - 1) 可以善用 for 的初始化

## 8/22

### [392. Is Subsequence](https://leetcode.com/problems/is-subsequence/description/?source=submission-noac)

<font color="#46c6c2">**Easy**</font>
==Topics== : `Two Pointers` `String` `Dynamic Programming`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(1)$

```cpp
class Solution {
public:
    bool isSubsequence(string s, string t) {
        if (s == "") return true;
        int checkIndex = 0;
        for (int i = 0; i < t.length(); i++) {
            if (t[i] == s[checkIndex]) checkIndex++;
            if (checkIndex == s.length()) return true;
        }
        return false;
    }
};
```
### [115. Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences/description/?source=submission-noac)

**review**
<font color="#f8615c">**Hard**</font>
==Topics== : `String` `Dynamic Programming`

#### Writing Method 1 (2D)
* <font color="#2DB55D">**AC** (26ms) | **Beats** 73.18%</font>
* $Time: O(n \times m)$
* $Space: O(n \times m)$
```cpp
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.length() + 1, vector<uint64_t>(t.length() + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[s.length()][t.length()];
    }
};
```

#### Writing Method 2 (1D)
* <font color="#2DB55D">**AC** (7ms) | **Beats** 97.00%</font>
* $Time: O(n \times m)$
* $Space: O(1)$

```cpp
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<uint64_t> dp(t.length() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = t.length(); j > 0; j--) {
                if (s[i - 1] == t[j - 1]) dp[j] = dp[j - 1] + dp[j];
            }
        }
        return dp[t.length()];
    }
};
```

## 8/23

### [583. Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/description/?source=submission-noac)

<font color="#fac31d">**Medium**</font>
==Topics== : `String` `Dynamic Programming`

#### Writing Method 1 (2D)
* <font color="#2DB55D">**AC** (13ms) | **Beats** 44.21%</font>
* $Time: O(n \times m)$
* $Space: O(n \times m)$


```cpp
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.length() + 1, vector<int>(word2.length() + 1, 0));
        for (int i = 1; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= word2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
        return dp[word1.length()][word2.length()];
    }
};
```
#### Writing Method 2 (1D)
* <font color="#2DB55D">**AC** (3ms) | **Beats** 97.92%</font>
* $Time: O(n \times m)$
* $Space: O(m)$

---
>[!Warning] 錯誤初始化

```cpp=
public:
    int minDistance(string word1, string word2) {
        vector<int> dp(word2.length() + 1);
        for (int i = 0; i <= word2.length(); i++) {
            dp[i] = i;
        }
        for (int i = 1, prev = 0; i <= word1.length(); prev = i++) {
            for (int j = 1; j <= word2.length(); j++) {
                int cur = dp[j];
                if (word1[i - 1] == word2[j - 1]) dp[j] = prev;
                else dp[j] = min(dp[j - 1], dp[j]) + 1;
                prev = cur;
            }
        }
        return dp[word2.length()];
    }
};
```
```diff
+8 dp[0] = i
```
---


```cpp
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<int> dp(word2.length() + 1);
        for (int i = 0; i <= word2.length(); i++) {
            dp[i] = i;
        }
        for (int i = 1, prev = 0; i <= word1.length(); prev = i++) {
            dp[0] = i;
            for (int j = 1; j <= word2.length(); j++) {
                int cur = dp[j];
                if (word1[i - 1] == word2[j - 1]) dp[j] = prev;
                else dp[j] = min(dp[j - 1], dp[j]) + 1;
                prev = cur;
            }
        }
        return dp[word2.length()];
    }
};
```

## 8/26
weekly contest

## 8/27 
weekly contest

## 8/28
### [496. Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/description/)

<font color="#46c6c2">**Easy**</font>
==Topics== : `Array` `Hash Table` `Stack` `Monotonic Stack`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(nums1.size() + nums2.size())$
* $Space: O(nums1.size())$

```cpp
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans(nums1.size());
        unordered_map<int, int> map;
        stack<int> st;
        for (int i = 0; i < nums2.size(); i++) {
            while (!st.empty() && st.top() < nums2[i]) {
                map[st.top()] = nums2[i];
                st.pop();
            }
            st.push(nums2[i]);
        }
        while (!st.empty()) {
            map[st.top()] = -1;
            st.pop();
        }
        for (int i = 0; i < nums1.size(); i++) {
            ans[i] = map[nums1[i]];
        }

        return ans;
    }
};
```

### [503. Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Stack` `Monotonic Stack`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(n)$
```cpp
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        vector<int> ans(nums.size(), -1);
        for (int i = 0; i < nums.size(); i++) {
            while (!st.empty() && nums[st.top()] < nums[i]) {
                ans[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        for (int i = 0; i < nums.size(); i++) {
            if (st.size() == 1) break;
            while (nums[st.top()] < nums[i]) {
                ans[st.top()] = nums[i];
                st.pop();
            }
        }
        return ans;
    }
};
```

## 8/30
### [797. All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Backtracking` `Depth-First Search` `Breadth-First Search` `Graph` `Weekly Contest 75`

* <font color="#2DB55D">**AC** (3ms) | **Beats** 76.02%</font>
* $Time: O(2^n)$
* $Space: O(n)$

```cpp
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> ans_element;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        ans_element.push_back(0);
        dfs(graph, 0, graph.size() - 1);
        return ans;
    }

    void dfs(vector<vector<int>>& graph, int node, int last_node) {
        if (node == last_node) {
            ans.push_back(ans_element);
            return;
        }

        for (int i = 0; i < graph[node].size(); i++) {
            ans_element.push_back(graph[node][i]);
            dfs(graph, graph[node][i], last_node);
            ans_element.pop_back();
        }
        return;
    }

};
```

## 9/4

### [200. Number of Islands](https://leetcode.com/problems/number-of-islands/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Depth-First Search` `Breadth-First Search` `Union Find` `Matrix`

#### Writing Method 1 (DFS)
* <font color="#2DB55D">**AC** (30ms) | **Beats** 37.16%</font>
* $Time: O(m \times n)$
* $Space: O(m \times n)$

```cpp
class Solution {
public:
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
    void dfs(vector<vector<char>>& grid, int row, int col) {
        for (int i = 0; i < 4; i++) {
            int next_row = row + dir[i][0];
            int next_col = col + dir[i][1];
            if (next_row < 0 || next_row >= grid.size() || next_col < 0 || next_col >= grid[0].size()) continue;
            if (grid[next_row][next_col] != '0') {
                grid[next_row][next_col] = '0';
                dfs(grid, next_row, next_col);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] != '0') {
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }
};
```

#### Writing Method 2 (bfs)
* <font color="#2DB55D">**AC** (26ms) | **Beats** 64.75%</font>
* $Time: O(m \times n)$
* $Space: O(m \times n)$
```cpp
class Solution {
public:
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
    void bfs(vector<vector<char>>& grid, int row, int col) {
        queue<pair<int, int>> que;
        grid[row][col] = '0';
        que.push({row, col});
        while (!que.empty()) {
            pair<int, int> cur = que.front();
            que.pop();
            row = cur.first;
            col = cur.second;
            for (int i = 0; i < 4; i++) {
                int next_row = row + dir[i][0];
                int next_col = col + dir[i][1];
                if (next_row < 0 || next_row >= grid.size() || next_col < 0 || next_col >= grid[0].size()) continue;
                if (grid[next_row][next_col] != '0') {
                    grid[next_row][next_col] = '0';
                    que.push({next_row, next_col});
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] != '0') {
                    ans++;
                    bfs(grid, i, j);
                }
            }
        }
        return ans;
    }
};
```
### [695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Depth-First Search` `Breadth-First Search` `Union Find` `Matrix`

* <font color="#2DB55D">**AC** (1ms) | **Beats** 66.30%</font>
* $Time: O(m \times n)$
* $Space: O(m \times n)$
```cpp
class Solution {
public:
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
    int bfs(vector<vector<int>>& grid, int row, int col) {
        int area = 0;
        queue<pair<int, int>> que;
        que.push({row, col});
        area++;
        grid[row][col] = 0;
        while (!que.empty()) {
            int row = que.front().first;
            int col = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int next_row = row + dir[i][0];
                int next_col = col + dir[i][1];
                if (next_row < 0 || next_row >= grid.size() || next_col < 0 || next_col >= grid[0].size()) continue;
                if (grid[next_row][next_col] == 1) {
                    que.push({next_row, next_col});
                    area++;
                    grid[next_row][next_col] = 0;
                }
            }
        }
        return area;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
       int ans = 0; 
       for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {
                ans = max(ans, bfs(grid, i, j));
            }
        }
       }
       return ans;
    }
};
```
### [1254. Number of Closed Islands](https://leetcode.com/problems/number-of-closed-islands/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Depth-First Search` `Breadth-First Search` `Union Find` `Matrix` `Weekly Contest 162`

* <font color="#2DB55D">**AC** (2ms) | **Beats** 51.90%</font>
* $Time: O(m \times n)$
* $Space: O(m \times n)$


```cpp
class Solution {
public:
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    void bfs(vector<vector<int>>& grid, int row, int col) {
        queue<pair<int, int>> que;
        que.push({row, col});
        grid[row][col] = 1;
        while (!que.empty()) {
            int row = que.front().first;
            int col = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int next_row = row + dir[i][0];
                int next_col = col + dir[i][1];
                if (next_row < 0 || next_row >= grid.size() || next_col < 0 || next_col >= grid[0].size()) continue;
                if (grid[next_row][next_col] == 0) {
                    que.push({next_row, next_col});
                    grid[next_row][next_col] = 1;
                }
            }
        }
    }
    int closedIsland(vector<vector<int>>& grid) {
        int cnt = 0;
        for (int i = 0; i < grid.size(); i++) {
            if (grid[i][0] == 0) bfs(grid, i, 0);
            if (grid[i][grid[0].size() - 1] == 0) bfs(grid, i, grid[0].size() - 1);
        }
        for (int i = 0; i < grid[0].size(); i++) {
            if (grid[0][i] == 0) bfs(grid, 0, i);
            if (grid[grid.size() - 1][i] == 0) bfs(grid, grid.size() - 1, i);
        }
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0) {
                    cnt++;
                    bfs(grid, i, j);
                }
            }
        }
        return cnt;
    }
};
```

## 9/5
### [1254. Number of Closed Islands](https://leetcode.com/problems/number-of-closed-islands/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Depth-First Search` `Breadth-First Search` `Union Find` `Matrix` `Weekly Contest 162`

* <font color="#2DB55D">Time Limit Exceeded</font>
* $Time: O(m^2 \times n^2)$
* $Space: O(m \times n)$

```cpp
class Solution {
public:
    vector<vector<int>> ans;
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    bool bfs(vector<vector<int>>& heights, vector<vector<int>>& reach_both, int row, int col) {
        bool reach_pacific = false, reach_atlantic = false;
        queue<pair<int, int>> que;
        que.push({row, col});
        while (!que.empty()) {
            row = que.front().first;
            col = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int next_row = row + dir[i][0];
                int next_col = col + dir[i][1];
                if (next_row < 0 || next_col < 0) {
                    reach_pacific = true;
                } else if (next_row >= heights.size() || next_col >= heights[0].size()) {
                    reach_atlantic = true;
                } else if (heights[next_row][next_col] > heights[row][col]) {
                    continue;
                } else if (reach_both[next_row][next_col] == 1) {
                    return true;
                } else {
                    que.push({next_row, next_col});
                }
                
                if (reach_pacific && reach_atlantic) return true;
            }
        }
        return false;
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> reach_both(heights.size(), vector<int>(heights[0].size(), 0));
        for (int i = 0; i < heights.size(); i++) {
            for (int j = 0; j < heights[0].size(); j++) {
                if (bfs(heights, reach_both, i, j)) {
                    reach_both[i][j] = 1;
                    ans.push_back({i, j});
                } else {
                    reach_both[i][j] = -1;
                }
            }
        }
        return ans;
    }
};
```
* <font color="#2DB55D">**AC** (15ms) | **Beats** 30.07%</font>
* $Time: O(m \times n)$
* $Space: O(m \times n)$

```cpp
class Solution {
public:
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    void bfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int row, int col) {
        if (visited[row][col]) return;
        queue<pair<int, int>> que;
        visited[row][col] = true;
        que.push({row, col});
        while (!que.empty()) {
            row = que.front().first;
            col = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int next_row = row + dir[i][0];
                int next_col = col + dir[i][1];
                if (next_row < 0 || next_row >= heights.size() || next_col < 0 || next_col >= heights[0].size()) continue;
                if (visited[next_row][next_col] || heights[next_row][next_col] < heights[row][col]) continue;
                visited[next_row][next_col] = true;
                que.push({next_row, next_col});
            }
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> ans;
        vector<vector<bool>> reach_pacific(heights.size(), vector<bool>(heights[0].size(), false));
        vector<vector<bool>> reach_atlantic(heights.size(), vector<bool>(heights[0].size(), false));
        for (int i = 0; i < heights.size(); i++) {
            bfs(heights, reach_pacific, i, 0);
            bfs(heights, reach_atlantic, i, heights[0].size() - 1);
        }
        for (int i = 0; i < heights[0].size(); i++) {
            bfs(heights, reach_pacific, 0, i);
            bfs(heights, reach_atlantic, heights.size() - 1, i);
        }
        for (int i = 0; i < heights.size(); i++) {
            for (int j = 0; j < heights[0].size(); j++) {
                if (reach_pacific[i][j] && reach_atlantic[i][j]) ans.push_back({i, j});
            }
        }
        return ans;
    }
};
```

## 9/6
### [Q3. Maximum Product of Two Integers With No Common Bits](https://leetcode.com/contest/weekly-contest-465/problems/maximum-product-of-two-integers-with-no-common-bits/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Weekly Contest 465`

* <font color="#2DB55D">Time Limit Exceeded</font>
* $Time: O(n^2)$
* $Space: O(1)$


```cpp
class Solution {
public:
    long long maxProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        long long ans = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            if ((long long) nums[i] * nums[i] <= ans) break;
            for (int j = i + 1; j < nums.size(); j++) {
                if ((nums[i] & nums[j]) != 0) continue;
                long long product = (long long) nums[i] * nums[j];
                if (product <= ans) break;
                ans = max(ans, product);
            }
        }
        return ans;
    }
};
```
* <font color="#2DB55D">**AC** (419ms)</font>
* $Time: O(m \times 2 ^ m)$
* $Space: O(2 ^ m)$
```cpp
class Solution {
public:
    long long maxProduct(vector<int>& nums) {
        long long ans = 0;
        int num_bits = 0, max_num = *max_element(nums.begin(), nums.end());
        while ((1 << num_bits) <= max_num) num_bits++;
        vector<int> dp(1 << num_bits, 0);
        for (int i: nums) {
            dp[i] = i;
        }
        for (int i = 0; i < num_bits; i++) {
            for (int mask = 0; mask < (1 << num_bits); mask++) {
                if (mask & (1 << i)) {
                    dp[mask] = max(dp[mask], dp[mask ^ (1 << i)]);
                }
            }
        }
        for (int i: nums) {
            int complement = ((1 << num_bits) - 1) ^ i;
            ans = max(ans, 1LL * dp[i] * dp[complement]);
        }
        return ans;
    }
};
```

## 9/7
### [827. Making A Large Island](https://leetcode.com/problems/making-a-large-island/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Depth-First Search` `Breadth-First Search` `Union Find` `Matrix` `Weekly Contest 82`

* <font color="#2DB55D">Time Limit Exceeded</font>
* $Time: O(n^2)$
* $Space: O(1)$

```cpp
class Solution {
public:
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    int bfs(vector<vector<int>>& grid, int row, int col) {
        int area = 0;
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        queue<pair<int, int>> que;
        que.push({row, col});
        visited[row][col] = true;
        area++;
        while (!que.empty()) {
            row = que.front().first;
            col = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int next_row = row + dir[i][0];
                int next_col = col + dir[i][1];
                if (next_row < 0 || next_row >= grid.size() || next_col < 0 || next_col >= grid[0].size()) continue;
                if (grid[next_row][next_col] == 0 || visited[next_row][next_col]) continue;
                que.push({next_row, next_col});
                visited[next_row][next_col] = true;
                area++;
            }
        }
        return area;
    }
    int largestIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                ans = max(ans, bfs(grid, i, j));
            }
        }
        return ans;
    }
};
```
* <font color="#2DB55D">**AC** (20ms) | **Beats** 40.98%</font>
* $Time: O(m \times n)$
* $Space: O(m \times n)$
```cpp
class Solution {
public:
    vector<int> island_area;
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    int bfs(vector<vector<int>>& grid, int id, int row, int col) {
        int area = 0;
        queue<pair<int, int>> que;
        que.push({row, col});
        area++;
        grid[row][col] = id;
        while (!que.empty()) {
            row = que.front().first;
            col = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int next_row = row + dir[i][0];
                int next_col = col + dir[i][1];
                if (next_row < 0 || next_row >= grid.size() || next_col < 0 || next_col >= grid[0].size()) continue;
                if (grid[next_row][next_col] != 1) continue;
                que.push({next_row, next_col});
                area++;
                grid[next_row][next_col] = id;
            }
        }
        island_area.push_back(area);
        return area;
    }
    int largestIsland(vector<vector<int>>& grid) {
        island_area.push_back(0);
        island_area.push_back(0);
        int id = 2, ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    ans = max(ans, bfs(grid, id, i, j));
                    id++;
                }
            }
        }
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] != 0) continue;
                unordered_set<int> uset;
                int cur_area = 1;
                for (int k = 0; k < 4; k++) {
                    int next_i = i + dir[k][0];
                    int next_j = j + dir[k][1];
                    if (next_i < 0 || next_i >= grid.size() || next_j < 0 || next_j >=grid[0].size()) continue;
                    if (grid[next_i][next_j] == 0) continue;
                    uset.insert(grid[next_i][next_j]);
                }
                for (const auto& s: uset) {
                    cur_area += island_area[s];
                }
                ans = max(ans, cur_area);
            }
        }
        return ans;
    }
};
```


## 9/9
### [463. Island Perimeter](https://leetcode.com/problems/island-perimeter/description/)
<font color="#46c6c2">**Easy**</font>
==Topics== : `Array` `Depth-First Search` `Breadth-First Search` `Matrix`

* <font color="#2DB55D">**AC** (3ms) | **Beats** 70.95%</font>
* $Time: O(m \times n)$
* $Space: O(1)$


```cpp
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0) continue;
                for (int k = 0; k < 4; k++) {
                    int next_i = i + dir[k][0];
                    int next_j = j + dir[k][1];
                    if (next_i < 0 || next_i >= grid.size() || next_j < 0 || next_j >= grid[0].size()) {
                        ans++;
                        continue;
                    }
                    if (grid[next_i][next_j] == 0) ans++;
                }
            }
        }
        return ans;
    }
};
```

## 9/10
### [127. Word Ladder](https://leetcode.com/problems/word-ladder/description/)
<font color="#f8615c">**Hard**</font>
==Topics== : `Hash Table` `String` `Breadth-First Search`
* <font color="#2DB55D">**AC** (99ms) | **Beats** 44.64%</font>
* $Time: O(m \times n \times 26)$ 
* $Space: O(m)$
>m: number of edges
>n: the length of beginWord and endWord


```cpp
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> uset(wordList.begin(), wordList.end());
        unordered_map<string, int> umap;
        umap[beginWord] = 1;
        queue<string> que;
        que.push(beginWord);
        while (!que.empty()) {
            string cur = que.front();
            int cur_path = umap[cur];
            que.pop();
            if (cur == endWord) return cur_path;
            for (int i = 0; i < cur.length(); i++) {
                for (char j = 'a'; j <= 'z'; j++) {
                    if (j == cur[i]) continue;
                    string tmp = cur;
                    tmp[i] = j;
                    if (uset.find(tmp) == uset.end() || umap.find(tmp) != umap.end()) continue;
                    umap[tmp] = cur_path + 1;
                    que.push(tmp);
                }
            }
        }
        return 0;
    }
};
```
### [1557. Minimum Number of Vertices to Reach All Nodes](https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/)

<font color="#fac31d">**Medium**</font>
==Topics== : `Graph` `Biweekly Contest 33`
* <font color="#2DB55D">**AC** (3ms) | **Beats** 78.12%</font>
* $Time: O(n + e)$ 
* $Space: O(n)$

```cpp
class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> edge_node(n, 0);
        vector<int> ans;
        for (int i = 0; i < edges.size(); i++) {
            edge_node[edges[i][1]] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (edge_node[i] == 0) ans.push_back(i);
        }
        return ans;
    }
};
```

## 9/11
### [Learning Union Find](https://gitee.com/programmercarl/leetcode-master/blob/master/problems/kamacoder/%E5%9B%BE%E8%AE%BA%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.md)

```cpp
#include <bits/stdc++.h>
#define N 10
using namespace std;

vector<int> father(N);
void fatherInit(vector<int>& father) {
    for (int i = 0; i < father.size(); i++) {
        father[i] = i;
    }
}

int findFather(vector<int>& father, int a) {
    return (a == father[a]) ? a : father[a] = findFather(father, father[a]);
}

bool fatherIsSame(vector<int>& father, int a, int b) {
    return findFather(father, a) == findFather(father, b);
}

void join(vector<int>& father, int a, int b) {
    int v = findFather(father, a);
    int u = findFather(father, b);
    if (v == u) return;
    father[u] = v;
}

void printNode(vector<int>& node) {
    for (int i = 0; i < node.size(); i++) {
        cout << i << "-->" << node[i] << endl;
    }
}

int main() {
    // initialize
    fatherInit(father);

    // chose optino
    int option, a, b;
    while (true) {
        cout << "1. print father \n2. join node \n3. in the same union \n4. exit" << endl;
        cin >> option;
        switch (option) {
            case 1:
                printNode(father);
                break;
            case 2:
                cin >> a >> b;
                join(father, a, b);
                cout << "finished join" << endl;
                break;
            case 3:
                cin >> a >> b;
                if (fatherIsSame(father, a, b)) {
                    cout << a << " and " << b << " in the same union" << endl;
                } else {
                    cout << a << " and " << b << " in the different union" << endl;
                }
                break;
            default:
                break;
        }
        if (option == 4) break;
        cout << endl << "==============================" << endl;
    }
    return 0;
}
```

## 9/12
### [1971. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/description/)
<font color="#46c6c2">**Easy**</font>
==Topics== : `Depth-First Search` `Breadth-First Search` `Union Find` `Graph`

* <font color="#2DB55D">**AC** (27ms) | **Beats** 94.94%</font>
* $Time: O(n)$
* $Space: O(n)$
```cpp
class Solution {
public:
    int findFather(vector<int>& father, int a) {
        return (father[a] == a) ? a : father[a] = findFather(father, father[a]);
    }
    bool isSame(vector<int>& father, int a, int b) {
        return findFather(father, a) == findFather(father, b);
    }
    void join(vector<int>& father, int a, int b) {
        int v = findFather(father, a);
        int u = findFather(father, b);
        if (v != u) father[v] = u;
    }
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
       vector<int> father(n);
       // initialize
       for (int i = 0; i < n; i++) {
        father[i] = i;
       }
       for (int i = 0; i < edges.size(); i++) {
        join(father, edges[i][0], edges[i][1]);
       }
       return isSame(father, source, destination);
    }
};
```
### [684. Redundant Connection](https://leetcode.com/problems/redundant-connection/description/)
<font color="#fac31d">**Medium**</font>
==Topics== : `Depth-First Search` `Breadth-First Search` `Union Find` `Graph`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(n)$
```cpp
class Solution {
public:
    vector<int> father;
    int find(int a) {
        return (a == father[a]) ? a : father[a] = find(father[a]);
    }
    bool isSame(int a, int b) {
        return find(a) == find(b);
    }
    void join(int a, int b) {
        int v = find(a);
        int u = find(b);
        if (v != u) father[u] = v;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        for (int i = 0; i <= edges.size(); i++) {
            father.push_back(i);
        }
        for (int i = 0; i < edges.size(); i++) {
            if (isSame(edges[i][0], edges[i][1])) return edges[i];
            join(edges[i][0], edges[i][1]);
        }
        return {0, 0};
    }
};
```

### [685. Redundant Connection II](https://leetcode.com/problems/redundant-connection-ii/description/)
<font color="#f8615c">**Hard**</font>
==Topics== : `Depth-First Search` `Breadth-First Search` `Union Find` `Graph`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$
* $Space: O(n)$

>[!Note] 思考三種 case
>case 1: 兩個入沒有環
>case 2: 兩個入有環
>case 3: 都只有一個入，直接判斷環
```cpp
class Solution {
public:
    vector<int> father;
    int find(int a) {
        return (a == father[a]) ? a : father[a] = find(father[a]);
    }
    bool isSame(int a, int b) {
        return find(a) == find(b);
    }
    void join(int a, int b) {
        int v = find(a);
        int u = find(b);
        if (v != u) father[u] = v;
    }
    bool isTreeAfterRemoved(vector<vector<int>>& edges, vector<int>& deleteEdge) {
        for (int i = 0; i < edges.size(); i++) {
            if (edges[i][0] == deleteEdge[0] && edges[i][1] == deleteEdge[1]) continue;
            if (isSame(edges[i][0], edges[i][1])) return false;
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        vector<int> ans1, ans2;
        vector<int> node_in(edges.size() + 1, 0);
        for (int i = 0; i <= edges.size(); i++) {
            father.push_back(i);
        }
        for (int i = 0; i < edges.size(); i++) {
            if (node_in[edges[i][1]] != 0) {
                ans1 = {node_in[edges[i][1]], edges[i][1]};
                ans2 = edges[i];
                break;
            }
            node_in[edges[i][1]] = edges[i][0];
        }
        if (ans1.size() == 2) {
            if (isTreeAfterRemoved(edges, ans2)) return ans2;
            return ans1;
        }
        for (int i = 0; i < edges.size(); i++) {
            if (isSame(edges[i][0], edges[i][1])) return edges[i];
            join(edges[i][0], edges[i][1]);
        }
        return {0, 0};
    }
};
```

## 9/13
### [1584. Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/description/)
<font color="#fac31d">**Medium**</font>
==Topics== : `Array` `Union Find` `Graph` `Minimum Spanning Tree` `Weekly Contest 206`

#### Writing Method 1 (prim)
* <font color="#2DB55D">**AC** (15ms) | **Beats** 98.14%</font>
* $Time: O(n ^ 2)$ n is the number of nodes
* $Space: O(n)$

>[!Note] prim 算法找 mini spinning tree
>1. find nearest point
>2. join the point
>3. update the min distance of tree
```cpp
class Solution {
public:
    int countDist(int x1, int y1, int x2, int y2) {
        return abs(x1 - x2) + abs(y1 - y2);
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int ans = -INT_MAX;
        vector<int> minDist(points.size(), INT_MAX);
        vector<int> isVisit(points.size(), false);
        for (int i = 0; i < points.size(); i++) {
            int cur = 0;
            int dist = minDist[0];
            for (int i = 1; i < points.size(); i++) {
                if (!isVisit[i] && minDist[i] < dist) {
                    dist = minDist[i];
                    cur = i;
                }
            }
            isVisit[cur] = true;
            ans += minDist[cur];
            for (int i = 1; i < points.size(); i++) {
                if (!isVisit[i]) {
                    minDist[i] = min(minDist[i], countDist(points[cur][0], points[cur][1], points[i][0], points[i][1]));
                }
            }
        }
        return ans;
    }
};
```

#### Writing Method 2 (Kruskal)
* <font color="#2DB55D">**AC** (286ms) | **Beats** 56.91%</font>
* $Time: O(n \times log(n))$ n is the number of edges.
* $Space: O(n)$

>[!Note] Kruskal
>1. sort every edges
>2. union find
```cpp
class Solution {
public:
    vector<int> father;
    struct Edge {
        int l, r, val;
    };
    int dist(vector<int>& v1, vector<int>& v2) {
        return abs(v1[0] - v2[0]) + abs(v1[1] - v2[1]);
    }
    int find(int a) {
        return (a == father[a]) ? a : father[a] = find(father[a]);
    }
    bool isSame(int a, int b) {
        return find(a) == find(b);
    }
    void join(int a, int b) {
        int v = find(a);
        int u = find(b);
        if (v != u) father[u] = v;
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        vector<Edge> edges;
        int ans = 0;
        for (int i = 0; i < points.size(); i++) {
            father.push_back(i);
            for (int j = i + 1; j < points.size(); j++) {
                edges.push_back({i, j, dist(points[i], points[j])});
            }
        }
        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
        });
        for (int i = 0; i < edges.size(); i++) {
            if (isSame(edges[i].l, edges[i]. r)) continue;
            join(edges[i].l, edges[i].r);
            ans += edges[i].val;
        }
        return ans;
    }
};
```

## 9/16
### [662. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/description/)
<font color="#fac31d">**Medium**</font>
==Topics== : `Tree` `Depth-First Search` `Breadth-First Search` `Binary Tree`

* <font color="#2DB55D">**AC** (0ms) | **Beats** 100%</font>
* $Time: O(n)$ n is the number of nodes
* $Space: O(n)$
```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        int ans = 1;
        int previous_width = 1;
        bool count_width = false;
        queue<pair<uint64_t, TreeNode*>> que;
        que.push({1, root});
        while (!que.empty()) {
            int size = que.size();
            uint64_t right = que.front().first;
            uint64_t left = right;
            for (int i = 0; i < size; i++) {
                uint64_t cur_width = que.front().first;
                TreeNode* cur_node = que.front().second;
                que.pop();
                left = cur_width;
                if (cur_node->right != nullptr) {
                    que.push({2 * cur_width, cur_node->right});
                }
                if (cur_node->left != nullptr) {
                    que.push({2 * cur_width - 1, cur_node->left});
                }
            }
            ans = max(ans, (int) (right - left) + 1);
        }
        return ans;
    }
};
```