# Leetcode summary of 20200217-20200223

Posted by chunyang on February 24, 2020

### Summary

Solved problems list

• 393. UTF-8 Validation
• 200. Number of Islands
• 138. Copy List with Random Pointer
• 148. Sort List
• 154. Find Minimum in Rotated Sorted Array II
• 153. Find Minimum in Rotated Sorted Array
• 150. Evaluate Reverse Polish Notation
• 130. Surrounded Regions
• 117. Populating Next Right Pointers in Each Node II
• 103. Binary Tree Zigzag Level Order Traversal
• 116. Populating Next Right Pointers in Each Node
• 1352. Product of the Last K Numbers
• 1347. Minimum Number of Steps to Make Two Strings Anagram
• 79. Word Search
• 80. Remove Duplicates from Sorted Array II
• 96. Unique Binary Search Trees
• 109. Convert Sorted List to Binary Search Tree
• 98. Validate Binary Search Tree
• 1025. Divisor Game
• 1071. Greatest Common Divisor of Strings
• 1114. Print in Order
• 748. Shortest Completing Word
• 733. Flood Fill
• 836. Rectangle Overlap
• 999. Available Captures for Rook
• 1033. Moving Stones Until Consecutive
• 1103. Distribute Candies to People
• 942. DI String Match
• 888. Fair Candy Swap
• 806. Number of Lines To Write String
• 690. Employee Importance
• 884. Uncommon Words from Two Sentences
• 976. Largest Perimeter Triangle
• 1351. Count Negative Numbers in a Sorted Matrix

### Highlight

#### DFS or BFS

Be careful about the visited status when using DFS or BFS. Otherwise, you may get stuck in a dead loop.

#### Implementation

• 0 started string is not valid.
• UTF-8 Validation
• Sometimes manipulating numbers is more convenient than bits.

#### Rotated sorted array

There are two searching problems and two finding problems about rotated sorted arrays.

The key point is that: you need to know which one (the left or the right part) is an increasing sequence.

Finding the minimum element is a little tricky here. You havee to exit when you find targeting pattern, otherwise it is not easy to tell the result when you leave the loop.

Double check here

### Code Section

The sequence of code is the same with the problem list.

// 393. UTF-8 Validation
// https://leetcode.com/problems/utf-8-validation/
class Solution {
public:
bool validUtf8(vector<int>& data) {
if (data.empty()) return false;
int size = data.size();
function<bool(int, int)> valid = [&](int i, int n) {
if ((size - i - 1) < n) return false;
int j = i + 1;
while (j <= i + n) {
if (data[j] < 128 || data[j] > 191) return false;
++j;
}
return true;
};
for (int i = 0; i < size; ++i) {
if (data[i] < 128) continue;
else if (data[i] <= 247 && data[i] >= 240) {
// three
bool res = valid(i, 3);
if (!res) return res;
i = i + 3;
} else if (data[i] >= 224 && data[i] <=239) {
// two
bool res = valid(i, 2);
if (!res) return res;
i = i + 2;
} else if (data[i] >= 192 && data[i] <= 223) {
// one
bool res = valid(i, 1);
if (!res) return res;
i = i + 1;
} else {
return false;
}
}
return true;
}
};
// 200. Number of Islands
// https://leetcode.com/problems/number-of-islands/
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if (grid.empty()) return 0;
int n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
function<int(int, int)> dfs = [&](int r, int c) {
if (r >= m || r < 0) return 0;
if (c >= n || c < 0) return 0 ;
if (visited[r][c] || grid[r][c] == '0') return 0;
visited[r][c] = true;
r+1 < m ? dfs(r+1, c) : 0;
r > 0 ? dfs(r-1, c) : 0;
c+1 < n ? dfs(r, c+1): 0;
c > 0 ? dfs(r, c-1): 0;
return 0;

};
int cnt = 0;
// cout << "---------" << endl;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// cout << "visited[i][j]: " << visited[i][j] << endl;
if (visited[i][j] || grid[i][j] == '0') continue;
// cout << "i: " << i << " j: " << j << " grid[i][j]: " <<  grid[i][j] << endl;
dfs(i, j);
++cnt;
}
}
return cnt;
}
};
// 138. Copy List with Random Pointer
// https://leetcode.com/problems/copy-list-with-random-pointer/
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
// cout << "valxx: " << head->val <<endl;
node->next = next;
}
// cout << "h->val: " << h->val <<endl;
// p(h);
// cout << "XXX" << endl;
}
Node e(0), o(0);
auto even = &e;
auto odd = &o;
odd = odd->next;
odd->next = nullptr;
even->next = next;
even = even->next;
even->next = nullptr;
}
even->next = nullptr;
odd->next = nullptr;
//vp(e.next);p(o.next);
return e.next;
}
void p(Node* n) {
cout << "val = ";
while (n) {
cout << n->val << ",";
n = n->next;
}
cout << "。" << endl;
}
};
// 148. Sort List
// https://leetcode.com/problems/sort-list/
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
function<ListNode*(ListNode*, ListNode*)> merge = [](
ListNode* l, ListNode* r
) {
if (!l) return r;
if (!r) return l;
ListNode dummy(0); ListNode* head = &dummy;
while (l || r) {
if (!l) {
r = r->next;
} else if (!r) {
l = l->next;
} else {
if (l->val < r->val) {
l = l->next;
} else {
r = r->next;
}
}
}
return dummy.next;
};
function<ListNode*(ListNode*)> mid = [](ListNode* node) {
if (!node || !node->next) return node;
auto slow = node;
auto fast = node->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
};
// cout << "mid: " << m->val << endl;
ListNode* n = m->next;
m->next = nullptr;
auto r = sortList(n);
return merge(l, r);
}
void p(ListNode* n) {
if (!n) cout << "shit" << endl;
while (n) {
cout << n->val << ",";
n = n->next;
}
cout << endl;
}
};

// 154. Find Minimum in Rotated Sorted Array II
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
class Solution {
public:
int findMin(vector<int>& nums) {
int s = 0;
int e = nums.size();
if (e == 1) return nums[0];
if (nums[0] < nums[e-1]) return nums[0];
// cout << "____________________" << endl;
// start + 1 = e, only one element,
// start + 2 = e, mid = start + 1, min(start, start+1)
while (s < e) {
int mid = (e-s)/2 + s;
// cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
if (mid > 0 && nums[mid] < nums[mid-1]) return nums[mid];
if (mid + 1 < e && nums[mid] > nums[mid+1]) return nums[mid+1];
if (nums[mid] < nums[e-1])
e = mid;
else if (nums[mid] > nums[e-1])
s = mid+1;
// else if (nums[mid] == nums[s]) ++s;
else if (nums[mid] == nums[e-1]) --e;
// cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
}
// cout << "s: " << s << " e: " << e << endl;
return s > 0 ?nums[s-1] : nums[s];
}
};
// 153. Find Minimum in Rotated Sorted Array
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
class Solution {
public:
int findMin(vector<int>& nums) {
int s = 0;
int e = nums.size();
if (e == 1) return nums[0];
if (nums[0] < nums[e-1]) return nums[0];
// cout << "____________________" << endl;
// start + 1 = e, only one element,
// start + 2 = e, mid = start + 1, min(start, start+1)
while (s < e) {
int mid = (e-s)/2 + s;
// cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
if (mid > 0 && nums[mid] < nums[mid-1]) return nums[mid];
if (mid + 1 < e && nums[mid] > nums[mid+1]) return nums[mid+1];
if (nums[mid] < nums[e-1])
e = mid;
else if (nums[mid] > nums[s])
s = mid+1;
else
--e;
// cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
}
// cout << "s: " << s << " e: " << e << endl;
return -1;
}
};
// 150. Evaluate Reverse Polish Notation
// https://leetcode.com/problems/evaluate-reverse-polish-notation/
class Solution {
public:
int evalRPN(vector<string>& tokens) {
if (tokens.empty()) return 0;
if (tokens.size() == 1) return stoi(tokens[0]);
stack<int> st;
function<int(int, int, char)> calc = [](int l, int r, char c) {
switch(c) {
case '+': return l+r;
case '-': return l-r;
case '*': return l*r;
case '/': return l/r;
default:
return 0;
}
};
function<bool(string&)> is_op = [](string& s) {
return s.size()==1 &&(s[0]=='+' || s[0] == '-' || s[0] =='/' || s[0] =='*');
};
for (string& s : tokens) {
if (is_op(s)) {
auto r = st.top(); st.pop();
auto l = st.top(); st.pop();
st.push(calc(l, r, s[0]));
} else {
st.push(stoi(s));
}
}
return st.top();
}
};
// 130. Surrounded Regions
// https://leetcode.com/problems/surrounded-regions/
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
function<void(int, int)> color = [&](int row, int col) {
if (row >= m || row < 0) return;
if (col >= n || col < 0) return;
if (board[row][col] != 'O') return;
board[row][col] = 'Y';
color(row+1, col);
color(row-1, col);
color(row, col+1);
color(row, col-1);
};
for (int i = 0; i < n; ++i) {
color(0, i);
color(m-1, i);
}
for (int i = 0; i < m; ++i) {
color(i, 0);
color(i, n-1);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'Y') board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
}
}
}
};
// 117. Populating Next Right Pointers in Each Node II
// https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect_space(Node* root) {
if (!root) return root;
vector<Node*> cur;
vector<Node*> next;
cur.push_back(root);
while (!cur.empty()) {
auto b = begin(cur);
auto e = end(cur);
while (b != e) {
auto c = b;
++b;
if (b != e) {
(*c)->next = *b;
}
if ((*c)->left) next.push_back((*c)->left);
if ((*c)->right) next.push_back((*c)->right);
}
cur.swap(next);
next.clear();
}
return root;
}
Node* connect(Node* root) {
function<int(Node*)> height = [&](Node* node) {
if (!node) return 0;
int left = node->left? height(node->left): 0;
int right = node->right? height(node->right): 0;
return 1 + max(left, right);
};
function<Node*(Node*, int, int, bool)> node_of_height = [&](Node* node, int height, int target, bool left) {
if (height == target || !node) return node;
if (left) {
// leftmost
auto l = node_of_height(node->left, height+1, target, left);
return l? l : node_of_height(node->right, height+1, target, left);
} else {
// rightmost
auto r = node_of_height(node->right, height+1, target, left);
return r? r : node_of_height(node->left, height+1, target, left);
}
};
function<void(Node*)> traverse = [&](Node* node) {
if (!node) return;
auto l = node->left;
auto r = node->right;
int target = min(height(l), height(r));
int h = 1;
while (h <= target) {
auto ll = node_of_height(l, 1, h, false);
auto rr = node_of_height(r, 1, h, true);
ll->next = rr;
++h;
}
traverse(node->left);
traverse(node->right);
};
traverse(root);
return root;
}
};
// 103. Binary Tree Zigzag Level Order Traversal
// https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/submissions/
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
vector<TreeNode*> dq;
if (!root) return res;
dq.push_back(root);
bool reversed = false;
function<void(vector<TreeNode*>&)> traverse = [&](
vector<TreeNode*>& dq
) {
vector<TreeNode*> next;
vector<int> v;
for_each(begin(dq), end(dq), [&] (TreeNode* node
) {
v.push_back(node->val);
if (node->left) next.push_back(node->left);
if (node->right) next.push_back(node->right);
});
if (reversed) {
reverse(begin(v), end(v));
}
res.push_back(v);
reversed = !reversed;
dq.swap(next);
};
while (!dq.empty()) {
traverse(dq);
}
return res;
}
};
// 116. Populating Next Right Pointers in Each Node
// https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect_space(Node* root) {
if (!root) return root;
vector<Node*> cur;
vector<Node*> next;
cur.push_back(root);
while (!cur.empty()) {
auto b = begin(cur);
auto e = end(cur);
while (b != e) {
auto c = b;
++b;
if (b != e) {
(*c)->next = *b;
}
if ((*c)->left) next.push_back((*c)->left);
if ((*c)->right) next.push_back((*c)->right);
}
cur.swap(next);
next.clear();
}
return root;
}
Node* connect(Node* root) {
function<void(Node*)> traverse = [&](Node*node) {
if (!node) return;
auto left = node->left;
auto right = node->right;
while (left && left->right && right->left) {
auto l = left->right;
auto r = right->left;
l->next = r;
left = l;right = r;
}

if (node->left) {
node->left->next = node->right;
}
traverse(node->left);
traverse(node->right);
};
traverse(root);
return root;
}
};
// 1352. Product of the Last K Numbers
// https://leetcode.com/problems/product-of-the-last-k-numbers/
class ProductOfNumbers {
int prod;
vector<int> bkp;
vector<int> zeros;
public:
ProductOfNumbers() {
prod = 1;
bkp.push_back(1);
}

prod *= num;
prod = max(1, prod);
if (num == 0) {
zeros.push_back(bkp.size());
}
bkp.push_back(prod);
}
// 2, 3, 0
// {1} -> {1, 2} -> {1, 2, 6, 1}
// {3}

// {1, 3, 1, 2, 10, 40}
// {2}
// 2,3,4

int getProduct(int k) {
int size = bkp.size();
int n = bkp[size - k - 1];
auto ite = upper_bound(begin(zeros), end(zeros), size-k-1);
/*
cout << "k: " << k << " size: " << size << endl;
cout << "size-k-1: " << size-k-1 << endl << "zeros: ";
copy(zeros.begin(), zeros.end(), ostream_iterator<int>(cout, ","));
cout << endl;
cout << "ite == zeros.end(): " << (ite == zeros.end()) << endl;
*/
if (ite != zeros.end()) return 0;
else return bkp.back() / bkp[size-k-1];
}
};

/**
* Your ProductOfNumbers object will be instantiated and called as such:
* ProductOfNumbers* obj = new ProductOfNumbers();
* int param_2 = obj->getProduct(k);
*/
// 1347. Minimum Number of Steps to Make Two Strings Anagram
// https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/
class Solution {
public:
int minStepsAlgo(string s, string t) {
sort(s.begin(), s.end());
sort(t.begin(), t.end());
string r;
set_difference(s.begin(), s.end(), t.begin(), t.end(), back_inserter(r));
return r.size();
}
int minSteps(string s, string t) {
array<int, 26> s1 = {0};
array<int, 26> s2 = {0};
int size = s.size();
for (int i = 0; i < size; ++i) {
++s1[s[i]-'a'];
++s2[t[i]-'a'];
}
int res = 0;
for (int i = 0; i < 26; ++i) {
// cout << "i: " << i << " s1[i]: " << s1[i] << " s2[i]: " << s2[i] << endl;
if (s1[i] > s2[i]) {
res += (s1[i] - s2[i]);
}
}
return res;
}
};
class Solution {
public:
int size = s.size();
vector<string> res;
if (size < 4 || size > 12) return res;
for (int i = 0; i < 3; ++i) {
string s1 = s.substr(0, i+1);
int n1 = stoi(s1);
if (n1 > 255) break;
if (s1.size() > 1 && s1[0] == '0') break;
for (int j = i+1; j < min(i+4, size); ++j) {
string s2 = s.substr(i+1, j-i);
int n2 = stoi(s2);
if (n2 > 255) break;
if (s2.size() > 1 & s2[0] == '0') break;
for (int k = j+1; k < min(j+4, size-1); ++k) {
string s3 = s.substr(j+1, k-j);
string s4 = s.substr(k+1);
if (s4.size() > 3) continue;
int n3 = stoi(s3);
int n4 = stoi(s4);
// cout << s1 << " " << s2 << " " << s3 << " " << s4 << endl;
if (n3 > 255) break;
if (s3.size() > 1 && s3[0] == '0') break;
if (n4 > 255 || (s4.size() > 1 && s4[0] == '0')) continue;
res.push_back(move(s1+"."+s2+"."+s3+"."+s4));
}
}
}
return res;
}
};
// 79. Word Search
// https://leetcode.com/problems/word-search/
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
int word_size = word.size() - 1;
vector<vector<bool>> flag(m, vector<bool>(n, false));
function<bool(int, int, int)> search = [&](int row, int col, int index) {
if (row >= m || row < 0) return false;
if (col >= n || col < 0) return false;
if (flag[row][col]) return false;
if (board[row][col] != word[index]) return false;

flag[row][col] = true;
// cout << "index: " << index << " word_size: " << word_size << endl;
// cout << "row: " << row << " col: "<< col<<endl;
if (index == word_size) return true;
bool res = search(row+1, col, index+1) || search(row-1, col, index+1) || search(row, col+1, index+1) || search(row, col-1, index+1);
flag[row][col] = false;
return res;
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (search(i, j, 0)) return true;
}
}
return false;
}
};
// 80. Remove Duplicates from Sorted Array II
// https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
class Solution {
public:
int removeDuplicatesComplex(vector<int>& nums) {
int size = nums.size();
int count = 0;
int prev = -1;
int j = 0;
for (int i = 0; i < size; ++i) {
if (count == 0 || nums[i] != prev) {
prev = nums[i];
nums[j] = nums[i];
++j;
count = 1;
} else if (nums[i] == prev) {
++count;
nums[j] = nums[i];
++j;
if (count == 2) {
while (i < size && nums[i] == prev) ++i;
count = 0;
--i;
}
}
}
return j;
}
int removeDuplicates(vector<int>& nums) {
int size = nums.size();
if (size < 3) return size;
int index = 2;
for (int i = 2; i < size; ++i) {
if (nums[i] != nums[index-2]) {
nums[index++] = nums[i];
}
}
return index;
}
};
// 96. Unique Binary Search Trees
// https://leetcode.com/problems/unique-binary-search-trees/
class Solution {
public:
int numTrees(int n) {
// use dp with cache
unordered_map<int, int> _c;
_c[0] = 1;
_c[1] = 1;
_c[2] = 2;
function<int(int)>  dp = [&](int n) {
if (_c.find(n) != _c.end()) {
return _c[n];
}
int sum = 0;
for (int i = 1; i <= n; ++i) {
sum += dp(i - 1) * dp(n - i);
}
_c[n] = sum;
return sum;
};
return dp(n);
}
};
// 109. Convert Sorted List to Binary Search Tree
// https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
// 1 2
//
// 1
// 1 2 3
public:
function<TreeNode*(ListNode*, ListNode*)> convert = [&](
ListNode* start, ListNode* end
) ->TreeNode* {
if (!start || !end) return nullptr;
if (start->val > end->val) return nullptr;
ListNode* slow = start;
ListNode* fast = start->next;
ListNode* prev = nullptr;
while (fast && fast->val < end->val) {
prev = slow;
slow = slow->next;
fast = fast->next;
if (fast->val == end->val) break;
fast = fast->next;
}
TreeNode* cur = new TreeNode(slow->val);
cur->left = convert(start, prev);
cur->right = convert(slow->next, end);
return cur;
};
while (node) {
end = node;
node = node->next;
}
}
};
// 98. Validate Binary Search Tree
// https://leetcode.com/problems/validate-binary-search-tree/
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
function<bool(TreeNode*, long long, long long)> valid_tree = [&](
TreeNode* node,
long long l,
long long r)
{
if (!node) return true;
auto val = node->val;
if (val <= l || val >= r) return false;
return valid_tree(node->left, l, val) && valid_tree(node->right, val, r);
};
return valid_tree(root, LLONG_MIN, LLONG_MAX);
}
};
// 1025. Divisor Game
// https://leetcode.com/problems/divisor-game/
class Solution {
public:
bool divisorGame(int N) {
return !(N%2);
}
};
// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
int s1 = str1.size();
int s2 = str2.size();
if (s1 > s2) {
swap(s1, s2);
str1.swap(str2);
}
// find all factors
stack<int> fac;
for (int i = 1; i <= s1; ++i) {
if (s1 % i == 0) fac.push(i);
}
function<bool(string&, string&)> repeat = [](
string& target,  string& rep
) {
int size = rep.size();
int s = target.size();
if (s % size != 0) return false;
string tmp;
int time = s / size;
while (time--) tmp += rep;
return tmp == target;
};
while(!fac.empty()) {
auto factor = fac.top(); fac.pop();
string t = str1.substr(0, factor);
bool l = repeat(str1, t);
bool r = repeat(str2, t);
if (l && r) return t;
}
return "";
}
};
// 1114. Print in Order
// https://leetcode.com/problems/print-in-order/submissions/
class Foo {
public:
Foo() {
first_.lock();
second_.lock();
}

void first(function<void()> printFirst) {

// printFirst() outputs "first". Do not change or remove this line.
printFirst();
first_.unlock();
}

void second(function<void()> printSecond) {
first_.lock();
// printSecond() outputs "second". Do not change or remove this line.
printSecond();
second_.unlock();
}

void third(function<void()> printThird) {

second_.lock();
// printThird() outputs "third". Do not change or remove this line.
printThird();
second_.unlock();
}
private:
std::mutex first_;
std::mutex second_;
};
// 748. Shortest Completing Word
// https://leetcode.com/problems/shortest-completing-word/
class Solution {
public:
string shortestCompletingWord(string licensePlate, vector<string>& words) {
vector<int> src(26, 0);
for_each(
[&](char c) {
c = tolower(c);
if (c >= 'a' && c <= 'z') {
++src[c-'a'];
}
}
);
string result;
for (string& word: words) {
vector<int> dst(26, 0);

for_each(
begin(word),
end(word),
[&](char c) {
++dst[c-'a'];
}
);
bool res = [&]() {
for (int i = 0; i < 26; ++i) {
if (dst[i] < src[i])
return false;
}
return true;
}();
if (res && (result.empty() || word.size() < result.size())) {
result = word;
};
}

return result;

}
};
// 733. Flood Fill
// https://leetcode.com/problems/flood-fill/
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
// 1 1 1
// 1 1 0
// 1 0 1
int m = image.size();
int n = image[0].size();
int srcColor = image[sr][sc];
vector<vector<bool>> flag(m, vector<bool>(n, false));
function<void(int, int)> dfs = [&](int sr, int sc) {
if (sr < 0 || sr >= m) return;
if (sc < 0 || sc >= n) return;
if (image[sr][sc] != srcColor || flag[sr][sc]) return;
flag[sr][sc] = true;
image[sr][sc] = newColor;
dfs(sr-1, sc);
dfs(sr+1, sc);
dfs(sr, sc-1);
dfs(sr, sc+1);
};
dfs(sr, sc);
return image;
}
};
// 836. Rectangle Overlap
// https://leetcode.com/problems/rectangle-overlap/
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
if (rec1[0]>=rec2[2] || rec2[0]>=rec1[2]) return false;
if (rec1[1]>=rec2[3] || rec2[1]>=rec1[3]) return false;
return true;
}
};
// 999. Available Captures for Rook
// https://leetcode.com/problems/available-captures-for-rook/
class Solution {
public:
int numRookCaptures(vector<vector<char>>& board) {
int cnt = 0;
int mx, my;
[&]() {
for (mx = 0; mx < 8; ++mx) {
for (my = 0; my < 8; ++my) {
if (board[mx][my] != 'R') continue;
else return;
}
}
}();
/*
for (mx = 0; mx < 8; ++mx) {
for (my = 0; my < 8; ++my) {
if (board[mx][my] != 'R') continue;
else goto SHIT;
}
}
*/
// right
int z = my;
while (z < 8) {
if (board[mx][z] == 'B') break;
else if (board[mx][z] == 'p') { ++cnt; break;}
++z;
}
// left
z = my;
while (z >= 0) {
if (board[mx][z] == 'B') break;
else if (board[mx][z] == 'p') { ++cnt; break;}
--z;
}
// down
z = mx;
while (z < 8) {
if (board[z][my] == 'B') break;
else if (board[z][my] == 'p') { ++cnt; break;}
++z;
}
// up
z = mx;
while (z >= 0) {
if (board[z][my] == 'B') break;
else if (board[z][my] == 'p') { ++cnt; break;}
--z;
}
return cnt;
}
};
// 1033. Moving Stones Until Consecutive
// https://leetcode.com/problems/moving-stones-until-consecutive/
class Solution {
public:
vector<int> numMovesStones(int a, int b, int c) {
vector<int> v{a, b, c};
sort(begin(v), end(v));
int diff1 = v[1] - v[0];
int diff2 = v[2] - v[1];
if (diff1 > diff2) swap(diff1, diff2);
int m = 0;
if (diff1 == 1 && diff2 == 1) m = 0;
else if (diff1 == 1 || diff2 == 1) m = 1;
else if (diff1 == 2 || diff2 == 2) m = 1;
else m = 2;
return {m, diff1 + diff2 - 2};
}
};
// 1103. Distribute Candies to People
// https://leetcode.com/problems/distribute-candies-to-people/
class Solution {
public:
vector<int> distributeCandies(int candies, int num_people) {
// 1 2 ... n = 0*n^2 + prev
// n+1 n+2 ... 2*n = 1*n^2 + prev
// 2*n+1 2*n+2 ... 2*n+n = 2*n^2 + prev
// n*n (0 + k)*k/2 + k * n(n+1)/2 = candies line K
int sq = num_people * num_people;
int k = 0;
while ( k * (k+1) * sq / 2 + (sq+num_people)/2 * (k+1) <= candies) {
++k;
}
k =  max(k-1, 0);
vector<int> res(num_people, 0);
int candies1 = candies;
for (int i = 0; i < num_people; ++i) {
res[i] = (k+1) * (i+1) + (0 + k) * (k+1) / 2 * num_people;
res[i] = min(candies1, res[i]);
candies1 -= res[i];
if (candies1 < 0) break;
}
int remain = candies - k * (k+1) * sq / 2 - (sq+num_people)/2 * (k+1);
// if (remain < 0) { res.back() += remain; return res;}
// cout << "k: " << k << " remain: " << remain << " sq:" << sq << endl;
++k;
// cout << "res[0] = " << res[0] << endl;
for (int i = 0; remain > 0; ++i) {
int diff = min(remain, k * num_people + i + 1);
res[i] += diff;
remain -= diff;
}
return res;
}
};
// 942. DI String Match
// https://leetcode.com/problems/di-string-match/
class Solution {
public:
vector<int> diStringMatch(string S) {
S += 'I';
int N = S.size() - 1;
int M = 0;
vector<int> res; res.reserve(N+1);
for (char c : S) {
if (c == 'I') {
res.push_back(M++);
} else {
res.push_back(N--);
}
}
return res;
}
};
// 888. Fair Candy Swap
// https://leetcode.com/problems/fair-candy-swap/
class Solution {
public:
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
A.swap(B);
int s_a = accumulate(begin(A), end(A), 0);
int s_b = 0;
unordered_set<int> num;
for_each(
begin(B),
end(B),
[&](int n) {
s_b += n;
num.insert(n);
}
);
int avg = (s_a + s_b) / 2;
int diff = avg - s_a;
int size = A.size();
for (int i = 0; i < size; ++i) {
if (num.find(A[i] + diff) != num.end()) {
return {A[i]+diff, A[i]};
}
}
return {0, 0};
}
};
// 806. Number of Lines To Write String
// https://leetcode.com/problems/number-of-lines-to-write-string/
class Solution {
public:
vector<int> numberOfLines(vector<int>& widths, string S) {
int cur_sum = 0;
int lines = 1;
const int L = 100;
for (char c : S) {
int len = widths[c - 'a'];
if (cur_sum + len <= L) {
cur_sum += len;
} else {
++lines;
cur_sum = len;
}
}
return {lines, cur_sum};
}
};
// 690. Employee Importance
// https://leetcode.com/problems/employee-importance/
/*
// Employee info
class Employee {
public:
// It's the unique ID of each node.
// unique id of this employee
int id;
// the importance value of this employee
int importance;
// the id of direct subordinates
vector<int> subordinates;
};
*/
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
unordered_map<int, Employee*> m;
for_each(
begin(employees),
end(employees),
[&](Employee* e) {
m[e->id] = e;
}
);
vector<int> st; st.push_back(id);
int sum = 0;
while (!st.empty()) {
vector<int> next;
while (!st.empty()) {
auto e = m[st.back()];
sum += e->importance;
copy(e->subordinates.begin(), e->subordinates.end(), back_inserter(next));
st.pop_back();
}
st.swap(next);
}
return sum;
}
};
// 884. Uncommon Words from Two Sentences
// https://leetcode.com/problems/uncommon-words-from-two-sentences/
class Solution {
public:
vector<string> uncommonFromSentences(string A, string B) {
istringstream iss1(A), iss2(B);
unordered_map<string, int>m;
for_each(
istream_iterator<string>(iss1),
istream_iterator<string>(),
[&](const string& s) { ++m[s];}
);
for_each(
istream_iterator<string>(iss2),
istream_iterator<string>(),
[&](const string& s) { ++m[s];}
);
vector<string> result;

for_each(
begin(m),
end(m),
[&](auto& v) {
if (v.second == 1)
result.push_back(v.first);
}
);

return result;

}
};
// 976. Largest Perimeter Triangle
// https://leetcode.com/problems/largest-perimeter-triangle/
class Solution {
public:
int largestPerimeter(vector<int>& A) {
sort(A.begin(), A.end(), [](int a, int b) {return a > b;});
function<bool(int, int, int)> valid = [](int a, int b, int c) {
return (a+b) > c;
};
int size = A.size();
int m = 0;
int K = size;
for (int i = 0; i < size - 2; ++i) {
if (valid(A[i+1], A[i+2], A[i])) {
return A[i] + A[i+1] + A[i+2];
}
}
return m;
}
};
// 1351. Count Negative Numbers in a Sorted Matrix
// https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
class Solution {
public:
int countNegativesNaive(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int cnt = 0;
for_each(begin(grid), end(grid),
[&](const vector<int>& v) {
for_each(begin(v), end(v),
[&](int vv) { cnt += vv < 0;});
});
return cnt;
}
int countNegatives(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int cnt = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] < 0) {
cnt += (n - j) * (m - i);
n = j;
break;
}
}
}
return cnt;
}

};