力扣5977——最少交换次数来组合所有的 1 II(贪心+滑动窗口)

力扣5977——最少交换次数来组合所有的 1 II(贪心+滑动窗口)
力扣5977——最少交换次数来组合所有的 1 II(贪心+滑动窗口)
思路,贪心,首先统计所有1的个数num1,按num1大小的滑动窗口滑过整个数组,窗口内1的个数为m,则需要将窗口外的num1-m个1换进来,交换次数为num1-m,整个滑过后最小值就是答案。

本题可以考虑首尾相连,那就可以构造两个nums相连,横跨的部分就是首尾相连的情况

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int num1 = 0;
        int n = nums.size();
        vector<int> data(2*n);
        for(int i = 0; i < 2*n; i++) 
            data[i] = nums[i%n];
        for(auto x : nums) if(x == 1) num1++;
        int cnt = 0;
        for(int i = 0; i < num1; i++) if(data[i] == 1) cnt++;
        int maxm = cnt; 
        for(int i = 1; i <= data.size() - num1; i++) {
            if(data[i-1] == 1) cnt--;
            if(data[i+num1-1] == 1) cnt++;
            maxm = max(maxm, cnt);
        }
        return num1 - maxm;
    }
};
上一篇:方法的定义和调用


下一篇:JAVA方法重载(第11节)