深圳网站建_企业网站设计定制,专业放心的企业展厅设计,怎么用txt做网站,jqueryui做的网站文章目录 T1 统计已测试设备代码解释 T2 双模幂运算代码解释 T3 统计最大元素出现至少 K 次的子数组代码解释 T4 统计好分割方案的数目代码解释 链接#xff1a;第 375 场周赛 - 力扣#xff08;LeetCode#xff09;
T1 统计已测试设备
给你一个长度为 n 、下标从 0 开始的… 文章目录 T1 统计已测试设备代码解释 T2 双模幂运算代码解释 T3 统计最大元素出现至少 K 次的子数组代码解释 T4 统计好分割方案的数目代码解释 链接第 375 场周赛 - 力扣LeetCode
T1 统计已测试设备
给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages 表示 n 个设备的电池百分比。
你的任务是按照顺序测试每个设备 i执行以下测试操作
如果 batteryPercentages[i] 大于 0 增加 已测试设备的计数。将下标在 [i 1, n - 1] 的所有设备的电池百分比减少 1确保它们的电池百分比 不会低于 0 即 batteryPercentages[j] max(0, batteryPercentages[j] - 1)。移动到下一个设备。 否则移动到下一个设备而不执行任何测试。
返回一个整数表示按顺序执行测试操作后 已测试设备 的数量。
示例 1 输入batteryPercentages [1,1,2,1,3] 输出3 解释按顺序从设备 0 开始执行测试操作 在设备 0 上batteryPercentages[0] 0 现在有 1 个已测试设备batteryPercentages 变为 [1,0,1,0,2] 。 在设备 1 上batteryPercentages[1] 0 移动到下一个设备而不进行测试。 在设备 2 上batteryPercentages[2] 0 现在有 2 个已测试设备batteryPercentages 变为 [1,0,1,0,1] 。 在设备 3 上batteryPercentages[3] 0 移动到下一个设备而不进行测试。 在设备 4 上batteryPercentages[4] 0 现在有 3 个已测试设备batteryPercentages 保持不变。 因此答案是 3 。 示例 2 输入batteryPercentages [0,1,2] 输出2 解释按顺序从设备 0 开始执行测试操作 在设备 0 上batteryPercentages[0] 0 移动到下一个设备而不进行测试。 在设备 1 上batteryPercentages[1] 0 现在有 1 个已测试设备batteryPercentages 变为 [0,1,1] 。 在设备 2 上batteryPercentages[2] 0 现在有 2 个已测试设备batteryPercentages 保持不变。 因此答案是 2 。 提示
1 n batteryPercentages.length 100 0 batteryPercentages[i] 100
代码解释
暴力 O(n^2)
class Solution {public int countTestedDevices(int[] batteryPercentages) {int ans 0;int n batteryPercentages.length;for (int i 0; i n; i) {if (batteryPercentages[i] 0) {for (int j i 1; j n; j) {batteryPercentages[j] Math.max(0, batteryPercentages[j]-1);}ans;}}return ans;}
}T2 双模幂运算
给你一个下标从 0 开始的二维数组 v a r i a b l e s variables variables 其中 v a r i a b l e s [ i ] [ a i , b i , c i , m i ] variables[i] [a_i, b_i, c_i, m_i] variables[i][ai,bi,ci,mi]以及一个整数 target 。
如果满足以下公式则下标 i 是 好下标 0 i v a r i a b l e s . l e n g t h 0 i variables.length 0ivariables.length ( ( a i b i m o d 10 ) c i ) m o d m i t a r g e t ((a_i^{b_i} mod~ 10)^{c_i}) ~mod~ m_i target ((aibimod 10)ci) mod mitarget
返回一个由 好下标 组成的数组顺序不限 。
提示
1 variables.length 100variables[i] [ai, bi, ci, mi]1 ai, bi, ci, mi 1030 target 103
代码解释
暴力 O(n(bc))用 BigInteger 防止超范围
import java.math.BigInteger;
class Solution {public ListInteger getGoodIndices(int[][] variables, int target) {ListInteger ans new ArrayList();int n variables.length;for (int j 0; j n; j) {int[] v variables[j];int a v[0], b v[1], c v[2], m v[3];long sum 1;for (int i 0; i b; i) {sum * a;sum % 10;}BigInteger s new BigInteger(String.valueOf(sum));long t sum;for (int i 1; i c; i) {s s.multiply(BigInteger.valueOf(t));}if (s.mod(BigInteger.valueOf(m)).intValue() target) {ans.add(j);}}return ans;}
}T3 统计最大元素出现至少 K 次的子数组
给你一个整数数组 nums 和一个 正整数 k 。
请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组并返回满足这一条件的子数组的数目。
子数组是数组中的一个连续元素序列。
示例 1 输入nums [1,3,2,3,3], k 2 输出6 解释包含元素 3 至少 2 次的子数组为[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。 示例 2 输入nums [1,4,2,1], k 3 输出0 解释没有子数组包含元素 4 至少 3 次。 提示
1 nums.length 10^51 nums[i] 10^61 k 10^5
代码解释
滑动窗口窗口内最大值刚好为 K 次时包含此窗口数组的子数组数为左长度乘右长度用队列记录每个最大值的位置多找到一个最大值左长度向右侧移动一个位置防止左侧算重复了。时间复杂度 O(n) 。
做的时候脑抽了以为是子数组里的最大元素出现至少 K 次没写出来快结束了才发现最大值固定了。
class Solution {public long countSubarrays(int[] nums, int k) {int n nums.length;int max Arrays.stream(nums).max().getAsInt();QueueInteger queue new LinkedList();int cnt 0, l 0, r 0;for (int i 0; i n; i) {if (nums[i] max) {cnt;queue.add(i);r i;}if (cnt k) {break;}}if (cnt k) return 0;int pre queue.poll();long ans (long) (pre 1) * (n - r);while (r n) {if (nums[r] max) {queue.add(r);int t queue.poll();ans (long) (t - pre) * (n - r);pre t;}}return ans;}
}T4 统计好分割方案的数目
给你一个下标从 0 开始、由 正整数 组成的数组 nums。
将数组分割成一个或多个 连续 子数组如果不存在包含了相同数字的两个子数组则认为是一种 好分割方案 。
返回 nums 的 好分割方案 的 数目。
由于答案可能很大请返回答案对 109 7 取余 的结果。
示例 1 输入nums [1,2,3,4] 输出8 解释有 8 种 好分割方案 ([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]) 和 ([1,2,3,4]) 。 示例 2 输入nums [1,1,1,1] 输出1 解释唯一的 好分割方案 是([1,1,1,1]) 。 示例 3 输入nums [1,2,1,3] 输出2 解释有 2 种 好分割方案 ([1,2,1], [3]) 和 ([1,2,1,3]) 。 提示
1 nums.length 10^5 1 nums[i] 10^9
代码解释
这次最后一题也比较简单用一个哈希表记数的出现次数一个哈希集合记出现的数所有集合中的数都有了就划分为一个组划分出来的所有组可以随意组合根据组合公式可以知道 n n n 组就有 2 n 2^n 2n 个方案数最后用 BigInteger 防止超范围。
import java.math.BigInteger;
class Solution {public int numberOfGoodPartitions(int[] nums) {MapInteger, Integer map new HashMap();for (int n : nums) {map.putIfAbsent(n, 0);map.put(n, map.get(n) 1);}int n nums.length, cnt 0;SetInteger set new HashSet();for (int num : nums) {set.add(num);map.put(num, map.get(num) - 1);if (map.get(num) 0) {set.remove(num);}if (set.isEmpty()) {cnt;}}BigInteger ans new BigInteger(1);BigInteger t new BigInteger(2);BigInteger mod new BigInteger(1000000007);for (int i 1; i cnt; i) {ans ans.multiply(t);}return ans.mod(mod).intValue();}
}
