Summary
Solved problems list
- Check If Word Is Valid After Substitutions
- Redundant Connection
- Array Nesting
- Beautiful Arrangement
- Optimal Division
- Reverse Substrings Between Each Pair of Parentheses
- Longest Arithmetic Sequence
- Filling Bookcase Shelves
- Escape The Ghosts
- Longest String Chain
- Hand of Straights
- Replace Words
The medium-diffculty problems require a more careful analysis of the problems themselves and the implementation normally is a little longer. You should try to come out with a simple solution first and try to optimize it. It is hard for me to solve multiple problems at a single night.
Highlight
STL unique function
unique function is used to remove all the duplcate elements in a container. But it only moves.
Usually we should call the erase function between the resulting iterator
returned and then end iterator.
vector<int> a{1,1,2,3,3};
auto iter = unique(begin(a), end(a));
erase(iter, a.end());
Union Find
In Redundant Connection, the best solution uses Union-Find data structure. Please refer to
Union-Find for more details.
Dynamic Programming
Filling Bookcase Shelves can be solved using dynamic programming. In each iteration, we try to
move previous books on current row until the width exceeds.
Array Nesting
It is similar to the problem of finding the missing element in an array.
Code Section
The sequence of code is the same with the problem list.
class Solution {
public:
bool isValid(string S) {
stack<char> st;
int size = S.size();
for (int i = 0; i < size; ++i) {
switch(S[i]) {
case 'a':
case 'b':
st.push(S[i]); break;
case 'c':
{
if (st.size() < 2) return false;
auto b = st.top(); st.pop();
auto a = st.top(); st.pop();
if (b != 'b' || a != 'a') return false;
}
}
}
return st.empty();
}
};
class Solution {
// https://www.cnblogs.com/grandyang/p/7628977.html
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
vector<int> root(2001, -1);
for (auto edge : edges) {
int x = find(root, edge[0]), y = find(root, edge[1]);
if (x == y) return edge;
root[x] = y;
}
return {};
}
int find(vector<int>& root, int i) {
while (root[i] != -1) {
i = root[i];
}
return i;
}
};
class Solution {
public:
int arrayNesting(vector<int>& nums) {
int max_len = 1;
int size = nums.size();
for (int i = 0; i < size; ++i) {
if (nums[i] == i) continue;
int j = i;
int cnt = 1;
while (j != nums[i]) {
++cnt;
swap(nums[i], nums[nums[i]]);
}
max_len = max(cnt, max_len);
}
return max_len;
}
};
class Solution {
void countArrangement(int N, int& count, int cur, vector<bool>& used) {
if (cur == N) {
++count;
return;
}
while (true) {
int i = cur;
for (int j = 0; j < N; ++j) {
if (used[j]) continue;
if ((i+1) % (j+1) == 0 || (j+1) % (i+1) == 0) {
used[j] = true;
countArrangement(N, count, cur+1, used);
used[j] = false;
}
}
break;
}
}
public:
int countArrangement(int N) {
int count = 0;
vector<bool> used(N, false);
countArrangement(N, count, 0, used);
return count;
}
};
class Solution {
// https://www.cnblogs.com/grandyang/p/6886673.html
public:
string optimalDivision(vector<int>& nums) {
if (nums.empty()) return "";
string res = to_string(nums[0]);
if (nums.size() == 1) return res;
if (nums.size() == 2) return res + "/" + to_string(nums[1]);
res += "/(" + to_string(nums[1]);
for (int i = 2; i < nums.size(); ++i) {
res += "/" + to_string(nums[i]);
}
return res + ")";
}
};
class Solution {
public:
string reverseParentheses(string s) {
string result;
int size = s.size();
for (int i = 0; i < size; ++i) {
switch(s[i]) {
case ')':
// find previous (, and reverse
{
int j = result.size();
while (j > 0 && result[j] != '(') --j;
string tmp = result.substr(j+1);
result.erase(next(result.begin(), j), result.end());
copy(tmp.rbegin(), tmp.rend(), back_inserter(result));
}
break;
default:
result += s[i];
break;
}
}
return result;
}
};
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
unordered_map<int, vector<int>> m;
int size = A.size();
for (int i = 0; i < size; ++i) {
m[A[i]].push_back(i);
}
int max_len = 0;
for (auto& p : m) {
max_len = max(max_len, int(p.second.size()));
}
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < (size - max_len); ++j) {
if (A[j] == A[i]) {
continue;
} else {
int diff = A[j] - A[i];
int prev = A[j] + diff;
int index = j;
int cnt = 2;
while (m.find(prev) != m.end()) {
auto iter = upper_bound(m[prev].begin(), m[prev].end(), index);
if (iter == m[prev].end()) break;
prev = prev + diff;
index = *iter;
++cnt;
}
max_len = max(max_len, cnt);
}
}
}
return max_len;
}
};
class Solution {
// https://www.cnblogs.com/fish1996/p/11323889.html
public:
int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
int n = books.size();
vector<int> dp(n + 1, 10000000);
dp[0] = 0;
for(int i = 1; i <= n; i++)
{
int height = 0;
int width = 0;
for(int j = i - 1; j >= 0; j--)
{
height = max(height,books[j][1]);
width += books[j][0];
if(width > shelf_width) break;
dp[i] = min(dp[i], dp[j] + height);
}
}
return dp[n];
}
};
class Solution {
public:
bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
// calculate manhattan distance between every ghost and the target,
// if that is less than or equal to player's distance from target,
// it is not possible
// think like this, the ghost will reach target before us and will catch us there
int dis = abs(target[0]) + abs(target[1]);
for(auto &g: ghosts) {
if(abs(g[0] - target[0]) + abs(g[1] - target[1]) <= dis) return false;
}
return true;
}
};
class Solution {
bool diff_one(string& l, string& r) {
if (r.size() - l.size() != 1) return false;
int i = 0, j = 0;
int size1 = l.size(), size2 = r.size();
while (i < size1 && j < size2) {
if (l[i] != r[j]) ++j;
else {
++i; ++j;
}
}
return i == size1;
}
int max_len(unordered_map<int, vector<string>>& m,
unordered_map<string, bool>& indicator,
int size,
int cur_len,
string& prev
) {
if (m[size].empty()) return cur_len;
int l = m[size].size();
int max = cur_len;
for (int i = 0; i < l; ++i) {
// cout << "prev: " << prev << " m[size][i]: " << m[size][i]
// cout << " = " << diff_one(prev, m[size][i]) << endl;
if (!diff_one(prev, m[size][i])) continue;
indicator[m[size][i]] = true;
int tmp = max_len(m, indicator, size+1, cur_len+1, m[size][i]);
if (tmp > max) max = tmp;
}
return max;
}
public:
int longestStrChain(vector<string>& words) {
auto func = [](const string&l, const string& r) {return l.size() < r.size();};
sort(words.begin(), words.end(), func);
// unique(words.begin(), words.end());
// copy(words.begin(), words.end(), ostream_iterator<string>(cout, ","));
// cout << endl;
unordered_map<int, vector<string>> m;
for (string& w : words) {
m[w.size()].push_back(w);
}
unordered_map<string, bool> indicator;
int len = -1;
for (string& w : words) {
if (indicator[w]) continue;
int tmp = max_len(m, indicator, w.size()+1, 1, w);
// cout << "TMP: " << tmp << " w = " << w << endl;
if (tmp > len) len = tmp;
}
return len;
}
};
auto _ = []() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int W) {
unordered_map<int, int> cnt;
for (int h : hand) {
++cnt[h];
}
vector<pair<int, int>> hands(cnt.begin(), cnt.end());
sort(hands.begin(), hands.end());
int size = hands.size();
int start = 0;
while (true) {
int prev = -1;
int len = 0;
while (start < size && hands[start].second == 0) ++start;
for (int i = start; i < size; ++i) {
if (hands[i].second == 0) continue;
if (prev == -1) {
prev = hands[i].first;
++len;
--hands[i].second;
} else {
if (len == W) break;
if (hands[i].first != prev + 1) {
return false;
}
--hands[i].second;
++len;
++prev;
}
}
if (len == 0) break;
if (len != W) return false;
}
return true;
}
};
class Solution {
struct Node {
char c;
bool is_end;
vector<Node*> children;
Node(): c(0), is_end(false), children(26, NULL) {}
};
vector<Node*> build_node(vector<string>& dict) {
// cout << "Default init" << endl;
vector<Node*> nodes(26);
// cout << "Default init finishes" << endl;
for (auto& str : dict) {
int size = str.size();
if (size == 0) continue;
vector<Node*>* prev = &nodes;
Node** cur = NULL;
for (int i = 0; i < size; ++i) {
// cout << "str[i] = " << str[i] << " - 'a' = " << (str[i] - 'a') << endl;
cur = &((*prev)[str[i] - 'a']);
if (*cur == NULL) {
*cur = new Node();
}
(*cur)->c = str[i];
prev = &((*cur)->children);
}
(*cur)->is_end = true;
}
return nodes;
}
string replace(string& str, vector<Node*>& nodes) {
int size = str.size();
int i = 0;
vector<Node*>* prev = &nodes;
string res = "";
for (; i < size; ++i) {
int ind = str[i] - 'a';
auto& node = (*prev)[ind];
if (node == NULL || node->c == 0) break;
res += str[i];
if (node->is_end) return res;
prev = &(node->children);
}
return str;
}
string replaceWords(vector<Node*>& nodes, string& sent) {
int size = sent.size();
int i = 0;
string res = "";
while (i < size) {
int j = i;
while (j < size && sent[j] != ' ') ++j;
string tmp = sent.substr(i, j - i);
if (!res.empty()) res += " ";
// cout << "replace start: " << i << " : j " << j << endl;
res += replace(tmp, nodes);
// cout << "replace finishes" << endl;
i = j + 1;
}
return res;
}
public:
string replaceWords(vector<string>& dict, string sentence) {
auto nodes = build_node(dict);
// cout << "build node finishes" << endl;
return replaceWords(nodes, sentence);
}
};