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

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