Skip to content

第 320 场周赛

比赛链接

Date: 2022-11-20

A 数组中不等三元组的数目

暴力即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                for (int k = j + 1; k < nums.size(); k++) {
                    if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        res = 0
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] != nums[j] and nums[j] != nums[k] and nums[k] != nums[i]:
                        res += 1
        return res

复杂度分析

  • 时间复杂度：\(O(n^3)\)
  • 空间复杂度：\(O(1)\)

B 二叉搜索树最近节点查询

将树上元素放到序列中，利用二分查找会更快。因为直接在树上做搜索，有可能会 T。题目中没有保证树的高度。

 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
class Solution {
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        vector<int> val;
        function<void(TreeNode*)> dfs = [&](TreeNode* root) {
            if (root == nullptr) {
                return;
            }
            dfs(root->left);
            val.push_back(root->val);
            dfs(root->right);
        };
        dfs(root);
        sort(val.begin(), val.end());
        vector<vector<int>> res;
        for (auto x : queries) {
            int a = -1, b = -1;
            int l = 0, r = val.size() - 1;
            while (l < r) {
                int m = (l + r + 1) >> 1;
                if (val[m] <= x) {
                    l = m;
                } else {
                    r = m - 1;
                }
            }
            if (val[l] <= x) {
                a = val[l];
            }
            auto pos = lower_bound(val.begin(), val.end(), x);
            if (pos != val.end()) {
                b = *pos;
            }
            res.push_back({a, b});
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n + q\log n)\)
  • 空间复杂度：\(O(n)\)

C 到达首都的最少油耗

对于每个节点 \(x\) 的每个孩子 \(y\)，设 \(y\) 子树的节点个数为 \(sum\)，那么从 \(y\) 到达 \(x\) 所需的车子个数就是 \((sum + seats - 1) / seats\)。对此求和即可。

 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
class Solution {
public:
    using ll = long long;
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for (auto v : roads) {
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }
        long long res = 0;
        function<int(int, int)> dfs = [&](int x, int f) {
            int sz = 1;
            for (auto &y : g[x]) {
                if (y == f) continue;
                int son = dfs(y, x);
                res += (son + seats - 1) / seats;
                sz += son;
            }
            return sz;
        };
        dfs(0, -1);
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)

D 完美分割的方案数

\(d[i][j]\) 表示以 \(i\) 结尾的前缀分为 \(j\) 段的方案数。

对于 \(p < i\) 并且 \(s[p]\) 是质数，\(s[i]\) 不是质数，\(i-p+1 \ge minLength\) 。那么 \(d[i][j] += d[p - 1][j - 1]\)。

遍历所有的 \(p\) 和 \(j\) 即可。但这样做负载度是 \(O(n^3)\) 的。可能无法通过。

然后发现，我们只需要考虑所有满足 \(p \le i - minLength + 1\) 且 \(s[p]\) 为质数的那些 \(p\) 就行。对于这些 \(p\) 的每个 \(j\)，用 \(g[j]\) 去表示 \(\sum_{p\in P}{d[p - 1][j - 1]}\)，其中 \(P\) 是上述所有合法 \(p\) 的集合。

class Solution {
public:
    static constexpr int MOD = 1E9 + 7;
    using ll = long long;
    int beautifulPartitions(string s, int k, int minLength) {
        int n = s.size();
        s = " " + s;
        vector<vector<ll>> d(n + 1, vector<ll>(k + 1));
        vector<ll> g(k + 1);

        unordered_map<char, int> isprime;
        isprime['2'] = isprime['3'] = isprime['5'] = isprime['7'] = 1;

        d[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            if (i - minLength + 1 >= 1 && isprime.count(s[i - minLength + 1])) {
                for (int j = 0; j < k; j++) {
                    g[j] = (g[j] + d[i - minLength][j]) % MOD;
                }
            }
            if (!isprime.count(s[i])) {
                for (int j = 0; j < k; j++) {
                    d[i][j + 1] = g[j];
                }
            }
        }
        return d[n][k];
    }
};

复杂度分析

  • 时间复杂度：\(O(n^2)\)
  • 空间复杂度：\(O(n^2)\)
本文访问 次