LeetCode weekly contest 140

Posted on Edited on In Disqus:
Rank Name Score Finish Time Q1 (4) Q2 (5) Q3 (6) Q4 (8)
313 / 4046 YoungForest 16 1:03:21 0:21:32 (1) 0:36:08 0:53:21 (1) null

This contest was moderately difficult. Because of an issue with the judging program, many people were trapped by the third problem. The test case was corrected after the contest. This is already not the first LeetCode incident.

5083. Occurrences After Bigram

Idea:
A warm-up problem. Solve it directly. Use a state machine to record the current state.

Time complexity: O(text.size()),
Space complexity: O(1). In my implementation, I store tokens in a vector for convenience, but it is actually unnecessary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    enum class State {
        other,
        first,
        second
    };
public:
    vector<string> findOcurrences(string text, string first, string second) {
        vector<string> ret;
        istringstream iss(text);
        vector<string> tokens{istream_iterator<string>{iss}, {}};
        State state = State::other;
        for (const auto & token : tokens) {
            if (state == State::second) {
                ret.push_back(token);
                state = State::other;
            }
            if (token == first) {
                state = State::first;
            } else if (token == second && state == State::first) {
                state = State::second;
            } else {
                state = State::other;
            }
        }
        return ret;
    }
};

5087. Letter Tile Possibilities

Because the data scale is small, tiles.length <= 7, directly brute-force enumerate all possibilities.
Time complexity: O(N!),
Space complexity: O(N!).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    set<string> ret;
    void backtracking(map<char, int>& count, int size, int step, string& current) {
        if (step == size) {
            ret.insert(current);
            return;
        }
        for (auto& p : count) {
            char c = p.first;
            if (count[c] > 0) {
                --count[c];
                current.push_back(c);
                backtracking(count, size, step + 1, current);
                current.pop_back();
                ++count[c];
            }
        } 
    }
public:
    int numTilePossibilities(string tiles) {
        map<char, int> count;
        for (char tile : tiles) {
            ++count[tile];
        }
        int s = tiles.size();
        for (int len = 1; len <= s; ++len) {
            string current;
            backtracking(count, len, 0, current);
        }
        // for (auto& s : ret) {
        //     cout << s << " ";
        // }
        return ret.size();
    }
};

5084. Insufficient Nodes in Root to Leaf Paths

A typical recursion problem. Just delete nodes according to the statement. If you are familiar with tree recursion, it is quick to write.
One thing to note: the definition of a leaf node is that both left and right subtrees are null, not just the left subtree or the right subtree.

Time complexity: O(N), each node in the tree calls the recursive function once.
Space complexity: O(N), the depth of the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int limit = 0;
    // return: 是否删除，子树从根到叶子最大的sum
    // current: 从根到父节点的sum
    pair<TreeNode*, int> recurse(TreeNode* root, int current) {
      if (root == nullptr) {
            return {nullptr, 0};
        }
        auto l = recurse(root->left, current + root->val);
        auto r = recurse(root->right, current + root->val);
        TreeNode* ret_ptr = nullptr;
        int ret_int;
        if (root->left != nullptr && root->right != nullptr)
            ret_int = max(l.second, r.second);
        else if (root->left != nullptr)
            ret_int = l.second;
        else if (root->right)
            ret_int = r.second;
        else    // 叶子结点
            ret_int = 0;
        root->left = l.first;
        root->right = r.first;
        // cout << root->val << " : " << ret_int << endl;
        if (ret_int + root->val + current >= limit) {
            return {root, ret_int + root->val};
        } else {
            return {nullptr, ret_int + root->val};
        }
    }
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        this->limit = limit;
        auto ret = recurse(root, 0);
        return ret.first;
    }
};

5086. Smallest Subsequence of Distinct Characters

I did not solve this problem during the contest. I tried a greedy solution, adding one character each time. But this greedy idea is actually wrong and cannot handle input like
"ddeeeccdce".
When processing the final d, "ecd" cannot be greater than "dec".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 错误的贪心思路
// 时间复杂度: O(N^2)
// 空间复杂度: O(N)
class Solution {
public:
    string smallestSubsequence(string text) {
        string current;
        for (int i = 0; i < text.size(); ++i) {
            char c = text.at(i);
            auto index = current.find(c);
            if (index == string::npos) {
                current.push_back(c);
            } else {
                string new_current = current.substr(0, index) + current.substr(index + 1);
                new_current.push_back(c);
                if (new_current < current) {
                    current = std::move(new_current);
                }
            }
        }
        return current;
    }
};

Correct idea:
This is exactly the same problem as LeetCode 316.
There are many high-quality answers in the discuss section for that problem.

For the input string, we try to maintain a monotonically increasing result string. If the input character is smaller than the last character of the result string, and that last character will appear again later, then we remove that character from the result string.
This is also a greedy idea. Each operation makes the string smaller.

Time complexity: O(N),
Space complexity: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string smallestSubsequence(string text) {
        unordered_map<char, int> used, count;
        for (char c : text) {
            ++count[c];
        }
        string ret;
        for (char c : text) {
            --count[c];
            if (used[c]++ > 0) {
                continue;
            }
            while (!ret.empty() && ret.back() > c && count[ret.back()] > 0) {
                used[ret.back()] = 0;
                ret.pop_back();
            }
            ret.push_back(c);
        }
        return ret;
    }
};