# LeetCode

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

CSDIY

# Array

# 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};
	}
	};

# Two Sum II - Input Array is Sorted

題目： https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
難度： Medium
語言： C++17
技巧： array two pointers

Two pointers
- 如果 nums[l] + nums[r] == target , 遊戲通關
- 如果 nums[l] + nums[r] < target , 代表需要一個大一點的數字， l++
- 如果 nums[l] + nums[r] > target , 代表需要一個小一點的數字， r++

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

	while (l < r) {
	int sum = numbers[l] + numbers[r];
	if (sum == target) {
	return {l + 1, r + 1};
	} else if (sum < target) {
	l++;
	} else {
	r--;
	}
	}

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

# 3Sum

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

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());
	}
	};

# Move Zeros

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

	class Solution {
	public:
	// std::fill(std::remove(nums.begin(), nums.end(), 0), nums.end(), 0);
	void moveZeroes(vector<int> &nums) {
	int l = 0;
	int r = 0;

	while (r < nums.size()) {
	if (nums[r] == 0) {
	r++;
	continue;
	}
	nums[l] = nums[r];
	l++;
	r++;
	}

	while (l < nums.size()) {
	nums[l] = 0;
	l++;
	}
	}
	};

# 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];
	}
	};

# Contains Duplicate

題目： https://leetcode.com/problems/contains-duplicate/
難度： Easy
語言： C++17
技巧： hash 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;
	}
	};

# Squares of a Sorted Array

題目： https://leetcode.com/problems/squares-of-a-sorted-array/
難度： Easy
語言： C++17
技巧： array two pointers

	class Solution {
	public:
	vector<int> sortedSquares(const vector<int> &nums) {
	const int n = nums.size();
	vector<int> ret(n);
	int i = n - 1;
	int l = 0;
	int r = n - 1;

	while (i >= 0) {
	const int abs_l = std::abs(nums[l]);
	const int abs_r = std::abs(nums[r]);

	if (abs_l < abs_r) {
	ret[i--] = std::pow(nums[r--], 2);
	} else {
	ret[i--] = std::pow(nums[l++], 2);
	}
	}

	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;
	}
	}
	};

# Valid Sudoku

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

	class Solution {
	public:
	bool isValidSudoku(const vector<vector<char>> &board) {
	vector<vector<bool>> row_contains(9, vector<bool>(10, false));
	vector<vector<bool>> col_contains(9, vector<bool>(10, false));
	vector<vector<bool>> subbox_contains(9, vector<bool>(10, false));

	for (int r = 0; r < 9; r++) {
	for (int c = 0; c < 9; c++) {
	if (board[r][c] == '.') {
	continue;
	}

	const int n = board[r][c] - '0';

	if (row_contains[r][n]) {
	return false;
	}
	row_contains[r][n] = true;

	if (col_contains[c][n]) {
	return false;
	}
	col_contains[c][n] = true;

	const int idx = getSubboxIndex(r, c);
	if (subbox_contains[idx][n]) {
	return false;
	}
	subbox_contains[idx][n] = true;
	}
	}

	return true;
	}

	private:
	int getSubboxIndex(const int row, const int col) {
	int idx;
	if (col >= 0 && col <= 2) {
	idx = 0;
	} else if (col >= 3 && col <= 5) {
	idx = 1;
	} else {
	idx = 2;
	}

	if (row >= 0 && row <= 2) {
	idx += 0;
	} else if (row >= 3 && row <= 5) {
	idx += 3;
	} else {
	idx += 6;
	}

	return idx;
	}
	};

# 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;
	}
	};

# Range Sum Query - Immutable

題目： https://leetcode.com/problems/range-sum-query-immutable/
難度： Easy
語言： C++17
技巧： array design prefix sum

題解
- 給你一個 immutable int array，假設是： nums = [-2, 0, 3, -5, 2, -1]
- 之後會有數次 query，每次 query 給你一個 left 和 right ，求 sum(nums[left:right+1])
解法
- 建 prefix sum array ps
- 每次 query 取 ps[right + 1] - ps[left]

nums =  [-2,  0, 3, -5,  2, -1]
ps = [0, -2, -2, 1, -4, -2, -3]

	class NumArray {
	public:
	NumArray(const vector<int> &nums)
	: prefix_sums_(1 + nums.size()) {
	prefix_sums_[1] = nums[0];
	for (int i = 1; i < nums.size(); i++) {
	prefix_sums_[i + 1] = prefix_sums_[i] + nums[i];
	}
	}

	int sumRange(int left, int right) {
	return prefix_sums_[right + 1] - prefix_sums_[left];
	}

	private:
	vector<int> prefix_sums_;
	};

# Stack

# 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_;
	};

# Backspace String Compare

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

	class Solution {
	public:
	bool backspaceCompare(const string &s, const string &t) {
	stack<char> st1 = buildStack(s);
	stack<char> st2 = buildStack(t);
	if (st1.size() != st2.size()) {
	return false;
	}

	while (st1.size()) {
	if (st1.top() != st2.top()) {
	return false;
	}
	st1.pop();
	st2.pop();
	}
	return true;
	}

	private:
	stack<char> buildStack(const string &s) {
	stack<char> st;
	for (const auto c : s) {
	if (c == '#') {
	if (st.size()) {
	st.pop();
	}
	} else {
	st.emplace(c);
	}
	}
	return st;
	}
	};

# 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();
	*/

# 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;
	}
	}
	};

# Daily Temperatures

題目： https://leetcode.com/problems/daily-temperatures/
難度： Medium
語言： C++17
技巧： array monotonic stack

Monotonic decreasing stack

	class Solution {
	public:
	vector<int> dailyTemperatures(const vector<int> &temps) {
	vector<int> ret(temps.size(), 0);
	stack<pair<int, int>> st;

	for (int i = 0; i < temps.size(); i++) {
	while (st.size() && st.top().first < temps[i]) {
	auto j = st.top().second;
	st.pop();

	ret[j] = i - j;
	}
	st.emplace(temps[i], i);
	}

	return ret;
	}
	};

# Car Fleets

題目： https://leetcode.com/problems/car-fleets/
難度： Medium
語言： C++17
技巧： array sorting monotonic stack

題解：
- 在一個 2D 的地圖上，有一堆車子在不同的 position x ，且各有各的速度在往右開
- 終點是 x = target
- 若有 n 台車能同時抵達終點，那麼這 n 台車就算一個 car fleet (車隊)
- 請問有幾個車隊？ i.e. 有幾組車會同時抵達終點？
解法：
1. 先將 position 和 speed 拼成 vector<pair<int, int>> ，然後按照 position 升冪排序
  - 因為不能超車，所以左邊的車再快，其速度最終會被右邊的慢車 cap 住
2. Monotonic increasing stack (用於紀錄各台車抵達終點的所需時間)
  - 對於剛才排序好的 vector<pair<int, int>> ，從右往左掃
    - 計算此車抵達 x = target 抵達終點的所需時間： (target - pos) / velocity
    - 如果右邊的車花 3 秒，左邊有台車只要花 5 秒，那麼他們必定是一個車隊
    - 所以只要這台車抵達終點的所需時間比前一台車少，就必定和前一台是同一個車隊
    - 只要比前一台車的所需時間大，再將所需時間 push 上 stack 即可
  - 所以最後會有幾個車隊呢？ stack size 就是答案

	class Solution {
	public:
	int carFleet(int target,
	const vector<int> &position,
	const vector<int> &speed) {
	const int n = position.size();

	vector<pair<int, int>> pos_speed(n);
	for (int i = 0; i < n; i++) {
	pos_speed[i] = {position[i], speed[i]};
	}
	std::sort(pos_speed.begin(), pos_speed.end());

	stack<double> st;
	for (int i = n - 1; i >= 0; i--) {
	const auto &[src, v] = pos_speed[i];
	double t = static_cast<double>(target - src) / v;
	if (st.empty() \|\| t > st.top()) {
	st.emplace(t);
	}
	}

	return st.size();
	}
	};

# 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
開一個 monotonic increasing 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;
	}
	};

# Linked List

# Add Two Numbers

題目： https://leetcode.com/problems/add-two-numbers/
難度： Medium
語言： C++17
技巧： linked list

	class Solution {
	public:
	ListNode addTwoNumbers(ListNode l1, ListNode *l2) {
	bool carry = false;
	ListNode *head = nullptr;
	ListNode *curr = nullptr;

	while (l1 \|\| l2 \|\| carry) {
	int val = carry;
	carry = false;

	if (l1) {
	val += l1->val;
	l1 = l1->next;
	}
	if (l2) {
	val += l2->val;
	l2 = l2->next;
	}

	if (val > 9) {
	val %= 10;
	carry = true;
	}

	ListNode *node = new ListNode(val);
	if (!head) {
	head = node;
	} else {
	curr->next = node;
	}
	curr = node;
	}

	return head;
	}
	};

# Merge Two Sorted Lists

題目： https://leetcode.com/problems/merge-two-sorted-lists/
難度： Easy
語言： C++17
技巧： linked 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;
	}
	};

# Linked List Cycle

題目： https://leetcode.com/problems/linked-list-cycle/
難度： Easy
語言： C++17
技巧： linked list 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;
	}
	};

# 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;
	}
	};

# Rotate List

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

首先找出 linked list 有幾個 node，假設有 n 個 nodes
n - k 就是 new_head 的 index
定位到 new_head，將其前一個 node 指向 nullptr，然後將原本的 tail 指向 old_head
回傳 new_head

	class Solution {
	public:
	ListNode rotateRight(ListNode head, int k) {
	if (!head \|\| k == 0) {
	return head;
	}

	int size = 0;
	for (auto node = head; node; node = node->next) {
	size++;
	}

	k %= size;
	if (k == 0) {
	return head;
	}

	int new_head_idx = size - k;
	ListNode *new_head = nullptr;
	ListNode *curr = head;
	ListNode *prev = nullptr;
	for (int i = 0; i < new_head_idx; i++) {
	prev = curr;
	curr = curr->next;
	}
	new_head = curr;
	prev->next = nullptr;

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

	return new_head;
	}
	};

# 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;
	}
	};

# Remove Nth Node From End of List

題目： https://leetcode.com/problems/remove-nth-node-from-end-of-list/
難度： Medium
語言： C++17
技巧： linked list two pointers

快慢指標，快的先走 n 步
- 如果走完 n 步， fast 就已經是 nullptr，那就代表我們是要移除 head
接著，快慢指標用同樣速度一起走到底
- 這時候 slow 就是我們要移除的對象
- 可以再維護一個 previous node of slow ，將它的 next 指到 slow->next 就行了

	class Solution {
	public:
	ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode *fast = head;
	for (int i = 0; i < n; i++) {
	fast = fast->next;
	}
	if (!fast) {
	return head->next;
	}

	ListNode *prev = head;
	ListNode *slow = head;
	while (fast) {
	prev = slow;
	slow = slow->next;
	fast = fast->next;
	}
	prev->next = slow->next;
	return head;
	}
	};

# Copy List with Random Pointer

題目： https://leetcode.com/problems/copy-list-with-random-pointer/
難度： Medium
語言： C++17
技巧： linked list hash table

先掃一次 original linked list
- 將 old node to new node 的映射關係存在一張 unordered map
- 因為 node->random 可能指向後面的 node，所以只好先完整掃一次
再掃一次 original linked list
- 這次可以用 unordered map 填好每一個 new node 的 next 和 random

	class Solution {
	public:
	Node copyRandomList(Node head) {
	if (!head) {
	return nullptr;
	}

	unordered_map<Node , Node > old_to_new;
	for (Node *node = head; node; node = node->next) {
	Node *new_node = new Node(node->val);
	old_to_new.emplace(node, new_node);
	}

	for (Node *node = head; node; node = node->next) {
	Node *new_node = old_to_new[node];
	if (node->next) {
	new_node->next = old_to_new[node->next];
	}
	if (node->random) {
	new_node->random = old_to_new[node->random];
	}
	}
	return old_to_new[head];
	}
	};

# Swapping Nodes in a Linked List

題目： https://leetcode.com/problems/swapping-nodes-in-a-linked-list/
難度： Medium
語言： C++17
技巧： linked list two pointers

	class Solution {
	public:
	ListNode swapNodes(ListNode head, int k) {
	ListNode *node1 = getKthNodeFromTheBeginning(head, k);
	ListNode *node2 = getKthNodeFromTheEnd(head, k);
	std::swap(node1->val, node2->val);
	return head;
	}

	private:
	ListNode getKthNodeFromTheBeginning(ListNode head, int k) {
	for (int i = 1; i < k; i++) {
	head = head->next;
	}
	return head;
	}

	ListNode getKthNodeFromTheEnd(ListNode head, int k) {
	ListNode *slow = head;
	ListNode *fast = head;
	for (int i = 0; i < k; i++) {
	fast = fast->next;
	}

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

# Swap Nodes in Pairs

題目： https://leetcode.com/problems/swap-nodes-in-pairs/
難度： Medium
語言： C++17
技巧： linked list recursion

解法：遞迴，每次接收兩個 nodes n1 和 n2
- swapPairsImpl() 永遠會回傳 “下一組的頭”
- n1 將會是這組的尾巴，讓 n1 指向下一組的頭
- n2 指向 n1
- 回傳這組的頭 (i.e., n2 ), 如果 n2 == nullptr 的話，這組的頭就是 n1 , 在一開始就要回傳 n1
這題以前要想一個小時，如今已是一拳一個小朋友。

	class Solution {
	public:
	ListNode swapPairs(ListNode head) {
	if (!head) {
	return nullptr;
	}

	return swapPairsImpl(head, head->next);
	}

	private:
	ListNode swapPairsImpl(ListNode n1, ListNode *n2) {
	if (!n2) {
	return n1;
	}

	n1->next = swapPairsImpl(n2->next, n2->next ? n2->next->next : nullptr);
	n2->next = n1;
	return n2;
	}
	}

# Reverse Nodes in k-Group

題目： https://leetcode.com/problems/reverse-nodes-in-k-group/
難度： Hard
語言： C++17
技巧： linked list recursion

這題是 Swap Nodes in Pairs 的 follow up
- 雖然叫做 “swap”, 但實際上就是 reverse nodes in k-group, k = 2 的特化版
解法：遞迴，每次接收要 reverse 的 begin node 和 end node (inclusive)
- reverseKGroupImpl() 永遠會回傳 “下一組的頭”
- 先嘗試找出下一組的頭和尾 (k 個 nodes)
- 如果還有下一組，就遞迴下去找下一組的新頭
- 如果沒有下一組，就不要再遞迴下去了，下一組的新頭就是 end->next
- 將這組的新尾 ( begin ) 指向下一組的新頭
- 反轉這組的所有 nodes
- 回傳這組的頭，i.e. end ，如果 end == nullptr ，這組的頭就是 begin ，在最一開始就要回傳 begin

	class Solution {
	public:
	ListNode reverseKGroup(ListNode head, int k) {
	ListNode *first_group_end = head;
	for (int i = 1; i < k && first_group_end; i++) {
	first_group_end = first_group_end->next;
	}

	return reverseKGroupImpl(head, first_group_end, k);
	}

	private:
	ListNode reverseKGroupImpl(ListNode begin, ListNode *end, int k) {
	if (!end) {
	return begin;
	}

	ListNode *next_group_begin = end->next;
	ListNode *next_group_end = end->next;
	for (int i = 1; i < k && next_group_end; i++) {
	next_group_end = next_group_end->next;
	}

	if (next_group_end) {
	next_group_begin = reverseKGroupImpl(next_group_begin, next_group_end, k);
	}
	reverseListInRange(begin, end);
	begin->next = next_group_begin;
	return end;
	}

	void reverseListInRange(ListNode begin, ListNode end) {
	ListNode *new_begin = nullptr;
	ListNode *next = begin;

	while (new_begin != end) {
	next = begin->next;
	begin->next = new_begin;
	new_begin = begin;
	begin = next;
	}
	}
	};

# String

# Longest Common Prefix

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

	class Solution {
	public:
	string longestCommonPrefix(const vector<string> &strs) {
	if (strs.size() == 1) {
	return strs.front();
	}

	size_t min_len = std::numeric_limits<size_t>::max();
	for (const auto &str : strs) {
	min_len = std::min(min_len, str.size());
	}

	int i = 0;
	for (; i < min_len; i++) {
	for (int j = 1; j < strs.size(); j++) {
	if (strs[j][i] != strs[0][i]) {
	return strs[0].substr(0, i);
	}
	}
	}

	return strs[0].substr(0, i);
	}
	};

# Valid Palindrome

題目： https://leetcode.com/problems/valid-palindrome/
難度： Easy
語言： C++17
技巧： string 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;
	}
	};

# Longest Palindrome

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

	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;
	}
	};

# Maximum Number of Vowels in a Substring of Given Length

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

	class Solution {
	public:
	int maxVowels(const string &s, int k) {
	int num_max_vowels = 0;
	int num_vowels = 0;
	int l = 0;
	int r = 0;

	while (r < s.size()) {
	if (isVowel(s[r])) {
	num_vowels++;
	}
	if (r - l + 1 < k) {
	r++;
	continue;
	}

	num_max_vowels = std::max(num_max_vowels, num_vowels);

	if (isVowel(s[l])) {
	num_vowels--;
	}
	l++;
	r++;
	}

	return num_max_vowels;
	}

	private:
	inline bool isVowel(const char c) {
	switch (c) {
	case 'a':
	case 'e':
	case 'i':
	case 'o':
	case 'u':
	return true;
	default:
	return false;
	}
	}
	};

# Longest Substring Without Repeating Characters

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

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;
	}
	};

# Longest Repeating Character Replacement

題目： https://leetcode.com/problems/longest-repeating-character-replacement/
難度： Medium
語言： C++17
技巧： string sliding window

https://www.youtube.com/watch?v=gqXU1UyA8pk

	// 解法一 (AC): 51 ms (11.46%), 7.1 MB (55.58%)
	class Solution {
	public:
	int characterReplacement(string s, int k) {
	map<char, int> char_freqs;
	int max_win_len = 0;
	int win_len = 0;
	int l = 0;
	int r = 0;

	char_freqs[s.front()]++;
	while (r < s.size()) {
	win_len = r - l + 1;

	auto it = std::max_element(char_freqs.begin(),
	char_freqs.end(),
	[](const pair<char, int> &p1, const pair<char, int> &p2) {
	return p1.second < p2.second;
	});
	if (win_len - it->second > k) {
	char_freqs[s[l]]--;
	l++;
	continue;
	}

	max_win_len = std::max(max_win_len, win_len);
	r++;
	char_freqs[s[r]]++;
	}

	return max_win_len;
	}
	};

	// 解法二 (AC): 9 ms (75%), 7.2 MB (9.92%)
	class Solution {
	public:
	int characterReplacement(string s, int k) {
	unordered_map<char, int> char_freqs;
	int max_freq = 0;
	int max_win_len = 0;
	int win_len = 0;
	int l = 0;
	int r = 0;

	while (r < s.size()) {
	max_freq = std::max(max_freq, ++char_freqs[s[r]]);

	while ((r - l + 1) - max_freq > k) {
	char_freqs[s[l]]--;
	l++;
	}

	max_win_len = std::max(max_win_len, r - l + 1);
	r++;
	}

	return max_win_len;
	}
	};

# 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;
	}
	};

# 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;
	}
	};

# Permutation in String

題目： https://leetcode.com/problems/permutation-in-string/
難度： Medium
語言： C++17
技巧： string sliding window

詳解請參考 Find All Anagrams in a String

	class Solution {
	public:
	bool checkInclusion(const string &s1, const string &s2) {
	unordered_map<char, int> target_char_freqs;
	for (const auto c : s1) {
	target_char_freqs[c]++;
	}

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

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

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

	if (need == have) {
	return true;
	}

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

	l++;
	}

	return false;
	}
	};

# Find All Anagrams in a String

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

解法一
- 每次左指標 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 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);
	}
	};

# Hash Table

# Ransom Note

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

問你 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;
	}
	};

# Valid Anagram

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

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;
	}
	};

# Group Anagrams

題目： https://leetcode.com/problems/group-anagrams/
難度： Medium
語言： C++17
技巧： hash table

將 strs 裡任何一個字串排序後，即可作為 anagram 的 unique identifier
- abc 和 bca 排序後都是 abc

	class Solution {
	public:
	vector<vector<string>> groupAnagrams(const vector<string> &strs) {
	unordered_map<string, vector<string>> anagram_groups;
	for (int i = 0; i < strs.size(); i++) {
	string key(strs[i]);
	std::sort(key.begin(), key.end());
	anagram_groups[key].emplace_back(strs[i]);
	}

	vector<vector<string>> ret;
	for (auto &[_, strings] : anagram_groups) {
	ret.push_back(std::move(strings));
	}
	return ret;
	}
	};

# Binary Tree

# 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;
	}
	};

# Same Tree

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

	class Solution {
	public:
	bool isSameTree(TreeNode p, TreeNode q) {
	if (!p && !q) {
	return true;
	}
	if ((!p && q) \|\| (p && !q)) {
	return false;
	}
	return p->val == q->val &&
	isSameTree(p->left, q->left) &&
	isSameTree(p->right, q->right);
	}
	};

# Symmetric Tree

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

	class Solution {
	public:
	bool isSymmetric(TreeNode *root) {
	if (!root) {
	return true;
	}
	return isSymmetricImpl(root->left, root->right);
	}

	private:
	bool isSymmetricImpl(TreeNode node1, TreeNode node2) {
	if (!node1 && !node2) {
	return true;
	}
	if ((!node1 && node2) \|\| (node1 && !node2)) {
	return false;
	}
	return node1->val == node2->val &&
	isSymmetricImpl(node1->left, node2->right) &&
	isSymmetricImpl(node1->right, node2->left);
	}
	};

# 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;
	};

# 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;
	};

# 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;
	};

# Subtree of Another Tree

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

解法一：Bruteforce
- 將問題 reduce 成 same tree 的問題
- root 底下的每一個 node，都和 sub_root 比較是否為 same tree
- 複雜度分析
  - Time: O (M*N), where M 為 original tree 的節點數，N 為 subtree 的節點數
  - Space: O(M+N)

	class Solution {
	public:
	bool isSubtree(TreeNode root, TreeNode sub_root) {
	if (!sub_root) {
	return true;
	}
	if (!root) {
	return false;
	}

	return sameTree(root, sub_root) \|\|
	isSubtree(root->left, sub_root) \|\|
	isSubtree(root->right, sub_root);
	}

	private:
	bool sameTree(TreeNode root1, TreeNode root2) {
	if (!root1 && !root2) {
	return true;
	}
	if ((!root1 && root2) \|\| (root1 && !root2)) {
	return false;
	}
	return root1->val == root2->val &&
	sameTree(root1->left, root2->left) &&
	sameTree(root1->right, root2->right);
	}
	};

# 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;
	}
	};

# Maximum Width of Binary Tree

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

	class Solution {
	public:
	int widthOfBinaryTree(TreeNode *root) {
	uint32_t max_width = 0;

	queue<tuple<TreeNode *, int, uint32_t>> q; // node, level, idx
	q.emplace(root, 0, 0);

	while (q.size()) {
	uint32_t leftmost_idx = std::get<2>(q.front());
	uint32_t rightmost_idx = 0;

	int len = q.size();
	for (int i = 0; i < len; i++) {
	auto [node, level, idx] = q.front();
	q.pop();

	rightmost_idx = idx;

	if (node->left) {
	q.emplace(node->left, level + 1, idx * 2);
	}
	if (node->right) {
	q.emplace(node->right, level + 1, idx * 2 + 1);
	}
	}
	max_width = std::max(max_width, rightmost_idx - leftmost_idx + 1);
	}

	return max_width;
	}
	};

# Path Sum II

題目： https://leetcode.com/problems/path-sum-ii/
難度： Medium
語言： C++17
技巧： binary tree dfs backtrack

只搜集 root-to-leaf 的路徑喔！

	class Solution {
	public:
	vector<vector<int>> pathSum(TreeNode *root, int target_sum) {
	vector<vector<int>> ret;
	vector<int> path;
	int sum = 0;
	pathSumImpl(root, target_sum, sum, ret, path);
	return ret;
	}

	private:
	void pathSumImpl(TreeNode *node,
	int target_sum,
	int &sum,
	vector<vector<int>> &ret,
	vector<int> &path) {
	if (!node) {
	return;
	}

	path.emplace_back(node->val);
	sum += node->val;

	shared_ptr<void> defer(nullptr, [&](void *) {
	sum -= node->val;
	path.pop_back();
	});

	if (!node->left && !node->right && sum == target_sum) {
	ret.emplace_back(path);
	return;
	}

	pathSumImpl(node->left, target_sum, sum, ret, path);
	pathSumImpl(node->right, target_sum, sum, ret, path);
	}
	};

# 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;
	}
	}
	};

# 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;
	}
	};

# 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;
	}
	};

# 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;
	}

	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));

# Binary Search Tree

# Convert Sorted Array to Binary Search Tree

題目： https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
難度： Easy
語言： C++17
技巧： binary search tree divide and conquer

必須是 height-balanced BST，也就是任一節點的 left & right subtree 的深度之差 ≤ 1

	class Solution {
	public:
	TreeNode *sortedArrayToBST(const vector<int> &nums) {
	return sortedArrayToBSTImpl(nums, 0, nums.size() - 1);
	}

	private:
	TreeNode *sortedArrayToBSTImpl(const vector<int> &nums, int l, int r) {
	if (l > r) {
	return nullptr;
	}
	int m = l + (r - l) / 2;
	return new TreeNode(nums[m],
	sortedArrayToBSTImpl(nums, l, m - 1),
	sortedArrayToBSTImpl(nums, m + 1, r));
	}
	};

# 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;
	}
	}
	};

# 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);
	}
	};

# 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);
	}
	};

# Trie

# 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);
	*/

# Design Add and Search Words Data Structure

題目： https://leetcode.com/problems/design-add-and-search-words-data-structure/
難度： Medium
語言： C++17
技巧： trie dfs

碰到 . 就進行 Trie DFS

	class WordDictionary {
	private:
	struct Node {
	char val;
	vector<Node> children;
	bool end_of_word;
	};

	public:
	WordDictionary() : root_() {}

	void addWord(const string &word) {
	Node *curr = &root_;
	for (const auto c : word) {
	auto it = std::find_if(curr->children.begin(),
	curr->children.end(),
	[c](const Node &node) { return node.val == c; });
	if (it != curr->children.end()) {
	curr = &(*it);
	continue;
	}
	curr->children.push_back({c, {}, false});
	curr = &curr->children.back();
	}
	curr->end_of_word = true;
	}

	bool search(const string &word) {
	return searchImpl(word, 0, root_);
	}

	private:
	bool searchImpl(const string &word, int i, const Node &curr) {
	if (i == word.size()) {
	return curr.end_of_word;
	}

	constexpr char kWildcard = '.';
	const char c = word[i];
	if (c != kWildcard) {
	auto it = std::find_if(curr.children.begin(),
	curr.children.end(),
	[c](const Node &node) { return node.val == c; });
	if (it == curr.children.end()) {
	return false;
	}
	return searchImpl(word, i + 1, *it);
	}

	return std::any_of(curr.children.begin(),
	curr.children.end(),
	[this, &word, i](const auto &child) {
	return searchImpl(word, i + 1, child);
	});
	}

	Node root_;
	};

	/**
	* Your WordDictionary object will be instantiated and called as such:
	* WordDictionary* obj = new WordDictionary();
	* obj->addWord(word);
	* bool param_2 = obj->search(word);
	*/

# Heap

# Last Stone Weight

題目： https://leetcode.com/problems/last-stone-weight/
難度： Easy
語言： C++17
技巧： max heap

用 max heap 存所有 stone weight
- 每次可以在 O (1) 時間內取得重量為第一大、第二大的石頭
- 新的石頭的重量為 stone1 - stone2
- 如果還能生出新的石頭，就丟回 max heap

	class Solution {
	public:
	int lastStoneWeight(const vector<int> &stones) {
	priority_queue<int> pq(stones.begin(), stones.end());
	while (pq.size() > 1) {
	int stone1 = pq.top();
	pq.pop();

	int stone2 = pq.top();
	pq.pop();

	if (auto new_stone = stone1 - stone2; new_stone > 0) {
	pq.emplace(new_stone);
	}
	}

	return pq.size() ? pq.top() : 0;
	}
	};

# 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;
	}
	};

# Find K Closest Elements

題目： https://leetcode.com/problems/find-k-closest-elements/
難度： Medium
語言： C++17
技巧： min heap

解法一：min heap + 根據題目定義自定義排序
- An integer a is closer to x than an integer b if:
  - |a - x| < |b - x| , or
  - |a - x| == |b - x| and a < b
- 為 priority_queue 寫 custom comparator 的時候，要將比大小的邏輯顛倒
解法二：binary search
- 題目有特別告訴我們 input array arr is sorted
- todo

	// 解法一 (AC)
	class Solution {
	public:
	vector<int> findClosestElements(const vector<int> &arr, int k, int x) {
	auto cmp = [&](int a, int b) {
	auto abs_diff_a_x = std::abs(a - x);
	auto abs_diff_b_x = std::abs(b - x);
	if (abs_diff_a_x > abs_diff_b_x) return true;
	if (abs_diff_a_x < abs_diff_b_x) return false;
	if (a > b) return true;
	if (a < b) return false;
	return false;
	};
	priority_queue<int, vector<int>, decltype(cmp)> pq(arr.begin(), arr.end(), cmp);

	multiset<int> ret;
	for (int i = 0; i < k; i++) {
	ret.emplace(pq.top());
	pq.pop();
	}

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

# Top K Frequent Elements

題目： https://leetcode.com/problems/top-k-frequent-elements/
難度： Medium
語言： C++17
技巧： hash table max heap

	class Solution {
	public:
	vector<int> topKFrequent(const vector<int>& nums, int k) {
	unordered_map<int, int> num_freqs;
	for (const auto n : nums) {
	num_freqs[n]++;
	}

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

	vector<int> ret;
	while (k) {
	ret.emplace_back(pq.top().second);
	pq.pop();
	k--;
	}

	return ret;
	}
	};

# Top K Frequent Words

題目： https://leetcode.com/problems/top-k-frequent-words/
難度： Medium
語言： C++17
技巧： hash table max heap

	class Solution {
	public:
	vector<string> topKFrequent(const vector<string> &words, int k) {
	unordered_map<string, int> freqs;
	for (const auto &word : words) {
	freqs[word]++;
	}

	using T = pair<int, string>;
	auto cmp = [](const T &a, const T &b) {
	// Sort freqs by desc order
	if (a.first < b.first) return true;
	if (a.first > b.first) return false;
	// Sort strings by asc order
	if (a.second < b.second) return false;
	if (a.second > b.second) return true;
	return false;
	};
	priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);
	for (const auto &[word, freq] : freqs) {
	pq.emplace(freq, word);
	}

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

# Smallest Number in Infinite Set

題目： https://leetcode.com/problems/smallest-number-in-infinite-set/
難度： Medium
語言： C++17
技巧： hash table min heap

想法
- 用 min heap 紀錄下一個可以被取出的最小正整數 (因為是 min heap，所以取最小值 O (1))
- 因為 C++ priority queue 可以插入重複元素，因此再開一個 unordered_set 紀錄 min heap 中已出現過的數字
- 用一個 unordered_set 紀錄哪些數字已經被取出過（黑名單）
int popSmallest()
- 直接從 min heap 取出下一個最小正整數， num
- 從 num + 1 開始繼續往上找，如果在 removed_nums_set_ 這個黑名單內就跳過
- 找到不在 removed_nums_set_ 的數字，就插入 min heap
void addBack(int num)
- 如果根本不在 removed_nums_set_ 裡面，就 no-op
- 如果在，就 erase 它，然後丟回 min heap

	class SmallestInfiniteSet {
	public:
	SmallestInfiniteSet()
	: removed_nums_set_(),
	available_nums_set_(),
	available_nums_pq_() {
	available_nums_set_.emplace(1);
	available_nums_pq_.emplace(1);
	}

	int popSmallest() {
	int num = available_nums_pq_.top();
	available_nums_pq_.pop();
	removed_nums_set_.emplace(num);

	int next = num + 1;
	while (removed_nums_set_.count(next)) {
	next++;
	}
	if (auto [it, inserted] = available_nums_set_.emplace(next); inserted) {
	available_nums_pq_.emplace(next);
	}

	return num;
	}

	void addBack(int num) {
	if (removed_nums_set_.erase(num)) {
	available_nums_pq_.emplace(num);
	}
	}

	private:
	unordered_set<int> removed_nums_set_;
	unordered_set<int> available_nums_set_;
	priority_queue<int, vector<int>, greater<int>> available_nums_pq_;
	};

	/**
	* Your SmallestInfiniteSet object will be instantiated and called as such:
	* SmallestInfiniteSet* obj = new SmallestInfiniteSet();
	* int param_1 = obj->popSmallest();
	* obj->addBack(num);
	*/

# 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;
	}
	};

# 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;
	}
	};

# Maximum Subsequence Score

題目： https://leetcode.com/problems/maximum-subsequence-score/
難度： Medium
語言： C++17
技巧： array greedy min heap

	class Solution {
	public:
	using ll = long long;
	ll maxScore(const vector<int> &nums1, const vector<int> &nums2, int k) {
	const int n = nums1.size();

	vector<pair<ll, ll>> nums(n);
	for (int i = 0; i < n; i++) {
	nums[i] = {nums2[i], nums1[i]};
	}
	std::sort(nums.begin(), nums.end(), greater<>());

	priority_queue<ll, vector<ll>, greater<ll>> nums1_pq;
	ll nums1_sum = 0;
	ll max_score = 0;

	for (const auto &[n2, n1] : nums) {
	nums1_pq.emplace(n1);
	nums1_sum += n1;

	if (nums1_pq.size() > k) {
	auto nums1_pq_min_val = nums1_pq.top();
	nums1_sum -= nums1_pq_min_val;
	nums1_pq.pop();
	}

	if (nums1_pq.size() == k) {
	max_score = std::max(max_score, nums1_sum * n2);
	}
	}

	return max_score;
	}
	};

# IPO

題目： https://leetcode.com/problems/ipo/
難度： Hard
語言： C++17
技巧： array greedy max heap

	class Solution {
	public:
	int findMaximizedCapital(int k,
	int w,
	const vector<int> &profits,
	const vector<int> &capitals) {
	const int n = profits.size();

	vector<pair<int, int>> nums(n);
	for (int i = 0; i < n; i++) {
	nums[i] = {capitals[i], profits[i]};
	}
	std::sort(nums.begin(), nums.end());

	priority_queue<int> profits_pq;
	int total_capital = w;
	int j = 0;

	for (int i = 0; i < k; i++) {
	while (j < n && total_capital >= nums[j].first) {
	profits_pq.emplace(nums[j].second);
	j++;
	}

	if (profits_pq.empty()) {
	break;
	}

	auto max_profit = profits_pq.top();
	profits_pq.pop();
	total_capital += max_profit;
	}

	return total_capital;
	}
	};

# Graph

# 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);
	image[sr][sc] = new_color;

	while (q.size()) {
	const auto [r, c] = q.front();
	q.pop();

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

	return image;
	}
	};

# Max Area of Island

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

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

	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (grid[i][j] == 1) {
	max_area = std::max(max_area, maxAreaOfIslandImpl(grid, i, j));
	}
	}
	}

	return max_area;
	}

	private:
	int maxAreaOfIslandImpl(vector<vector<int>> &grid,
	int sr,
	int sc) {
	const int m = grid.size();
	const int n = grid[0].size();
	int area = 0;

	queue<pair<int, int>> q;
	q.emplace(sr, sc);
	grid[sr][sc] = 0;

	while (q.size()) {
	const auto [r, c] = q.front();
	q.pop();

	area++;

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

	return area;
	}
	};

# 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_;
	};

# Is Graph Bipartite

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

題解
- 給你一個 adjacency list，問你這張 disconnected undirected acyclic graph 是否為二分圖
解法
- graph single-source BFS，每走到一個 vertex，檢查其所有 neighbors
  - 此 neighbor 尚未 visited：將它著色，使其顏色和本 vertex 相反，然後將 neighbor 丟到 queue 中
  - 此 neighbor 已經 visited：若 neighbor 顏色和本 vertex 相同，就代表此 graph 不是二分圖
- 注意
  - 由於此 graph 可能為 connected /disconnected，所以 BFS 外層還要包一層 loop
  - 只要還有 unvisted vertex，就要從它開始再做一輪 BFS，直到 all vertices visited

	class Solution {
	public:
	bool isBipartite(const vector<vector<int>> &graph) {
	const int n = graph.size();
	vector<bool> visited(n, false);
	vector<bool> colors(n, false);

	while (true) {
	auto it = std::find(visited.begin(), visited.end(), false);
	if (it == visited.end()) {
	break;
	}
	int src = it - visited.begin();

	queue<int> q;
	q.emplace(src);
	visited[src] = true;
	colors[src] = true;

	while (q.size()) {
	auto node = q.front();
	q.pop();

	for (auto neighbor : graph[node]) {
	if (!visited[neighbor]) {
	q.emplace(neighbor);
	visited[neighbor] = true;
	colors[neighbor] = !colors[node];
	continue;
	}
	if (colors[neighbor] == colors[node]) {
	return false;
	}
	}
	}
	}

	return true;
	}
	};

# 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();

	visited[node] = true;

	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;
	}
	};

# 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);
	}
	}
	}
	}
	};

# Surrounded Regions

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

題解
- 給你一個 matrix，裡面只有 ‘O’ 和 ‘X’
- 如果有一塊 ‘O’ 四個 directions 都被 ‘X’ 環繞，請把那一整塊 ‘O’ 全部變成 ‘X’
- 注意：在四個 borders 上的 ‘O’ 不用變成 ‘X’，因為根據題目描述，它們有一邊沒被 ‘X’ 圍住，所以不用變成 ‘X’
解法一（2019, 大三）
- 從任何一個 ‘O’ 開始做 matrix single-source BFS
- 但如果該 ‘O’ 是在 border 上，跳過它不做 BFS
- BFS 途中，將經過的 cell 記錄下來，如果碰到 border 就將剛剛設成 ‘X’ 的 cells 全部 revert 回 ‘O’
- 這種解法是哪個沙雕想出來的？對不起，是我
解法二（2023, Synology）
- 掃四個 borders，如果有發現 ‘O’，就從他開始做 matrix single-source BFS
- 將碰到的 ‘O’ 都感染成 ‘Y’，這些 ‘Y’ 代表 border-connected regions，必不可被感染成 ‘X’
- 全數 BFS 完畢後，‘Y’ 以外的通通感染成 ‘X’，然後把全部都 ‘Y’ 還原回 ‘O’
- 我進步啦

	// 解法一：AC, Speed: 44 ms (beats 6.64%), Memory: 20.3 MB (beats 6.25%)
	class Solution {
	public:
	void solve(vector<vector<char>>& board) {
	if (board.empty() \|\| board.size() < 3) {
	return;
	}

	int rowSize = board.size();
	int colSize = board.front().size();

	for (int i = 0; i < rowSize; i++) {
	for (int j = 0; j < colSize; j++) {
	// Skip borders
	if (i == 0 \|\| i == rowSize - 1 \|\| j == 0 \|\| j == colSize - 1 \|\| board[i][j] == 'X') {
	continue;
	}

	bool reachedBorder = false;
	std::vector<char*> flipped;

	std::queue<std::pair<int, int>> q;
	q.push({i, j});

	while (!q.empty()) {
	int row = q.front().first;
	int col = q.front().second;
	q.pop();

	if (board[row][col] == 'X') {
	continue;
	}

	board[row][col] = 'X';
	flipped.push_back(&board[row][col]);

	if (row - 1 >= 0) q.push({row - 1, col}); else reachedBorder = true;
	if (col - 1 >= 0) q.push({row, col - 1}); else reachedBorder = true;
	if (row + 1 <= rowSize - 1) q.push({row + 1, col}); else reachedBorder = true;
	if (col + 1 <= colSize - 1) q.push({row, col + 1}); else reachedBorder = true;

	if (reachedBorder) break;
	}

	if (reachedBorder) {
	for (auto p : flipped) {
	*p = 'O';
	}
	}
	}
	}
	}
	};

	// 解法二：AC, Speed: 7 ms (beats 98.58%), Memory: 10.2 MB (beats 64.40%)
	class Solution {
	public:
	void solve(vector<vector<char>> &board) {
	const int m = board.size();
	const int n = board[0].size();

	// Start BFS from all the 'O' on the four borders.
	for (int r = 0; r < m; r++) {
	if (board[r][0] == 'O') {
	bfs(board, r, 0);
	}
	if (board[r][n - 1] == 'O') {
	bfs(board, r, n - 1);
	}
	}
	for (int c = 0; c < n; c++) {
	if (board[0][c] == 'O') {
	bfs(board, 0, c);
	}
	if (board[m - 1][c] == 'O') {
	bfs(board, m - 1, c);
	}
	}

	for (int r = 0; r < m; r++) {
	for (int c = 0; c < n; c++) {
	if (board[r][c] == 'O') {
	board[r][c] = 'X';
	} else if (board[r][c] == 'Y') {
	board[r][c] = 'O';
	}
	}
	}
	}

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

	queue<pair<int, int>> q;
	q.emplace(sr, sc);
	board[sr][sc] = 'Y';

	while (q.size()) {
	auto [r, c] = q.front();
	q.pop();

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

# Pacific Atlantic Water Flow

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

維護兩個和 heights 一樣大的 matrix
- pacificReachable - 其中 matrix[i][j] 代表該點是否可以抵達 pacific ocean
- atlanticReachable - 其中 matrix[i][j] 代表該點是否可以抵達 atlantic ocean
做兩次 matrix multi-source BFS
- 第一次：將 pacific ocean 臨海的左邊全部 push 到 queue，然後往高處擴散
- 第二次：將 atlantic ocean 臨海的左邊全部 push 到 queue，然後往高處擴散
最後掃一次 heights，對於每個 row i 和 col j
- 若 pacificReachable[i][j] 且 atlanticReachable[i][j] ，就加入 result vector

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

	vector<vector<bool>> pacificReachable(m, vector<bool>(n, false));
	bfsPacific(heights, pacificReachable);

	vector<vector<bool>> atlanticReachable(m, vector<bool>(n, false));
	bfsAtlantic(heights, atlanticReachable);

	vector<vector<int>> ret;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (pacificReachable[i][j] && atlanticReachable[i][j]) {
	ret.push_back({i, j});
	}
	}
	}
	return ret;
	}

	private:
	void bfsPacific(const vector<vector<int>> &heights,
	vector<vector<bool>> &reachable) {
	const int m = heights.size();
	const int n = heights[0].size();

	queue<pair<int, int>> q;
	vector<vector<bool>> visited(m, vector<bool>(n, false));

	for (int i = 0; i < m; i++) {
	visited[i][0] = true;
	q.emplace(i, 0);
	}
	for (int i = 1; i < n; i++) {
	visited[0][i] = true;
	q.emplace(0, i);
	}

	bfs(heights, q, visited, reachable);
	}

	void bfsAtlantic(const vector<vector<int>> &heights,
	vector<vector<bool>> &reachable) {
	const int m = heights.size();
	const int n = heights[0].size();

	queue<pair<int, int>> q;
	vector<vector<bool>> visited(m, vector<bool>(n, false));

	for (int i = 0; i < m; i++) {
	visited[i][n - 1] = true;
	q.emplace(i, n - 1);
	}
	for (int i = 0; i < n - 1; i++) {
	visited[m - 1][i] = true;
	q.emplace(m - 1, i);
	}

	bfs(heights, q, visited, reachable);
	}

	void bfs(const vector<vector<int>> &heights,
	queue<pair<int, int>> &q,
	vector<vector<bool>> &visited,
	vector<vector<bool>> &reachable) {
	const int m = heights.size();
	const int n = heights[0].size();

	while (q.size()) {
	auto [r, c] = q.front();
	q.pop();

	reachable[r][c] = true;

	int h = heights[r][c];
	if (r - 1 >= 0 && heights[r - 1][c] >= h && !visited[r - 1][c]) {
	visited[r - 1][c] = true;
	q.emplace(r - 1, c);
	}
	if (r + 1 < m && heights[r + 1][c] >= h && !visited[r + 1][c]) {
	visited[r + 1][c] = true;
	q.emplace(r + 1, c);
	}
	if (c - 1 >= 0 && heights[r][c - 1] >= h && !visited[r][c - 1]) {
	visited[r][c - 1] = true;
	q.emplace(r, c - 1);
	}
	if (c + 1 < n && heights[r][c + 1] >= h && !visited[r][c + 1]) {
	visited[r][c + 1] = true;
	q.emplace(r, c + 1);
	}
	}
	}
	};

# 01 Matrix

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

從 mat 中所有 0 同時做 BFS，平行擴散。第一個到達 1 者，當下的 dist 就是該點和它最近的 0 的距離。

	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;
	}
	};

# 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;
	}
	};

# 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;
	}
	};

# Time Needed To Inform All Employees

題目： https://leetcode.com/problems/time-needed-to-inform-all-employees/
難度： Medium
語言： C++17
技巧： tree dfs

題解
- 題目沒有直接給我們 tree，但我們可以將 input 組出一棵 n-ary tree
- 以 adjacency list 就足夠了，如果要用 struct tree node 也可以，但 memory allocation 會較慢
- 每個主管可能會有 N 個下屬，且該主管向其直屬下屬通知消息的時間是一樣的
  - 每個主管是個 parent node，下屬是個 child node，此 parent 到其所有 child 的 edge weight 都是一樣的
- 所有員工都被通知到需要多少時間
  - 此 tree 的 maximum path weight 是多少？
解法
- 建 adjacency list
- Tree DFS 求 maximum path weight

	class Solution {
	public:
	int numOfMinutes(int n,
	int head_id,
	const vector<int> &manager,
	const vector<int> &inform_time) {
	vector<vector<pair<int, int>>> adj_list(n);
	for (int i = 0; i < n; i++) {
	if (i == head_id) {
	continue;
	}
	int manager_id = manager[i];
	int subordinate_id = i;
	adj_list[manager_id].emplace_back(subordinate_id, inform_time[manager_id]);
	}

	int max_path_weight = 0;
	dfs(adj_list, head_id, 0, max_path_weight);
	return max_path_weight;
	}

	void dfs(const vector<vector<pair<int, int>>> &adj_list,
	int manager_id,
	int curr_path_weight,
	int &max_path_weight) {
	max_path_weight = std::max(max_path_weight, curr_path_weight);
	for (const auto &[subordinate_id, weight] : adj_list[manager_id]) {
	dfs(adj_list, subordinate_id, curr_path_weight + weight, max_path_weight);
	}
	}
	};

# Minimum Height Trees

題目： https://leetcode.com/problems/minimum-height-trees/
難度： 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;
	}
	};

# Network Delay Time

題目： https://leetcode.com/problems/network-delay-time/
難度： Medium
語言： C++17
技巧： weighted digraph dijkstra single-source bfs min heap

題解
- 給你一個 weighted digraph，告訴你它有 n 個 vertices，且 source vertex 為 k
- 注意：vertex 的編號從 1 開始（真是個老陰 B）
- 今天我們從 vertex k 發出一個訊號，求所有 vertices 都接收到此訊號的最小時間？
解法
- dijkstra (single-source BFS using a min heap)
- 找到從 source vertex k 到其他 vertices 的最短路徑，取最大值
- 注意：按題目要求，如果訊號無法抵達所有 vertices，就要回傳 -1

	class Solution {
	public:
	int networkDelayTime(const vector<vector<int>> &times, int n, int k) {
	vector<vector<pair<int, int>>> adjacency_list(n);
	for (const auto &edge_info : times) {
	int u = edge_info[0];
	int v = edge_info[1];
	int w = edge_info[2];
	adjacency_list[u - 1].emplace_back(v - 1, w);
	}

	vector<int> min_dists = dijkstra(adjacency_list, n, k - 1);
	if (std::any_of(min_dists.begin(),
	min_dists.end(),
	[](const int dist) {
	return dist == std::numeric_limits<int>::max(); })) {
	// If it is impossible for all the n nodes to receive the signal, return -1.
	return -1;
	}

	return *std::max_element(min_dists.begin(), min_dists.end());
	}

	private:
	vector<int> dijkstra(const vector<vector<pair<int, int>>> &adjacency_list, int n, int src) {
	vector<int> min_dists(n, std::numeric_limits<int>::max());
	min_dists[src] = 0;

	using T = pair<int, int>; // <dist_to_src, node>
	priority_queue<T, vector<T>, greater<T>> pq;
	pq.emplace(0, src);

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

	for (const auto &[neighbor, dist_to_neighbor] : adjacency_list[node]) {
	int new_dist = dist_to_neighbor + dist_to_src;
	if (new_dist < min_dists[neighbor]) {
	min_dists[neighbor] = new_dist;
	pq.emplace(new_dist, neighbor);
	}
	}
	}

	return min_dists;
	}
	};

# 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;
	}
	};

# Design

# Design HashSet

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

資料結構
- 開 N 個 buckets
- 每個 bucket 裡面，會有一條 linked list
操作
- 用 key 找出 bucket index 的時間為 O (1)
- 若兩個 keys 發生 hash collision，這兩個 keys 就會進入同一個 bucket 內，搜尋時間 O (N)

	class MyHashSet {
	public:
	MyHashSet() : buckets_(kNumBuckets) {}

	void add(const int key) {
	const int idx = get_bucket_index(key);
	if (bucket_contains(idx, key)) {
	return;
	}

	buckets_[idx].emplace_back(key);
	}

	void remove(const int key) {
	const int idx = get_bucket_index(key);
	buckets_[idx].remove(key);
	}

	bool contains(const int key) const {
	const int idx = get_bucket_index(key);
	return bucket_contains(idx, key);
	}

	private:
	int get_bucket_index(const int key) const {
	return key % kNumBuckets;
	}

	bool bucket_contains(const int bucket_idx, const int key) const {
	return std::any_of(buckets_[bucket_idx].begin(),
	buckets_[bucket_idx].end(),
	[key](const int k) { return k == key; });
	}

	static constexpr auto kNumBuckets = 10000;
	vector<list<int>> buckets_;
	};

# 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_;
	};

# 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();
	*/

# Insert Delete GetRandom O(1)

題目： https://leetcode.com/problems/insert-delete-getrandom-o1/
難度： Medium
語言： C++17
技巧： array hash table design

用 unordered_map 紀錄 value to vector idx 的映射關係
用 vector 提供 GetRandom () in O (1)
remove () 時，若 target value 存在我們的 RandomizedSet
- 透過 unordered_map 查到 target value 在 vector 裡的 offset
- 將該 element 於 vector.back () 交換，然後 vector pop_back
- unordered_map 裡面的 mapping 也要記得更新

	class RandomizedSet {
	public:
	RandomizedSet() : v_(), m_() {}

	bool insert(int val) {
	auto m_it = m_.find(val);
	if (m_it != m_.end()) {
	return false;
	}

	auto v_it = v_.insert(v_.end(), val);
	m_.emplace(val, v_it - v_.begin());
	return true;
	}

	bool remove(int val) {
	auto m_it = m_.find(val);
	if (m_it == m_.end()) {
	return false;
	}

	m_[v_.back()] = m_it->second;
	std::swap(v_[m_it->second], v_.back());
	v_.pop_back();
	m_.erase(val);
	return true;
	}

	int getRandom() {
	return v_[rand () % v_.size()];
	}

	private:
	vector<int> v_;
	unordered_map<int, int> m_;
	};

	/**
	* Your RandomizedSet object will be instantiated and called as such:
	* RandomizedSet* obj = new RandomizedSet();
	* bool param_1 = obj->insert(val);
	* bool param_2 = obj->remove(val);
	* int param_3 = obj->getRandom();
	*/

# Time Based Key-Value Store

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

讓各個 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_;
	};

# Kth Largest Element in a Stream

題目： https://leetcode.com/problems/kth-largest-element-in-a-stream/
難度： Easy
語言： C++17
技巧： min heap design

題解：
- 設計一個 class
- constructor: KthLargest(int k, const vector<int> &nums) 將 nums 倒進我們的資料結構
- add(int val) 將 val 加入我們的資料結構，並回傳加入 val 後第 k 大的數字
解法：
- 維護一個 min heap，並使其 size 維持在 k
- 如此一來 min heap 的 root node 永遠就會是 kth largest element，且可以 O (1) 時間內取得
- 複雜度：
  - 空間：O (N)
  - 時間：O (N⋅log (N) + M⋅log (k))
    - N⋅log(N) constructor
      - N: 先將 nums 變成 min heap
      - log (N): 呼叫 k 次 pq_.pop (), 也就是 k⋅log (N), 也可進一步化簡得 log (N)
    - M⋅log(k) add()
      - M: 假設我們需要呼叫 M 次 add()
      - log (k): 每次呼叫時 pq_.size () == k，呼叫一次 pq_.pop () 的時間複雜度為 log (k)

	class KthLargest {
	public:
	KthLargest(int k, const vector<int> &nums)
	: k_(k),
	pq_(nums.begin(), nums.end()) {
	while (pq_.size() > k) {
	pq_.pop();
	}
	}

	int add(int val) {
	pq_.emplace(val);
	if (pq_.size() > k_) {
	pq_.pop();
	}
	return pq_.top();
	}

	private:
	const int k_;
	priority_queue<int, vector<int>, greater<int>> pq_;
	};

# Design Twitter

題目： https://leetcode.com/problems/design-twitter/
難度： Medium
語言： C++17
技巧： hash table max heap multi-source bfs design

特別注意， tweetID 只保證 uniqueness，不代表 tweet ordering
- 因此如果我們要紀錄 tweet ordering，必須自行處理
- 一個作法是我們在 postTweet 自行配發每一則 tweet 的流水號
這題最重要的是如何實作有效率的 vector<int> getNewsFeed(UserID userID)
- 可以將此問題 reduce 成 merge k sorted lists
- 準備一個 priority queue pq (max heap, 根據 tweet seq 降冪排序)
  - 將自己的最新一則 tweet 丟進 pq
  - 將自己 following 的每一個 user 的最後一則 tweet 丟進 pq
- 開始做 BFS
  - pq 的頭永遠會是最新的 tweet
  - 每次抓出 pq.top 後，就將發文者的前一則 tweet 拿出來抓交替，丟進 pq
  - 如此反覆，直到 pq 已空，或是 returning vector size 已達 10

	class Twitter {
	using UserID = int;
	using TweetID = int; // Unique but not guaranteed to be in ascending order!
	using TweetSeq = int;

	public:
	Twitter()
	: user_tweets_(),
	user_following_() {}

	void postTweet(UserID userID, TweetID tweetID) {
	static TweetSeq next_seq = 0;
	user_tweets_[userID].emplace_back(++next_seq, tweetID);
	}

	vector<int> getNewsFeed(UserID userID) {
	using T = tuple<TweetSeq, UserID, int>;
	auto cmp = [](const T &t1, const T &t2) {
	return std::get<0>(t1) < std::get<0>(t2);
	};
	priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);

	for (const auto followingUserID : user_following_[userID]) {
	auto it = user_tweets_.find(followingUserID);
	if (it != user_tweets_.end() && it->second.size()) {
	pq.emplace(it->second.back().first, followingUserID, it->second.size() - 1);
	}
	}

	auto it = user_tweets_.find(userID);
	if (it != user_tweets_.end() && it->second.size()) {
	pq.emplace(it->second.back().first, userID, it->second.size() - 1);
	}

	vector<TweetID> tweetIDs;
	while (pq.size() && tweetIDs.size() < 10) {
	auto [_, userID, idx] = pq.top();
	pq.pop();

	tweetIDs.emplace_back(user_tweets_[userID][idx].second);

	if (idx == 0) {
	continue;
	}

	auto it = user_tweets_.find(userID);
	pq.emplace(it->second[idx - 1].first, userID, idx - 1);
	}

	return tweetIDs;
	}

	void follow(UserID followerID, UserID followeeID) {
	user_following_[followerID].emplace(followeeID);
	}

	void unfollow(UserID followerID, UserID followeeID) {
	user_following_[followerID].erase(followeeID);
	}

	private:
	unordered_map<UserID, vector<pair<TweetSeq, TweetID>>> user_tweets_;
	unordered_map<UserID, unordered_set<UserID>> user_following_;
	};

	/**
	* Your Twitter object will be instantiated and called as such:
	* Twitter* obj = new Twitter();
	* obj->postTweet(userId,tweetId);
	* vector<int> param_2 = obj->getNewsFeed(userId);
	* obj->follow(followerId,followeeId);
	* obj->unfollow(followerId,followeeId);
	*/

# Find Median from Data Stream

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

假設今天有一串 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();
	*/

# Bit Manipulation

# 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;
	}
	};

# Number of 1 Bits

題目： https://leetcode.com/problems/number-of-1-bits/
難度： Easy
語言： C++17
技巧： bit manipulation

	class Solution {
	public:
	int hammingWeight(uint32_t n) {
	int num_of_1_bits = 0;
	for (int i = 0; i < 32; i++) {
	if (n & (1 << i)) {
	num_of_1_bits++;
	}
	}
	return num_of_1_bits;
	}
	};

# Reverse Bits

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

	class Solution {
	public:
	uint32_t reverseBits(uint32_t n) {
	uint32_t ret = 0;
	for (int i = 0; i < 32; i++) {
	if (n & (1 << i)) {
	ret \|= (1 << (31 - i));
	}
	}
	return ret;
	}
	};

# Single Number

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

nums 中只有一個數字是獨自出現，其餘皆成雙
- [2, 2, 7, 1, 7]
這題考驗我們對 xor 的特性是否熟悉

	class Solution {
	public:
	int singleNumber(const vector<int> &nums) {
	int ret = 0;
	for (const auto num : nums) {
	ret ^= num;
	}
	return ret;
	}
	};

# 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;
	}
	};

# Subsets II

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

將 input nums 排序
自己算 subset hash

	class Solution {
	public:
	vector<vector<int>> subsetsWithDup(vector<int> nums) {
	std::sort(nums.begin(), nums.end());

	const int n = nums.size();
	vector<vector<int>> ret;
	unordered_set<string> seen;

	for (int i = 0; i < std::pow(2, n); i++) {
	vector<int> subset;
	subset.reserve(nums.size()); // Speed 3 ms (Beats 73.91%) lol
	string bits = to_bit_string(n, i);
	for (int j = 0; j < bits.size(); j++) {
	if (bits[j] == '1') {
	subset.emplace_back(nums[j]);
	}
	}

	string subset_hash = generateHash(subset);
	if (!seen.count(subset_hash)) {
	seen.emplace(subset_hash);
	ret.emplace_back(std::move(subset));
	}
	}

	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;
	}

	string generateHash(const vector<int> &subset) {
	string hashcode;
	for (int i = 0; i < subset.size(); i++) {
	hashcode += std::to_string(subset[i]);
	if (i != subset.size() - 1) {
	hashcode += ',';
	}
	}
	return hashcode;
	}
	};

# 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) {
	r = m;
	} else {
	l = m + 1;
	}
	}

	return nums[l] == target ? l : -1;
	}
	};

	// 解法二
	class Solution {
	public:
	int search(const vector<int> &nums, const int target) {
	auto it = std::lower_bound(nums.begin(), nums.end(), target);
	return (it != nums.end() && *it == target) ? it - nums.begin() : -1;
	}
	};

# 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;
	} else {
	l = m + 1;
	}
	}

	return l;
	}
	};

# Search a 2D Matrix

題目： https://leetcode.com/problems/search-a-2d-matrix/
難度： Medium
語言： C++17
技巧： matrix binary search

	class Solution {
	public:
	bool searchMatrix(const vector<vector<int>> &matrix, int target) {
	int row = 0;
	int col = 0;

	int l = 0;
	int r = matrix.size() - 1;
	int m = 0;
	while (l < r) {
	m = l + (r - l + 1) / 2;
	if (matrix[m][0] <= target) {
	l = m;
	} else {
	r = m - 1;
	}
	}
	row = r;

	l = 0;
	r = matrix[0].size() - 1;
	while (l < r) {
	m = l + (r - l) / 2;
	if (matrix[row][m] >= target) {
	r = m;
	} else {
	l = m + 1;
	}
	}
	col = l;

	return matrix[row][col] == target;
	}
	};

# 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;
	}
	};

# Backtracking

# Subsets

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

題解
- 給一個 integer array, e.g. [1,2,3]
- nums 裡的數字，每個只能用一次
- 回傳它的所有 subsets（subsets 之間彼此不能重複）
解法：
- 遞迴 + 回溯
- 每個 recursion level 有兩個選擇：取、不取
如果題目要求：
- 每個 element 只能用一次，建議套用解法二的模板 (See Subsets, Subsets II, Combination Sum II)
- 每個 element 可以重複使用，套用解法一的模板 (See Combination Sum)

	// 解法一
	class Solution {
	public:
	vector<vector<int>> subsets(const vector<int> &nums) {
	vector<vector<int>> ret;
	vector<int> current;

	subsetsImpl(nums, 0, current, ret);
	return ret;
	}

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

	// Skip nums[i]
	subsetsImpl(nums, i + 1, current, ret);

	// Pick nums[i]
	current.emplace_back(nums[i]);
	subsetsImpl(nums, i + 1, current, ret);
	current.pop_back();
	}
	};

	// 解法二
	class Solution {
	public:
	vector<vector<int>> subsets(const vector<int> &nums) {
	vector<vector<int>> ret;
	vector<int> current;

	subsetsImpl(nums, 0, current, ret);
	return ret;
	}

	private:
	void subsetsImpl(const vector<int> &nums,
	int begin,
	vector<int> &current,
	vector<vector<int>> &ret) {
	ret.emplace_back(current);

	for (int i = begin; i < nums.size(); i++) {
	current.emplace_back(nums[i]);
	subsetsImpl(nums, i + 1, current, ret);
	current.pop_back();
	}
	}
	};

# Subsets II

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

題解
- 給你一個 array nums ，裡面的數字可能有 duplicates
- nums 裡的數字，每個只能用一次
- 回傳它的所有 subsets（subsets 之間彼此不能重複）
如何避免 duplicated combinations
- 先將 input array 做排序，然後 exploit sorted array 的特性
  - 選定一個 index 作為此次 subset (i.e. current ) 的 first element
  - 如果這次的 first element 和前一個一樣，代表剛剛已經處理過了，跳過這輪，直到出現新的 first element
  - 從它開始，往後掃所有的 elements
    - pick nums[i] ：遞迴進去
    - skip nums[i] ：backtrack 後，for loop 下一輪即是探索 skipped nums[i] 的 path

	class Solution {
	public:
	vector<vector<int>> subsetsWithDup(vector<int> nums) {
	std::sort(nums.begin(), nums.end());

	vector<vector<int>> ret;
	vector<int> current;
	subsetsWithDupImpl(nums, 0, current, ret);

	return ret;
	}

	private:
	void subsetsWithDupImpl(const vector<int> &nums,
	int begin,
	vector<int> &current,
	vector<vector<int>> &ret) {
	ret.emplace_back(current);

	for (int i = begin; i < nums.size(); i++) {
	if (i > begin && nums[i - 1] == nums[i]) {
	continue;
	}

	current.emplace_back(nums[i]);
	subsetsWithDupImpl(nums, i + 1, current, ret);
	current.pop_back();
	}
	}
	};

# Combination Sum

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

題解
- 給你一個 array candidates , 裡面的數字全都是 distinct integers
- 給你一個 int target
- candidates 裡的數字可重複使用，求 candidates 中所有能 sum up to target 的組合
解法：遞迴，每一個 recursion level 可以有兩種選擇
- 跳過目前這個數字
- 取現在這個數字 (下一次遞迴進來，還可以重複取這個數字)
- 每次取了一個數字，就將該數字從 target 扣除，若 target (remaining) 能剛好歸零就加入 ret

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

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

	private:
	void combinationSumImpl(vector<int> &candidates,
	int i,
	int remaining,
	vector<int> &current,
	vector<vector<int>> &ret) {
	if (remaining < 0) {
	return;
	}
	if (remaining == 0) {
	ret.emplace_back(current);
	return;
	}
	if (i >= candidates.size()) {
	return;
	}

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

	// Take candidates[i], note according to this question,
	// we may reuse candidates[i] multiple times.
	current.emplace_back(candidates[i]);
	combinationSumImpl(candidates, i, remaining - candidates[i], current, ret);
	current.pop_back();
	}
	};

# Combination Sum II

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

題解
- 給你一個 array candidates ，裡面的數字可能有 duplicates
- 給你一個 int target
- candidates 裡的數字，每個只能用一次
- 求 candidates 中所有能 sum up to target 的組合，且不能回傳有重複的組合
如何避免 duplicated combinations
- 先將 input array 做排序，然後 exploit sorted array 的特性
  - 選定一個 index 作為此次 combination (i.e. current ) 的 first element
  - 如果這次的 first element 和前一個一樣，代表剛剛已經處理過了，跳過這輪，直到出現新的 first element
  - 從它開始，往後掃所有的 elements
    - pick candidates[i] ：遞迴進去
    - skip candidates[i] ：backtrack 後，for loop 下一輪即是探索 skipped candidates[i] 的 path

	class Solution {
	public:
	vector<vector<int>> combinationSum2(vector<int> candidates, int target) {
	std::sort(candidates.begin(), candidates.end());

	vector<vector<int>> ret;
	vector<int> current;
	combinationSum2Impl(candidates, 0, target, current, ret);

	return ret;
	}

	private:
	void combinationSum2Impl(const vector<int> &candidates,
	int begin,
	int remaining,
	vector<int> &current,
	vector<vector<int>> &ret) {
	if (remaining < 0) {
	return;
	}
	if (remaining == 0) {
	ret.emplace_back(current);
	return;
	}

	for (int i = begin; i < candidates.size(); i++) {
	if (i > begin && candidates[i - 1] == candidates[i]) {
	continue;
	}

	current.emplace_back(candidates[i]);
	combinationSum2Impl(candidates, i + 1, remaining - candidates[i], current, ret);
	current.pop_back();
	}
	}
	};

# Generate Parentheses

題目： https://leetcode.com/problems/generate-parentheses/
難度： Medium
語言： C++17
技巧： string backtracking

範例測資
- 輸入：n = 3
- 輸出： ["((()))","(()())","(())()","()(())","()()()"]
遞迴 + 回溯，在每個階段
- 紀錄當下已有的 open parenthesis 數量、close parenthesis 數量
- 只要 open parenthesis 的數量還沒超過 n，就可以再加入一個 open parenthesis
- 如果 close parenthesis 的數量還小於 open parenthesis 的數量，就可以再加入一個 close parenthesis

	class Solution {
	public:
	vector<string> generateParenthesis(int n) {
	vector<string> ret;
	string s;
	generateParenthesisImpl(n, 0, 0, s, ret);
	return ret;
	}

	private:
	void generateParenthesisImpl(int n,
	int num_open,
	int num_close,
	string &s,
	vector<string> &ret) {
	if (num_open >= n && num_close >= n) {
	ret.emplace_back(s);
	return;
	}

	if (num_open < n) {
	s.push_back('(');
	generateParenthesisImpl(n, num_open + 1, num_close, s, ret);
	s.pop_back();
	}

	if (num_close < num_open) {
	s.push_back(')');
	generateParenthesisImpl(n, num_open, num_close + 1, s, ret);
	s.pop_back();
	}
	}
	};

# Permutations

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

遞迴，每一個 recursion level 可以選擇還沒加入過 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();
	}
	}
	};

# Letter Combinations of a Phone Number

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

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

	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"
	};
	};

# 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;
	}
	};

# N-Queens

題目： https://leetcode.com/problems/n-queens/
難度： Hard
語言： C++17
技巧： matrix recursion backtracking

	class Solution {
	public:
	vector<vector<string>> solveNQueens(int n) {
	board_ = vector<string>(n, string(n, '.'));
	solveNQueensImpl(0);
	return ret_;
	}

	private:
	void solveNQueensImpl(const int r) {
	if (r == board_.size()) {
	ret_.push_back(board_);
	return;
	}

	for (int c = 0; c < board_.size(); c++) {
	if (cols_.count(c) \|\|
	positive_diagonals_.count(r + c) \|\|
	negative_diagonals_.count(r - c)) {
	continue;
	}

	cols_.emplace(c);
	positive_diagonals_.emplace(r + c);
	negative_diagonals_.emplace(r - c);
	board_[r][c] = 'Q';

	solveNQueensImpl(r + 1);

	cols_.erase(c);
	positive_diagonals_.erase(r + c);
	negative_diagonals_.erase(r - c);
	board_[r][c] = '.';
	}
	}

	unordered_set<int> cols_;
	unordered_set<int> positive_diagonals_;
	unordered_set<int> negative_diagonals_;
	vector<string> board_;
	vector<vector<string>> ret_;
	};

# Dynamic Programming

# 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];
	}
	};

# Min Cost Climbing Stairs

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

題解
- 你可以從第 0 個台階開始，也可以從第 1 個台階開始
- 每次可以往上走一階、兩階
- cost[i] 代表踩上第 i 個台階要付多少成本
- 如果總共有 n 個台階，請問踩上第 n + 1 個台階的最低成本為何？
DP
- dp[i] 代表踩上第 i 個台階的最低累積成本
- dp[0] = 0 , 因為可以從第 0 個台階開始，所以累積成本為 0
- dp[1] = 0 , 因為可以從第 1 個台階開始，所以累積成本為 0
- dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])

	class Solution {
	public:
	int minCostClimbingStairs(const vector<int> &cost) {
	const int n = cost.size();
	vector<int> dp(n + 1, 0);
	for (int i = 2; i < n + 1; i++) {
	dp[i] = std::min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
	}
	return dp[n];
	}
	};

# 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;
	}
	};

# House Robber

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

DP
- dp[i] 代表從 nums[0] 搶到 nums[i] 為止，所能獲得的最大金額
  - dp[0] = 搶到 nums[0] 為止最多能搶多少，這邊只有 nums[0] 一間房屋能搶
  - dp[1] = 搶到 nums[1] 為止最多能搶多少，這邊選 nums[0] 與 nums[1] 價值較高者
- 要搶這一棟，就不能搶它前一棟
  - max (前一棟可以搶到的最大金額，前前一棟可以搶到的最大金額 + 現在這棟)
值得思考的問題
- 為什麼 dp[1] 不能直接填 nums[1] 呢？
- [2, 1, 1, 2]

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

	vector<int> dp(n);
	dp[0] = nums[0];
	dp[1] = std::max(nums[0], nums[1]);

	for (int i = 2; i < n; i++) {
	dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
	}
	return dp.back();
	}
	};

# House Robber II

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

這次所有的房子圍成一個圈圈，也就是說，頭尾是相連的
- 搶了 first house，就不能搶 last house，因為它們相連
DP，解法和 House Robber 第一題相同，做兩次 DP
- 第一次 DP 不搶 last house
- 第二次 DP 不搶 first house
- 兩次 DP 結果取 max 就是答案

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

	return std::max(robExcludingTheLastHouse(nums),
	robExcludingTheFirstHouse(nums));
	}

	private:
	int robExcludingTheLastHouse(const vector<int> &nums) {
	const int n = nums.size();

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

	int robExcludingTheFirstHouse(const vector<int> &nums) {
	const int n = nums.size();

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

# Delete and Earn

題目： https://leetcode.com/problems/delete-and-earn/
難度： Medium
語言： C++17
技巧： array hash table dynamic programming

題解
- 給你一個 int array，例如： [2,2,3,3,4,4,4,6,8]
- 假設我們從上述 array 刪除了 n
  - 我們可以獲得 n points
  - 但同時必須移除 n-1 與 n+1，且無法獲得 n-1 與 n+1 的分數
- 假設我們從上述 array 刪除了一個 4
  - 所有的 3 和 5 都要跟著被移除 (但此例題中，只有 3 沒有 5)
  - 另外 2 個 4 都還是可以用來得分，所以光是選擇刪除 4 就能得到 12 分
解法：DP
- 此問題可以 reduce 為 house robber。如果我們搶了 n，就無法搶 n-1 與 n+1
  - 建立 points int array，其中 points[i] 代表刪除 i 本身可以獲得幾分
  - 也就是說， points[i] = i * (i 在 input array 裡的個數)
  - 就上面的例題來說，我們可以建出 points = [0, 0, 4, 6, 12, 0, 6, 0, 8]
- 如此一來就順利 reduce 成 house robber 了

	class Solution {
	public:
	int deleteAndEarn(vector<int> &nums) {
	int max_num = 0;
	unordered_map<int, int> score_map;
	for (const auto num : nums) {
	score_map[num] += num;
	max_num = std::max(max_num, num);
	}

	if (score_map.size() == 1) {
	return score_map.begin()->second;
	}

	vector<int> points(1 + max_num);
	for (const auto &[num, score] : score_map) {
	points[num] = score;
	}

	vector<int> dp(points.size());
	dp[1] = points[1];
	dp[2] = std::max(points[1], points[2]);
	for (int i = 3; i < dp.size(); i++) {
	dp[i] = std::max(dp[i - 1], dp[i - 2] + points[i]);
	}
	return dp.back();
	}
	};

# Solving Questions With Brainpower

題目： https://leetcode.com/problems/solving-questions-with-brainpower/
難度： Medium
語言： C++17
技巧： array dynamic programming

DP
- dp[i] 代表從第 i 題開始作答，最後可拿到的最大分數
  - dp[n - 1] = 從最後一題開始作答，所以只能拿到最後一題的分數
  - dp[n - 2] = 從倒數第二題開始作答
- 狀態轉移方程
  - 假設我們現在碰到第 i 題，我們可以決定跳過它 / 解它
  - 跳過它： dp[此題] = dp[下一題]
  - 解它： dp[此題] = 此題分數 + dp[下一題]
  - dp[i] = std::max(dp[i + 1], score + dp[next_question_idx])
- 注意：下一題 index 如果會越界的話
  - dp[i] = std::max(dp[i + 1], score)

	class Solution {
	using ll = long long;

	public:
	ll mostPoints(const vector<vector<int>> &questions) {
	const int n = questions.size();

	vector<ll> dp(n, 0);
	dp[n - 1] = questions[n - 1][0];

	for (int i = n - 2; i >= 0; i--) {
	ll score = questions[i][0];
	int next_question_idx = i + questions[i][1] + 1;

	if (next_question_idx >= n) {
	dp[i] = std::max(dp[i + 1], score);
	continue;
	}

	dp[i] = std::max(dp[i + 1], score + dp[next_question_idx]);
	}

	return dp[0];
	}
	};

# 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;
	}
	};

# Maximum Product Subarray

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

舉個例子：[-1,-2,-9,-6]

                  local_max [1]    local_min [1]
processing [-1]:  local_max [-1]   local_min [-1]
processing [-2]:  local_max [2]    local_min [-2]
processing [-9]:  local_max [18]   local_min [-18]
processing [-6]:  local_max [108]  local_min [-108]

另個例子：[2,3,-2,4]

                  local_max [1]    local_min [1]
processing [2]:   local_max [2]    local_min [2]
processing [3]:   local_max [6]    local_min [3]
processing [-2]:  local_max [-2]   local_min [-12]
processing [4]:   local_max [4]    local_min [-48]

每次讓 current num 乘上 local_max 與 local_min
- 得到兩個不同的 products
- 拿去更新 local_max 和 local_min

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

	for (const auto num : nums) {
	int prod1 = num * local_max;
	int prod2 = num * local_min;
	local_max = std::max({num, prod1, prod2});
	local_min = std::min({num, prod1, prod2});
	global_max = std::max(global_max, local_max);
	}

	return global_max;
	}
	};

# Maximum Sum Circular Subarray

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

Regular Kadane’s Algorithm
- 和 LeetCode 53. Maximum Subarray 相同
Inverted Kadane’s Algorithm
- 由於答案可能是頭部 subarray + 尾部 subarray
- 所以我們可以找到 global min 後，用 sum 扣除之
- 舉個例子： [4, 1, 3]
  - global_min 為 1
  - 我們可以回傳 (4 + 1 + 3) - global_min = 7 作為 potential global max
- 特別注意： [-3, -2, -3]
  - global_min 為 (-3) + (-2) + (-3) = -8
  - 但實際上我們應該回傳 -2 作為 potential global max
兩者其中一者必為答案

	class Solution {
	public:
	int maxSubarraySumCircular(const vector<int> &nums) {
	return std::max(kadane(nums), invertedKadane(nums));
	}

	private:
	int kadane(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;
	}

	int invertedKadane(const vector<int> &nums) {
	int global_min = std::numeric_limits<int>::max();
	int local_min = 0;

	for (const auto n : nums) {
	local_min = std::min(n, local_min + n);
	global_min = std::min(global_min, local_min);
	}

	int sum = std::accumulate(nums.begin(), nums.end(), 0);
	return sum == global_min ? global_min : sum - global_min;
	}
	};

# Coin Change

題目： https://leetcode.com/problems/coin-change/
難度： Medium
語言： C++17
技巧： array 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;
	}
	};

# Longest Common Subsequence

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

https://www.youtube.com/watch?v=Ua0GhsJSlWM

	class Solution {
	public:
	int longestCommonSubsequence(const string &text1, const string &text2) {
	// a b c d e
	// 0 0 0 0 0 0
	// a 0 1 1 1 1 1
	// c 0 1 1 2 2 2
	// e 0 1 1 2 2 3
	const int m = text1.size();
	const int n = text2.size();

	vector<vector<int>> dp(1 + n, vector<int>(1 + m, 0));
	for (int i = 1; i < n + 1; i++) {
	for (int j = 1; j < m + 1; j++) {
	if (text2[i - 1] != text1[j - 1]) {
	dp[i][j] = std::max(dp[i][j - 1], dp[i - 1][j]);
	} else {
	dp[i][j] = dp[i - 1][j - 1] + 1;
	}
	}
	}

	return dp[n][m];
	}
	};

# Longest Increasing Subsequence

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

	class Solution {
	public:
	int lengthOfLIS(const vector<int> &nums) {
	vector<int> dp(nums.size(), 1);
	for (int i = 1; i < nums.size(); i++) {
	for (int j = 0; j < i; j++) {
	if (nums[i] > nums[j]) {
	dp[i] = std::max(dp[i], dp[j] + 1);
	}
	}
	}

	return *std::max_element(dp.begin(), dp.end());
	}
	};

# 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;
	}
	};

# 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;
	}
	};

# 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 的所有格子填入 1
  - 第一個 col 的所有格子填入 1
- 每次移動只能往右、往下
  - 也就是說，抵達每個格子的方法數 = 左邊來的方法數 + 上面來的方法數

	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];
	}
	};

# Unique Paths II

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

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

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

	vector<vector<int>> dp(m, vector<int>(n));
	for (int i = 0; i < m; i++) {
	if (grid[i][0]) {
	break;
	}
	dp[i][0] = 1;
	}
	for (int j = 0; j < n; j++) {
	if (grid[0][j]) {
	break;
	}
	dp[0][j] = 1;
	}

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

# Minimum Path Sum

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

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

	vector<vector<int>> dp(m, vector<int>(n));
	dp[0][0] = grid[0][0];
	for (int i = 1; i < m; i++) {
	dp[i][0] = dp[i - 1][0] + grid[i][0];
	}
	for (int i = 1; i < n; i++) {
	dp[0][i] = dp[0][i - 1] + grid[0][i];
	}

	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
	dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
	}
	}

	return dp[m - 1][n - 1];
	}
	};

# 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();
	}
	};

# Disjoint Set / Union Find

# Redundant Connection

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

題解
- 題目給你一個 connected undirected cyclic graph，告訴了你它所有的 edges
- 只要拿掉其中一個 edge，該 graph 就會成為一個 tree (i.e. connected undirected acyclic graph)
- 你能找出該 edge 是哪一個嗎？
- 可能有多組答案，請回傳 input (edges) 中的最後一個 edge
解法
- DSU
- 從頭開始掃描所有 edges，並將每個 edge (u, v) 做 union
- union 失敗（若 u, v 本來就已經在同一組了，union 就會失敗），該 edge 就是 redundant edge，回傳之

	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 (x != parents_[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] += ranks_[px];
	} else {
	parents_[py] = px;
	ranks_[px] = ranks_[py];
	}
	return true;
	}

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

	class Solution {
	public:
	vector<int> findRedundantConnection(const vector<vector<int>> &edges) {
	UnionFind uf(1001);
	for (const auto edge_info : edges) {
	int u = edge_info[0];
	int v = edge_info[1];
	if (!uf.Union(u, v)) {
	return edge_info;
	}
	}

	return {};
	}
	};

# 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
建一個 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] += ranks_[px];
	} else {
	parents_[py] = px;
	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;
	}
	};

# Longest Consecutive Sequence

題目： https://leetcode.com/problems/longest-consecutive-sequence/
難度： Medium
語言： C++17
技巧： hash table union find

資料結構
- 用一個 unordered_map 紀錄數字出現的 idx
- 用 union find 做 group merging
解法
- 題目要求時間複雜度必須壓在 O (N)
- 掃描 nums ，對於每一個數字 n
  - 若 n - 1 曾出現過，我們就會知道它的 index，假設是 j ， uf.Union(i, j)
  - 若 n + 1 曾出現過，我們就會知道它的 index，假設是 k ， uf.Union(i, k)
- 最後只要回傳 size of the largest group 即可
分析
- 時間複雜度 O (N)
- 空間複雜度 O (N)

	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] += ranks_[px];
	} else {
	parents_[py] = px;
	ranks_[px] += ranks_[py];
	}
	return true;
	}

	const vector<int> &ranks() const { return ranks_; }

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

	class Solution {
	public:
	int longestConsecutive(const vector<int> &nums) {
	if (nums.empty()) {
	return 0;
	}

	unordered_map<int, int> num_to_idx;
	UnionFind uf(nums.size());

	for (int i = 0; i < nums.size(); i++) {
	if (num_to_idx.count(nums[i])) {
	continue;
	}

	int prev = nums[i] - 1;
	auto it_prev = num_to_idx.find(prev);
	if (it_prev != num_to_idx.end()) {
	uf.Union(i, it_prev->second);
	}

	int next = nums[i] + 1;
	auto it_next = num_to_idx.find(next);
	if (it_next != num_to_idx.end()) {
	uf.Union(i, it_next->second);
	}

	num_to_idx.emplace(nums[i], i);
	}

	return *std::max_element(uf.ranks().begin(), uf.ranks().end());
	}
	};

# Similar String Groups

題目： https://leetcode.com/problems/similar-string-groups/
難度： Hard
語言： C++17
技巧： string union find

給你 strs
- 裡面所有的 s ∈ strs 都等長，且兩兩互相為 anagrams
針對 strs 內的所有字串，兩兩檢查是否為 “similar”，其中 “similar” 的定義為：
- str1 == str2 ，或
- str1 選擇兩個 idx i 和 j ( i ≠ j )，對調 str1[i] 和 str1[j] 後會等於 str2
  - e.g. “rats” is similar to “tars” (i = 0, j = 2)
利用 str1 和 str2 必定互為 anagrams 的特性
- str1 = "aabc"
- str2 = "abac"
- 將 str1 index 0,1 的 chars 對調，即可得到 str2
- 只要檢查 number of different chars 即可確認兩個字串是否為 similar
- 不用擔心下面這種情況，因為這樣它們就不是 anagrams，所以不會發生
  - str1 = "aabc"
  - str2 = "acac"
Generate all the distinct pairs of strings from strs
- strs[i] and strs[j] , 其中 i ≠ j
- 如果 strs[i] is similar to strs[j] 就 Union (i, j)

	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 (x != parents_[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] += ranks_[px];
	} else {
	parents_[py] = px;
	ranks_[px] += ranks_[py];
	}
	return true;
	}

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

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

	class Solution {
	public:
	int numSimilarGroups(const vector<string> &strs) {
	const int n = strs.size();
	UnionFind uf(n);
	for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
	if (similar(strs[i], strs[j])) {
	uf.Union(i, j);
	}
	}
	}

	unordered_set<int> parents;
	for (const auto parent : uf.parents()) {
	parents.emplace(uf.Find(parent));
	}
	return parents.size();
	}

	private:
	bool similar(const string &s1, const string &s2) {
	int count = 0;
	for (int i = 0; i < s1.size(); i++) {
	if (s1[i] != s2[i]) {
	count++;
	}
	if (count > 2) {
	return false;
	}
	}

	return true;
	}
	};

# Checking Existence of Edge Length Limited Paths

題目： https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/
難度： Hard
語言： C++17
技巧： array sorting graph union find

題目給了
- 一個 undirected weighted graph（ n 個 vertices 和 edgeList ）
- 一串 queries ，其中每個 query = (p, q, limit)
  - p , q 分別代表 source vertex 和 destination vertex
  - limit 代表 weight limit
  - 如果 graph 中存在一條 path，且 path 上的所有 edge 的 weight 都小於 limit ，該 query 的結果就是 true
解法一：Undirected graph single-source BFS (TLE)
- 暴力解
- 路上有小於 weight limit 的路就 push 到 queue
- BFS 過程中若走到了，該 query 的結果為 true
- 若 queue empty 了就代表走不到，該 query 的結果為 false
解法二：Union find (AC)
- 將 edgeList 根據 weight 升冪排序
- 將 queries 根據 weight limit 升冪排序
- 開一個 edgeList 的 index i ，初始化為 0
- 掃描 queries
  - 從 edgeList[i] 開始檢查，如果 edgeList[i].weight 還沒超過 current query 的 weight limit
    - 將 edgeList[i].u 和 edgeList[i].v 做 union
  - current query 的兩個 vertex 是否屬於同個 group?
    - 是，此次 query 的結果為 true
    - 否，此次 query 的結果為 false
- 問題來了，上面這樣的作法會導致 results 的順序是錯的，因為我們直接對 queries 排序，破壞它的順序了 QQ
  - 解法：另外開一個 vector 存 [0, queries.size() - 1] ，然後根據 weight limit 排序這些 indices

	// 解法一 (TLE)
	class Solution {
	public:
	vector<bool> distanceLimitedPathsExist(int n,
	const vector<vector<int>> &edgeList,
	const vector<vector<int>> &queries) {
	using T = pair<int, int>; // dist, vertex
	vector<priority_queue<T, vector<T>, greater<T>>> adjacency_pq(n);
	for (const auto &edge : edgeList) {
	int dist = edge[2];
	int u = edge[0];
	int v = edge[1];
	adjacency_pq[u].emplace(dist, v);
	adjacency_pq[v].emplace(dist, u);
	}

	vector<vector<pair<int, int>>> adjacency_list(n);
	for (int i = 0; i < adjacency_pq.size(); i++) {
	auto &pq = adjacency_pq[i];
	while (pq.size()) {
	adjacency_list[i].emplace_back(pq.top());
	pq.pop();
	}
	}

	vector<bool> results;
	for (const auto &query : queries) {
	int src = query[0];
	int dst = query[1];
	if (src == dst) {
	results.emplace_back(true);
	continue;
	}

	bool success = false;
	queue<tuple<int, int, int>> q; // curr vertex, dest vertex, edge_dist_limit
	unordered_set<int> visited;
	int edge_dist_limit = query[2];
	q.emplace(src, dst, edge_dist_limit);

	while (q.size()) {
	auto [curr_vertex, dest_vertex, edge_dist_limit] = q.front();
	q.pop();

	if (curr_vertex == dest_vertex) {
	results.emplace_back(true);
	success = true;
	break;
	}
	visited.emplace(curr_vertex);

	for (const auto &[edge_dist, neighbor] : adjacency_list[curr_vertex]) {
	if (edge_dist < edge_dist_limit && !visited.count(neighbor)) {
	q.emplace(neighbor, dest_vertex, edge_dist_limit);
	visited.emplace(neighbor);
	}
	}
	}

	if (!success) {
	results.emplace_back(false);
	}
	}

	return results;
	}
	};

	// 解法二 (AC)
	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 (x != parents_[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] += ranks_[px];
	} else {
	parents_[py] = px;
	ranks_[px] += ranks_[py];
	}
	return true;
	}

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

	class Solution {
	public:
	vector<bool> distanceLimitedPathsExist(int n,
	vector<vector<int>> &edgeList,
	vector<vector<int>> &queries) {
	std::sort(edgeList.begin(),
	edgeList.end(),
	[](const vector<int> &e1, const vector<int> &e2) {
	return e1[2] < e2[2];
	});

	vector<int> query_indices(queries.size());
	for (int i = 0; i < queries.size(); i++) {
	query_indices[i] = i;
	}
	std::sort(query_indices.begin(),
	query_indices.end(),
	[&](const int i1, const int i2) {
	return queries[i1][2] < queries[i2][2];
	});

	vector<bool> results(queries.size());
	UnionFind uf(n);
	int i = 0;

	for (const auto query_idx : query_indices) {
	const auto &query = queries[query_idx];
	while (i < edgeList.size() && edgeList[i][2] < query[2]) {
	uf.Union(edgeList[i][0], edgeList[i][1]);
	i++;
	}
	results[query_idx] = uf.Find(query[0]) == uf.Find(query[1]);
	}

	return results;
	}
	};

# Intervals

# 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;
	}
	};

# Insert Interval

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

暴力解：
- 將 new_interval append 到 intervals 並根據左界進行 ascending sort
- 將此問題 reduce 成 Merge Intervals（見 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;
	}
	};

# Non-Overlapping Intervals

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

給你一串 intervals，從中移除 n 個 intervals 可以使得剩餘者無 overlapped，求 n 的最小值
Greedy
- 當發現兩個 intervals 之間有 overlapped 時，我們要優先移除右界較大者
- 如此一來，才能減低與下一個 interval 又發生 overlap 的機率
解法
- 由於題目沒特別說 intervals 會排序，所以我們先將它按左界排序（左界相同再比右界）
- last_interval 代表 last non-overlapped interval
- 掃一次 intervals（跳過第 0 個，從第 1 個開始掃）
  - 若 current interval 和 last_interval 無 overlapped，更新 last_interval 為 current interval
  - 若有 overlapped
    - 我們勢必得移除一個 interval， num_overlapped++
    - 優先移除右界較大者，所以將 current interval 與 last_interval 右界較小者留下，放到 last_interval
考慮下列情況，用上述算法 dry run 一下，是不是只要移除最下面那條就行了呢 o(^▽^)o
```
     *------*  *--*  *-----*     *---------*
   *---------------------------------*
```

	class Solution {
	public:
	int eraseOverlapIntervals(vector<vector<int>> &intervals) {
	std::sort(intervals.begin(),
	intervals.end(),
	[](const vector<int> &i1, const vector<int> &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<int> last_interval = intervals.front();
	int num_overlapped = 0;
	for (int i = 1; i < intervals.size(); i++) {
	const auto &interval = intervals[i];
	if (last_interval[1] <= interval[0]) { // not overlapped
	last_interval = interval;
	} else {
	if (last_interval[1] > interval[1]) {
	last_interval = interval;
	}
	num_overlapped++;
	}
	}

	return num_overlapped;
	}
	};

# Segment Tree (Interval Tree)

# Range Sum Query - Mutable

題目： https://leetcode.com/problems/range-sum-query-mutable/
難度： Medium
語言： C++17
技巧： array segment tree

題解
- 給你一個 mutable int array，假設是： nums = [-2, 0, 3, -5, 2, -1]
- 之後會有數次交錯的 update 與 query
  - update: nums[index] = value
  - query: 給你一個 left 和 right ，求 sum(nums[left:right+1])
解法：segment tree
- internal nodes 代表區間的 sum，leaf nodes 代表 input array 的各個 elements
- 建立 segment tree：時間複雜度 O (N)
- 更新 segment tree 中的某個 leaf：時間複雜度 O (logN)
- 查詢 segment tree 中的某個區間的 sum：時間複雜度 O (logN)
參考
- https://jojozhuang.github.io/algorithm/data-structure-segment-tree/

	class SegmentTree {
	struct Node {
	int begin;
	int end;
	int sum;
	unique_ptr<Node> left;
	unique_ptr<Node> right;
	};

	public:
	SegmentTree(const vector<int> &nums)
	: root_(buildSegmentTree(nums, 0, nums.size() - 1)) {}

	void update(int index, int val) {
	update(root_.get(), index, val);
	}

	int query(int l, int r) const {
	return query(root_.get(), l, r);
	}

	private:
	unique_ptr<Node> buildSegmentTree(const vector<int> &nums, int l, int r) {
	if (l > r) {
	return nullptr;
	}

	unique_ptr<Node> new_node(new Node{l, r, 0, nullptr, nullptr});
	if (l == r) {
	new_node->sum = nums[l];
	return new_node;
	}

	int m = l + (r - l) / 2;
	new_node->left = buildSegmentTree(nums, l, m);
	new_node->right = buildSegmentTree(nums, m + 1, r);
	new_node->sum = (new_node->left ? new_node->left->sum : 0) +
	(new_node->right ? new_node->right->sum : 0);
	return new_node;
	}

	void update(Node *node, int index, int val) {
	if (!node) {
	return;
	}

	if (node->begin == index && node->end == index) {
	node->sum = val;
	return;
	}

	int m = node->begin + (node->end - node->begin) / 2;
	if (index <= m) {
	update(node->left.get(), index, val);
	} else {
	update(node->right.get(), index, val);
	}

	node->sum = (node->left ? node->left->sum : 0) +
	(node->right ? node->right->sum : 0);
	}

	int query(Node *node, int l, int r) const {
	if (!node) {
	return 0;
	}

	if (node->begin == l && node->end == r) {
	return node->sum;
	}

	int m = node->begin + (node->end - node->begin) / 2;
	if (r <= m) {
	return query(node->left.get(), l, r);
	} else if (l > m) {
	return query(node->right.get(), l, r);
	} else {
	return query(node->left.get(), l, m) +
	query(node->right.get(), m + 1, r);
	}
	}

	unique_ptr<Node> root_;
	};

	class NumArray {
	public:
	NumArray(const vector<int> &nums)
	: segment_tree_(nums) {}

	void update(int index, int val) {
	segment_tree_.update(index, val);
	}

	int sumRange(int left, int right) {
	return segment_tree_.query(left, right);
	}

	private:
	SegmentTree segment_tree_;
	};

# Math

# Add Digits

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

	class Solution {
	public:
	int addDigits(int num) {
	if (num < 10) {
	return num;
	}

	int sum = 0;
	while (num) {
	sum += num % 10;
	num /= 10;
	}
	return addDigits(sum);
	}
	};

# Palindrome Number

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

根據題目定義
- 121 倒過來讀還是 121 ，是 palindrome
- -121 倒過來讀是 121- ，不是 palindrome
所以只要是負數，就直接 return false
大於等於 0 的話，reverse integer 後和原數字比較是否相同即可

	class Solution {
	public:
	bool isPalindrome(int x) {
	if (x < 0) {
	return false;
	}

	uint32_t original_x = x;
	uint32_t reversed_x = 0;

	while (x) {
	reversed_x *= 10;
	reversed_x += x % 10;
	x /= 10;
	}

	return original_x == reversed_x;
	}
	};

# Roman to Integer

題目： https://leetcode.com/problems/roman-to-integer/
難度： Easy
語言： C++17
技巧： math

	class Solution {
	public:
	int romanToInt(const string &s) {
	int ret = 0;
	for (int i = 0; i < s.size(); i++) {
	if (i == s.size() - 1) {
	ret += toVal(s[i]);
	} else if (s[i] == 'I' && s[i + 1] == 'V') {
	ret += 4;
	i++;
	} else if (s[i] == 'I' && s[i + 1] == 'X') {
	ret += 9;
	i++;
	} else if (s[i] == 'X' && s[i + 1] == 'L') {
	ret += 40;
	i++;
	} else if (s[i] == 'X' && s[i + 1] == 'C') {
	ret += 90;
	i++;
	} else if (s[i] == 'C' && s[i + 1] == 'D') {
	ret += 400;
	i++;
	} else if (s[i] == 'C' && s[i + 1] == 'M') {
	ret += 900;
	i++;
	} else {
	ret += toVal(s[i]);
	}
	}
	return ret;
	}

	private:
	int toVal(const char c) {
	switch (c) {
	case 'I':
	return 1;
	case 'V':
	return 5;
	case 'X':
	return 10;
	case 'L':
	return 50;
	case 'C':
	return 100;
	case 'D':
	return 500;
	case 'M':
	return 1000;
	default:
	return 0;
	}
	}
	};

# Reverse Integer

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

	class Solution {
	public:
	int reverse(int x) {
	int ret = 0;
	while (x) {
	if (x > 0 && ret > std::numeric_limits<int>::max() / 10) {
	return 0;
	}
	if (x < 0 && ret < std::numeric_limits<int>::lowest() / 10) {
	return 0;
	}
	ret *= 10;

	if (x > 0 && ret > std::numeric_limits<int>::max() - x % 10) {
	return 0;
	}
	if (x < 0 && ret < std::numeric_limits<int>::lowest() - x % 10) {
	return 0;
	}
	ret += x % 10;

	x /= 10;
	}
	return ret;
	}
	};

# Missing Number

題目： https://leetcode.com/problems/missing-number/
難度： Medium
語言： C++17
技巧： math

題目給你一串數字，由 [0, n] 這個範圍內的數字，但是其中一個被拿掉了，你能找到是誰嗎？
梯形公式可以算出此範圍內的 expected sum，扣掉 actual sum 就是該數字。

	class Solution {
	public:
	int missingNumber(const vector<int> &nums) {
	int n = nums.size();
	int expected_sum = (0 + n) * (n + 1) / 2;
	int actual_sum = std::accumulate(nums.begin(), nums.end(), 0);
	return expected_sum - actual_sum;
	}
	};

# Rotate Array

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

[1,2,3,4,5,6,7], k = 3

反轉全部: [7,6,5,4,3,2,1]
反轉左邊: [6,7,5,4,3,2,1]
           ^ ^
反轉右邊: [6,7,1,2,3,4,5]
               ^ ^ ^ ^ ^

	class Solution {
	public:
	void rotate(vector<int> &nums, int k) {
	k %= nums.size();
	if (k == 0) {
	return;
	}

	std::reverse(nums.begin(), nums.end());
	std::reverse(nums.begin(), nums.begin() + k);
	std::reverse(nums.begin() + k, nums.end());
	}
	};

# Rotate Image

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

Transpose (行列交換)
Reverse each row

	class Solution {
	public:
	void rotate(vector<vector<int>> &matrix) {
	// transpose: swap row and col
	const int n = matrix.size();
	for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
	std::swap(matrix[i][j], matrix[j][i]);
	}
	}

	for (auto &row : matrix) {
	std::reverse(row.begin(), row.end());
	}
	}
	};

# Simulation

# 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);
	}
	};