网站设计ui,沈阳 网站开发,网络服务器可提供的常见服务有什么服务,海口建站模板#x1f468;#x1f393;作者简介#xff1a;爱好技术和算法的研究生 #x1f30c;上期文章#xff1a;力扣周赛#xff1a;第422场周赛 #x1f4da;订阅专栏#xff1a;力扣周赛 希望文章对你们有所帮助 第一道题模拟题#xff0c;第二道题经典拆分数组/线段树都… 作者简介爱好技术和算法的研究生 上期文章力扣周赛第422场周赛 订阅专栏力扣周赛 希望文章对你们有所帮助 第一道题模拟题第二道题经典拆分数组/线段树都可以做这两个要是都不会那就是基础不行需要差缺补漏了。第三题那个味太足了一看那个答案的顺序性就知道要二分答案了也很简单。 力扣周赛第424场周赛 使数组元素等于零零数组变换 I零数组变换 II 使数组元素等于零
题目描述 给你一个整数数组 nums 。
开始时选择一个满足 nums[curr] 0 的起始位置 curr 并选择一个移动 方向 向左或者向右。
此后你需要重复下面的过程
如果 curr 超过范围 [0, n - 1] 过程结束。如果 nums[curr] 0 沿当前方向继续移动如果向右移则 递增 curr 如果向左移则 递减 curr 。如果 nums[curr] 0: 将 nums[curr] 减 1 。 反转 移动方向向左变向右反之亦然。 沿新方向移动一步。
如果在结束整个过程后nums 中的所有元素都变为 0 则认为选出的初始位置和移动方向 有效 。
返回可能的有效选择方案数目。 示例1
示例2 输入nums [2,3,4,0,4,1,0]
输出0
解释 不存在有效的选择方案。
提示
1 nums.length 1000 nums[i] 100至少存在一个元素 i 满足 nums[i] 0 。 模拟题没啥好说的 class Solution {public int countValidSelections(int[] nums) {int ans 0;for(int i 0; i nums.length; i){if(nums[i] 0){int[] temp1 new int[nums.length];int[] temp2 new int[nums.length];for(int j 0; j nums.length; j){temp1[j] nums[j];temp2[j] nums[j];}if(check(temp1, i, 1))ans;if(check(temp2, i, -1))ans;}}return ans;}public boolean check(int[] nums, int cur, int dir){while(true){cur cur dir;if(cur 0 || cur nums.length)break;if(nums[cur] 0){nums[cur]--;dir * -1;}}for(int i 0; i nums.length; i){if(nums[i] ! 0)return false;}return true;}
}零数组变换 I
题目描述 给定一个长度为 n 的整数数组 nums 和一个二维数组 queries其中 queries[i] [li, ri]。
对于每个查询 queries[i]
在 nums 的下标范围 [li, ri] 内选择一个下标子集。将选中的每个下标对应的元素值减 1。
零数组 是指所有元素都等于 0 的数组。
如果在按顺序处理所有查询后可以将 nums 转换为 零数组 则返回 true否则返回 false。
数组的 子集 是对数组元素的选择可能为空。 示例1 输入 nums [1,0,1], queries [[0,2]]
输出 true
解释
对于 i 0 选择下标子集 [0, 2] 并将这些下标处的值减 1。 数组将变为 [0, 0, 0]这是一个零数组。
示例2 输入 nums [4,3,2,1], queries [[1,3],[0,2]]
输出 false
解释
对于 i 0 选择下标子集 [1, 2, 3] 并将这些下标处的值减 1。 数组将变为 [4, 2, 1, 0]。对于 i 1 选择下标子集 [0, 1, 2] 并将这些下标处的值减 1。 数组将变为 [3, 1, 0, 0]这不是一个零数组。
提示
1 nums.length 1050 nums[i] 1051 queries.length 105queries[i].length 20 li ri nums.length 很显然是拆分数组直接维护一个f其中f[i]表示nums[i]共处在哪些区间中只要f[i] nums[i]则说明肯定是可以在queries中将其处理到0。 所以问题转化为某个下标处在哪些区间中对于每个query的起始点start和终止点end只需要让f[start]和f[end 1]–即可维护这部分关系了。 class Solution {public boolean isZeroArray(int[] nums, int[][] queries) {int[] f new int[nums.length];for(int[] query : queries){int start query[0], end query[1];f[start];if(end 1 nums.length)continue;f[end 1]--;}int sum0;for(int i 0; i nums.length; i){sum f[i];if(nums[i] sum)return false;}return true;}
}零数组变换 II
题目描述 给你一个长度为 n 的整数数组 nums 和一个二维数组 queries其中 queries[i] [li, ri, vali]。
每个 queries[i] 表示在 nums 上执行以下操作
将 nums 中 [li, ri] 范围内的每个下标对应元素的值 最多 减少 vali。每个下标的减少的数值可以独立选择。
零数组 是指所有元素都等于 0 的数组。
返回 k 可以取到的 最小非负 值使得在 顺序 处理前 k 个查询后nums 变成 零数组。如果不存在这样的 k则返回 -1。 示例1 输入 nums [2,0,2], queries [[0,2,1],[0,2,1],[1,1,3]]
输出 2
解释
对于 i 0l 0, r 2, val 1 在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。 数组将变为 [1, 0, 1]。 对于 i 1l 0, r 2, val 1 在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。 数组将变为 [0, 0, 0]这是一个零数组。因此k 的最小值为 2。
示例2 输入 nums [4,3,2,1], queries [[1,3,2],[0,2,1]]
输出 -1
解释
对于 i 0l 1, r 3, val 2 在下标 [1, 2, 3] 处分别减少 [2, 2, 1]。 数组将变为 [4, 1, 0, 0]。 对于 i 1l 0, r 2, val 1 在下标 [0, 1, 2] 处分别减少 [1, 1, 0]。 数组将变为 [3, 0, 0, 0]这不是一个零数组。
提示
1 nums.length 1050 nums[i] 5 * 1051 queries.length 105queries[i].length 30 li ri nums.length1 vali 5 这个顺序性味太足了直接二分答案是不会超时的当然了你还是还想优化也可以因为那个拆分数组肯定是可以在每次复用的时候被二分的。 记得特判一下我没特判wa了一发。 class Solution {public int minZeroArray(int[] nums, int[][] queries) {int n nums.length;int now 0;for(int i 0; i n; i)now nums[i];if(now 0)return 0;int l 0, r queries.length - 1;while(l r){int mid (l r) 1;int[] f new int[n];for(int i 0; i mid; i){int start queries[i][0], end queries[i][1], val queries[i][2];f[start] val;if(end 1 n)continue;f[end 1] - val;}int sum 0;boolean flag true;for(int i 0; i n; i){sum f[i];if(nums[i] sum){flag false;break;}}if(!flag){l mid 1;}else{r mid - 1;}}return l queries.length ? -1 : l 1;}
}
