6208. 有效时间的数目
- 通过的用户数2686
- 尝试过的用户数2790
- 用户总通过次数2721
- 用户总提交次数7089
- 题目难度Easy
给你一个长度为 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 之间的数字替换。
思路：回溯 check
class Solution {public int countTime(String time) {return dfs(time, 0, "");}int dfs(String s, int u, String t) {if (u == 5) {if (check(t))return 1;else return 0;}if (s.charAt(u) != '?') return dfs(s, u + 1, t + s.charAt(u));else {int res = 0;for (char c = '0'; c <= '9'; c++) {res += dfs(s, u + 1, t + c);}return res;}}boolean check(String s) {int h = (s.charAt(0) - '0') * 10 + s.charAt(1) - '0';int m = (s.charAt(3) - '0') * 10 + s.charAt(4) - '0';return h >= 0 && h <= 23 && m >= 0 && m <= 59;}}
6209. 二的幂数组中查询范围内的乘积
- 通过的用户数1976
- 尝试过的用户数2316
- 用户总通过次数2016
- 用户总提交次数5933
- 题目难度Medium
给你一个正整数 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
思路：数乘转换为指数相加
class Solution {public int[] productQueries(int n, int[][] q) {int m = Integer.bitCount(n);int[] a = new int[m];for (int i = 0; i < m; i++) {for (int j = 0; j < 31; j++) {if ((n >> j & 1) == 1) {a[i] = j;n ^= 1 << j;break;}}}// System.out.println(Arrays.toString(a));int[] p = new int[m + 1];for (int i = 1; i <= m; i++) {p[i] = p[i - 1] + a[i - 1];}int[] res = new int[q.length];for (int i = 0; i < q.length; i++) {int l = q[i][0], r = q[i][1];res[i] = pow(2, p[r + 1] - p[l]);}return res;}int pow(long x, int c) {long res = 1;int MOD = (int)(1e9 + 7);while (c > 0) {if ((c & 1) == 1)res = (res * x) % MOD;x = (x * x) % MOD;c >>= 1;}return (int) res;}}
6210. 最小化数组中的最大值
- 通过的用户数1028
- 尝试过的用户数1963
- 用户总通过次数1083
- 用户总提交次数5104
- 题目难度Medium
给你一个下标从 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
思路：二分
class Solution {public int minimizeArrayValue(int[] nums) {int l = 0, r = (int)(1e9);while (l < r) {int mid = l + r >> 1;if (check(mid, nums))r = mid;else l = mid + 1;}return l;}boolean check(int x, int[] nums) {long s = 0;for (int i = nums.length - 1; i >= 0; i--) {if (nums[i] <= x)s = Math.max(0, s - (x - nums[i]));else s += nums[i] - x;}return s == 0;}}
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 表示一棵合法的树。
思路：考虑每条边将整棵树分成两部分的最大公因子，再一次枚举总和的所有因子，判断边数能否满足要求
class Solution {final int N = 20010;int[] h = new int[N], e = new int[2 * N], ne = new int[2 * N];Map<Integer, Integer> map = new HashMap<>();int idx = 0, s = 0;int[] nums;public int componentValue(int[] nums, int[][] edges) {Arrays.fill(h, -1);this.nums = nums;for (int[] p : edges) {int a = p[0], b = p[1];add(a, b);add(b, a);}for (int x : nums) {s += x;}dfs(0, -1);for (int i = 1; i <= s; i++) {if (s % i != 0 || s / i > nums.length) continue;int c = 0, j = i;while (j <= s) {c += map.getOrDefault(j, 0);j += i;}if (c >= s / i - 1) {return s / i - 1;}}return 0;}int dfs(int u, int p) {int res = nums[u];for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j == p) continue;int x = dfs(j, u);res += x;map.merge(gcd(s-x, x), 1, Integer::sum);}return res;}void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}}
若有收获，就点个赞吧
0 人点赞
