# Grind 75

你得有足够的驱动力强迫自己静下心来，阅读几十页的 Project Handout，理解上千行的代码框架，忍受数个小时的 debug 时光。而这一切，没有学分，没有绩点，没有老师，没有同学，只有一个信念 —— 你在变强。

CSDIY

# Week 1 (13/13)

# Two Sum

題目： https://leetcode.com/problems/two-sum/
難度： Easy
語言： C++17
技巧： unordered_map

建一個 map
- key：num
- value：the index of (target - num)
掃瞄 nums，對於每個 num ∈ nums
- 對於每個 num，用 num 去查詢 complement map
  - 若存在，{value, 目前的 index} 就是答案了
  - 不存在，將 {target - num, 目前的 index} 存進去

	class Solution {
	public:
	vector<int> twoSum(const vector<int> &nums, const int target) {
	unordered_map<int, int> num_to_complement_idx;

	for (int i = 0; i < nums.size(); i++) {
	const auto it = num_to_complement_idx.find(nums[i]);
	if (it != num_to_complement_idx.end()) {
	return {i, it->second};
	}
	num_to_complement_idx[target - nums[i]] = i;
	}

	return {-1, -1};
	}
	};

# Valid Parentheses

題目： https://leetcode.com/problems/valid-parentheses/
難度： Easy
語言： C++17
技巧： stack

檢查字串 s 裡括號的合法性
- ( 不合法
- ([)] 不合法
- (([])) 合法

	class Solution {
	public:
	bool isValid(const string &s) {
	for (const auto c : s) {
	switch (c) {
	case '(':
	stack_.emplace(')');
	break;
	case '[':
	stack_.emplace(']');
	break;
	case '{':
	stack_.emplace('}');
	break;
	case ')':
	case ']':
	case '}':
	if (stack_.empty() \|\| stack_.top() != c) {
	return false;
	}
	stack_.pop();
	break;
	default:
	return false;
	}
	}

	return stack_.empty();
	}

	private:
	stack<char> stack_;
	};

# Merge Two Sorted Lists

題目： https://leetcode.com/problems/merge-two-sorted-lists/
難度： Easy
語言： C++17
技巧： list

	class Solution {
	public:
	ListNode* mergeTwoLists(ListNode list1, ListNode list2) {
	ListNode *head = nullptr;
	ListNode *curr = nullptr;

	while (list1 \|\| list2) {
	ListNode *new_node = nullptr;
	if (list1 && !list2) {
	new_node = list1;
	list1 = list1->next;
	} else if (!list1 && list2) {
	new_node = list2;
	list2 = list2->next;
	} else { // list1 && list2
	if (list1->val <= list2->val) {
	new_node = list1;
	list1 = list1->next;
	} else {
	new_node = list2;
	list2 = list2->next;
	}
	}

	if (!head) {
	head = new_node;
	curr = new_node;
	} else {
	curr->next = new_node;
	curr = new_node;
	}
	}

	return head;
	}
	};

# Best Time to Buy and Sell Stock

題目： https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
難度： Easy
語言： C++17
技巧： array dynamic programming

如果將 prices 中每個 price 視為買點，那麼每個買點都會有個最佳賣點
- best_sell_prices
最佳賣點 = 此點往右（不包含自己）的最大值
- 有沒有聞到 <LC> #238 - Product of Array Except Self 的味道？
複雜度：
- Time O(N)
- Space O(N)

	// best_sell_prices: [6,6,6,6,4,0]
	// input: [7,1,5,3,6,4]

	// best_sell_prices: [6,4,3,1,0]
	// input: [7,6,4,3,1]

	class Solution {
	public:
	int maxProfit(const vector<int> &prices) {
	vector<int> best_sell_prices(prices.size(), 0);
	for (int i = prices.size() - 2; i >= 0; i--) {
	best_sell_prices[i] = std::max(prices[i + 1], best_sell_prices[i + 1]);
	}

	int max_profit = 0;
	for (int i = 0; i < prices.size(); i++) {
	max_profit = std::max(max_profit, best_sell_prices[i] - prices[i]);
	}
	return max_profit;
	}
	};

上面的邏輯再稍微 distill 一下
- Time O(N)
- Space O(1)

	class Solution {
	public:
	int maxProfit(const vector<int> &prices) {
	int best_sell_price = 0;
	int max_profit = 0;

	for (int i = prices.size() - 2; i >= 0; i--) {
	best_sell_price = std::max(best_sell_price, prices[i + 1]);
	max_profit = std::max(max_profit, best_sell_price - prices[i]);
	}

	return max_profit;
	}
	};

# Valid Palindrome

題目： https://leetcode.com/problems/valid-palindrome/
難度： Easy
語言： C++17
技巧： two pointers

	class Solution {
	public:
	bool isPalindrome(const string &s) {
	int l = 0;
	int r = s.size() - 1;

	while (l < r) {
	if (!isalnum(s[l])) {
	l++;
	continue;
	}
	if (!isalnum(s[r])) {
	r--;
	continue;
	}
	if (std::tolower(s[l]) != std::tolower(s[r])) {
	return false;
	}
	l++;
	r--;
	}

	return true;
	}
	};

# Invert Binary Tree

題目： https://leetcode.com/problems/invert-binary-tree/
難度： Easy
語言： C++17
技巧： binary tree recursion

	class Solution {
	public:
	TreeNode* invertTree(TreeNode* root) {
	if (!root) {
	return nullptr;
	}

	std::swap(root->left, root->right);
	invertTree(root->left);
	invertTree(root->right);
	return root;
	}
	};

# Valid Anagram

題目： https://leetcode.com/problems/valid-anagram/
難度： Easy
語言： C++17
技巧： unordered_map

anagram 的定義：同字母異序字、重組字、變位字
用 unordered_map 紀錄各個字母出現的頻率，任何一個字的頻率不對就 return false
長度不一樣就不用比了，肯定不是 anagram

	class Solution {
	public:
	bool isAnagram(string s, string t) {
	if (s.size() != t.size()) {
	return false;
	}

	unordered_map<char, int> char_freqs;
	for (const auto c : s) {
	char_freqs[c]++;
	}

	for (const auto c : t) {
	auto it = char_freqs.find(c);
	if (it == char_freqs.end()) {
	return false;
	}

	if (--it->second == 0) {
	char_freqs.erase(it);
	}
	}

	return true;
	}
	};

# Binary Search

題目： https://leetcode.com/problems/binary-search/
難度： Easy
語言： C++17
技巧： binary search

	class Solution {
	public:
	int search(const vector<int> &nums, const int target) {
	int l = 0;
	int r = nums.size() - 1;
	int m;

	while (l <= r) {
	m = l + (r - l) / 2;
	if (nums[m] == target) {
	return m;
	} else if (nums[m] < target) {
	l = m + 1;
	} else { // nums[m] > target
	r = m - 1;
	}
	}

	return -1;
	}
	};

# Flood Fill

題目： https://leetcode.com/problems/flood-fill/
難度： Easy
語言： C++17
技巧： matrix single-source bfs

小畫家的 paint bucket/fill tool
Single-source matrix bfs
BFS 過程中，記得不要走出界，也不要走到不是原本顏色的 pixel

	class Solution {
	public:
	vector<vector<int>> floodFill(vector<vector<int>> &image,
	const int sr,
	const int sc,
	const int new_color) {
	const int old_color = image[sr][sc];
	if (old_color == new_color) {
	return image;
	}

	queue<pair<int, int>> q;
	q.emplace(sr, sc);
	while (q.size()) {
	const auto [r, c] = q.front();
	q.pop();

	image[r][c] = new_color;

	if (r - 1 >= 0 && image[r - 1][c] == old_color) {
	image[r - 1][c] = new_color;
	q.emplace(r - 1, c);
	}
	if (r + 1 < image.size() && image[r + 1][c] == old_color) {
	image[r + 1][c] = new_color;
	q.emplace(r + 1, c);
	}
	if (c - 1 >= 0 && image[r][c - 1] == old_color) {
	image[r][c - 1] = new_color;
	q.emplace(r, c - 1);
	}
	if (c + 1 < image[0].size() && image[r][c + 1] == old_color) {
	image[r][c + 1] = new_color;
	q.emplace(r, c + 1);
	}
	}

	return image;
	}
	};

# Lowest Common Ancestor of a Binary Search Tree

題目： https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
難度： Medium
語言： C++17
技巧： binary search tree

第一次寫的時候沒注意到有 binary search tree 的 sorted property 可以利用，所以寫了一個 generic binary tree 的 solution。

題目給你一棵 BST，然後給你 BST 中的兩個 tree node p, q ，要你找出它們的 lowest common ancestor (grandparent node)，並且自己也算是自己的 ancestor。

如果 current node root 比兩個 target nodes p, q 小，就往 right subtree 找
如果 current node root 比兩個 target nodes p, q 大，就往 left subtree 找
如果 current node root 和 p, q 相比是一大一小，代表 p, q 必定在自己下面的一左一右。

	class Solution {
	public:
	TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	// Remember to exploit the property of a binary search tree! :-^)
	if (root->val < p->val && root->val < q->val) {
	return lowestCommonAncestor(root->right, p, q);
	} else if (root->val > p->val && root->val > q->val) {
	return lowestCommonAncestor(root->left, p, q);
	} else {
	return root;
	}
	}
	};

# Balanced Binary Tree

題目： https://leetcode.com/problems/balanced-binary-tree/
難度： Easy
語言： C++17
技巧： binary tree dfs

每一個 node 都去找它左右子樹的深度，深度的差只能是 0 或 1，不能是 2 (含) 以上。

	class Solution {
	public:
	bool isBalanced(TreeNode *root) {
	getDepth(root);
	return is_balanced_;
	}

	private:
	int getDepth(TreeNode *node) {
	if (!node) {
	return 0;
	}

	int l_depth = getDepth(node->left);
	int r_depth = getDepth(node->right);
	int current_depth = std::max(l_depth, r_depth) + 1;
	is_balanced_ &= std::abs(l_depth - r_depth) <= 1;
	return current_depth;
	}

	bool is_balanced_ = true;
	};

# Linked List Cycle

題目： https://leetcode.com/problems/linked-list-cycle/
難度： Easy
語言： C++17
技巧： two pointers

Fast & Slow Pointers

如果 linked list 沒 cycle 的話，while loop 必定能走完，最終回傳 false
如果 linked list 有 cycle 的話，while loop 必定無窮迴圈
- 讓 fast pointer 一次走兩步
- 讓 slow pointer 一次走一步
- 如果有 cycle 的話，有朝一日 fast pointer 和 slow pointer 必會相等

	class Solution {
	public:
	bool hasCycle(ListNode *head) {
	ListNode *fast = head;
	ListNode *slow = head;

	while (fast && slow) {
	fast = fast->next;
	if (!fast) {
	return false;
	}
	fast = fast->next;
	slow = slow->next;

	if (fast == slow) {
	return true;
	}
	}

	return false;
	}
	};

# Implement Queue using Stacks

題目： https://leetcode.com/problems/implement-queue-using-stacks/
難度： Easy
語言： C++17
技巧： stack

開一個 stack，存放資料

push () - 直接 push 到這個 stack 裡面就行了
pop () - 開一個 tmp stack
- 將原本的 stack 的資料一個一個 pop 出來然後 push 進 tmp stack，然後返回 tmp stack 的 top element
- 記得再把 tmp stack 的東西倒回原本的 stack

	class MyQueue {
	public:
	MyQueue() : stack_() {}

	void push(int x) {
	stack_.emplace(x);
	}

	int pop() {
	stack<int> tmp_stack;
	while (stack_.size()) {
	tmp_stack.emplace(stack_.top());
	stack_.pop();
	}

	int ret = tmp_stack.top();
	tmp_stack.pop();
	while (tmp_stack.size()) {
	stack_.emplace(tmp_stack.top());
	tmp_stack.pop();
	}

	return ret;
	}

	int peek() {
	stack<int> tmp_stack;
	while (stack_.size()) {
	tmp_stack.emplace(stack_.top());
	stack_.pop();
	}

	int ret = tmp_stack.top();
	while (tmp_stack.size()) {
	stack_.emplace(tmp_stack.top());
	tmp_stack.pop();
	}

	return ret;
	}

	bool empty() {
	return stack_.empty();
	}

	private:
	stack<int> stack_;
	};

	/**
	* Your MyQueue object will be instantiated and called as such:
	* MyQueue* obj = new MyQueue();
	* obj->push(x);
	* int param_2 = obj->pop();
	* int param_3 = obj->peek();
	* bool param_4 = obj->empty();
	*/

# Week 2 (12/12)

# First Bad Version

題目： https://leetcode.com/problems/first-bad-version/
難度： Easy
語言： C++17
技巧： binary search

	// The API isBadVersion is defined for you.
	// bool isBadVersion(int version);

	class Solution {
	public:
	int firstBadVersion(int n) {
	int l = 0;
	int r = n;
	int m;

	while (l <= r) {
	m = l + (r - l) / 2;
	if (isBadVersion(m)) {
	r = m - 1;
	} else {
	l = m + 1;
	}
	}

	return l;
	}
	};

# Ransom Note

題目： https://leetcode.com/problems/ransom-note/
難度： Easy
語言： C++17
技巧： unordered_map

問你 magazine 裡面的字母是否為 ransomNote 的 superset, 必須考量字母頻率。

	class Solution {
	public:
	bool canConstruct(const string &ransomNote, const string &magazine) {
	unordered_map<char, int> char_freqs;
	for (const auto c : magazine) {
	char_freqs[c]++;
	}

	for (const auto c : ransomNote) {
	auto it = char_freqs.find(c);
	if (it == char_freqs.end()) {
	return false;
	}

	it->second--;
	if (it->second == 0) {
	char_freqs.erase(it);
	}
	}

	return true;
	}
	};

# Climbing Stairs

題目： https://leetcode.com/problems/climbing-stairs/
難度： Easy
語言： C++17
技巧： dynamic programming bottom up

	class Solution {
	public:
	int climbStairs(int n) {
	uint64_t dp[50] = {0, 1, 2};
	for (int i = 3; i < 50; i++) {
	dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
	}
	};

# Longest Palindrome

題目： https://leetcode.com/problems/longest-palindrome/
難度： Easy
語言： C++17
技巧： unordered_map

	class Solution {
	public:
	int longestPalindrome(const string &s) {
	unordered_map<char, int> char_freqs;
	for (const auto c : s) {
	char_freqs[c]++;
	}

	int len = std::any_of(char_freqs.begin(),
	char_freqs.end(),
	[](const pair<char, int> &entry) {
	return entry.second % 2 == 1;
	});
	for (const auto &[c, f] : char_freqs) {
	len += 2 * (f / 2);
	}
	return len;
	}
	};

# Reverse Linked List

題目： https://leetcode.com/problems/reverse-linked-list/
難度： Easy
語言： C++17
技巧： linked list

Iterative solution
- https://www.youtube.com/watch?v=W1BLGgWZhK8
Recursive solution
- 將自己下一個 node 指向自己
- 回傳 new head! 回傳 new head! 回傳 new head!

	class Solution {
	public:
	ListNode reverseList(ListNode head) {
	return reverseListRecursively(head);
	}

	private:
	ListNode reverseListIteratively(ListNode head) {
	if (!head) {
	return nullptr;
	}

	ListNode *new_head = nullptr;
	ListNode *next = nullptr;

	while (head) {
	next = head->next;
	head->next = new_head;
	new_head = head;
	head = next;
	}

	return new_head;
	}

	ListNode reverseListRecursively(ListNode head) {
	if (!head \|\| !head->next) {
	return head;
	}

	ListNode *new_head = reverseListRecursively(head->next);
	head->next->next = head;
	head->next = nullptr;
	return new_head;
	}
	};

# Majority Element

題目： https://leetcode.com/problems/majority-element/
難度： Easy
語言： C++17
技巧： sorting

給你一串 unsorted 的數字，並且裡面有某個數字的出現頻率必定超過總數的一半，請找出該數字為何。

	// -------
	// odd: {0, 1, 2, 3, 4} => 5 / 2 = 2
	// -------
	// -------
	// even: {0, 1, 2, 3} => 4 / 2 = 2
	// -------
	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	std::sort(nums.begin(), nums.end());
	return nums[nums.size() / 2];
	}
	};

# Diameter of Binary Tree

題目： https://leetcode.com/problems/diameter-of-binary-tree/
難度： Easy
語言： C++17
技巧： binary tree dfs

	class Solution {
	public:
	int diameterOfBinaryTree(TreeNode *root) {
	getDepth(root);
	return max_diameter_;
	}

	private:
	int getDepth(TreeNode *node) {
	if (!node) {
	return 0;
	}

	int l_depth = getDepth(node->left);
	int r_depth = getDepth(node->right);
	int current_depth = std::max(l_depth, r_depth) + 1;

	int diameter = l_depth + r_depth;
	max_diameter_ = std::max(max_diameter_, diameter);

	return current_depth;
	}

	int max_diameter_ = 0;
	};

# Add Binary

題目： https://leetcode.com/problems/add-binary/
難度： Easy
語言： C++17
技巧： string bit manipulation

	class Solution {
	public:
	string addBinary(string a, string b) {
	bool carry = false;
	int digit = 0;
	int i = 0;
	int j = 0;
	string result;

	std::reverse(a.begin(), a.end());
	std::reverse(b.begin(), b.end());

	while (i < a.size() \|\| j < b.size() \|\| carry) {
	digit = carry;
	if (i < a.size()) {
	digit += a[i] - '0';
	i++;
	}
	if (j < b.size()) {
	digit += b[j] - '0';
	j++;
	}
	result.push_back('0' + digit % 2);
	carry = digit > 1;
	}

	std::reverse(result.begin(), result.end());
	return result;
	}
	};

# Middle of the Linked List

題目： https://leetcode.com/problems/middle-of-the-linked-list/
難度： Easy
語言： C++17
技巧： linked list two pointers

快慢指標，走完 slow 就是答案。

有個 edge case 要特別注意，就是當 list size 為奇數時，快指標走到最後一個節點就要提早 break loop 了。

面試時可以自己簡單拿 odd & even size 的兩條 linked lists 自己驗證一下，就不會漏掉這個 case 了。

	class Solution {
	public:
	ListNode middleNode(ListNode head) {
	ListNode *fast = head;
	ListNode *slow = head;

	while (fast && slow && fast->next) {
	fast = fast->next;
	if (fast) {
	fast = fast->next;
	}
	slow = slow->next;
	}

	return slow;
	}
	};

# Maximum Depth of Binary Tree

題目： https://leetcode.com/problems/maximum-depth-of-binary-tree/
難度： Easy
語言： C++17
技巧： binary tree dfs

	class Solution {
	public:
	int maxDepth(TreeNode *root) {
	getDepth(root);
	return max_depth_;
	}

	private:
	int getDepth(TreeNode *node) {
	if (!node) {
	return 0;
	}

	int l_depth = getDepth(node->left);
	int r_depth = getDepth(node->right);
	int current_depth = std::max(l_depth, r_depth) + 1;
	max_depth_ = std::max(max_depth_, current_depth);
	return current_depth;
	}

	int max_depth_ = 0;
	};

# Contains Duplicate

題目： https://leetcode.com/problems/contains-duplicate/
難度： Easy
語言： C++17
技巧： unordered_set

	class Solution {
	public:
	bool containsDuplicate(const vector<int> &nums) {
	unordered_set<int> appeared;

	for (const auto n : nums) {
	if (appeared.find(n) != appeared.end()) {
	return true;
	}
	appeared.emplace(n);
	}

	return false;
	}
	};

# Maximum Subarray

題目： https://leetcode.com/problems/maximum-subarray/
難度： Medium
語言： C++17
技巧： array dynamic programming kadane

https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d

	class Solution {
	public:
	int maxSubArray(const vector<int> &nums) {
	int global_max = std::numeric_limits<int>::lowest();
	int local_max = 0;

	for (const auto n : nums) {
	local_max = std::max(n, local_max + n);
	global_max = std::max(global_max, local_max);
	}
	return global_max;
	}
	};

# Week 3 (8/8)

# Insert Interval

題目： https://leetcode.com/problems/insert-interval/
難度： Medium
語言： C++17
技巧： array interval

暴力解：
- 將 new_interval append 到 intervals 並根據左界進行 ascending sort
- 將此問題 reduce 成 Merge Intervals（見 Week 5 的 Merge Intervals）
比較有效率的解法：
- 從頭掃描 intervals
  - 若與 new_interval 無 overlapped，直接 append 到 ret
  - 若與 new_interval 有 overlapped，確認目前掃描到的 interval 與 new_interval 融合後的左右界
- 將 new_interval append 到 ret
- 從剛剛掃描暫停的地方繼續，往後掃完 intervals 剩餘的部分
  - 因為不確定 new_interval 所橫跨的範圍多大，故此部分的邏輯同 Merge Intervals 的解法

	class Solution {
	public:
	vector<vector<int>> insert(vector<vector<int>> &intervals,
	vector<int> &new_interval) {
	vector<vector<int>> ret;
	int i = 0;

	for (; i < intervals.size(); i++) {
	const auto &interval = intervals[i];
	if (new_interval[0] <= interval[1]) { // overlapped
	new_interval[0] = std::min(new_interval[0], interval[0]);
	break;
	}
	ret.emplace_back(interval);
	}

	ret.emplace_back(new_interval);

	for (; i < intervals.size(); i++) {
	const auto &interval = intervals[i];
	if (ret.back()[1] < interval[0]) { // not overlapped
	ret.emplace_back(interval);
	} else { // overlapped
	ret.back()[1] = std::max(ret.back()[1], interval[1]);
	}
	}

	return ret;
	}
	};

# 01 Matrix

題目： https://leetcode.com/problems/01-matrix/
難度： Medium
語言： C++17
技巧： matrix multi-source bfs

解法一：對 mat 中每個 1 做 BFS，找到最近的 0 的距離後填入 ret 中 => TLE
解法二：從 mat 中所有 0 同時做 BFS，平行擴散。第一個到達 1 者，當下的 dist 就是該點和它最近的 0 的距離。

	// 解法一 (TLE)
	class Solution {
	public:
	vector<vector<int>> updateMatrix(const vector<vector<int>> &mat) {
	const int m = mat.size();
	const int n = mat[0].size();

	vector<vector<int>> ret(m, vector<int>(n, 0));
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	ret[i][j] = bfs(mat, m, n, i, j);
	}
	}
	return ret;
	}

	private:
	int bfs(const vector<vector<int>> &mat,
	const int m,
	const int n,
	const int sr,
	const int sc) {
	if (mat[sr][sc] == 0) {
	return 0;
	}

	vector<vector<bool>> visited(m);
	for (auto &row : visited) {
	row = vector<bool>(n, false);
	}

	int dist = 0;
	queue<pair<int, int>> q;
	q.emplace(sr, sc);
	while (q.size()) {
	int len = q.size();
	for (int i = 0; i < len; i++) {
	const auto [r, c] = q.front();
	q.pop();

	if (mat[r][c] == 0) {
	return dist;
	}
	visited[r][c] = true;

	if (r - 1 >= 0 && !visited[r - 1][c]) {
	q.emplace(r - 1, c);
	}
	if (r + 1 < mat.size() && !visited[r + 1][c]) {
	q.emplace(r + 1, c);
	}
	if (c - 1 >= 0 && !visited[r][c - 1]) {
	q.emplace(r, c - 1);
	}
	if (c + 1 < mat[0].size() && !visited[r][c + 1]) {
	q.emplace(r, c + 1);
	}
	}
	dist++;
	}

	return -1; // shouldn't have reached here.
	}
	};

	// 解法二 (AC)
	class Solution {
	public:
	vector<vector<int>> updateMatrix(const vector<vector<int>> &mat) {
	const int uninitialized = std::numeric_limits<int>::max();
	const int m = mat.size();
	const int n = mat[0].size();

	vector<vector<int>> ret(m, vector<int>(n, 0));
	queue<pair<int, int>> q;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (mat[i][j] == 0) {
	ret[i][j] = 0;
	q.emplace(i, j);
	} else {
	ret[i][j] = uninitialized;
	}
	}
	}

	int dist = 0;
	while (q.size()) {
	int len = q.size();
	for (int i = 0; i < len; i++) {
	const auto [r, c] = q.front();
	q.pop();

	ret[r][c] = dist;

	if (r - 1 >= 0 && ret[r - 1][c] == uninitialized) {
	ret[r - 1][c] = dist + 1;
	q.emplace(r - 1, c);
	}
	if (r + 1 < m && ret[r + 1][c] == uninitialized) {
	ret[r + 1][c] = dist + 1;
	q.emplace(r + 1, c);
	}
	if (c - 1 >= 0 && ret[r][c - 1] == uninitialized) {
	ret[r][c - 1] = dist + 1;
	q.emplace(r, c - 1);
	}
	if (c + 1 < n && ret[r][c + 1] == uninitialized) {
	ret[r][c + 1] = dist + 1;
	q.emplace(r, c + 1);
	}
	}
	dist++;
	}

	return ret;
	}
	};

# K Closest Points to Origin

題目： https://leetcode.com/problems/k-closest-points-to-origin/
難度： Medium
語言： C++17
技巧： sorting max heap

解法一：計算各點和 (0, 0) 的歐式距離後以之進行升冪排序，取前 k 個點回傳。
解法二：使用 max heap
- 各個點進入 priority queue 的時候，自動按歐式距離降冪排序
- priority queue size 大於 k 的時候，front 會是歐式距離最大的點，將它 pop 掉，讓 size 維持在 <= k
解法三：使用 min heap
- 各個點進入 priority queue 的時候，自動按歐式距離升冪排序
- 最後 pop k 次，放入 ret 中並回傳之。

	class Solution {
	public:
	vector<vector<int>> kClosest(vector<vector<int>> &points, int k) {
	return kClosestMaxHeap(points, k);
	}

	private:
	vector<vector<int>> kClosestSorting(vector<vector<int>> &points, int k) {
	std::sort(points.begin(),
	points.end(),
	[](const vector<int> &p1, const vector<int> &p2) {
	return std::hypotf(p1[0], p1[1]) < std::hypotf(p2[0], p2[1]);
	});

	return vector(points.begin(), points.begin() + k);
	}

	vector<vector<int>> kClosestMaxHeap(vector<vector<int>> &points, int k) {
	priority_queue<pair<float, int>> pq;
	for (int i = 0; i < points.size(); i++) {
	const auto &point = points[i];
	pq.emplace(std::hypotf(point[0], point[1]), i);
	if (pq.size() > k) {
	pq.pop();
	}
	}

	vector<vector<int>> ret;
	ret.reserve(k);
	while (pq.size()) {
	ret.emplace_back(points[pq.top().second]);
	pq.pop();
	}
	return ret;
	}

	vector<vector<int>> kClosestMinHeap(vector<vector<int>> &points, int k) {
	// pair<float, int> => pair<distance, points_idx>
	// * sorted by distance in asc order => greater
	// * sorted by distance in desc order => less
	using T = pair<float, int>;
	priority_queue<T, vector<T>, greater<T>> pq;
	for (int i = 0; i < points.size(); i++) {
	const auto &point = points[i];
	pq.emplace(std::hypotf(point[0], point[1]), i);
	}

	vector<vector<int>> ret(k);
	for (int i = 0; i < k; i++) {
	ret[i] = points[pq.top().second];
	pq.pop();
	}
	return ret;
	}
	};

# Longest Substring Without Repeating Characters

題目： https://leetcode.com/problems/longest-substring-without-repeating-characters/
難度： Medium
語言： C++17
技巧： string sliding window two pointers

Bruteforce
- 選一個 begin
  - 選一個 end
    - 掃描 [begin, end] 內的字元是否有重複
- O(N^3)
Sliding Window
- 準備一個 map
  - key：s 中出現過的字元
  - value：該字元最後一次出現的 index
- l 與 r 分別代表 window 左右界
  - 規則：window 中不可出現重複字元
- 不斷擴張 window 右界，同時檢查此次擴張是否會使 window 變得不合法
  - 若合法，繼續擴張
  - 不合法，必須讓它再次合法
- 對於每個字元 c ∈ s，我們讓
  - 若 c 已經在目前的 window 內（即：l ≤ i ≤ r）
    - 則目前 window 已無效，故更新 l 為最後出現的 idx + 1 使得 window 再次合法
  - 用 max() 更新 max_len ，最後回傳之
  - 將 c 的最後出現 index（即： r ）記下來
- O(N)

	class Solution {
	public:
	int lengthOfLongestSubstring(const string &s) {
	unordered_map<char, int> last_appeared_idx;
	int max_len = 0;

	for (int l = 0, r = 0; r < s.size(); r++) {
	// If this character has already appeared before,
	// and if it's within the current window...
	auto it = last_appeared_idx.find(s[r]);
	if (it != last_appeared_idx.end() && it->second >= l) {
	l = it->second + 1;
	}

	last_appeared_idx[s[r]] = r;
	max_len = std::max(max_len, r - l + 1);
	}

	return max_len;
	}
	};

# 3Sum

題目： https://leetcode.com/problems/3sum/
難度： Medium
語言： C++17
技巧： array sorting two pointers

暴力解
- 三層 for loop, 太蛋疼了，和單戀一樣痛苦，別浪費時間去想了
- O(N^3)
Two Pointers
- 和 Two sum 不同之處在於，Two sum 要我們回傳 index, 但這題要回傳 value
  - 因此，Two sum 不能排序測資，但 Three sum 可以
- 兩層 for loop
  - 外層 for loop 固定一個數字
  - 對該數字右邊的部分，用 Two pointers 做類似 binary search 的事情
    - 如果 nums[i] + nums[l] + nums[r] == 0 , 記錄下來， l++; r--
    - 如果 nums[i] + nums[l] + nums[r] < 0 , 代表需要大一點的數字， l++
    - 如果 nums[i] + nums[l] + nums[r] > 0 , 代表需要小一點的數字， r++

	class Solution {
	public:
	vector<vector<int>> threeSum(vector<int> &nums) {
	const int n = nums.size();
	set<vector<int>> triplets;

	std::sort(nums.begin(), nums.end());
	for (int i = 0; i < n; i++) {
	int l = i + 1;
	int r = n - 1;
	int sum;
	if (l >= n \|\| r >= n) {
	continue;
	}
	while (l < r) {
	sum = nums[i] + nums[l] + nums[r];
	if (sum == 0) {
	triplets.insert({nums[i], nums[l], nums[r]});
	l++;
	r--;
	} else if (sum < 0) {
	l++;
	} else { // sum > 0
	r--;
	}
	}
	}

	return vector(triplets.begin(), triplets.end());
	}
	};

# Binary Tree Level Order Traversal

題目： https://leetcode.com/problems/binary-tree-level-order-traversal/
難度： Medium
語言： C++17
技巧： binary tree single-source bfs

	class Solution {
	public:
	vector<vector<int>> levelOrder(TreeNode *root) {
	if (!root) {
	return {};
	}

	vector<vector<int>> ret;
	queue<TreeNode *> q;

	q.emplace(root);
	while (q.size()) {
	ret.push_back({});

	int len = q.size();
	for (int i = 0; i < len; i++) {
	TreeNode *curr = q.front();
	q.pop();
	ret.back().emplace_back(curr->val);

	if (curr->left) {
	q.emplace(curr->left);
	}
	if (curr->right) {
	q.emplace(curr->right);
	}
	}
	}

	return ret;
	}
	};

# Clone Graph

題目： https://leetcode.com/problems/clone-graph/
難度： Medium
語言： C++17
技巧： graph dfs unordered_map

開一個 unordered_map 紀錄 old node -> new node 的映射關係。

	class Solution {
	public:
	Node cloneGraph(Node node) {
	if (!node) {
	return nullptr;
	}

	if (auto it = old_to_new_.find(node); it != old_to_new_.end()) {
	return it->second;
	}

	auto cloned_node = new Node(node->val);
	cloned_node->neighbors.reserve(node->neighbors.size());
	old_to_new_.emplace(node, cloned_node);

	for (const auto neighbor : node->neighbors) {
	auto cloned_neighbor = cloneGraph(neighbor);
	cloned_node->neighbors.emplace_back(cloned_neighbor);
	}

	return cloned_node;
	}

	private:
	unordered_map<Node , Node > old_to_new_;
	};

# Evaluate Reverse Polish Notation

題目： https://leetcode.com/problems/evaluate-reverse-polish-notation/
難度： Medium
語言： C++17
技巧： stack

開一個 stack，正向掃 tokens

遇到 operand 就 push to stack
遇到 operator 就 pop from stack 兩次，運算完將結果再次 push to stack
最後答案會在 stack top

	class Solution {
	public:
	int evalRPN(const vector<string> &tokens) {
	stack<int> st;

	for (const auto &token : tokens) {
	if (!isOperator(token)) {
	st.emplace(std::atoi(token.c_str()));
	continue;
	}

	int operand2 = st.top();
	st.pop();
	int operand1 = st.top();
	st.pop();
	st.emplace(eval(token[0], operand1, operand2));
	}

	return st.top();
	}

	private:
	bool isOperator(const string &token) {
	return token == "+" \|\| token == "-" \|\| token == "*" \|\| token == "/";
	}

	int eval(const char op, const int operand1, const int operand2) {
	switch (op) {
	case '+':
	return operand1 + operand2;
	case '-':
	return operand1 - operand2;
	case '*':
	return operand1 * operand2;
	case '/':
	return operand1 / operand2;
	default:
	return 0;
	}
	}
	};

# Week 4 (8/8)

# Course Schedule

題目： https://leetcode.com/problems/course-schedule/
難度： Medium
語言： C++17
技巧： digraph single-source bfs

使用 single-source BFS 檢查 directed graph 是否有 cyclic path

每個有 outgoing edge 的 node 都檢查
只要 BFS 會走回自己，就有 cyclic path

	class Solution {
	using AdjacencyList = vector<vector<int>>;
	using Digraph = AdjacencyList;

	public:
	bool canFinish(const int n, const vector<vector<int>> &prerequisites) {
	if (prerequisites.empty()) {
	return true;
	}

	Digraph digraph = buildDigraph(n, prerequisites);
	for (int i = 0; i < n; i++) {
	if (hasCyclicPath(digraph, i)) {
	return false;
	}
	}
	return true;
	}

	private:
	Digraph buildDigraph(const int n, const vector<vector<int>> &edges) {
	Digraph digraph(n);
	for (const auto &edge : edges) {
	const int src = edge[0];
	const int dst = edge[1];
	digraph[src].emplace_back(dst);
	}
	return digraph;
	}

	bool hasCyclicPath(const Digraph &digraph, const int src) {
	vector<bool> visited(digraph.size(), false);
	queue<int> q;

	q.emplace(src);
	while (q.size()) {
	int len = q.size();
	for (int i = 0; i < len; i++) {
	const auto node = q.front();
	q.pop();

	for (int j = 0; j < digraph[node].size(); j++) {
	const auto neighbor = digraph[node][j];
	if (neighbor == src) {
	return true;
	}
	if (!visited[neighbor]) {
	q.emplace(neighbor);
	}
	visited[neighbor] = true;
	}
	}
	}
	return false;
	}
	};

# Implement Trie (Prefix Tree)

題目： https://leetcode.com/problems/implement-trie-prefix-tree/
難度： Medium
語言： C++17
技巧： trie

Trie::search() 記得檢查 end of word mark, Trie::startsWith() 不需要。
經過實測， Trie::Node::children 用 vector/list 去做是最快的，用 map/unordered_map 反而慢了。

	class Trie {
	private:
	struct Node {
	char val;
	map<char, Node> children;
	bool end_of_word;
	};

	public:
	Trie() : root_() {}

	void insert(const string &word) {
	Node *curr = &root_;
	for (const auto c : word) {
	Node new_node = {c, {}, false};
	const auto [it, _] = curr->children.emplace(c, std::move(new_node));
	curr = &it->second;
	}
	curr->end_of_word = true;
	}

	bool search(const string &word) {
	Node *node = walk(word);
	return node ? node->end_of_word : false;
	}

	bool startsWith(const string &prefix) {
	return walk(prefix);
	}

	private:
	Node *walk(const string &s) {
	Node *curr = &root_;
	for (const auto c : s) {
	auto it = curr->children.find(c);
	if (it != curr->children.end()) {
	curr = &it->second;
	continue;
	}
	return nullptr;
	}
	return curr;
	}

	Node root_;
	};

	/**
	* Your Trie object will be instantiated and called as such:
	* Trie* obj = new Trie();
	* obj->insert(word);
	* bool param_2 = obj->search(word);
	* bool param_3 = obj->startsWith(prefix);
	*/

# Coin Change

題目： https://leetcode.com/problems/coin-change/
難度： Medium
語言： C++17
技巧： dynamic programming

DP
- bottom up 建表
- dp[0] 代表 0 元只能用 0 個硬幣湊出來（相當合理）
- dp[i] = min(dp[i], dp[i - coin] + 1) 為狀態轉移方程
  - 如果我們要湊出金額 i，那麼我們可以從 i - coin 的金額狀態湊出來，再加上一個面值為 coin 的硬幣，即可湊出金額 i
  - 因此 dp [i] 的值應該是在所有可能的 i - coin 狀態中取最小值加 1。

	class Solution {
	public:
	int coinChange(const vector<int> &coins, const int amount) {
	constexpr int kMax = 10005;
	vector<int> dp(kMax, amount + 1);
	dp[0] = 0;

	for (const auto coin : coins) {
	for (int i = coin; i < kMax; i++) {
	dp[i] = std::min(dp[i], dp[i - coin] + 1);
	}
	}
	return dp[amount] == amount + 1 ? -1 : dp[amount];
	}
	};

# Product of Array Except Self

題目： https://leetcode.com/problems/product-of-array-except-self/
難度： Medium
語言： C++17
技巧： array dynamic programming

Bruteforce
- 選定第 i 個元素，計算其 product of array except self
- 從頭到尾掃一次，遇到自己就跳過
- O(N^2)
一維 DP
- 準備兩個 vector
  - l_prod ：自己以左（不含自己）所有元素的積，如：[1, 1, 2, 6]，從左到右建
  - r_prod ：自己以右（不含自己）所有元素的積，如：[24, 12, 4, 1]，從右到左建
- 將 l_prod 與 r_prod 相同 index 的元素乘起來就是答案
- O(N)

	class Solution {
	public:
	vector<int> productExceptSelf(const vector<int>& nums) {
	const size_t n = nums.size();

	vector<int> l_prod(n, 1);
	for (int i = 1; i < n; i++) {
	l_prod[i] = l_prod[i - 1] * nums[i - 1];
	}

	vector<int> r_prod(n, 1);
	r_prod[n - 1] = 1;
	for (int i = n - 2; i >= 0; i--) {
	r_prod[i] = r_prod[i + 1] * nums[i + 1];
	}

	vector<int> ret(n);
	for (int i = 0; i < n; i++) {
	ret[i] = l_prod[i] * r_prod[i];
	}
	return ret;
	}
	};

# Min Stack

題目： https://leetcode.com/problems/min-stack/
難度： Medium
語言： C++17
技巧： stack design

讓 current value 與 current min 同進退。

	class MinStack {
	public:
	MinStack() : stack_() {}

	void push(int val) {
	if (stack_.empty()) {
	stack_.emplace(val, val);
	} else {
	stack_.emplace(val, std::min(val, stack_.top().second));
	}
	}

	void pop() {
	stack_.pop();
	}

	int top() {
	return stack_.top().first;
	}

	int getMin() {
	return stack_.top().second;
	}

	private:
	stack<pair<int, int>> stack_;
	};

	/**
	* Your MinStack object will be instantiated and called as such:
	* MinStack* obj = new MinStack();
	* obj->push(val);
	* obj->pop();
	* int param_3 = obj->top();
	* int param_4 = obj->getMin();
	*/

# Validate Binary Search Tree

題目： https://leetcode.com/problems/validate-binary-search-tree/
難度： Medium
語言： C++17
技巧： binary search tree

誤區：不能單純檢查每個 node 的關係是否為 node->left->val < node->val < node->right->val
正解：遞迴檢查 node->val 是否介於 lowerbound 與 upperbound 之間
- 往左 subtree 走時，lowerbound 不變，upperbound 改為自己 (node->val)
- 往右 subtree 走時，lowerbound 改為自己 (node->val)，upperbound 不變
https://www.youtube.com/watch?v=s6ATEkipzow

	class Solution {
	public:
	bool isValidBST(TreeNode *root) {
	return isValidBSTImpl(root,
	std::numeric_limits<int64_t>::min(),
	std::numeric_limits<int64_t>::max());
	}

	private:
	bool isValidBSTImpl(TreeNode *node, const int64_t lowerbound, const int64_t upperbound) {
	if (!node) {
	return true;
	}

	if (node->val <= lowerbound \|\| node->val >= upperbound) {
	return false;
	}

	return isValidBSTImpl(node->left, lowerbound, node->val) &&
	isValidBSTImpl(node->right, node->val, upperbound);
	}
	};

# Number of Islands

題目： https://leetcode.com/problems/number-of-islands/
難度： Medium
語言： C++17
技巧： matrix single-source bfs

兩層 for loop 掃 matrix, 遇到 1 就用單點 BFS 進行擴散，將上下左右走到的 1 都填成 0
每填完一組，就算是探索完一個 island

	class Solution {
	public:
	int numIslands(vector<vector<char>> &grid) {
	const int m = grid.size();
	const int n = grid[0].size();

	int ret = 0;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (grid[i][j] == '1') {
	bfs(grid, i, j);
	ret++;
	}
	}
	}
	return ret;
	}

	private:
	void bfs(vector<vector<char>> &grid, const int sr, const int sc) {
	const int m = grid.size();
	const int n = grid[0].size();
	queue<pair<int, int>> q;

	q.emplace(sr, sc);
	while (q.size()) {
	int len = q.size();
	for (int i = 0; i < len; i++) {
	auto [r, c] = q.front();
	q.pop();

	grid[r][c] = '0';

	if (r - 1 >= 0 && grid[r - 1][c] == '1') {
	grid[r - 1][c] = '0';
	q.emplace(r - 1, c);
	}
	if (r + 1 < m && grid[r + 1][c] == '1') {
	grid[r + 1][c] = '0';
	q.emplace(r + 1, c);
	}
	if (c - 1 >= 0 && grid[r][c - 1] == '1') {
	grid[r][c - 1] = '0';
	q.emplace(r, c - 1);
	}
	if (c + 1 < n && grid[r][c + 1] == '1') {
	grid[r][c + 1] = '0';
	q.emplace(r, c + 1);
	}
	}
	}
	}
	};

# Rotting Oranges

題目： https://leetcode.com/problems/rotting-oranges/
難度： Medium
語言： C++17
技巧： matrix multi-source bfs

將所有 rotten oranges 的 (row, col) 全部 push 到 queue 裡面，然後開始做 BFS
- 每做一輪 BFS， min += 1
有一些雞巴測資
- 如果 BFS 完還有任何 normal orange，回傳 -1
- 如果一開始就完全沒有任何 rotten orange，回傳 0
- 其餘情況回傳 BFS 後累積的 min

	class Solution {
	public:
	int orangesRotting(vector<vector<int>> &grid) {
	const int m = grid.size();
	const int n = grid[0].size();
	queue<pair<int, int>> q;

	bool has_rotten_oranges = false;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (grid[i][j] == 2) {
	q.emplace(i, j);
	has_rotten_oranges = true;
	}
	}
	}

	int min = -1;
	while (q.size()) {
	int len = q.size();
	for (int i = 0; i < len; i++) {
	auto [r, c] = q.front();
	q.pop();

	grid[r][c] = 2;

	if (r - 1 >= 0 && grid[r - 1][c] == 1) {
	grid[r - 1][c] = 2;
	q.emplace(r - 1, c);
	}
	if (r + 1 < m && grid[r + 1][c] == 1) {
	grid[r + 1][c] = 2;
	q.emplace(r + 1, c);
	}
	if (c - 1 >= 0 && grid[r][c - 1] == 1) {
	grid[r][c - 1] = 2;
	q.emplace(r, c - 1);
	}
	if (c + 1 < n && grid[r][c + 1] == 1) {
	grid[r][c + 1] = 2;
	q.emplace(r, c + 1);
	}
	}
	min++;
	}

	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (grid[i][j] == 1) {
	return -1;
	}
	}
	}

	if (!has_rotten_oranges) {
	return 0;
	}

	return min;
	}
	};

# Week 5 (8/8)

# Search in Rotated Sorted Array

題目： https://leetcode.com/problems/search-in-rotated-sorted-array/
難度： Medium
語言： C++17
技巧： array binary search

先使用 binary search 定位到 pivot point
- 如果 nums [m] 比前一個數字大，代表 m 就是 pivot
- 如果 nums [m] 比下一個數字大，代表 m + 1 是 pivot
- https://www.youtube.com/watch?v=MRMOJSGWnYU
找到 pivot point 之後
- 左半部： nums[0:pivot] 為 sorted
- 右半部： nums[pivot:] 為 sorted
接著判斷 target 會落於左半部還是右半部，對該半部繼續進行 binary search

	class Solution {
	public:
	int search(const vector<int> &nums, const int target) {
	int l = 0;
	int r = nums.size() - 1;
	int m = 0;
	int pivot = 0;

	while (l < r) {
	m = l + (r - l) / 2;

	if (nums[m] == target) {
	return m;
	}

	if (m - 1 >= 0 && nums[m] < nums[m - 1]) {
	pivot = m;
	break;
	} else if (m + 1 < nums.size() && nums[m] > nums[m + 1]) {
	pivot = m + 1;
	break;
	}

	if (nums[m] < nums.back()) { // the right half is sorted
	r = m;
	} else { // the left half is sorted
	l = m;
	}
	}

	if (target >= nums[0] && pivot - 1 >= 0 && target <= nums[pivot - 1]) {
	l = 0;
	r = pivot - 1;
	} else {
	l = pivot;
	r = nums.size() - 1;
	}

	while (l <= r) {
	m = l + (r - l) / 2;
	if (nums[m] == target) {
	return m;
	} else if (nums[m] < target) {
	l = m + 1;
	} else { // nums[m] > target
	r = m - 1;
	}
	}

	return -1;
	}
	};

# Combination Sum

題目： https://leetcode.com/problems/combination-sum/
難度： Medium
語言： C++17
技巧： array backtracking

遞迴，每一個 stage 可以有兩種選擇
- 跳過目前這個數字
- 取現在這個數字 (下一次遞迴進來，還可以重複取這個數字)
每次取了一個數字，就將該數字從 target 扣除，若 target (remainder) 能剛好歸零就加入 ret

	class Solution {
	public:
	vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
	vector<vector<int>> ret;
	vector<int> current;

	combinationSumImpl(candidates, target, 0, current, ret);
	return ret;
	}

	private:
	void combinationSumImpl(vector<int> &candidates,
	int remainder,
	int idx,
	vector<int> &current,
	vector<vector<int>> &ret) {
	if (idx >= candidates.size()) {
	return;
	}

	// Skip candidates[idx], and move on to the next candidate.
	combinationSumImpl(candidates, remainder, idx + 1, current, ret);

	// Take candidates[idx].
	current.emplace_back(candidates[idx]);
	remainder -= candidates[idx];
	if (remainder <= 0) {
	if (remainder == 0) {
	ret.emplace_back(current);
	}
	current.pop_back();
	return;
	}
	combinationSumImpl(candidates, remainder, idx, current, ret);
	current.pop_back();
	}
	};

# Permutations

題目： https://leetcode.com/problems/permutations/
難度： Medium
語言： C++17
技巧： array backtracking

遞迴，每一個 stage 可以選擇還沒加入過 current 的數字
- 怎麼知道還沒加入過 current ? 可以開一個 picked 的 bool vector 來紀錄
- 當 current.size() 等於 nums.size() 時，加入 ret

	class Solution {
	public:
	vector<vector<int>> permute(const vector<int> &nums) {
	vector<vector<int>> ret;
	vector<int> current;
	vector<bool> picked(nums.size(), 0);

	permuteImpl(nums, picked, current, ret);
	return ret;
	}

	private:
	void permuteImpl(const vector<int> &nums,
	vector<bool> &picked,
	vector<int> &current,
	vector<vector<int>> &ret) {
	if (current.size() == nums.size()) {
	ret.emplace_back(current);
	return;
	}

	for (int i = 0; i < nums.size(); i++) {
	if (picked[i]) {
	continue;
	}
	current.emplace_back(nums[i]);
	picked[i] = true;
	permuteImpl(nums, picked, current, ret);
	picked[i] = false;
	current.pop_back();
	}
	}
	};

# Merge Intervals

題目： https://leetcode.com/problems/merge-intervals/
難度： Medium
語言： C++17
技巧： array interval

因為測資會有 unsorted intervals，所以要先對 intervals 根據左界進行 ascending 排序
掃一次 intervals
- 與 last merged interval 無 overlap：就直接 append
- 與 last merged interval 有 overlap：更新右界，看是原本的大，還是新的大

	class Solution {
	public:
	vector<vector<int>> merge(vector<vector<int>> &intervals) {
	std::sort(intervals.begin(),
	intervals.end(),
	[](const auto &i1, const auto &i2) {
	if (i1[0] < i2[0]) return true;
	if (i1[0] > i2[0]) return false;
	if (i1[1] < i2[1]) return true;
	if (i1[1] > i2[1]) return false;
	return false;
	});

	vector<vector<int>> ret;
	for (int i = 0; i < intervals.size(); i++) {
	const auto &interval = intervals[i];
	if (ret.empty() \|\| ret.back()[1] < interval[0]) { // not overlapped
	ret.emplace_back(interval);
	} else { // overlapped
	ret.back()[1] = std::max(ret.back()[1], interval[1]);
	}
	}
	return ret;
	}
	};

# Lowest Common Ancestor of a Binary Tree

題目： https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
難度： Medium
語言： C++17
技巧： binary tree

使用 recursion + backtracking 維護 current path
- 遇到 p 就複製 current path 到 path of p
- 遇到 q 就複製 current path 到 path of q
- 當 path of p 和 path of q 都準備好時，尋找 longest common prefix 中的最後一個 node
使用 recursion
- 找到 p 就回傳 p, 找到 q 就回傳 q, 沒找到就回 nullptr
- 左右 subtree 都 non-null 時，該 node 就是答案
- https://www.youtube.com/watch?v=KobQcxdaZKY

	class Solution {
	public:
	TreeNode* lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode *q) {
	if (!root) {
	return nullptr;
	}

	if (root == p \|\| root == q) {
	return root;
	}

	TreeNode *l = lowestCommonAncestor(root->left, p, q);
	TreeNode *r = lowestCommonAncestor(root->right, p, q);
	if (l && r) {
	return root;
	} else if (l && !r) {
	return l;
	} else if (!l && r) {
	return r;
	} else {
	return nullptr;
	}
	}
	};

# Time Based Key-Value Store

題目： https://leetcode.com/problems/time-based-key-value-store/
難度： Medium
語言： C++17
技巧： hash table binary search

讓各個 key 對應到一棵 rbtree ( std::map )
- rbtree 的 key 為 timestamp, value 為字串
- 對 rbtree 使用 std::map::lower_bound() 做 binary search
upper_bound vs lower_bound:
- upper_bound: return the iterator to the first element which is > value. If not, return end().
- lower_bound: return the iterator to the first element which is ≥ value. If not, return end().
這題要求我們找到 <= timestamp 的 values 當中 timestamp 最大者
- lower_bound + negative timestamp
- ω・´) 鬼腦袋

	class TimeMap {
	public:
	TimeMap() : map_() {}

	void set(const string &key, const string &value, int timestamp) {
	map_[key].emplace(-timestamp, value);
	}

	string get(const string &key, int timestamp) {
	auto it = map_.find(key);
	if (it == map_.end()) {
	return "";
	}

	auto it2 = it->second.lower_bound(-timestamp);
	if (it2 == it->second.end()) {
	return "";
	}

	return it2->second;
	}

	private:
	unordered_map<string, map<int, string>> map_;
	};

# Accounts Merge

題目： https://leetcode.com/problems/accounts-merge/
難度： Medium
語言： C++17
技巧： union find

Union find 概念：https://hackmd.io/@CLKO/rkRVS_o-4?type=view
Union by ranks (tree depth)
建一個 map
- 掃所有 accounts 裡面的 emails，逐步建立 email to account index 的映射關係
- 如果某個 email 已經有 existing mapping，代表它已經屬於其他 account
- 根據題目定義，若兩個 accounts 出現一個以上的 email in common，這兩個 accounts 就要 merge
- 呼叫 uf.Union(existing_idx, idx) 來 merge 兩組 account
剩下的就是準備我們要 return 的 vector 了
- vector<set<string>> merged_emails ，大小初始化為 account.size()
- 掃 uf.parents() ，對於每一個 account index i ，用 uf.Find(i) 找出該組 account 的 root
- 此時假設 merged_emails[i].empty() ，代表該 account 已經被 merged 到其他 account 了
- 因此只要輸出 merged_emails[i].size() > 0 者

	class UnionFind {
	public:
	UnionFind(int size)
	: parents_(size),
	ranks_(size, 1) {
	for (int i = 0; i < size; i++) {
	parents_[i] = i;
	}
	}

	int Find(int x) {
	while (parents_[x] != x) {
	parents_[x] = parents_[parents_[x]];
	x = parents_[x];
	}
	return x;
	}

	bool Union(int x, int y) {
	int px = Find(x);
	int py = Find(y);
	if (px == py) {
	return false;
	}

	if (ranks_[px] < ranks_[py]) {
	parents_[px] = py;
	ranks_[py] = std::max(ranks_[px], ranks_[py]);
	} else {
	parents_[py] = px;
	ranks_[px] = std::max(ranks_[px], ranks_[py]);
	}
	return true;
	}

	const vector<int> &parents() const { return parents_; }

	private:
	vector<int> parents_;
	vector<int> ranks_;
	};

	class Solution {
	public:
	vector<vector<string>> accountsMerge(const vector<vector<string>> &accounts) {
	UnionFind uf(accounts.size());
	unordered_map<string, int> email_to_account_idx;

	for (int i = 0; i < accounts.size(); i++) {
	const auto &account = accounts[i];
	const string &name = account[0];
	for (int j = 1; j < account.size(); j++) {
	const string &email = account[j];
	auto it = email_to_account_idx.find(email);
	if (it != email_to_account_idx.end()) {
	uf.Union(it->second, i);
	}
	email_to_account_idx[email] = uf.Find(i);
	}
	}

	vector<set<string>> merged_emails(accounts.size());
	for (int i = 0; i < uf.parents().size(); i++) {
	int root = uf.Find(uf.parents()[i]);
	for (int j = 1; j < accounts[i].size(); j++) {
	merged_emails[root].emplace(accounts[i][j]);
	}
	}

	vector<vector<string>> ret;
	for (int i = 0; i < accounts.size(); i++) {
	if (merged_emails[i].empty()) {
	continue;
	}
	vector<string> account;
	account.reserve(1 + merged_emails[i].size());
	account.emplace_back(accounts[i][0]);
	account.insert(account.end(), merged_emails[i].begin(), merged_emails[i].end());
	ret.emplace_back(std::move(account));
	}
	return ret;
	}
	};

# Sort Colors

題目： https://leetcode.com/problems/sort-colors/
難度： Medium
語言： C++17
技巧： array

nums 只有 0, 1, 2 三種 element
- 掃一次，計算各個 element 的出現頻率
- 再掃一次，按照 0, 1, 2 的頻率將 nums 填滿
這麼水的題目，也能算 medium 嗎？

	class Solution {
	public:
	void sortColors(vector<int>& nums) {
	int count[3] = {0};
	for (const auto n : nums) {
	count[n]++;
	}

	int i = 0;
	for (int j = 0; j < count[0]; j++) {
	nums[i++] = 0;
	}
	for (int j = 0; j < count[1]; j++) {
	nums[i++] = 1;
	}
	for (int j = 0; j < count[2]; j++) {
	nums[i++] = 2;
	}
	}
	};

# Week 6 (9/9)

# Word Break

題目： https://leetcode.com/problems/word-break/
難度： Medium
語言： C++17
技巧： string dynamic programming

定義 Overlapping Subproblems
- 從 s 的頭，每次都拿 word ∈ word_dict 來匹配的話
- 下一個 subproblem 就是從 s + word.size() 開始是否能從 word ∈ word_dict 再次選一個來匹配？
動態轉移方程
- 我們可以維護一個 bool array dp ，並且令 dp[s.size()] = true
- dp 中每一個 bool 代表從 s[i] 開始是否能選中一個 word ∈ word_dict 來匹配
- dp[i] = dp[i] || dp[i + word.size()]
- 注意：後面的結果不要被前面的覆蓋噢，這就是上面為什麼需要一個 logical or

	class Solution {
	public:
	bool wordBreak(const string &s, const vector<string> &word_dict) {
	vector<bool> dp(s.size() + 1, false);
	dp[s.size()] = true;

	for (int i = s.size() - 1; i >= 0; i--) {
	for (const auto &word : word_dict) {
	if (i + word.size() >= dp.size()) {
	continue;
	}
	string_view sv(s.data() + i, word.size());
	if (sv == word) {
	dp[i] = dp[i] \|\| dp[i + word.size()];
	}
	}
	}

	return dp[0];
	}
	}

# Partition Equal Subset Sum

題目： https://leetcode.com/problems/partition-equal-subset-sum/
難度： Medium
語言： C++17
技巧： array dynamic programming

給你一個 array nums ，請問是否能將它分為兩個 subsets s.t. sum(subset1) == sum(subset2)
- sum(nums) 必須是偶數，如果是奇數必定不行
用 memo 紀錄 subset sum
- memo 一開始只有一個元素，0
- 對於 m ∈ memo
  - 對於 num ∈ nums ，我們可以選擇取 num ( m + num )、不取 ( m )
  - 只要過程中 m + num == target ，就代表中了

	class Solution {
	public:
	bool canPartition(const vector<int> &nums) {
	int sum = std::accumulate(nums.begin(), nums.end(), 0);
	if (sum % 2) {
	return false;
	}

	int target = sum / 2;
	unordered_set<int> memo = {0};
	for (const auto num : nums) {
	unordered_set<int> next_memo(memo);
	for (const auto m : memo) {
	if (m + num == target) {
	return true;
	}
	next_memo.emplace(m + num);
	}
	memo = next_memo;
	}

	return false;
	}
	};

# String to Integer (atoi)

題目： https://leetcode.com/problems/string-to-integer-atoi/
難度： Medium
語言： C++17
技巧： string

Signed integer overflow 檢查可以用移項達成
- ret * 10 > INT_MAX 改成 ret > INT_MAX / 10
- ret * 10 < INT_MIN 改成 ret < IMT_MIN / 10
- ret + x > INT_MAX 改成 ret > INT_MAX - x
- ret - x < INT_MIN 改成 ret < INT_MIN + x

	class Solution {
	public:
	int myAtoi(string s) {
	int i = 0;
	while (s[i] == ' ') {
	i++;
	}

	if (i == s.size()) {
	return 0;
	}

	bool negative;
	if (s[i] == '+') {
	negative = false;
	i++;
	} else if (s[i] == '-') {
	negative = true;
	i++;
	}

	int ret = 0;
	while (i < s.size() && std::isdigit(s[i])) {
	if (ret > std::numeric_limits<int>::max() / 10) {
	return std::numeric_limits<int>::max();
	}
	if (ret < std::numeric_limits<int>::min() / 10) {
	return std::numeric_limits<int>::min();
	}
	ret *= 10;

	int digit = s[i] - '0';
	if (ret > std::numeric_limits<int>::max() - digit) {
	return std::numeric_limits<int>::max();
	}
	if (ret < std::numeric_limits<int>::min() + digit) {
	return std::numeric_limits<int>::min();
	}

	ret += negative ? -digit : digit;
	i++;
	}
	return ret;
	}
	};

# Spiral Matrix

題目： https://leetcode.com/problems/spiral-matrix/
難度： Medium
語言： C++17
技巧： matrix simulation

定義上下左右界的 index，遞迴剝洋蔥
- 還能往右走嗎？
  - 不能，return
  - 可以，走到底
- 往下
- 往左
- 往上

	class Solution {
	public:
	vector<int> spiralOrder(const vector<vector<int>> &matrix) {
	int top = 0;
	int bottom = matrix.size() - 1;
	int left = 0;
	int right = matrix[0].size() - 1;

	vector<int> ret;
	ret.reserve(matrix.size() * matrix[0].size());
	spiralOrderImpl(matrix, top, bottom, left, right, ret);
	return ret;
	}

	private:
	void spiralOrderImpl(const vector<vector<int>> &matrix,
	int top,
	int bottom,
	int left,
	int right,
	vector<int> &out) {
	if (top > bottom \|\| left > right) {
	return;
	}

	int r = top;
	int c = left;

	if (c > right) {
	return;
	}
	while (c <= right) {
	out.emplace_back(matrix[r][c]);
	c++;
	}
	c--;
	r++;

	if (r > bottom) {
	return;
	}
	while (r <= bottom) {
	out.emplace_back(matrix[r][c]);
	r++;
	}
	r--;
	c--;

	if (c < left) {
	return;
	}
	while (c >= left) {
	out.emplace_back(matrix[r][c]);
	c--;
	}
	c++;
	r--;

	if (r < top) {
	return;
	}
	while (r > top) {
	out.emplace_back(matrix[r][c]);
	r--;
	}
	r++;
	c++;

	spiralOrderImpl(matrix, top + 1, bottom - 1, left + 1, right - 1, out);
	}
	};

# Subsets

題目： https://leetcode.com/problems/subsets/
難度： Medium
語言： C++17
技巧： bit manipulation

假設 nums.size() == 3 ，那我們就用 2^0 到 2^3 建 truth table
- 000 (2^0)
- 001
- 010
- 011
- 100
- 101
- 110
- 111 (2^3)
對於上述的每一組 bit representation，0 代表取，1 代表不取
Time: O (N * 2^N) - 每組 subset 長度最多為 N 個 elements, 共 2^N 個 subsets
Space: O (N * 2^N) - 同上

	class Solution {
	public:
	vector<vector<int>> subsets(const vector<int> &nums) {
	const int n = nums.size();
	vector<vector<int>> ret;

	for (int i = 0; i < std::pow(2, n); i++) {
	ret.emplace_back();

	string bits = to_bit_string(n, i);
	for (int j = 0; j < bits.size(); j++) {
	if (bits[j] == '1') {
	ret.back().emplace_back(nums[j]);
	}
	}
	}

	return ret;
	}

	private:
	string to_bit_string(const int max_len, const int val) {
	string ret;
	for (int i = 0; i < max_len; i++) {
	ret += (val & (1 << i)) ? '1' : '0';
	}
	return ret;
	}
	};

# Binary Tree Right Side View

題目： https://leetcode.com/problems/binary-tree-right-side-view/
難度： Medium
語言： C++17
技巧： binary tree bfs

用 binary tree BFS 搜集各個 level 的 values, 最後將每個 level 的 last node val 放到一個 vector 回傳。

	class Solution {
	public:
	vector<int> rightSideView(TreeNode *root) {
	if (!root) {
	return {};
	}

	vector<vector<int>> levels;
	queue<TreeNode *> q;

	q.emplace(root);
	while (q.size()) {
	levels.emplace_back();
	int len = q.size();
	for (int i = 0; i < len; i++) {
	auto node = q.front();
	q.pop();

	levels.back().emplace_back(node->val);

	if (node->left) {
	q.emplace(node->left);
	}
	if (node->right) {
	q.emplace(node->right);
	}
	}
	}

	vector<int> ret(levels.size());
	for (int i = 0; i < ret.size(); i++) {
	ret[i] = levels[i].back();
	}
	return ret;
	}
	};

# Longest Palindromic Substring

題目： https://leetcode.com/problems/longest-palindromic-substring/
難度： Medium
語言： C++17
技巧： string

Expand around center, 分為兩種情況
- palindromic substring 長度為 odd
- palindromic substring 長度為 even
用 string_view 避免 excessive copying

	class Solution {
	public:
	string longestPalindrome(const string &s) {
	string_view ret;

	for (int i = 0; i < s.size(); i++) {
	string_view candidate = expandAroundCenter(s, i, i);
	if (candidate.size() > ret.size()) {
	ret = candidate;
	}
	}

	for (int i = 0; i < s.size() - 1; i++) {
	string_view candidate = expandAroundCenter(s, i, i + 1);
	if (candidate.size() > ret.size()) {
	ret = candidate;
	}
	}

	return string(ret.begin(), ret.end());
	}

	private:
	string_view expandAroundCenter(const string &s, const int src1, const int src2) {
	string_view ret;
	int l = src1;
	int r = src2;

	while (l >= 0 && r < s.size() && s[l] == s[r]) {
	string_view candidate(s.data() + l, r - l + 1);
	if (candidate.size() > ret.size()) {
	ret = candidate;
	}
	l--;
	r++;
	}
	return ret;
	}
	};

# Unique Paths

題目： https://leetcode.com/problems/unique-paths/
難度： Medium
語言： C++17
技巧： matrix dynamic programming

DP
- dp 是一個二維 m x n matrix (m rows, n cols)
  - 每一格代表：從左上角走到該點的總方法數
  - 第一個 row 的所有格子填入 0
  - 第一個 col 的所有格子填入 0
- 每次移動只能往右、往下
  - 也就是說，抵達每個格子的方法數 = 左邊來的方法數 + 上面來的方法數

	class Solution {
	public:
	int uniquePaths(int m, int n) {
	int dp[m][n];
	memset(dp, 0, sizeof(dp));

	for (int i = 0; i < m; i++) {
	dp[i][0] = 1;
	}
	for (int i = 0; i < n; i++) {
	dp[0][i] = 1;
	}

	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
	dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
	}
	}
	return dp[m - 1][n - 1];
	}
	};

# Construct Binary Tree from Preorder and Inorder Traversal

題目： https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
難度： Medium
語言： C++17
技巧： binary tree

preorder 的第一個節點是 root
- 用 root 的值，定位到 inorder root 的 index
inorder root 以左為 left subtree, 以右為 right subtree
- 做出 left subtree 的 preorder & inorder
- 做出 right subtree 的 preorder & inorder
- 遞迴處理

	class Solution {
	public:
	TreeNode *buildTree(const vector<int> &preorder, const vector<int> &inorder) {
	if (preorder.empty()) {
	return nullptr;
	}

	auto root_inorder_it = std::find(inorder.begin(), inorder.end(), preorder.front());
	if (root_inorder_it == inorder.end()) {
	return nullptr;
	}

	TreeNode *root = new TreeNode(preorder.front());

	vector<int> left_subtree_inorder(inorder.begin(), root_inorder_it);
	vector<int> left_subtree_preorder(
	preorder.begin() + 1, preorder.begin() + 1 + left_subtree_inorder.size());
	root->left = buildTree(left_subtree_preorder, left_subtree_inorder);

	vector<int> right_subtree_inorder(root_inorder_it + 1, inorder.end());
	vector<int> right_subtree_preorder(
	preorder.begin() + 1 + left_subtree_preorder.size(), preorder.end());
	root->right = buildTree(right_subtree_preorder, right_subtree_inorder);

	return root;
	}
	};

# Week 7 (7/7)

# Container With Most Water

題目： https://leetcode.com/problems/container-with-most-water/
難度： Medium
語言： C++17
技巧： array two pointers greedy

Greedy: Make the locally optimal choice at each stage.
- two pointers l r , 從最外面開始往內檢查
- 計算當下的面積，必要時更新 max_area
- 比較 height[l] 和 height[r] , 較小者往中間走，嘗試讓它更高

	class Solution {
	public:
	int maxArea(vector<int>& height) {
	int l = 0;
	int r = height.size() - 1;
	int max_area = 0;

	while (l < r) {
	int area = (r - l) * std::min(height[l], height[r]);
	max_area = std::max(max_area, area);

	if (height[l] <= height[r]) {
	l++;
	} else {
	r--;
	}
	}

	return max_area;
	}
	};

# Letter Combinations of a Phone Number

題目： https://leetcode.com/problems/letter-combinations-of-a-phone-number/
難度： Medium
語言： C++17
技巧： backtracking

假設 letterCombinationsImpl() 讀到 ‘2’
- 實際上這個 stage 應該展開為 ‘a’、‘b’、‘c’ 三個 stage

	class Solution {
	public:
	vector<string> letterCombinations(const string &digits) {
	if (digits.empty()) {
	return {};
	}

	vector<string> ret;
	string current;

	letterCombinationsImpl(digits, 0, current, ret);
	return ret;
	}

	private:
	void letterCombinationsImpl(const string &digits,
	int idx,
	string &current,
	vector<string> &ret) {
	if (idx >= digits.size()) {
	ret.emplace_back(current);
	return;
	}

	for (const auto c : letters[digits[idx] - '0']) {
	current.push_back(c);
	letterCombinationsImpl(digits, idx + 1, current, ret);
	current.pop_back();
	}
	}

	static inline string letters[10] = {
	"",
	"",
	"abc",
	"def",
	"ghi",
	"jkl",
	"mno",
	"pqrs",
	"tuv",
	"wxyz"
	};
	};

# Word Search

題目： https://leetcode.com/problems/word-search/
難度： Medium
語言： C++17
技巧： matrix dfs backtracking

記得走過的格子就別再走進去啦！Backtrack 時將目前的格子恢復為可走的狀態。

	class Solution {
	public:
	bool exist(const vector<vector<char>> &board, const string &word) {
	const int m = board.size();
	const int n = board[0].size();

	vector<vector<bool>> visited(m, vector<bool>(n, false));
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (board[i][j] == word[0]) {
	if (existImpl(board, i, j, word, 0, visited)) {
	return true;
	}
	}
	}
	}
	return false;
	}

	private:
	bool existImpl(const vector<vector<char>> &board,
	int row,
	int col,
	const string &word,
	int idx,
	vector<vector<bool>> &visited) {
	if (idx >= word.size()) {
	return true;
	}

	if (row < 0 \|\| row >= board.size() \|\| col < 0 \|\| col >= board[0].size()) {
	return false;
	}

	if (visited[row][col]) {
	return false;
	}

	if (board[row][col] != word[idx]) {
	return false;
	}
	visited[row][col] = true;

	if (existImpl(board, row - 1, col, word, idx + 1, visited)) {
	return true;
	}

	if (existImpl(board, row + 1, col, word, idx + 1, visited)) {
	return true;
	}

	if (existImpl(board, row, col - 1, word, idx + 1, visited)) {
	return true;
	}

	if (existImpl(board, row, col + 1, word, idx + 1, visited)) {
	return true;
	}

	visited[row][col] = false;
	return false;
	}
	};

# Find All Anagrams in a String

題目： https://leetcode.com/problems/find-all-anagrams-in-a-string/
難度： Medium
語言： C++17
技巧： string sliding window two pointers

解法一
- 每次左指標 l 要往右走之前，就將 window_char_freqs[s[l]]-- ，必要時 erase s[l]
- 每一輪直接比較 target_char_freqs 是否等於 window_char_freqs ，是的話就將 l 加入 ret
解法二
- 類似 Minimum window substring (hard) 的解法
- 維護兩個 int: have 、 need
  - 當某個 character 的出現頻率 == target freq 時， have++
  - 當某個 character 的出現頻率從 target freq 往下掉時， have--
  - 當 have == need 時，紀錄當下的 l

	// 解法一 (AC), 50ms (23.23%), 12.8MB (13.80%)
	class Solution {
	public:
	vector<int> findAnagrams(const string &s, const string &p) {
	unordered_map<char, int> target_char_freqs;
	for (const auto c : p) {
	target_char_freqs[c]++;
	}

	int l = 0;
	int r = 0;
	vector<int> ret;
	unordered_map<char, int> window_char_freqs;

	while (r < s.size()) {
	if (target_char_freqs.find(s[r]) != target_char_freqs.end()) {
	window_char_freqs[s[r]]++;
	}

	if (r - l + 1 < p.size()) {
	r++;
	continue;
	}

	if (target_char_freqs == window_char_freqs) {
	ret.emplace_back(l);
	}

	if (--window_char_freqs[s[l]] <= 0) {
	window_char_freqs.erase(s[l]);
	}

	l++;
	r++;
	}

	return ret;
	}
	};

	// 解法二 (AC), 11ms (87.70%), 8.6MB (92.74%)
	class Solution {
	public:
	vector<int> findAnagrams(const string &s, const string &p) {
	unordered_map<char, int> target_char_freqs;
	for (const auto c : p) {
	target_char_freqs[c]++;
	}

	int have = 0;
	int need = target_char_freqs.size();
	vector<int> ret;
	unordered_map<char, int> window_char_freqs;

	for (int l = 0, r = 0; r < s.size(); r++) {
	auto it = target_char_freqs.find(s[r]);
	if (it != target_char_freqs.end()) {
	if (++window_char_freqs[s[r]] == it->second) {
	have++;
	}
	}

	int len = r - l + 1;
	if (len < p.size()) {
	continue;
	}

	if (have == need) {
	ret.emplace_back(l);
	}

	it = target_char_freqs.find(s[l]);
	if (it != target_char_freqs.end()) {
	if (window_char_freqs[s[l]]-- == it->second &&
	window_char_freqs[s[l]] < it->second) {
	have--;
	}
	}
	l++;
	}

	return ret;
	}
	};

# Minimum Height Trees

題目： https://leetcode.com/problems/lru-cache/
難度： Medium
語言： C++17
技巧： graph multi-source bfs

這題的解題思路可以想像成：
- 對所有 leaf nodes 同時點火，燒掉這個 undirected graph
- 也可以想像成撥洋蔥，每次將最外圍的 leaf nodes 刪除
- 到最後，必定只會剩 1 或 2 個 nodes，它們就是答案
建 adjacency list
multi-source bfs
- 將所有 leaf nodes 的 index 全部 push 到 queue
- 然後開始做 BFS (模擬火燒)

	class Solution {
	public:
	vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
	if (n == 1) {
	return {0};
	}

	vector<unordered_set<int>> adjacency_list(n);
	for (const auto &edge : edges) {
	int v1 = edge[0];
	int v2 = edge[1];
	adjacency_list[v1].emplace(v2);
	adjacency_list[v2].emplace(v1);
	}

	queue<int> q;
	for (int i = 0; i < n; i++) {
	if (adjacency_list[i].size() == 1) {
	q.emplace(i);
	}
	}

	while (n > 2) {
	int len = q.size();
	for (int i = 0; i < len; i++) {
	int vertex = q.front();
	q.pop();

	n--;

	for (auto it = adjacency_list[vertex].begin(); it != adjacency_list[vertex].end();) {
	int neighbor = *it++;

	adjacency_list[neighbor].erase(vertex);
	//adjacency_list[vertex].erase(neighbor);

	if (adjacency_list[neighbor].size() == 1) {
	q.emplace(neighbor);
	}
	}
	}
	}

	vector<int> ret;
	while (q.size()) {
	ret.emplace_back(q.front());
	q.pop();
	}
	return ret;
	}
	};

# Task Scheduler

題目： https://leetcode.com/problems/task-scheduler/
難度： Medium
語言： C++17
技巧： greedy max heap

Greedy
- 如果某個 task A 的數量特別多，就優先 schedule A
- 為什麼呢？
  - 反過來想，假設我們優先 schedule 數量少的 tasks，並且假設我們都先把這些雜魚 tasks 做掉了
  - 現在留下一大坨 A ，每次做完一個 A 都要等 cd，這些 cd 就沒其他 task 可以填補了，只能 idle
  - 但如果今天我們優先 schedule A ，並且假設有 5 個 A 要做，每個 A 之間的 cd 就可以拿雜魚來填補
  - 不僅填補了 cd，還順便消掉雜魚
Max heap (priority queue in descending order)
- 將各個 tasks 的數量，由大到小排序
- 每次將 front 拿出來做，也就是優先 schedule 數量最多的那個 task
- 做完丟到 queue 讓他等 cd（數量還大於 1 才要丟喔），因為 cd 都是固定的，就安心的丟吧
Queue
- pair<int, int>
  - 剩餘數量
  - 下次可再次被 schedule 的時間
- 如果 current time >= reschedulable_time ，就丟回 priority queue，自動按數量降冪排序
- 如此一來，下一輪仍會優先 schedule 數量最多的 task

	class Solution {
	public:
	int leastInterval(const vector<char> &tasks, int n) {
	unordered_map<char, int> task_freqs;
	for (const auto task : tasks) {
	task_freqs[task]++;
	}

	priority_queue<int> pq;
	for (const auto &[_, freq] : task_freqs) {
	pq.emplace(freq);
	}

	int time = 1;
	queue<pair<int, int>> q;
	while (pq.size() \|\| q.size()) {
	if (pq.size()) {
	int freq = pq.top();
	pq.pop();
	if (freq > 1) {
	q.emplace(freq - 1, time + n);
	}
	}

	if (q.size()) {
	auto [freq, reschedulable_time] = q.front();
	if (time >= reschedulable_time) {
	q.pop();
	pq.emplace(freq);
	}
	}

	time++;
	}

	return time - 1;
	}
	};

# LRU Cache

題目： https://leetcode.com/problems/lru-cache/
難度： Medium
語言： C++17
技巧： hash table linked list design

資料結構
- unordered_map 存放 key-value mapping
- list 存放 LRU keys
- 再加開一個 unordered_map 存放 key to LRU-keys-list-iterator 的 mapping => Promote: O (1)
get () 和 put () existing key 要記得 promote 該 key 為 MRU
- 可以用 list::splice () 將 list 的 last element 移動到 list head

	class LRUCache {
	public:
	LRUCache(int capacity)
	: capacity_(capacity),
	map_(),
	iter_cache_(),
	lru_keys_() {}

	int get(int key) {
	auto it = map_.find(key);
	if (it == map_.end()) {
	return -1;
	}

	// If key already exists, promote the key as MRU.
	lru_keys_.splice(lru_keys_.begin(), lru_keys_, iter_cache_[key]);
	return it->second;
	}

	void put(int key, int value) {
	// If key already exists, promote the key as MRU.
	auto it = map_.find(key);
	if (it != map_.end()) {
	it->second = value;
	lru_keys_.splice(lru_keys_.begin(), lru_keys_, iter_cache_[key]);
	return;
	}

	// Evict the LRU entry.
	if (map_.size() >= capacity_) {
	map_.erase(lru_keys_.back());
	iter_cache_.erase(key);
	lru_keys_.pop_back();
	}

	map_.emplace(key, value);
	lru_keys_.emplace_front(key);
	iter_cache_.emplace(key, lru_keys_.begin());
	}

	private:
	int capacity_;
	unordered_map<int, int> map_;
	unordered_map<int, list<int>::iterator> iter_cache_;
	list<int> lru_keys_;
	};

# Week 8 (10/10)

# Kth Smallest Element in a BST

題目： https://leetcode.com/problems/kth-smallest-element-in-a-bst/
難度： Medium
語言： C++17
技巧： binary search tree dfs

Inorder 走訪 BST，得 sorted nums
- 取第 k - 1 個 (因為是 1-indexed 所以要減 1)
- 優化：一旦搜集到第 k - 1 個，之後的都不用搜集了，可直接 early return

	class Solution {
	public:
	int kthSmallest(TreeNode *root, int k) {
	vector<int> nums;
	kthSmallestImpl(root, k, nums);
	return nums[k - 1];
	}

	private:
	void kthSmallestImpl(TreeNode *node, int k, vector<int> &nums) {
	if (!node) {
	return;
	}

	kthSmallestImpl(node->left, k, nums);

	nums.emplace_back(node->val);
	if (nums.size() >= k) {
	return;
	}

	kthSmallestImpl(node->right, k, nums);
	}
	};

# Minimum Window Substring

題目： https://leetcode.com/problems/minimum-window-substring/
難度： Hard
語言： C++17
技巧： string sliding window

維護兩個 int: have 、 need
- 每個 iteration 先嘗試將 window 向右 expand， r++
  - 當某個 character 的出現頻率，從一個 smaller value 變成 target freq 時， have++
- 當 have == need 時，代表我們已經有一個 valid window
  - 如果目前的 valid window 的長度是空前絕後的短，就記錄下來
  - 不斷嘗試 shrink window， l++
  - 當某個 character 的出現頻率不再是 target freq 時， have-- ，並停止 shrink window

	class Solution {
	public:
	string minWindow(const string &s, const string &t) {
	unordered_map<char, int> target_char_freqs;
	for (const auto c : t) {
	target_char_freqs[c]++;
	}

	int have = 0;
	int need = target_char_freqs.size();
	int min_len = std::numeric_limits<int>::max();
	string_view ret;
	unordered_map<char, int> window_char_freqs;

	for (int l = 0, r = 0; r < s.size(); r++) {
	auto it = target_char_freqs.find(s[r]);
	if (it != target_char_freqs.end()) {
	if (++window_char_freqs[s[r]] == it->second) {
	have++;
	}
	}

	// Update the result and continuously shrink the window,
	// trying to obtain a smaller valid window.
	while (have == need) {
	int len = r - l + 1;
	if (len < min_len) {
	ret = string_view(s.data() + l, len);
	min_len = len;
	}

	auto it = target_char_freqs.find(s[l]);
	if (it != target_char_freqs.end()) {
	if (--window_char_freqs[s[l]] < it->second) {
	have--;
	}
	}
	l++;
	}
	}

	return string(ret);
	}
	};

# Serialize and Deserialize Binary Tree

題目： https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
難度： Hard
語言： C++17
技巧： binary tree dfs recursive iterative

拿以前 wmderland 的 n-ary tree 序列化 / 反序列化的算法，改成 for binary tree 的

	vector<string> Split(const string &s, const char delim) {
	stringstream ss(s);
	string t;
	vector<string> tokens;

	while (std::getline(ss, t, delim)) {
	if (t.length() > 0) {
	tokens.emplace_back(std::move(t));
	}
	}
	return tokens;
	}

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Codec {
	struct NodeInfo {
	bool has_left_child;
	bool has_right_child;
	TreeNode *node;
	};

	public:
	string serialize(TreeNode *root) {
	string data;
	serializeImpl(root, data);

	if (data.size()) {
	data.pop_back();
	data.pop_back();
	data.pop_back();
	}
	return data;
	}

	TreeNode *deserialize(const string &data) {
	if (data.empty()) {
	return nullptr;
	}

	vector<string> tokens = Split(data, ',');
	int i = 1;

	string token = tokens[0];
	bool has_left_child = token[0] & kHasLeftChild;
	bool has_right_child = token[0] & kHasRightChild;
	int val = std::stoi(token.substr(1));
	TreeNode *root = new TreeNode(val);

	stack<NodeInfo> st;
	st.push({has_left_child, has_right_child, root});
	NodeInfo curr = st.top();

	while (i < tokens.size()) {
	string token = tokens[i++];
	if (token == kBacktrack) {
	st.pop();
	curr = st.top();
	continue;
	}

	bool has_left_child = token[0] & kHasLeftChild;
	bool has_right_child = token[0] & kHasRightChild;
	int val = std::stoi(token.substr(1));
	TreeNode *new_node = new TreeNode(val);

	if (curr.has_left_child && !curr.node->left) {
	curr.node->left = new_node;
	} else if (curr.has_right_child && !curr.node->right) {
	curr.node->right = new_node;
	}

	st.push({has_left_child, has_right_child, new_node});
	curr = st.top();
	}

	return root;
	}

	private:
	void serializeImpl(TreeNode *node, string &data) {
	if (!node) {
	return;
	}

	int child_info = 0;
	child_info \|= node->left ? kHasLeftChild : 0;
	child_info \|= node->right ? kHasRightChild : 0;
	data += std::to_string(child_info) + std::to_string(node->val) + ',';

	serializeImpl(node->left, data);
	serializeImpl(node->right, data);

	data += string(kBacktrack) + ',';
	}

	static constexpr inline auto kHasLeftChild = 1 << 0;
	static constexpr inline auto kHasRightChild = 1 << 1;
	static constexpr inline auto kBacktrack = "B";
	};

	// Your Codec object will be instantiated and called as such:
	// Codec ser, deser;
	// TreeNode* ans = deser.deserialize(ser.serialize(root));

# Trapping Rain Water

題目： https://leetcode.com/problems/trapping-rain-water/
難度： Hard
語言： C++17
技巧： array dynamic programming

對於每個點，我們需要知道
- 左邊最高高度 => l_highest
- 右邊最高高度 => r_highest
然後就可以算每個點能累積多少單位的水，加總即答案

	class Solution {
	public:
	int trap(const vector<int> &height) {
	const int n = height.size();

	vector<int> l_highest(n, 0);
	for (int i = 1; i < n; i++) {
	l_highest[i] = std::max(l_highest[i - 1], height[i - 1]);
	}

	vector<int> r_highest(n, 0);
	for (int i = n - 2; i >= 0; i--) {
	r_highest[i] = std::max(r_highest[i + 1], height[i + 1]);
	}

	int total_area = 0;
	for (int i = 0; i < n; i++) {
	int local_area = std::min(l_highest[i], r_highest[i]) - height[i];
	if (local_area > 0) {
	total_area += local_area;
	}
	}
	return total_area;
	}
	};

# Find Median from Data Stream

題目： https://leetcode.com/problems/find-median-from-data-stream/
難度： Hard
語言： C++17
技巧： max heap min heap

假設今天有一串 unsorted nums，例如：[5, 1, 7, 11, 3, 9]
請設計一個資料結構，叫 Median Heap，並實作下列兩個 methods
- addNum(int num) - 在 O (logN) 的時間複雜度插入 num
- findMedian() - 在 O (1) 的時間算出 “所有已插入的數字的 median”
解法
- 隨著上述 unsorted nums 被 addNum() ，我們希望它變成 sorted，也就是 [1, 3, 5, 7, 9, 11]
- 進一步開兩個 heap 來存上述的 sorted nums
  - max_heap_ [1, 3, 5]，可以在 O (1) 時間拿到 max value
  - min_heap_ [7, 9, 11]，可以在 O (1) 時間拿到 min value
- 原則：
  - max_heap_ 的所有元素 ≤ min_heap_ 的所有元素
  - 兩者的大小盡量保持平衡，兩者誰大誰小無所謂，但兩者大小的差不得大於 1
- 所以我們的 addNum() 需要考慮下列幾件事：
  - 無條件先插入 left part 的 max_heap_
  - 如果 max_heap_ 的 max val 大於 min_heap_ 的 min val，代表順序錯了，需要將 max_heap_ 的 max val 搬到 min_heap_
  - 如果 max_heap_ 的 size 已經大於 min_heap_ 的 size + 1，將 max_heap 的 max val 搬到 min_heap_
  - 到目前為止，還有一個情況沒處理到，會導致 heap size unbalanced
    - addNum(1) [1] []
    - addNum(2) [1, 2] [] -> [1] [2]
    - addNum(3) [1, 3] [2] -> [1] [2, 3]
    - addNum(4) [1, 4] [2, 3] -> [1] [2, 3, 4]
  - 所以最後需要再檢查一下，如果 min_heap_ 的 size 已經太大，要將 min_heap_ 的 min val 搬回 max_heap_

	class MedianFinder {
	public:
	MedianFinder() : max_heap_(), min_heap_() {}

	void addNum(int num) {
	max_heap_.emplace(num);

	if ((min_heap_.size() && max_heap_.top() > min_heap_.top()) \|\|
	max_heap_.size() > min_heap_.size() + 1) {
	min_heap_.emplace(max_heap_.top());
	max_heap_.pop();
	}

	if (max_heap_.size() + 1 < min_heap_.size()) {
	max_heap_.emplace(min_heap_.top());
	min_heap_.pop();
	}
	}

	double findMedian() {
	if (max_heap_.size() == min_heap_.size()) {
	return (static_cast<double>(max_heap_.top()) + min_heap_.top()) / 2;
	}
	return max_heap_.size() > min_heap_.size() ? max_heap_.top() : min_heap_.top();
	}

	private:
	// max heap min heap
	// [1, 3, 5] [7, 9, 11]
	// ^ ^
	priority_queue<int, vector<int>, less<int>> max_heap_;
	priority_queue<int, vector<int>, greater<int>> min_heap_;
	};

	/**
	* Your MedianFinder object will be instantiated and called as such:
	* MedianFinder* obj = new MedianFinder();
	* obj->addNum(num);
	* double param_2 = obj->findMedian();
	*/

# Word Ladder

題目： https://leetcode.com/problems/word-ladder/
難度： Hard
語言： C++17
技巧： string generate pattern graph single-source bfs

範例測資：
- beginWord = “hit”
- endWord = “cog”
- wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

用 string pattern generation 建 adjacency list

{
  "co*": ["cog"],
  "c*g": ["cog"],
  "hi*": ["hit"],
  "d*g": ["dog"],
  "ho*": ["hot"],
  "*og": ["cog", "log", "dog"],
  "*it": ["hit"],
  "d*t": ["dot"],
  "lo*": ["log", "lot"],
  "*ot": ["dot", "lot", "hot"],
  "do*": ["dog", "dot"],
  "h*t": ["hot", "hit"],
  "l*t": ["lot"],
  "l*g": ["log"],
}

然後從 begin_word 開始做 single-source BFS
- 每次 queue front 拿出來，就 generate pattern，找出所有 neighbor words
- 記得開一個 visited unordered set 來紀錄哪些 word 已經走過來，避免往回走唷

	class Solution {
	public:
	int ladderLength(const string &begin_word,
	const string &end_word,
	const vector<string> &word_list) {
	unordered_map<string, unordered_set<string>> pattern_to_candidates;
	for (int i = 0; i < begin_word.size(); i++) {
	string pattern(begin_word);
	pattern[i] = '*';
	pattern_to_candidates[pattern].emplace(begin_word);
	}
	for (const auto &word : word_list) {
	for (int i = 0; i < word.size(); i++) {
	string pattern(word);
	pattern[i] = '*';
	pattern_to_candidates[pattern].emplace(word);
	}
	}

	int dist = 1;
	unordered_set<string> visited = {begin_word};
	queue<string> q;
	q.emplace(begin_word);

	while (q.size()) {
	int len = q.size();
	for (int i = 0; i < len; i++) {
	auto word = q.front();
	q.pop();

	if (word == end_word) {
	return dist;
	}

	for (int j = 0; j < word.size(); j++) {
	string pattern(word);
	pattern[j] = '*';
	for (const auto &neighbor : pattern_to_candidates[pattern]) {
	if (!visited.count(neighbor)) {
	q.emplace(neighbor);
	}
	visited.emplace(neighbor);
	}
	}
	}
	dist++;
	}

	return 0;
	}
	};

# Basic Calculator

題目： https://leetcode.com/problems/basic-calculator/
難度： Hard
語言： C++17
技巧： string recursion

最外面用一個 int i 紀錄下一個 token 的 begin idx，然後嘗試 match next token，知道走到底了或是碰到 ‘)’
- ’ ’ 跳過
- ‘+’ 設 positive = true
- ‘-’ 設 positive = false
- ‘(’ 遞迴進去，回來的時候要記得 apply positive flag, apply 完 clear flag
- 剩下的就是 match num 了，也要記得 apply positive flag, apply 完 clear flag
Result
- Speed: 7 ms (beats 84.62%)
- Memory: 7.7 MB (beats 99.43%)

	class Solution {
	public:
	int calculate(const string &s) {
	int i = 0;
	return calculateImpl(s, i);
	}

	private:
	int calculateImpl(const string &s, int &i) {
	bool positive = true;
	int result = 0;

	while (i < s.size() && s[i] != ')') {
	if (s[i] == ' ') {
	i++;
	} else if (s[i] == '+') {
	positive = true;
	i++;
	} else if (s[i] == '-') {
	positive = false;
	i++;
	} else if (s[i] == '(') {
	int val = calculateImpl(s, ++i);
	result += positive ? val : -val;
	positive = true;
	} else { // digits
	int num = 0;
	while (std::isdigit(s[i])) {
	num *= 10;
	num += s[i] - '0';
	i++;
	}
	result += positive ? num : -num;
	positive = true;
	}
	}
	i++; // skip ')'
	return positive ? result : -result;
	}
	};

# Maximum Profit in Job Scheduling

題目： https://leetcode.com/problems/maximum-profit-in-job-scheduling/
難度： Hard
語言： C++17
技巧： dynamic programming

首先，將 jobs 按照 end_time 升冪排序
- 假設題目給了 n 個 jobs，我們存入 vector 的時候要建 1 + n 個
- 0-th job 具有特殊意義，代表 no such job (後面 DP 用得到這個東東)
- 其餘第 1 ~ n 個 jobs 就是題目給的
DP
- bottom up 建表， dp 的 size = 1 + n
  - dp[0] 代表 no such job 的 maximum profit
  - dp[i] (i>= 1) 代表 schedule 完第 i 個 job 可獲得的 maximum profit
- 掃描題目給的每個 job，假設目前掃描到的 job 是第 i 個：
  - 往回找到第 j 個 job，其中 jobs[j].end <= jobs[i].start
  - 狀態轉移方程： dp[i] = max(dp[i - 1], dp[j] + jobs[i].profit)
- 答案就在 dp.back()
Result
- Speed: 100 ms (beats 98.54%)
- Memory: 47.4 MB (beats 92.55%)

	class Solution {
	struct Job {
	int start;
	int end;
	int profit;
	};

	public:
	int jobScheduling(const vector<int> &start_time,
	const vector<int> &end_time,
	const vector<int> &profit) {
	const int n = start_time.size();

	vector<Job> jobs(1 + n);
	jobs[0] = {-1, -1, 0};
	for (int i = 0; i < n; i++) {
	jobs[i + 1] = {start_time[i], end_time[i], profit[i]};
	}
	std::sort(jobs.begin(), jobs.end(), [](const Job &j1, const Job &j2) {
	return j1.end < j2.end;
	});

	vector<int> dp(1 + n, 0);
	for (int i = 1; i <= n; i++) {
	int j = i - 1;
	while (j > 0) {
	if (jobs[j].end <= jobs[i].start) {
	break;
	}
	j--;
	}

	dp[i] = std::max(dp[i - 1], dp[j] + jobs[i].profit);
	}

	return dp.back();
	}
	};

# Merge k Sorted Lists

題目： https://leetcode.com/problems/merge-k-sorted-lists/
難度： Hard
語言： C++17
技巧： min heap multi-source bfs

Multi-Source BFS using Min Heap
- Min Heap:
  - priority queue (sorted in ascending order)
- Multi-Source BFS:
  - 先將各個 list 的 head 全部丟到 min heap 裡面
  - 每一輪取出 min heap 當前 value 最小的 node
  - 如果該 node 還有 next，就將 node->next 丟到 min heap 裡面，繼續 BFS
Result
- Speed: 22 ms (beats 81.13%)
- Memory: 13.6 MB (beats 47.99%)

	class Solution {
	public:
	ListNode mergeKLists(vector<ListNode > &lists) {
	if (lists.empty()) {
	return nullptr;
	}

	ListNode *head = nullptr;
	ListNode *curr = nullptr;

	using T = pair<int, ListNode *>;
	priority_queue<T, vector<T>, greater<T>> pq;

	for (auto node : lists) {
	if (node) {
	pq.emplace(node->val, node);
	}
	}

	while (pq.size()) {
	auto [_, node] = pq.top();
	pq.pop();

	if (!head) {
	head = node;
	} else {
	curr->next = node;
	}
	curr = node;

	if (node->next) {
	pq.emplace(node->next->val, node->next);
	}
	}

	return head;
	}
	};

# Largest Rectangle in Histogram

題目： https://leetcode.com/problems/largest-rectangle-in-histogram/
難度： Hard
語言： C++17
技巧： array monotonic stack

https://www.youtube.com/watch?v=zx5Sw9130L0
開一個 stack
- 存 (begin_index + height)
掃一次 heights，對於每一個 element (i, height)
- 往回檢查，剛才處理過的 heights 是否有比目前的 height 還高的
  - 如果有的話，設 begin 為該高度的 index
  - 直到高度已經比目前的 height 低就停止
  - 目的：因為現在走到的高度如果突然降低了，我們就可以先結算一下剛剛累積的最大 area
- 此時 begin 會是 “不比 heights [i]” 小的第一個 (最左邊) 的 height 的 index
- 將 (begin, height[i]) push 到 stack 上
掃完一輪以後，如果 stack 非空，裡面的每個 (begin_index, height) 都是可以頂到圖的最右邊的
- 進行最終的一輪結算
Result
- Speed: 159 ms (beats 92.27%)
- Memory: 75.9 MB (beats 86.26%)

	class Solution {
	public:
	int largestRectangleArea(const vector<int> &heights) {
	int max_area = 0;
	stack<pair<int, int>> st; // index, height

	for (int i = 0; i < heights.size(); i++) {
	int begin_index = i;

	while (st.size()) {
	auto [index, height] = st.top();
	if (height < heights[i]) {
	break;
	}

	st.pop();
	begin_index = index;
	max_area = std::max(max_area, height * (i - index));
	}

	st.emplace(begin_index, heights[i]);
	}

	while (st.size()) {
	auto [begin_index, height] = st.top();
	st.pop();
	max_area = std::max(max_area, height * (static_cast<int>(heights.size()) - begin_index));
	}

	return max_area;
	}
	};