[周赛第200场][Leetcode][第5477题][第5478题][JAVA][双指针][贪心]

╰半橙微兮° 2023-03-04 09:12 9阅读 0赞

#### 【问题描述】\[中等\]5477. 排布二进制网格的最少交换次数 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 贪心 ######

限制条件 第一行要求末尾的0要尽量多

1.  计算每行最后有几个0
2.  遍历交互 符合条件 第i行的末尾0的数量为n-i-1 统计交换次数
3.  第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 i=0;i<n;i++){ 
                sum=0;
                for(int j=n-1;j>=0;j--){ 
                    if(grid[i][j]==0) sum++;
                    else break;
                }
                cnt[i]=sum;
            }
            for(int i=0;i<n;i++){ 
                if(cnt[i]<n-i-1){ 
                    for(int j=i+1;j<n;j++){ 
                    //只要满足条件就可以交换一次，停止了
                    //这里因为cnt[i]，i越小，cnt[i]会越大
                        if(cnt[j]>=n-i-1){ 
                            res+=swap(cnt,i,j);
                            break;
                        }
                    }
                }
            }
            //第i行的末尾0的数量小于n-i-1，不符合条件
            for(int i=0;i<n;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(j>i){ 
                int temp = num[j-1];
                num[j-1] = num[j];
                num[j]=temp;
                j--;
                count++;
            }
            return count;
        }
    }

#### 【问题描述】\[困难\]5478. 最大得分 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

#### 【解答思路】 ####

###### 双指针 ######

求两个队列相等时可以切换的最大值  
双指针模拟a、b队列当前的和

1.  如果a队列的当前值>b队列的当前值，那么b队列的最大值只能+b队列的当前值了，  
    因为本身a>b了，后面会越差越大的，因为他是有序的，把b往后走一位才可能相等
2.  如果a队列的当前值 < b队列的当前值，那么a队列的最大值只能+a队列的当前值了
3.  如果相等了，就用两个队列的当前的和的最大值替换原来的值，再加上当前值  
    相等时，用两个队列的当前的和的最大值替换原来的值会怀疑这么写不对，他明明是另一个队列的最大值，并不是当前队列的最大值，  
    这时你就可以想一下，我走过去另一条队列，再走回来原队列 其实是一样的

**时间复杂度：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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/088aca472d224f16a77aee02e16669ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230208/b2332cfc8d254fb0957d7f1a6616e29d.png