LeetCode biweekly contest 26

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (7)
115 / 7795 YoungForest 19 0:33:49 0:03:55 0:08:25 0:11:57 0:28:49 1

上上周是五一假期，鸽了一场双周赛。之后还是会尽量参加的。最近比赛越来越顺手了，无论是每次的排名，还是rating，或是残酷群的排名。比之前都有所上升。尤其要感谢残酷群的每日一题和不定时的讲座，让我对DP和很多Hard的题目有了解决的信心。在此，再次安利一下残酷刷题群.

1446. Consecutive Characters

滑动窗口，维持整个窗口的字母相等。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxPower(string s) {
        const int n = s.size();
        int l = 0, r = 0;
        int ans = 1;
        for (; r < s.size(); ++r) {
            if (s[r] == s[l]) continue;
            else {
                ans = max(ans, r - l);
                l = r;
            }
        }
        ans = max(ans, n - l);
        return ans;
    }
};

1447. Simplified Fractions

枚举所有的分母和分子，并判断是否是最简形式。幸运的是，C++17已经内置提供gcd函数。

时间复杂度: O(n^2),
空间复杂度: O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for (int down = 2; down <= n; ++down) {
            for (int up = 1; up < down; ++up) {
                if (gcd(up, down) == 1) {
                    ans.push_back(to_string(up) + "/" + to_string(down));
                }
            }
        }
        return ans;
    }
};

1448. Count Good Nodes in Binary Tree

dfs, 把祖先节点的最大值作为参数传入。

时间复杂度: O(n),
空间复杂度: 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    const int INF = 0x3f3f3f3f;
    int recurse(TreeNode* root, int maxValue) {
        if (!root) return 0;
        int ans = 0;
        if (root->val >= maxValue) ans = 1;
        maxValue = max(maxValue, root->val);
        return recurse(root->left, maxValue) + recurse(root->right, maxValue) + ans;
    }
public:
    int goodNodes(TreeNode* root) {
        return recurse(root, -INF);
    }
};

1449. Form Largest Integer With Digits That Add up to Target

DP. 背包问题，每次尝试加入一个数字。
可以利用Greedy的思路，如果2个数的cost相同，则只有大数有用，进行常数上的优化。

时间复杂度: O(target * target * 9),
空间复杂度: O(target * target).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        unique = {}
        seen = set()
        for i in range(len(cost) - 1, -1, -1):
            if cost[i] not in seen:
                seen.add(cost[i])
                unique[i + 1] = cost[i]
        @lru_cache(None)
        def dp(t: int) -> int:
            if t < 0:
                return -1
            if t == 0:
                return 0
            ans = -1
            for i in unique:
                tmp = dp(t - unique[i])
                if tmp >= 0:
                    ans = max(ans,  tmp * 10 + i)
            return ans
        ans = dp(target)
        return str(ans) if ans >= 0 else '0'

Discuss中有O(target)的解法，主要思路是，不再以dp存储最大的字符串，而只存数位长度，然后再backward构造出结果。