Summary
Solved problems list
- Remove All Adjacent Duplicates in String II
- Most Stones Removed with Same Row or Column
- Sort an Array
- Group Anagrams
- Number of Enclaves
- Friend Circles
- Minimum ASCII Delete Sum for Two Strings
Highlight
Union-Find
This week’s problem contains at least two problems that can be solved using union-find data
structure. It is a simple but effective data structure. It includes two operations:
union(a, b):- Unions two node of
aandb
- Unions two node of
find(a)- Finds
a’s parent
- Finds
Usually we have an array which stores the parent of nodes.
array<int, 100> parent;
int find(array<int, 100>& parent, int n) {
// compression happens here
if (n != parent[n]) {
parent[n] = find(parent, parent[n]);
}
return parent[n];
}
int union(array<int, 100>& parent, int a, int b) {
// We could add a rank to each node, we can always link
// the short one to the longer one.
int aa = find(parent, a);
int bb = find(parent, b);
parent[aa] = bb;
}
Edit distance
Edit distance is a typical problem in dynamic programming. The dis[i][j] is equal to s[i]
and s[j], and its three previous nodes:
dis[i-1][j]dis[i][j-1]dis[i-1][j-1]
Minimum ASCII sum can be solved using a similar equation. I was at the wrong direction at
first. I tried to get the minimum delete characters that can make both strings equal and then
recover the characters deleted. It is wrong and we can directly use the condition to calculate
the result.
Code Section
The sequence of code is the same with the problem list.
class Solution {
public:
string removeDuplicates(string s, int k) {
int size = s.size();
string result = "";
for (int i = 0; i < size;) {
int prev = result.size();
if (!result.empty()) {
prev = prev - 1;
while (prev >= 0 && result[prev] == s[i]) --prev;
// cout << "result: " << result << " size: " << result.size();
// cout<< " prev: " << prev << " s[i]: " << s[i] << endl;
prev = result.size() - prev - 1;
}
int next = i + 1;
while (next < size && s[next] == s[i]) ++next;
next = next - i;
// cout << "s[i]: " << s[i] << " next: " << next;
// cout << " prev: " << prev << endl;
if (prev + next >= k) {
result.resize(result.size()-prev);
result.append((prev+next)%k, s[i]);
} else {
result.append(next, s[i]);
}
// cout << "result: " << result << " size: " << result.size() << endl;
i = next+i;
}
return result;
}
};
class Solution {
void unionn(vector<int>& parent, int x, int y) {
int p_x = find(parent, x);
int p_y = find(parent, y);
if (p_x != p_y) {
parent[p_y] = p_x;
}
}
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
public:
int removeStones(vector<vector<int>>& stones) {
// please refer to solution
// https://algorithms.tutorialhorizon.com/disjoint-set-union-find-algorithm-union-by-rank-and-path-compression/
vector<int> parent(20000);
iota(parent.begin(), parent.end(), 0);
for (vector<int>& v: stones) {
unionn(parent, v[0], v[1] + 10000);
}
unordered_set<int> components;
for (vector<int>& v: stones) {
components.insert(find(parent, v[0]));
}
return stones.size() - components.size();
}
};
class Solution {
typedef vector<int>::iterator Iter;
void quick_sort(Iter first, Iter last)
{
if (first != last) {
int pivot = *first;
auto middle1 = partition(first, last, [pivot](int x) { return x < pivot;});
auto middle2 = partition(middle1, last, [pivot](int x) {return x <= pivot;});
quick_sort(first, middle1);
quick_sort(middle2, last);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
quick_sort(nums.begin(), nums.end());
return nums;
}
};
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
typedef vector<string> VS;
typedef vector<VS> VVS;
int size = strs.size();
VVS result;
map<string, vector<string>> hah;
for (int i = 0; i < size; ++i) {
string x = strs[i];
sort(x.begin(), x.end());
hah[x].push_back(strs[i]);
}
for (auto p : hah) {
result.push_back(p.second);
}
return result;
}
};
class Solution {
void mark(vector<vector<int>> &A, vector<vector<bool>>& mirror, int s, int e) {
if (s < 0 || s >= A.size()) return;
if (e < 0 || e >= A[0].size()) return;
if (A[s][e] == 0 || mirror[s][e]) return;
mirror[s][e] = true;
mark(A, mirror, s-1, e);
mark(A, mirror, s+1, e);
mark(A, mirror, s, e-1);
mark(A, mirror, s, e+1);
}
public:
int numEnclaves(vector<vector<int>>& A) {
int row = A.size();
int col = A[0].size();
vector<vector<bool> > mirror(row, vector<bool>(col, false));
for (int j = 0; j < col; ++j) {
if (A[0][j] == 0 || mirror[0][j]) continue;
mark(A, mirror, 0, j);
}
for (int j = 0; j < col; ++j) {
if (A[row-1][j] == 0 || mirror[row-1][j]) continue;
mark(A, mirror, row-1, j);
}
for (int i = 0; i < row; ++i) {
if (A[i][0] == 0 || mirror[i][0]) continue;
mark(A, mirror, i, 0);
}
for (int i = 0; i < row; ++i) {
if (A[i][col-1] == 0 || mirror[i][col-1]) continue;
mark(A, mirror, i, col-1);
}
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; ++j) {
if (A[i][j] == 1 && !mirror[i][j]) ++count;;
}
}
return count;
}
};
class Solution {
int id(int a, vector<int>& parent) {
while (parent[a] != a) {
// parent[a] = parent[parent[a]];
a = parent[a];
}
return a;
}
void conn(int a, int b, vector<int>& parent) {
auto aa = id(a, parent);
auto bb = id(b, parent);
if (aa != bb) {
parent[bb] = aa;
}
}
public:
int findCircleNum(vector<vector<int>>& M) {
int size = M.size();
vector<int> parent(size, 0);
iota(parent.begin(), parent.end(), 0);
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
if (M[i][j] == 0 || i == j) continue;
conn(i, j, parent);
}
}
for (int i = 0; i < size; ++i) {
parent[i] = id(i, parent);
}
sort(parent.begin(), parent.end());
return distance(parent.begin(), unique(parent.begin(), parent.end()));
}
};
class Solution {
public :
int minimumDeleteSum(string s1, string s2) {
int size_1 = s1.size(), size_2 = s2.size();
vector<vector<int> > dp(size_1+1, vector<int>(size_2+1, 0));
for (int i = s1.size() - 1; i >= 0; i--) {
dp[i][s2.size()] = dp[i+1][s2.size()] + s1[i];
}
for (int j = s2.size() - 1; j >= 0; j--) {
dp[s1.size()][j] = dp[s1.size()][j+1] + s2[j];
}
for (int i = s1.size() - 1; i >= 0; i--) {
for (int j = s2.size() - 1; j >= 0; j--) {
if (s1[i] == s2[j]) {
dp[i][j] = dp[i+1][j+1];
} else {
dp[i][j] = min(dp[i+1][j] + s1[i],
dp[i][j+1] + s2[j]);
}
}
}
return dp[0][0];
}
public:
int _minimumDeleteSum(string s1, string s2) {
int sum_1 = 0, sum_2 = 0;
int size_1 = s1.size(), size_2 = s2.size();
for (char c : s1) sum_1 += c;
for (char c : s2) sum_2 += c;
// find lcs
vector<vector<int> > m(size_1+1, vector<int>(size_2+1, 0));
for (int i = 1; i <= size_1; ++i) {
for (int j = 1; j <= size_2; ++j) {
if (s1[i-1] == s2[j-1]) {
m[i][j] = m[i-1][j-1] + 1;
} else {
m[i][j] = max(m[i-1][j], m[i][j-1]);
}
}
}
vector<char> c;
int i = size_1;
int j = size_2;
while (i != 0 && j != 0) {
if (s1[i-1] == s2[j-1]) {
c.push_back(s1[i-1]);
--i;
--j;
} else {
if (m[i-1][j] > m[i][j-1]) {
--i;
} else if (m[i-1][j] < m[i][j-1]) {
--j;
} else {
if (s1[i-1] < s2[j-1]) {
--i;
} else {
--j;
}
}
}
}
cout << m[size_1][size_2] << endl;
copy(c.begin(), c.end(), ostream_iterator<char>(cout, ","));
cout << endl;
int sum_3 = 0;
for (char cc : c) sum_3 += cc;
return sum_1 + sum_2 - sum_3 * 2;
}
};