LeetCode Weekly Contest 225

Posted on Edited on In Disqus:
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
299 / 11282 YoungForest 18 1:16:19 0:05:09 0:18:06 0:29:04 1:11:19 1

1736. Latest Time by Replacing Hidden Digits

Greedy. Analyze each digit’s situation and solve it with if-else.

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
class Solution {
public:
    string maximumTime(string time) {
        if (time[4] == '?') {
            time[4] = '9';
        }
        if (time[3] == '?') {
            time[3] = '5';
        }
        if (time[1] == '?') {
            if (time[0] == '?') {
                time[0] = '2';
                time[1] = '3';
            } else if (time[0] == '2') {
                time[1] = '3';
            } else {
                time[1] = '9';
            }
        } else {
            if (time[0] == '?') {
                if (time[1] < '4') {
                    time[0] = '2';
                } else {
                    time[0] = '1';
                }
            }
        }
        return time;
    }
};

Time complexity: O(1),
space complexity: O(1).

1737. Change Minimum Characters to Satisfy One of Three Conditions

Compute every target case.
Cases 1 and 2: enumerate the split point and transform unsuitable characters beyond the split point.
Case 3: find the mode.

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
46
47
48
49
50
51
class Solution {
public:
    int minCharacters(string a, string b) {
        int ans = a.size() + b.size();
        auto calculatePresum = [&](const string& x) -> vector<int> {
            vector<int> ans(26, 0);
            for (char c : x) {
                ++ans[c - 'a'];
            }
            for (int i = 1; i < 26; ++i) {
                ans[i] += ans[i - 1];
            }
            return ans;
        };
        auto op12 = [&](const string& a, const string& b) -> void {
            // 26 * (a.size() + b.size())
            auto presumA = calculatePresum(a);
            auto presumB = calculatePresum(b);
            // b >= splitPoint, a < splitPoint
            for (int splitPoint = 1; splitPoint < 26; ++splitPoint) {
                int need = 0;
                // a need
                need += a.size() - presumA[splitPoint - 1];
                // b need
                need += presumB[splitPoint - 1];
                ans = min(ans, need);
            }
        };
        // 1, 2
        op12(a, b);
        op12(b, a);
        
        // 3
        // size 和 - 众数
        {
            unordered_map<char, int> cnt;
            for (char c : a) {
                ++cnt[c];
            }
            for (char c : b) {
                ++cnt[c];
            }
            int maxCnt = 0;
            for (auto p : cnt) {
                maxCnt = max(maxCnt, p.second);
            }
            ans = min(ans, static_cast<int>(a.size() + b.size()) - maxCnt);
        }
        return ans;
    }
};

Time complexity: O(n + 26),
space complexity: O(26).

1738. Find Kth Largest XOR Coordinate Value

Dynamic programming.
In fact, during the contest I made it too complicated. I used three DP arrays to represent rectangle XOR values, row XOR values, and column XOR values.
But based on the properties of XOR, namely commutativity and cancellation, maintaining one rectangle XOR value is enough.

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
class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        const int m = matrix.size();
        const int n = matrix[0].size();
        auto rows = matrix;
        auto cols = matrix;
        vector<int> nums;
        nums.reserve(m * n);
        nums.push_back(matrix[0][0]);
        for (int i = 1; i < m; ++i) {
            cols[i][0] = cols[i-1][0] ^ matrix[i][0];
            matrix[i][0] ^= matrix[i-1][0];
            nums.push_back(matrix[i][0]);
        }
        for (int j = 1; j < n; ++j) {
            rows[0][j] = rows[0][j-1] ^ matrix[0][j];
            matrix[0][j] ^= matrix[0][j-1];
            nums.push_back(matrix[0][j]);
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                rows[i][j] = rows[i][j-1] ^ matrix[i][j];
                cols[i][j] = cols[i-1][j] ^ matrix[i][j];
                matrix[i][j] ^= matrix[i-1][j-1] ^ rows[i][j-1] ^ cols[i-1][j];
                nums.push_back(matrix[i][j]);
            }
        }
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k-1];
    }
};

Time complexity: O(m * n),
space complexity: O(1), if matrix is reused and rows, cols are not needed.

1739. Building Boxes

Binary search.
Determine the number of boxes on the bottom layer, then calculate how many boxes it can hold at most.
According to the greedy idea, every layer should be squeezed into the corner as much as possible, forming an arithmetic sequence.

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
class Solution {
    using ll = long long;
public:
    int minimumBoxes(int n) {
        // time: log n * log n * log n
        // 1 + 3 + 6
        // level(x) = level(x-1) + x, level(1) = 1
        // level(2) = 3
        // level(3) = 6
        // binary_search
        // maxBoxesCount(x) = 
        const ll MAX = n + 1;
        auto binary = [&](ll lo, ll hi, function<bool(const ll)> predicate) -> int {
            while (lo < hi) {
                ll mid = lo + (hi - lo) / 2;
                if (predicate(mid)) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            return lo;
        };
        function<ll(const ll)> maxBoxesCouldHoldByLastLevel = [&](const ll x) -> ll {
            if (x <= 0) return 0;
            ll k = binary(0, MAX, [&](const ll k) -> bool {
                return k * (k + 1) / 2 > x;
            }) - 1;
            // if (x < 5) cout << "maxBoxesCouldHoldByLastLevel: " << x << " " << k << endl;
            const ll y = x - (k * (k + 1) / 2);
            const ll couldNotPut = y + (k) - (y == 0 ? y : (y - 1));
            const ll nextLevel = x - couldNotPut;
            return x + maxBoxesCouldHoldByLastLevel(nextLevel);
        };
        return binary(0, MAX, [&](const ll x) -> bool {
            return maxBoxesCouldHoldByLastLevel(x) >= n;
        });
    }
};

Time complexity: O(log n * log n * sqrt n), where sqrt n is the recursion depth of maxBoxesCouldHoldByLastLevel,
space complexity: O(sqrt n).