什么网站可以做新闻听写,网站建设 域名 数据库,制作网页需要多少钱,做网站可以先做再给钱吗目录
一#xff0c;3190. 使所有元素都可以被 3 整除的最少操作数
二#xff0c;3191. 使二进制数组全部等于 1 的最少操作次数 I
三#xff0c;3192. 使二进制数组全部等于 1 的最少操作次数 II
四#xff0c;3193. 统计逆序对的数目 一#xff0c;3190. 使所有元素都…目录
一3190. 使所有元素都可以被 3 整除的最少操作数
二3191. 使二进制数组全部等于 1 的最少操作次数 I
三3192. 使二进制数组全部等于 1 的最少操作次数 II
四3193. 统计逆序对的数目 一3190. 使所有元素都可以被 3 整除的最少操作数 本题可以直接模拟如果使用减法操作那么需要操作 x % 3 次如果使用加法操作那么需要操作 3 - x % 3 次。问最少的操作次数直接取两者的最小值就行。
代码如下
class Solution {public int minimumOperations(int[] nums) {int ans 0;for(int x : nums){ans Math.min(Math.abs(3-x%3), x%3);}return ans;}
}
二3191. 使二进制数组全部等于 1 的最少操作次数 I 本题直接从左往右遍历注 i nums.length-2
遇到0将nums[i]nums[i1]nums[i2] 反转即 ^1ans遇到1什么都不做循环结束判断后两个数是否全为1如果是返回ans否则返回-1
代码如下
class Solution {public int minOperations(int[] nums) {int ans 0;int i 0;for(; inums.length-2; i){if(nums[i]0){nums[i] ^ 1;nums[i1] ^ 1;nums[i2] ^ 1;ans;}}return nums[i]1 nums[i1]1 ? ans : -1;}
}
三3192. 使二进制数组全部等于 1 的最少操作次数 II 本题也可以采用上述做法代码如下
class Solution {public int minOperations(int[] nums) {int n nums.length;int ans 0;for(int i0; in; i){if(nums[i] 0){for(int ji; jn; j)nums[j] ^ 1;ans;}}return ans;}
}
但是该做法是O(n^2)的时间复杂度会超时那么上述做法还有哪里可以优化可以发现如果一个数执行 ^1操作偶数次它就会变回原来的值所以我们可以统计后续元素需要执行反转操作的次数cnt在枚举到x时如果cnt为奇数x ^1再判断 x 是否为 0如果为0cnt。依次类推最终得到的cnt就是答案。
代码如下
class Solution {public int minOperations(int[] nums) {int ans 0;for(int i0; inums.length; i){if(ans%21)nums[i] ^ 1;if(nums[i] 0){ans;}}return ans;}
}
四3193. 统计逆序对的数目 本题可以从后先前考虑假设有3个数构造逆序对为2的排序:
如果最后一个数是2那么该数与[0i-1]能组成0个逆序对就需要[0i-1]有2个逆序对如果最后一个数是1那么该数与[0i-1]能组成1个逆序对就需要[0i-1]有1个逆序对如果最后一个数是0那么该数与[0i-1]能组成2个逆序对就需要[0i-1]有0个逆序对
依次类推上述问题就化成了与原问题相同的子问题。可以定义dfs(ij)前 i 个数有 j 个逆序对时的排序个数。
没有requirements束缚假设 k 为 perm[i] 小于[0i-1]元素的个数即 perm[i] 能产生 k 个逆序对那么问题就转换成了前 i-1个数有 j - k 个逆序对的排序个数。注k Math.min(ij)有requirements束缚该问题就只能转换成前 i-1个数有 req[i-1] 个逆序对的排序个数。注req[i-1] j req[i-1] j - i这两个条件就表示req[i-1]的范围必须在[ j - ij]可以这样理解当前perm[i]能与前i-1个数组成[0i]个逆序对那么前i-1个数需要有[j - ij]个逆序对
代码如下
class Solution {public int numberOfPermutations(int n, int[][] requirements) {int[] req new int[n];Arrays.fill(req, -1);req[0] 0;for(int[] x : requirements){req[x[0]] x[1];}if(req[0]0) return 0; for(int[] r : memo)Arrays.fill(r, -1);return dfs(n-1, req[n-1], req);}int[][] memo new int[301][401];int dfs(int i, int j, int[] req){if(i 0) return 1;if(memo[i][j] ! -1) return memo[i][j];int res 0;int cnt req[i-1];if(cnt 0){if(cnt j cnt j-i)res dfs(i-1, cnt, req);}else{for(int k0; kMath.min(i, j); k){res (res dfs(i-1, j-k, req))%1_000_000_007;}}return memo[i][j] res;}
}
