Summary
Solved problems list
- 187. Repeated DNA Sequences
- 201. Bitwise AND of Numbers Range
- 166. Fraction to Recurring Decimal
- 146. LRU Cache
- 131. Palindrome Partitioning
- 91. Decode Ways
- 498. Diagonal Traverse
- 518. Coin Change 2
- 133. Clone Graph
- 1361. Validate Binary Tree Nodes
- 264. Ugly Number II
- 236. Lowest Common Ancestor of a Binary Tree
Highlight
Bitwise AND of Numbers Range
It is similar to the problem of counting the number of 1s in a number. For any number n, the way to remove the last bit of 1 in n is:
n = n & (n-1)
The largest number by performing AND is the number itself. So we keep repeating this process
until we can no no more. The remained n is the final result.
Coin change
It is one kind of knapsack problem. You can refer to knapsack
Code Section
The sequence of code is the same with the problem list.
// 187. Repeated DNA Sequences
// https://leetcode.com/problems/repeated-dna-sequences/
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int size = s.size();
unordered_map<string, int> m;
set<string> ss;
for (int i = 0; i < size; ++i) {
auto sub = s.substr(i, 10);
if (ss.find(sub) != ss.end()) continue;
if (m.find(sub) == m.end()) {
m[sub] = i;
} else {
ss.insert(sub);
}
}
return vector<string>(ss.begin(), ss.end());
}
};
// 201. Bitwise AND of Numbers Range
// https://leetcode.com/problems/bitwise-and-of-numbers-range/
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
if (m == n) return m;
if (m == 0 || n == 0) return 0;
while (true) {
if (n > m) n &= (n-1);
else break;
}
return n;
}
};
// 166. Fraction to Recurring Decimal
// https://leetcode.com/problems/fraction-to-recurring-decimal/
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
map<int, int> pos;
string result;
long long n = numerator;
long long d = denominator;
bool flag = false;
if (n < 0 && d < 0) {
n = -n;
d = -d;
} else if (n < 0) {
flag = true;
n = -n;
} else if (d < 0) {
flag = true;
d = -d;
}
if (n == 0) return "0";
bool add_dot = false;
int p = -1;
while (n) {
if (n % d == 0) {
result += to_string(n / d);
break;
} else {
if (n < d) {
if (!add_dot) {
if (result.empty()) result += "0";
result += ".";
add_dot = true;
p = result.size();
}
if (pos[n] != 0) {
// find repeat pattern
result += ")";
result.insert(pos[n], "(");
break;
}
pos[n] = p;
n *= 10;
auto div = n / d;
auto r = n % d;
n = r;
result += to_string(div);
++p;
} else {
result += to_string(n/d);
n = n % d;
}
}
}
return flag ? "-" + result : result;
}
};
// 146. LRU Cache
// https://leetcode.com/problems/lru-cache/
struct MyNode {
MyNode* prev;
MyNode* next;
int val;
int key;
MyNode(int key, int val):key(key), val(val), prev(nullptr), next(nullptr) {}
};
class LRUCache {
unordered_map<int, MyNode*> _indexer;
int size;
int cap;
MyNode* head;
MyNode* tail;
public:
LRUCache(int capacity): size(0), head(nullptr), tail(nullptr), cap(capacity) {
}
int get(int key) {
if (_indexer.empty() || _indexer.find(key) == _indexer.end()) {
return -1;
}
auto pos = _indexer[key];
if (pos == head) return head->val;
if (pos == tail) tail = pos->prev;
auto next = head;
auto prev = pos->prev;
if (prev) {
prev->next = pos->next;
if (pos->next) pos->next->prev = prev;
}
pos->next = next;
next->prev = pos;
head = pos;
auto t = head;
/*
cout << "----------getting: " << key << endl;
while (t) {
cout << "key: " << t->key << " val: " << t->val << endl;
t = t->next;
}
cout << "head: " << head->key << " tail: " << tail->key << endl;
if (tail->prev) {
cout << "tail->prev: " << tail->prev->key << endl;
} else {
cout << "tail->prev is nullptr" << endl;
}
*/
return head->val;
}
void put(int key, int value) {
if (_indexer.find(key) != _indexer.end()) {
get(key);
head->val = value;
} else {
auto n = new MyNode(key, value);
++size;
if (size > cap) {
auto pos = tail;
tail = tail->prev;
if (tail == nullptr) head = tail = nullptr;
else tail->next = nullptr;
--size;
_indexer.erase(pos->key);
delete pos;
}
n->next = head;
if (head) {
head->prev = n;
} else {
tail = n;
}
head = n;
_indexer[key] = n;
}
/*
cout << "----------Putting: " << key << " val: " << value << endl;
auto t = head;
while (t) {
cout << "key: " << t->key << " val: " << t->val << endl;
t = t->next;
}
cout << "head: " << head->key << " tail: " << tail->key << endl;
*/
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
// 131. Palindrome Partitioning
// https://leetcode.com/problems/palindrome-partitioning/
class Solution {
public:
vector<vector<string>> partition(string s) {
function<bool(int, int)> is_palindrome = [&](int start, int end) {
while (start < end && s[start] == s[end]) {
++start;
--end;
}
return start >= end;
};
vector<vector<string>> result;
vector<string> path;
int size = s.size();
function<void(int)> dfs = [&](int start) {
if (start == size) {
result.push_back(path);
}
for (int i = start; i < size; ++i) {
if (is_palindrome(start, i)) {
path.push_back(s.substr(start, i-start+1));
dfs(i+1);
path.pop_back();
}
}
};
dfs(0);
return result;
}
};
// 91. Decode Ways
// https://leetcode.com/problems/decode-ways/
class Solution {
public:
int numDecodings(string s) {
int size = s.size();
vector<int> dp(size+1);
dp[0] = 1;
dp[1] = 1;
if (s[0] == '0') return 0;
for (int i = 2; i <= size; ++i) {
bool good = false;
if (s[i-1] != '0') {
dp[i] = dp[i-1];
good = true;
}
if (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) {
dp[i] += dp[i-2];
good = true;
}
if (!good) return 0;
}
return dp[size];
}
};
// 498. Diagonal Traverse
// https://leetcode.com/problems/diagonal-traverse/
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
vector<int> result;
int m = matrix.size();
if (m == 0) return result;
int n = matrix[0].size();
result.reserve(m*n);
bool reversed = true;
for (int i = 0; i < n; ++i) {
vector<int> mid;
for (int r = 0, c = i; r < m && c >= 0; ++r, --c) {
mid.push_back(matrix[r][c]);
}
if (reversed) {
copy(mid.rbegin(), mid.rend(), back_inserter(result));
} else {
copy(mid.begin(), mid.end(), back_inserter(result));
}
reversed = !reversed;
}
for (int i = 1; i < m; ++i) {
vector<int> mid;
for (int r = i, c = n-1; r < m && c >= 0; ++r, --c) {
mid.push_back(matrix[r][c]);
}
if (reversed) {
copy(mid.rbegin(), mid.rend(), back_inserter(result));
} else {
copy(mid.begin(), mid.end(), back_inserter(result));
}
reversed = !reversed;
}
return result;
}
};
// 518. Coin Change 2
// https://leetcode.com/problems/coin-change-2/
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (const int coin : coins)
for (int i = 0; i <= amount - coin; ++i)
dp[i + coin] += dp[i];
return dp[amount];
}
};
/**
* 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<TreeNode*> generateTrees(int n) {
unordered_map<string, vector<TreeNode*>> cache;
function<vector<TreeNode*>(int, int )> gen = [&](int s, int e) {
vector<TreeNode*> result;
if (s > e) result.push_back(nullptr);
else if (s == e) result.push_back(new TreeNode(s));
else {
for (int i = s; i <= e; ++i) {
auto l = gen(s, i-1);
auto r = gen(i+1, e);
for (auto ll : l) {
for (auto rr : r) {
TreeNode* node = new TreeNode(i);
node->left = ll;
node->right = rr;
result.push_back(node);
}
}
}
}
return result;
};
if (n == 0) return vector<TreeNode*>();
return gen(1, n);
}
};
// 133. Clone Graph
// https://leetcode.com/problems/clone-graph/
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* cloneGraph(Node* node) {
unordered_map<int, Node*> cloned;
function<Node*(Node*)> clone_one = [&](Node* node) {
if (!node) return node;
if (cloned.find(node->val) != cloned.end()) return cloned[node->val];
Node* cloned_node = new Node(node->val);
cloned[node->val] = cloned_node;
for (Node* n : node->neighbors) {
cloned_node->neighbors.push_back(clone_one(n));
}
return cloned_node;
};
return clone_one(node);
}
};
// 1361. Validate Binary Tree Nodes
// https://leetcode.com/problems/validate-binary-tree-nodes/
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
// more than one root
// more than two child
// more than two parent
unordered_set<int> roots;
unordered_set<int> children;
function<bool(int)> be_child = [&](int n) {
if (n == -1) return true;
auto b = children.find(n) == children.end();
if (b) {
children.insert(n);
}
return b;
};
function<void(int)> del = [&](int n) {
if (n == -1) return;
if (roots.find(n) != roots.end()) {
roots.erase(n);
}
};
for (int i = 0; i < n; ++i) {
auto l = leftChild[i];
auto r = rightChild[i];
auto b1 = be_child(l); auto b2 = be_child(r);
del(l); del(r);
if (!b1 || !b2) return false;
/*
cout << "for i = " << i << " root: ";
copy(begin(roots), end(roots), ostream_iterator<int>(cout, ","));
cout << endl;
cout << "children: ";
copy(begin(children), end(children), ostream_iterator<int>(cout, ","));
cout << endl;
*/
if (children.find(i) == children.end()) {
roots.insert(i);
} else {
if (roots.find(i) != roots.end()) {
roots.erase(i);
}
}
}
// cout << "roots.size(): " << roots.size() << endl;
return roots.size() == 1;
}
};
// 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> l(n); // initialize the squence.
int p_2, p_3, p_5; // initialize the pointer
l[0] = 1;
p_2 = 0;
p_3 = 0;
p_5 = 0;
for (int i = 1; i < n; ++i) {
l[i] = min({l[p_2] * 2, l[p_3] * 3, l[p_5] * 5});
if (l[p_2] * 2 == l[i]) ++p_2;
if (l[p_3] * 3 == l[i]) ++p_3;
if (l[p_5] * 5 == l[i]) ++p_5;
}
return l[n - 1];
}
public:
bool isUglyNumber(int num) {
if (num <= 0) return false;
while (num % 6 == 0) num /= 6;
while (num % 10 == 0) num /= 10;
while (num % 15 == 0) num /= 15;
while (num % 2 == 0) num /= 2;
while (num % 3 == 0) num /= 3;
while (num % 5 == 0) num /= 5;
return num == 1;
}
int nthUglyNumberSlow(int n) {
int cnt = 0;
int i = 1;
while (cnt < n) {
if (isUglyNumber(i)) ++cnt;
++i;
}
return i-1;
}
};
// 236. Lowest Common Ancestor of a Binary Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
if (root->val == p->val || root->val == q->val) return root;
auto n = lowestCommonAncestor(root->left, p, q);
auto m = lowestCommonAncestor(root->right, p, q);
if (m && n) return root;
else if (m) return m;
else if (n) return n;
else return nullptr;
}
};