# Leetcode summary of 20190915-20190922

Posted by chunyang on September 22, 2019

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