什么网站模板,运营推广策略有哪些,苏州企业网站制作服务,QQ可以在网站做临时会话么【问题描述】[中等]5477. 排布二进制网格的最少交换次数 【解答思路】
贪心
限制条件 第一行要求末尾的0要尽量多
计算每行最后有几个0遍历交互 符合条件 第i行的末尾0的数量为n-i-1 统计交换次数第i行的末尾0的数量小于n-i-1#xff0c;不符合条件
时间复杂度#xff1a…【问题描述】[中等]5477. 排布二进制网格的最少交换次数 【解答思路】
贪心
限制条件 第一行要求末尾的0要尽量多
计算每行最后有几个0遍历交互 符合条件 第i行的末尾0的数量为n-i-1 统计交换次数第i行的末尾0的数量小于n-i-1不符合条件
时间复杂度O(N^2) 空间复杂度O(N)
class Solution {public int minSwaps(int[][] grid) {int n grid.length;int res 0;int sum;int[] cnt new int[n];//计算末尾0的数量for(int i0;in;i){sum0;for(int jn-1;j0;j--){if(grid[i][j]0) sum;else break;}cnt[i]sum;}for(int i0;in;i){if(cnt[i]n-i-1){for(int ji1;jn;j){//只要满足条件就可以交换一次停止了//这里因为cnt[i]i越小cnt[i]会越大if(cnt[j]n-i-1){resswap(cnt,i,j);break;}}}}//第i行的末尾0的数量小于n-i-1不符合条件for(int i0;in;i){if(cnt[i]n-1-i) return -1;}return res;}// 由j到i 依次向上交换 并统计次数private int swap(int[] num,int i,int j){int count 0;while(ji){int temp num[j-1];num[j-1] num[j];num[j]temp;j--;count;}return count;}
}
【问题描述】[困难]5478. 最大得分 【解答思路】
双指针
求两个队列相等时可以切换的最大值 双指针模拟a、b队列当前的和
如果a队列的当前值b队列的当前值那么b队列的最大值只能b队列的当前值了 因为本身ab了后面会越差越大的因为他是有序的把b往后走一位才可能相等如果a队列的当前值 b队列的当前值那么a队列的最大值只能a队列的当前值了如果相等了就用两个队列的当前的和的最大值替换原来的值再加上当前值 相等时用两个队列的当前的和的最大值替换原来的值会怀疑这么写不对他明明是另一个队列的最大值并不是当前队列的最大值 这时你就可以想一下我走过去另一条队列再走回来原队列 其实是一样的
时间复杂度O(N) 空间复杂度O(1)
class Solution {public int maxSum(int[] nums1, int[] nums2) {int MOD 1000000007;//两个数列的最大值long ans1 0, ans2 0;//两个数列的下标int i 0, j 0;//如果有一个到头了就不能再用了while (i nums1.length j nums2.length) {//如果num2[j]大了就不能切换数组了(毕竟是有序数组后面会越差越多)if (nums1[i] nums2[j]) {ans1 nums1[i];i;//反之num[i]大了也一样} else if (nums1[i] nums2[j]) {ans2 nums2[j];j;} else {//如果两个值一样了就选择最大的那个把两个队列的值替换掉还要加上当前的值ans1 Math.max(ans1, ans2) nums1[i];ans2 ans1;i;j;} }//把第一个序列的或者第二个序列的未完成的完成了while (i nums1.length) {ans1 nums1[i];i;}while (j nums2.length) {ans2 nums2[j];j;}return (int) (Math.max(ans1, ans2) % MOD);}}
【总结】
1. 数组题目不要太过于死板 要找到特殊的限制条件 用局部的思想代替全局如5477题目中用末尾0的个数进行统计、用统计的cnt数组计算交换次数
2.有序 双指针是个好东西 找到突破点 困难题目也不难了
参考链接https://blog.csdn.net/weixin_46285416/article/details/107744218
