LeetCode weekly contest 148

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (5) Q3 (6) Q4 (8)
77 / 5319 YoungForest 23 0:56:45 0:09:51 0:24:02 0:41:20 0:56:45

本次比赛是我时隔3个月再次进入前100名，也是连续2次进入前200名，还是有些小开心的。算是一扫上周kick start 翻车的阴郁。
事实上，由于评测机的问题，我比赛刚结束时看到的排名是56名。后来官方有重新评测了最后一题，有些人的提交就可以过了，也没有罚时了。
本次比赛也是质量蛮高，题目不是很难，但考察的知识点很全面，难度分布也比较合理。

1144. Decrease Elements To Make Array Zigzag

因为只能减1嘛，所以是到Easy题目。如果题目改成加1或减1，会难的多。
只需要比较2种情况，选择小的即可。

时间复杂度: O(N),
空间复杂度: O(1).

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
class Solution {
    const int INF = 0x3f3f3f3f;
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int ans1 = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            int neighbor = INF;
            if (i > 0) {
                neighbor = min(neighbor, nums[i - 1]);
            }
            if (i < nums.size() - 1) {
                neighbor = min(neighbor, nums[i + 1]);
            }
            if (neighbor != INF && neighbor <= nums[i]) {
                ans1 += nums[i] - neighbor + 1;
            }
        }
        int ans2 = 0;
        for (int i = 1; i < nums.size(); i += 2) {
            int neighbor = INF;
            if (i > 0) {
                neighbor = min(neighbor, nums[i - 1]);
            }
            if (i < nums.size() - 1) {
                neighbor = min(neighbor, nums[i + 1]);
            }
            if (neighbor != INF && neighbor <= nums[i]) {
                ans2 += nums[i] - neighbor + 1;
            }
        }
        return min(ans1, ans2);
    }
};

1145. Binary Tree Coloring Game

本题的难点在于理解题意。思路倒是十分直观，尽量选择最大的分支。如果大分支的数量大于一半，则必胜。
树的问题用递归，模版还是一个DFS。

时间复杂度: O(N), 遍历每个节点1次；
空间复杂度: O(N). 树的深度，最差为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
/**
 * 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 l, r;
    // return the number of node in subtree
    int dfs(TreeNode* root, int x) {
        if (root == nullptr)
            return 0;
        int left = dfs(root->left, x);
        int right = dfs(root->right, x);
        if (root->val == x) {
            l = left;
            r = right;
        }
        return left + right + 1;
    }
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        dfs(root, x);
        if (n == l + r + 1) {
            return l != r;
        } else {
            int parent = n - l - r - 1;
            return parent - 1 > l + r || l - 1 > r + parent || r - 1 > l + parent;
        }
    }
};

1146. Snapshot Array

比较暴力的思路是每次snap，保存一次所有状态。snap函数的时间，空间上会比较大。
另一个比较巧妙，但也不是很难想出来的思路是，每次保存变化的内容。我采用的是这种解法。

时间复杂度:

  • SnapshotArray: O(N)
  • set: O(1)
  • snap: O(1)
  • get: O(log 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
class SnapshotArray {
    vector<vector<pair<int, int>>> data;
    int current_snap_id = 0;
    const int INF = numeric_limits<int>::max();
public:
    SnapshotArray(int length) {
        data.resize(length, vector<pair<int, int>>(1, {0, 0}));
    }
    
    void set(int index, int val) {
        data[index].push_back({current_snap_id, val});
    }
    
    int snap() {
        return current_snap_id++;
    }
    
    int get(int index, int snap_id) {
        auto& target = data[index];
        auto it = lower_bound(target.begin(), target.end(), make_pair(snap_id, INF));
        --it;
        return it->second;
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

1147. Longest Chunked Palindrome Decomposition

Greedy。每次贪心的寻找相等的头和尾。
时间复杂度：O(n ^ 2),
空间复杂度: 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
class Solution {
    bool equal(const string& text, int begin1, int end1, int begin2, int end2) {
        if (end1 - begin1 != end2 - begin2) {
            return false;
        }
        for (int i = 0; i < end1 - begin1; ++i) {
            if (text[begin1 + i] != text[begin2 + i]) 
                return false;
        }
        return true;
    }
    int recurse(const string& text, int begin, int end) {
        if (begin == end)
            return 0;
        for (int i = 1; begin + i <= end - i; ++i) {
            if (equal(text, begin, begin + i, end - i, end)) {
                return recurse(text, begin + i, end - i) + 2;
            }
        }
        return 1;
    }
public:
    int longestDecomposition(string text) {
        return recurse(text, 0, text.size());
    }
};