Leetcode summary of 20190922-20190929

Posted by chunyang on September 29, 2019

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 a and b
  • find(a)
    • Finds a’s parent

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

Creative Commons License
This work is licensed under a CC A-S 4.0 International License.