# 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;
}
};
```
Sign in with Wallet
Connect another wallet