// Minimum Path Sum
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty())
return 0;
const int n = grid.size(), m = grid[0].size();
int f[n][m];
f[0][0] = grid[0][0];
for (int i = 1; i < n; i++)
f[i][0] = f[i - 1][0] + grid[i][0];
for (int j = 1; j < m; j++)
f[0][j] = f[0][j - 1] + grid[0][j];
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
return f[n - 1][m - 1];
}
// Minimum Two Path Sum
// Consider diagonal DP
// Search in Rotated Sorted Array
int search(vector<int>& nums, int target) {
if (nums.empty())
return -1;
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[low] <= nums[mid]) {
if (nums[mid] > target && nums[low] <= target)
high = mid - 1;
else
low = mid + 1;
} else {
if (nums[mid] < target && nums[high] >= target)
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
// Search in Rotated Sorted Array II
bool search(vector<int>& nums, int target) {
if (nums.empty())
return false;
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[low] < nums[mid]) {
if (nums[mid] > target && nums[low] <= target)
high = mid - 1;
else
low = mid + 1;
} else if (nums[low] > nums[mid]) {
if (nums[mid] < target && nums[high] >= target)
low = mid + 1;
else
high = mid - 1;
} else {
low++;
}
}
return false;
}
// Copy List with Random Pointer (LeetCode)
RandomListNode *copyRandomList(RandomListNode *head) {
if (head == NULL)
return NULL;
unordered_map<RandomListNode*, RandomListNode*> cache;
RandomListNode dummy(-1);
RandomListNode *p = head, *q = &dummy;
while (p) {
q->next = new RandomListNode(p->label);
q = q->next;
cache[p] = q;
p = p->next;
}
p = head;
while (p) {
if (p->random)
cache[p]->random = cache[p->random];
p = p->next;
}
return dummy.next;
}
// Binary Tree Level Order Traversal
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q, p;
vector<vector<int>> res;
if (root)
q.push(root);
while (!q.empty()) {
vector<int> level;
while (!q.empty()) {
level.push_back(q.front()->val);
if (q.front()->left)
p.push(q.front()->left);
if (q.front()->right)
p.push(q.front()->right);
q.pop();
}
swap(p, q);
res.push_back(level);
}
return res;
}
// Divide Two Integers
// Divide two integers without using multiplication, division and mod operator.
// If it is overflow, return MAX_INT.
// O((log n)^2)
int divide(int dividend, int divisor) {
if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) // Overflow
return INT_MAX;
bool negative = (divisor > 0) ^ (dividend > 0);
long long dvd = dividend, dvs = divisor;
dvd = abs(dvd); dvs = abs(dvs);
int res = 0;
while (dvd >= dvs) {
long long temp = dvs;
int mutiple = 1;
while (dvd >= (temp << 1)) {
temp <<= 1;
mutiple <<= 1;
}
dvd -= temp;
res += mutiple;
}
return negative ? -res : res;
}
// O(1)
int divide(int dividend, int divisor) {
if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) // Overflow
return INT_MAX;
bool negative = (divisor > 0) ^ (dividend > 0);
// Transform to unsigned int
unsigned int dvd = (dividend > 0) ? dividend : -dividend;
unsigned int dvs = (divisor > 0) ? divisor : -divisor;
// Shift W (= 32) times
const int W = sizeof(int) * 8;
int res = 0;
for (int i = W - 1; i >= 0; i--) {
if ((dvd >> i) >= dvs) { // dvd >= 2^i * dvs
res = (res << 1) | 1; // res = 2 * res + 1
dvd -= (dvs << i);
} else
res <<= 1; // res = 2 * res
}
return negative ? -res : res;
}
// Regular Expression Matching
// Implement regular expression matching with support for '.' and '*'.
// '.' Matches any single character.
// '*' Matches zero or more of the preceding element.
bool isMatch(string s, string p) {
if (p.empty())
return s.empty();
if (p.size() > 1 && p[1] == '*') {
return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
} else {
return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}
}
// Dynamic Programming
bool isMatch(string s, string p) {
// f[i][j]: if s[0..i-1] matches p[0..j-1]
int m = s.size(), n = p.size();
vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
f[0][0] = true;
for (int i = 1; i <= m; i++)
f[i][0] = false;
for (int j = 2; j <= n; j++)
f[0][j] = (p[j - 1] == '*' && f[0][j - 2]);
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= m; i++) {
if (p[j - 1] == '*')
f[i][j] = f[i][j - 2] || (f[i - 1][j] && (p[j - 2] == '.' || s[i - 1] == p[j - 2]));
else
f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
}
}
return f[m][n];
}
// Wildcard Matching
// Implement wildcard pattern matching with support for '?' and '*'.
// '?' Matches any single character.
// '*' Matches any sequence of characters (including the empty sequence).
// Time Limit Exceeded
bool isMatch(const string& s, const string& p) {
if (p.empty())
return s.empty();
if (p[0] == '*')
return isMatch(s, p.substr(1)) || (!s.empty() && isMatch(s.substr(1), p));
return !s.empty() && (p[0] == '?' || s[0] == p[0]) && isMatch(s.substr(1), p.substr(1));
}
// Time Limit Exceeded
bool isMatch(const string& s, const string& p) {
if (p.empty())
return s.empty();
if (p[0] == '*') {
int i = 1;
while (i < p.size() && p[i] == '*')
i++; // Skip continous '*'
return isMatch(s, p.substr(i)) || (!s.empty() && isMatch(s.substr(1), p));
}
return !s.empty() && (p[0] == '?' || s[0] == p[0]) && isMatch(s.substr(1), p.substr(1));
}
// Dynamic Programming
bool isMatch(string s, string p) {
// f[i][j]: is s[0..i-1] matches p[0..j-1]
int m = s.size(), n = p.size();
vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
f[0][0] = true;
for (int i = 1; i <= m; i++)
f[i][0] = false;
for (int j = 1; j <= n; j++)
f[0][j] = p[j - 1] == '*' && f[0][j - 1];
for (int j = 1; j <= n; j++)
for (int i = 1; i <= m; i++)
if (p[j - 1] == '*')
f[i][j] = f[i][j - 1] || f[i - 1][j];
else
f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
return f[m][n];
}
// Longest Consecutive Sequence
// Union-Find
int longestConsecutive(vector<int>& nums) {
vector<int> parent(nums.size(), -1), rank(nums.size(), 1);
unordered_map<int, int> cache;
for (int i = 0; i < nums.size(); i++) {
cache[nums[i]] = i;
}
for (auto iter = cache.begin(); iter != cache.end(); iter++) {
int num = iter->first;
if (cache.find(num + 1) != cache.end())
Union(parent, rank, iter->second, cache[num + 1]);
}
int max_length = 0;
for (int r : rank)
max_length = max(max_length, r);
return max_length;
}
int find(vector<int>& parent, int i) {
if (parent[i] == -1)
return i;
parent[i] = find(parent, parent[i]); // uses path compression technique
return parent[i];
}
void Union(vector<int>& parent, vector<int>& rank, int i, int j) {
// can't use the function name union(), union is a c++ keyword
int x = find(parent, i);
int y = find(parent, j);
if (x != y) {
if (rank[x] <= rank[y]) {
parent[x] = y;
rank[y] += rank[x];
}
else {
parent[y] = x;
rank[x] += rank[y];
}
}
}
// 哈希表 只更新线段端点的长度
int longestConsecutive(vector<int>& nums) {
int max_length = 0;
unordered_map<int, int> sequence; // pair (num, length)
for (int num : nums) {
if (sequence.find(num) != sequence.end())
continue;
int left = (sequence.find(num - 1) != sequence.end()) ? sequence[num - 1] : 0;
int right = (sequence.find(num + 1) != sequence.end()) ? sequence[num + 1] : 0;
int length = 1 + left + right;
sequence[num] = length;
sequence[num - left] = length;
sequence[num + right] = length;
max_length = max(max_length, length);
}
return max_length;
}
// Edit Distance
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
int D[m + 1][n + 1];
for (int i = 0; i <= m; i++)
D[i][0] = i;
for (int j = 1; j <= n; j++)
D[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1])
D[i][j] = min(min(D[i - 1][j] + 1, D[i][j - 1] + 1), D[i - 1][j - 1]);
else
D[i][j] = min(min(D[i - 1][j] + 1, D[i][j - 1] + 1), D[i - 1][j - 1] + 1);
}
}
return D[m][n];
}
// Populating Next Right Pointers in Each Node II
// 既然上一层的节点已经通过next指针连起来了，那么就只要能得到上一层的第一个节点就可以依次把上一层节点的子节点串联起来了
// 通过添加一个dummy假节点来标记当前行的首节点
void connect(TreeLinkNode *root) {
while (root) {
TreeLinkNode dummy(-1);
TreeLinkNode *p = &dummy, *q = root;
while (q) {
if (q->left) {
p->next = q->left;
p = p->next;
}
if (q->right) {
p->next = q->right;
p = p->next;
}
q = q->next;
}
root = dummy.next;
}
}
// Binary Search Tree Iterator
// In-order Traveral Binary Tree Iterator
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
TreeNode *p = root;
while (p) {
s.push(p);
p = p->left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !s.empty();
}
/** @return the next smallest number */
int next() {
int res = s.top()->val;
TreeNode *p = s.top()->right;
if (p) {
while (p) {
s.push(p);
p = p->left;
}
} else {
p = s.top();
s.pop();
while (!s.empty() && p == s.top()->right) {
p = s.top();
s.pop();
}
}
return res;
}
private:
stack<TreeNode*> s;
};
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
TreeNode *p = root;
while (p) {
s.push(p);
p = p->left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !s.empty();
}
/** @return the next smallest number */
int next() {
int res = s.top()->val;
TreeNode *p = s.top()->right;
s.pop();
while (p) {
s.push(p);
p = p->left;
}
return res;
}
private:
stack<TreeNode*> s;
};
// Kth Largest Element in an Array
// Sort
// O(N lg N) running time + O(1) memory
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
// Use a min oriented priority queue storing the K-th largest values
// O(N lg K) running time + O(K) memory
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minpq;
for (int i = 0; i < k; i++)
minpq.push(nums[i]);
for (int i = k; i < nums.size(); i++)
if (nums[i] > minpq.top()) {
minpq.pop();
minpq.push(nums[i]);
}
return minpq.top();
}
};
// Use the selection algorithm (based on the partion method - the same one as used in quicksort)
// O(N) best case / O(N^2) worst case / amortized O(N) running time + O(1) memory
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
random_shuffle(nums.begin(), nums.end());
k = nums.size() - k;
int low = 0, high = nums.size() - 1;
while (low < high) {
int mid = partition(nums, low, high);
if (mid < k)
low = mid + 1;
else if (mid > k)
high = mid - 1;
else
break;
}
return nums[k];
}
int partition(vector<int>& nums, int low, int high) {
int pivot = nums[low], i = low;
// nums[0..i] <= pivot, nums[i+1..j-1] > pivot, nums[j..n-1] unknown
for (int j = low + 1; j <= high; j++) {
if (nums[j] <= pivot)
swap(nums[++i], nums[j]);
}
swap(nums[low], nums[i]);
return i;
}
};
// Minimum Window Substring
// Hash Table + Two Pointers + String
string minWindow(string s, string t) {
string res = "";
unordered_map<char, int> pattern, window;
int count = 0, min_window = INT_MAX;
for (char c : t)
pattern[c]++;
for (int start = 0, end = 0; end < s.size(); end++) {
char c = s[end];
if (pattern.find(c) != pattern.end()) {
window[c]++;
if (window[c] <= pattern[c])
count++;
if (count == t.size()) {
while (pattern.find(s[start]) == pattern.end() || window[s[start]] > pattern[s[start]]) {
if (pattern.find(s[start]) != pattern.end())
window[s[start]]--;
start++;
}
if (end - start + 1 < min_window) {
min_window = end - start + 1;
res = s.substr(start, min_window);
}
}
}
}
return res;
}
// Longest Substring Without Repeating Characters
// Hash Table + Two Pointers + String
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> cache;
int start = 0, max_length = 0;
for (int end = 0; end < s.size(); end++) {
if (cache.find(s[end]) == cache.end() || cache[s[end]] < start) {
cache[s[end]] = end;
max_length = max(max_length, end - start + 1);
} else {
start = cache[s[end]] + 1;
cache[s[end]] = end;
max_length = max(max_length, end - start + 1);
}
}
return max_length;
}
};
// Decode Ways
int numDecodings(string s) {
if (s.empty() || s[0] == '0')
return 0;
vector<int> f(s.size() + 1);
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= s.size(); i++) {
if (s[i - 1] == '0') {
if (!(s[i - 2] == '1' || s[i - 2] == '2'))
return 0;
f[i] = f[i - 2];
} else if (s[i - 1] >= '1' && s[i - 1] <= '6') {
f[i] = ((s[i - 2] == '1' || s[i - 2] == '2') ? (f[i - 1] + f[i - 2]) : f[i - 1]);
} else {
f[i] = ((s[i - 2] == '1') ? (f[i - 1] + f[i - 2]) : f[i - 1]);
}
}
return f[s.size()];
}
// LCA of Binary Tree
// Find the paths to p and q and then find the last node where the paths match
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q)
return root;
vector<TreeNode*> path_p, path_q;
dfs(root, p, q, {}, path_p, path_q);
int i = 0;
while (path_p[i] == path_q[i])
i++;
return path_p[i - 1];
}
void dfs(TreeNode* root, TreeNode* p, TreeNode* q, vector<TreeNode*> path, vector<TreeNode*> &path_p, vector<TreeNode*> &path_q) {
if (root == NULL)
return;
path.push_back(root);
if (root == p)
path_p = path;
if (root == q)
path_q = path;
dfs(root->left, p, q, path, path_p, path_q);
dfs(root->right, p, q, path, path_p, path_q);
}
TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == NULL || root == p || root == q)
return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l != NULL && r != NULL)
return root;
if (l != NULL)
return l;
return r;
}
// Task Scheduler
int leastInterval(vector<char>& tasks, int n) {
vector<int> count(26);
for (char c : tasks)
count[c - 'A']++;
sort(count.begin(), count.end());
int timer = 0;
while (count[25] > 0) {
for (int i = 0, j = 25; i < n + 1; i++, j--) {
if (j >= 0 && count[j] > 0)
count[j]--;
else if (count[25] == 0)
break;
timer++;
}
sort(count.begin(), count.end());
}
return timer;
}
int leastInterval(vector<char>& tasks, int n) {
int count[26];
for (int i = 0; i < 26; i++)
count[i] = 0;
for (char c : tasks)
count[c - 'A']++;
sort(count, count + 26, greater<int>()); // sort in decreasing order
int timer = 0;
int j = 25;
while (j >= 0 && count[j] == 0)
j--;
while (j >= 0) {
timer += ((j >= n || count[0] > 1) ? n + 1 : j + 1); // j + 1 means #tasks left
for (int i = 0; i <= j && i < n + 1; i++)
count[i]--;
sort(count, count + j + 1, greater<int>());
while (j >= 0 && count[j] == 0)
j--;
}
return timer;
}
// Combination Sum
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<vector<int>>> sums(1 + target);
sums[0] = vector<vector<int>>(1); // sums[0].push_back(vector<int>());
for (int num : candidates) {
for (int i = num; i <= target; i++) {
vector<vector<int>> copy(sums[i - num].begin(), sums[i - num].end());
for (int j = 0; j < copy.size(); j++)
copy[j].push_back(num);
sums[i].insert(sums[i].end(), copy.begin(), copy.end());
}
}
return sums[target];
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> path;
combinationSum(0, candidates, target, path, res);
return res;
}
void combinationSum(int i, vector<int>& candidates, int target, vector<int> &path, vector<vector<int>> &res) {
if (i == candidates.size()) {
if (target == 0)
res.push_back(path);
return;
}
for (int num = 0; num <= target; num += candidates[i]) {
combinationSum(i + 1, candidates, target - num, path, res);
path.push_back(candidates[i]);
}
for (int num = 0; num <= target; num += candidates[i])
path.pop_back();
}
// Flatten Binary Tree to Linked List
void flatten(TreeNode* root) {
TreeNode *p = root;
stack<TreeNode*> s;
while (p) {
if (p->right)
s.push(p->right);
if (p->left) {
p->right = p->left;
p->left = NULL;
} else if (!s.empty()) {
p->right = s.top();
s.pop();
}
p = p->right;
}
}
// Reverse Words in a String
// Given an input string, reverse the string word by word.
// For example, given s = "the sky is blue", return "blue is sky the".
// For C programmers: Try to solve it in-place in O(1) space.
/* Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
*/
void reverseWords(string &s) {
vector<string> words;
string cur = "";
for (char c : s) {
if (c == ' ') {
if (cur != "")
words.push_back(cur);
cur = "";
} else {
cur += c;
}
}
if (cur != "")
words.push_back(cur);
if (words.empty()) {
s = "";
return;
}
reverse(words.begin(), words.end());
s = words[0];
for (int i = 1; i < words.size(); i++)
s += (' ' + words[i]);
}
// In place simple solution
// First, reverse the whole string, then reverse each word.
void reverseWords(string &s) {
// i: the beginning of one word, j: the end of one word(including one trailing space)
// k: the current position available for insertion
reverse(s.begin(), s.end());
int i = 0, j, k = 0;
while (i < s.size() && s[i] == ' ')
i++;
while (i < s.size()) {
if (k != 0)
s[k++] = ' ';
j = i;
while(j < s.size() && s[j] != ' ')
s[k++] = s[j++];
reverse(s.begin() + k - (j - i), s.begin() + k);
i = j + 1;
while (i < s.size() && s[i] == ' ')
i++;
}
s.erase(s.begin() + k, s.end()); // s.erase(k);
}
// Kth Smallest Element in a Sorted Matrix
// Heap
struct Element {
int i, j, num;
Element(int i, int j, int num): i(i), j(j), num(num) {}
bool operator< (const Element &other) const {
return num > other.num;
}
};
int kthSmallest(vector<vector<int>>& matrix, int k) {
const int n = matrix.size(), m = matrix[0].size();
priority_queue<Element> pq;
for (int i = 0; i < n; i++)
pq.push(Element(i, 0, matrix[i][0]));
for (int ii = 0; ii < k - 1; ii++) {
Element e = pq.top();
pq.pop();
if (e.j + 1 < m)
pq.push(Element(e.i, e.j + 1, matrix[e.i][e.j + 1]));
}
return pq.top().num;
}
// Binary Search
int kthSmallest(vector<vector<int>>& matrix, int k) {
// Find the smallest number num which #{numbers in the matrix <= num} >= k
const int n = matrix.size(), m = matrix[0].size();
int low = matrix[0][0], high = matrix[n - 1][m - 1];
while (low < high) {
int mid = low + (high - low) / 2;
int count = 0, i = n - 1, j = 0;
while (i >= 0 && j < m) {
if (matrix[i][j] <= mid) {
count += (i + 1);
j++;
} else {
i--;
}
}
if (count >= k)
high = mid;
else
low = mid + 1;
}
return low;
}
// Largest Rectangle in Histogram
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
heights.push_back(0);
int max_sum = 0, i = 0;
while (i < heights.size()) {
if (s.empty() || heights[i] > heights[s.top()]) {
s.push(i);
i++;
} else {
int j = s.top();
s.pop();
max_sum = max(max_sum, heights[j] * (s.empty() ? i : (i - 1 - s.top())));
}
}
return max_sum;
}
