第 319 场周赛

比赛链接

Date: 2022-11-13

A 温度转换

直接转换

C++Python

class Solution {
public:
    vector<double> convertTemperature(double c) {
        return {c + 273.15, c * 1.8 + 32};
    }
};

class Solution:
    def convertTemperature(self, celsius: float) -> List[float]:
        return [celsius + 273.15, celsius * 1.8 + 32]

复杂度分析

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

B 最小公倍数为 K 的子数组数目

遍历，维护每个窗口的 \(lcm\) 即可。

C++Python

class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int res = 0, n = nums.size();
        for (int i = 0; i < n; i++) {
            int l = nums[i];
            for (int j = i; j < n; j++) {
                l = lcm(l, nums[j]);
                if (l == k) {
                    res++;
                } else if(l > k) {
                    break;
                }
            }
        }
        return res;
    }
};

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        res = 0
        for i in range(len(nums)):
            l = nums[i]
            for j in range(i, len(nums)):
                l = lcm(l, nums[j])
                if l == k:
                    res += 1
                elif l > k:
                    break
        return res

复杂度分析

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

C 逐层排序二叉树所需的最少操作数目

首先通过 DFS 把每行的数字整理到一个 vec 中，然后对于一个序列，计算交换任意两个数字使其有序的最小次数。

记这个序列是 \(v\)，\(pos[v[i]]\) 是 \(v[i]\) 正确排序后所处的正确位置。对于每个置换环，长度为 \(len\)，那么交换次数就是 \(len - 1\)。

C++

class Solution {
public:
    int minimumOperations(TreeNode* root) {
        unordered_map<int, vector<int>> g;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* rt, int dep) {
            if (rt == nullptr) return;
            g[dep].push_back(rt->val);
            dfs(rt->left, dep + 1);
            dfs(rt->right, dep + 1);
        };
        dfs(root, 0);
        int res = 0;
        auto get = [&](vector<int>& v) {
            map<int, int> pos;
            for (int i = 0; i < v.size(); i++) {
                pos[v[i]] = i;
            }
            int corr_pos = 0;
            for (auto &[k, v] : pos) {
                pos[k] = corr_pos++;
            }
            for (int i = 0; i < v.size(); i++) {
                if (v[i] == -1 || i == pos[v[i]]) {
                    continue;
                }
                int p = pos[v[i]], cnt = 1;
                while (p != i) {
                    int val = v[p];
                    v[p] = -1;
                    cnt++;
                    p = pos[val];
                }
                res += cnt - 1;
            }
        };

        for (auto &[k, v] : g) {
            get(v);
        }
        return res;
    }
};

复杂度分析

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

D 不重叠回文子字符串的最大数目

设 \(d[i]\) 为将前 \(i\) 个字符构成的子串中选出若干个不重叠长度至少为 \(k\) 的回文子串个数。

那么转移方程有：

\[d[i] = \max_{0 \le j \le i - k} d[j] + 1 \quad s[j+1...i] 是回文串\]

由于长度只有 2000，所以可以 \(O(n^2)\) 的时间内预处理出每个子串是否是回文串。

C++

class Solution {
public:
    int maxPalindromes(string s, int k) {
        int n = s.size();
        vector<int> d(n + 1);
        vector<vector<int>> isp(n + 1, vector<int>(n + 1));
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l >= 0 && r < n) {
                if (s[l] == s[r]) {
                    isp[l + 1][r + 1] = 1;
                } else {
                    break;
                }
                l--; r++;
            }
            l = i - 1, r = i;
            while (l >= 0 && r < n) {
                if (s[l] == s[r]) {
                    isp[l + 1][r + 1] = 1;
                } else {
                    break;
                }
                l--; r++;
            }
        }
        for (int i = 1; i <= n; i++) {
            d[i] = d[i - 1];
            for (int j = 0; j <= i - k; j++) {
                if (isp[j + 1][i]) {
                    d[i] = max(d[i], d[j] + 1);
                }
            }
        }
        return d[n];
    }
};

复杂度分析

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

本文访问 次