最少交换次数来组合所有的 1 II 图解题解

这道题到底在问什么

输入

nums=[0,1,0,1,1,0,0]

输出

1

输入

nums=[0,1,1,1,0,0,1,1,0]

输出

2

输入

nums=[1,1,0,0,1]（环形已相邻）

输出

0

最优解：一步一步想明白

1. 3记牢这一句:目标段长度就等于 1 的总数 k,用一个长度 k 的窗口在环形上滑一圈,窗口内 1 越多、要换进来的 0 就越少。下面从最左边的窗口开始滑。
2. 4第一步,把所有 1 找出来数个数。这组数据里绿色的 1 有三个,分别在位置 1、3、4,所以 k 等于 3。既然要把三个 1 聚拢,它们最后一定占据某段连续的三格。接下来的任务,就是找那段最省力的三格。
3. 5把一个长度 3 的窗口想成最终这段连续的 1 该落在哪。窗口里已经是 1 的可以留着不动,而窗口里的每一个 0,都得用一次交换,把外面的某个 1 换进来。所以这个窗口需要的交换次数,正好等于窗口里 0 的个数。现在这个开头窗口里有两个 0,代价是 2,并不划算,我们再往右滑看看。
4. 6算法先把窗口停在最左边,框住前 k 个也就是位置 0、1、2。数一数窗口里的 1,只有位置 1 那一个,cnt 记成 1。这是我们见到的第一个窗口,所以把历史最多 mx 也先记成 1。窗口里那两个 0,就是这一摆位要付出的交换数。
5. 7窗口整体向右挪一格。左边位置 0 的 0 滑出窗口,右边位置 3 的 1 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 1 的基础上加上进来的 1、减掉出去的 0,得到 2。这种进一个出一个的增量更新,是定长窗口省时间的关键。
6. 8结算这个窗口:里面绿色的 1 有 2 个,红色的 0 有 1 个,也就是摆在这里要交换 1 次。这个 cnt 比之前见过的都大,刷新历史最多 mx 到 2。窗口内 1 越多,要换的 0 就越少,这正是我们想要的方向。
7. 9窗口整体向右挪一格。左边位置 1 的 1 滑出窗口,右边位置 4 的 1 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 2 的基础上加上进来的 1、减掉出去的 1,得到 2。这种进一个出一个的增量更新,是定长窗口省时间的关键。
8. 10结算这个窗口:里面绿色的 1 有 2 个,红色的 0 有 1 个,也就是摆在这里要交换 1 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
9. 11窗口整体向右挪一格。左边位置 2 的 0 滑出窗口,右边位置 5 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 2 的基础上加上进来的 0、减掉出去的 0,得到 2。这种进一个出一个的增量更新,是定长窗口省时间的关键。
10. 12结算这个窗口:里面绿色的 1 有 2 个,红色的 0 有 1 个,也就是摆在这里要交换 1 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
11. 13窗口整体向右挪一格。左边位置 3 的 1 滑出窗口,右边位置 6 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 2 的基础上加上进来的 0、减掉出去的 1,得到 1。这种进一个出一个的增量更新,是定长窗口省时间的关键。
12. 14结算这个窗口:里面绿色的 1 有 1 个,红色的 0 有 2 个,也就是摆在这里要交换 2 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
13. 15窗口整体向右挪一格,这一步右端绕回了数组开头,正是环形的体现。左边位置 4 的 1 滑出窗口,右边位置 0 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 1 的基础上加上进来的 0、减掉出去的 1,得到 0。这种进一个出一个的增量更新,是定长窗口省时间的关键。
14. 16结算这个窗口:里面绿色的 1 有 0 个,红色的 0 有 3 个,也就是摆在这里要交换 3 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
15. 17窗口整体向右挪一格,这一步右端绕回了数组开头,正是环形的体现。左边位置 5 的 0 滑出窗口,右边位置 1 的 1 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 0 的基础上加上进来的 1、减掉出去的 0,得到 1。这种进一个出一个的增量更新,是定长窗口省时间的关键。
16. 18结算这个窗口:里面绿色的 1 有 1 个,红色的 0 有 2 个,也就是摆在这里要交换 2 次。它没有超过当前的 mx 2,mx 保持不动,窗口继续往右滑。
17. 19窗口整体向右挪一格,这一步左端绕回数组开头,窗口正好回到最开始的位置 [0,2],和初始窗口重合。左边位置 6 的 0 滑出窗口,右边位置 2 的 0 滑进窗口(紫色高亮)。cnt 不用重数,只需在原来 1 的基础上加上进来的 0、减掉出去的 0,得到 1。这一格是多滑出来的,只是把第一个起点又走了一遍,结果不受影响。
18. 20结算这个窗口:里面绿色的 1 有 1 个,红色的 0 有 2 个,也就是摆在这里要交换 2 次。它没有超过当前的 mx 2,mx 保持不动,窗口已在环形上滑满一整圈,所有起点都覆盖到了,下面看最终答案。
19. 21窗口在环形上滑了一整圈,所有摆位都试过了。最好的窗口里有两个 1,mx 定格在 2。比如位置 1 到 3 这个窗口,里面位置 1 和位置 3 已经是 1,只有位置 2 是一个 0。要填满它,只需把这一个 0 换成 1,交换一次。这就是全场最省的方案。
20. 22来看这一次交换具体怎么发生。最优窗口位置 1 到 3 里,唯一的 0 在位置 2;窗口外面位置 4 有一个多出来的 1(紫色)。把这两个位置的值互换,位置 2 变成 1、位置 4 变成 0。交换过后数组是 [0,1,1,1,0,0,0],位置 1、2、3 三个 1 稳稳连在一起。一次交换搞定,和答案 1 完全对上。
21. 23回顾整个过程:先数出 1 的总数 k 等于 3,再用一个长度 3 的窗口在环形上滑一圈,记下窗口内最多的 1 是 mx 等于 2。最终答案就是 k 减 mx,3 减 2 等于 1。判定始终只看一件事:哪个长度 k 的窗口里现成的 1 最多,那里要换进来的 0 就最少。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        k = nums.count(1)
        mx = cnt = sum(nums[:k])
        n = len(nums)
        for i in range(k, n + k):
            cnt += nums[i % n]
            cnt -= nums[(i - k + n) % n]
            mx = max(mx, cnt)
        return k - mx

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int k = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        int cnt = accumulate(nums.begin(), nums.begin() + k, 0);
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = max(mx, cnt);
        }
        return k - mx;
    }
};

import java.util.*;
class Solution {
    public int minSwaps(int[] nums) {
        int k = Arrays.stream(nums).sum();
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            cnt += nums[i];
        }
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = Math.max(mx, cnt);
        }
        return k - mx;
    }
}

复杂度

面试官可能追问