leetcode biweekly contest 88

前三题确实都是常规题目，第四题出的不是很好。

6208. 有效时间的数目

题目

给你一个长度为 5 的字符串 time ，表示一个电子时钟当前的时间，格式为 "hh:mm" 。最早可能的时间是 "00:00" ，最晚可能的时间是 "23:59" 。

在字符串 time 中，被字符 ? 替换掉的数位是未知的，被替换的数字可能是 0 到 9 中的任何一个。

请你返回一个整数 answer ，将每一个 ? 都用 0 到 9 中一个数字替换后，可以得到的有效时间的数目。

示例 1：

输入：time = "?5:00"
输出：2
解释：我们可以将 ? 替换成 0 或 1 ，得到 "05:00" 或者 "15:00" 。注意我们不能替换成 2 ，因为时间 "25:00" 是无效时间。所以我们有两个选择。

示例 2：

输入：time = "0?:0?"
输出：100
解释：两个 ? 都可以被 0 到 9 之间的任意数字替换，所以我们总共有 100 种选择。

示例 3：

输入：time = "??:??"
输出：1440
解释：小时总共有 24 种选择，分钟总共有 60 种选择。所以总共有 24 * 60 = 1440 种选择。

提示：

time 是一个长度为 5 的有效字符串，格式为 "hh:mm" 。
"00" <= hh <= "23"
"00" <= mm <= "59"
字符串中有的数位是 '?' ，需要用 0 到 9 之间的数字替换。

地址

https://leetcode.cn/problems/number-of-valid-clock-times/

题意

直接模拟

思路

总共也就 1440 种状态，直接暴力搜索即可。
复杂度分析：

时间复杂度：$O(10^n)$。
空间复杂度：$O(n)$。

代码

class Solution {
public:
    void dfs(string &s, int pos, int &res) {
        if (pos == s.size()) {
            int h = (s[0] - '0')*10 + s[1] - '0';
            int m = (s[3] - '0')*10 + s[4] - '0';
            if (h < 24 && m < 60) {
                res++;
            }
            return;
        }
        
        if (s[pos] == '?') {
            for (int i = 0; i <= 9; i++) {
                s[pos] = '0' + i;
                dfs(s, pos + 1, res);
                s[pos] = '?';
            }
        } else {
            dfs(s, pos + 1, res);
        }
    }
    
    int countTime(string time) {
        int ans = 0;
        dfs(time, 0, ans);
        return ans;
    }
};

6209. 二的幂数组中查询范围内的乘积

题目

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含最少数目的 2 的幂，且它们的和为 n 。powers 数组是非递减顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 109 + 7 取余。

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 109 + 7 得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 109 + 7 取余后结果相同，所以返回 [2] 。

提示：

1 <= n <= 109
1 <= queries.length <= 105
0 <= starti <= endi < powers.length

地址

https://leetcode.cn/problems/find-the-original-array-of-prefix-xor/

题意

数学问题

思路

将一个整数拆分成 $2$ 的幂的很容易，直接拆分即可，根据二进制的定义可以知道，一个整数最多可以拆分为 $32$ 个 $2$ 的幂数，然后按照题目要求求出连乘的积即可。
复杂度分析：

时间复杂度：时间复杂度为 $O(log n + m \log n)$，其中 $m$ 表示数组的长度，$n$ 表示给定的数。
空间复杂度：空间复杂度为 $O(\log n)$。

代码

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> arr;
        for (int i = 0; i < 32; i++) {
            if (n & (1 << i)) {
                arr.emplace_back(1 << i);
            }
        }
        long long mod = 1e9 + 7;
        vector<int> ans;
        for (int i = 0; i < queries.size(); i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            long long curr = 1;
            for (int j = x; j <= y; j++) {
                curr = (curr * arr[j]) % mod;
            }
            ans.emplace_back(curr);
        }
        return ans;
    }
};

6210. 最小化数组中的最大值

题目

给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。

每一步操作中，你需要：

选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
将 nums[i] 减 1 。
将 nums[i - 1] 加 1 。
你可以对数组执行任意次上述操作，请你返回可以得到的 nums 数组中最大值最小为多少。

示例 1：

输入：nums = [3,7,1,6]
输出：5
解释：
一串最优操作是：
1. 选择 i = 1 ，nums 变为 [4,6,1,6] 。
2. 选择 i = 3 ，nums 变为 [4,6,2,5] 。
3. 选择 i = 1 ，nums 变为 [5,5,2,5] 。
nums 中最大值为 5 。无法得到比 5 更小的最大值。
所以我们返回 5 。

示例 2：

输入：nums = [10,1]
输出：10
解释：
最优解是不改动 nums ，10 是最大值，所以返回 10 。

提示：

n == nums.length
2 <= n <= 105
0 <= nums[i] <= 109

地址

https://leetcode.cn/problems/minimize-maximum-of-array/

题意

数学方法

思路

典型的贪心算法，我们知道如果想将 $nums[i]$ 进行减小，只能将 $i$ 之前的元素进行减小，因此我们知道前 $i$ 个数通过变换之后最小的元素也只能变为前 $i$ 个元素的平均值，否则一定会出现一个大于平均值的元素，因此我们尝试求出该序列的前 $i$ 个元素的平均值的最大值即为可能变换出来的最小值。因为我们无论如何进行变换均不能将前 $i$ 个元素的最大值变为前 $i$ 个元素平均值之下。
复杂度分析

时间复杂度：时间复杂度为 $O(n)$，$n$ 为数组的长度。
空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        long long ans = nums[0];
        long long sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            ans = max(ans, (sum + i) / (i + 1));
        }
        return ans;
    }
};

6211. 创建价值相同的连通块

题目

有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。

给你一个长度为 n 下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 个节点的值。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点ai与 bi 之间有一条边。

你可以删除一些边，将这棵树分成几个连通块。一个连通块的价值定义为这个连通块中所有节点 i 对应的 nums[i] 之和。

你需要删除一些边，删除后得到的各个连通块的价值都相等。请返回你可以删除的边数最多为多少。

示例 1：

输入：nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] 
输出：2 
解释：上图展示了我们可以删除边 [0,1] 和 [3,4] 。得到的连通块为 [0] ，[1,2,3] 和 [4] 。每个连通块的价值都为 6 。可以证明没有别的更好的删除方案存在了，所以答案为 2 。

示例 2：

输入：nums = [2], edges = []
输出：0
解释：没有任何边可以删除。

提示：

1 <= n <= 2 * 104
nums.length == n
1 <= nums[i] <= 50
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
edges 表示一棵合法的树。

地址

https://leetcode.cn/problems/create-components-with-same-value/

题意

深度优先搜索

思路

我们知道一个数 $x$ 的最多可能有 $d(x)$ 个不同的因子，因此我们直接尝试所有可能的因子即可。我们尝试将树分为 $k$ 部分，则每部分的和为 $\dfrac{\sum \limits _{i=0}^{n-1}nums[i]}{k}$，所以我们可以尝试的次数最多约为 $d(\sum \limits _{i=0}^{n-1}nums[i])$。
当然最重要的是要检测树是否可以被分为 $k$ 个子模块，此时我们需要用深度优先搜索来检测。感觉比较难写的倒是这个 DFS 检测算法不是很好写。非常经典的一个树的遍历的算法。
复杂度分析：

时间复杂度：$O(d(sum) \times n)$，其中 $n$ 表示给定的数组的长度。
空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。

代码

class Solution {
public:
    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        int tot = 0;
        vector<vector<int>> graph(n);
        tot = accumulate(nums.begin(), nums.end(), 0);
        for (auto v : edges) {
            graph[v[0]].emplace_back(v[1]);
            graph[v[1]].emplace_back(v[0]);
        }
        function<int(int, int, int)> dfs = [&](int from, int to, int target) {
            int sum = nums[to];
            for (auto v : graph[to]) {
                if (v == from) continue;
                int res = dfs(to, v, target);
                if (res < 0) {
                    return -1;
                }
                sum += res;
            }
            if (sum > target) return -1;
            return sum % target;
        };
        for (int i = n - 1; i > 0; i--) {
            if (tot % (i + 1) == 0) {
                int x = tot / (i + 1);
                if (dfs(-1, 0, x) == 0) {
                    return i;
                }
            }
        }
        return 0;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← 树状数组 leetcode contest 314 →

扫描二维码，分享此文章