1151. Minimum Swaps to Group All 1's Together

LeetCode medium original: C# #array #csharp #leetcode #math #medium #sliding-window #two-pointers

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Дан бинарный tableau data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в tableauе, вместе в любом месте tableauа.

Exemple:

Input: data = [1,0,1,0,1]

Output: 1

Explanation: There are 3 ways to group all 1's together:

[1,1,1,0,0] using 1 swap.

[0,1,1,1,0] using 2 swaps.

[0,0,1,1,1] using 1 swap.

The minimum is 1.

C# solution

correspondant/original

public class Solution {
    public int MinSwaps(int[] data) {
        int ones = data.Sum();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;
        while (right < data.Length) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = Math.Max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSwaps(vector<int>& data) {
        int ones = data.Sum();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;
        while (right < data.size()) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

Java solution

brouillon automatique, à relire avant soumission

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MinSwaps(int[] data) {
        int ones = data.Sum();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;
        while (right < data.length) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = Math.max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

JavaScript solution

correspondant/original

var minSwaps = function(data) {
    const ones = data.reduce((a, b) => a + b, 0);
    let cnt_one = 0, max_one = 0;
    let left = 0, right = 0;

    while (right < data.length) {
        cnt_one += data[right++];
        if (right - left > ones) {
            cnt_one -= data[left++];
        }
        max_one = Math.max(max_one, cnt_one);
    }
    return ones - max_one;
};

Python solution

correspondant/original

class Solution:
    def minSwaps(self, data):
        ones = sum(data)
        cnt_one = max_one = 0
        left = right = 0

        while right < len(data):
            cnt_one += data[right]
            right += 1
            if right - left > ones:
                cnt_one -= data[left]
                left += 1
            max_one = max(max_one, cnt_one)
        return ones - max_one

Algorithm

Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент tableauа data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

Пока окно скользит по tableauу data, поддерживаем его длину равной ones.

Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.