Найдите количество бит, которое нужно перевернуть, чтобы получить максимум 1 в массиве

Ответ 1

Вдохновленный комментарием @Nabbs, есть простой способ решить это в линейном времени: уменьшая задачу до максимальной суммы сегмента.

Преобразуйте все 0s в 1s и все от 1 до -1. Проблема тогда совпадает с минимизацией суммы массива после преобразования. (минимальная сумма содержит большинство -1s в преобразованном массиве, что соответствует большинству 1s в исходной задаче).

Мы можем вычислить сумму как

sum(after flipping) = sum(non-flipped) - sum(flipped part before flipping)

потому что сумма перевернутой части инвертирована. Если теперь выразить неотправленную часть следующим образом:

sum(non-flipped) = sum(original array) - sum(flipped part before flipping)

находим, что нам нужно минимизировать

sum(after flipping) = sum(original array) - 2 sum(flipped part before flipping)

Первая часть является константой, поэтому нам действительно нужно максимизировать сумму перевернутой части. Это именно то, что делает максимальная проблема суммы сегмента.

Я написал длинный вывод о том, как решить эту проблему в линейном времени некоторое время назад, поэтому теперь я буду делиться только кодом. Ниже я обновил код, чтобы сохранить границы. Я выбрал javascript как язык, потому что его так легко проверить в браузере и потому, что я не должен делать явные типы переменных x и y.

var A = Array(1, 0, 1, 0, 0, 1, 0, 1);
var sum = 0;

// count the 1s in the original array and
// do the 0 -> 1 and 1 -> -1 conversion
for(var i = 0; i < A.length; i++) {
    sum += A[i];
    A[i] = A[i] == 0 ? 1 : -1;        
}

// find the maximum subarray
var x = { value: 0, left: 0, right: 0 };
var y = { value: 0, left: 0 };
for (var n = 0; n < A.length; n++) {
    // update y
    if (y.value + A[n] >= 0) {
        y.value += A[n];
    } else {
        y.left = n+1;
        y.value = 0;
    }
    // update x
    if (x.value < y.value) {
        x.left = y.left;
        x.right = n;
        x.value = y.value;
    }
}

// convert the result back
alert("result = " + (sum + x.value) 
    + " in range [" + x.left + ", " + x.right + "]");

Вы можете легко проверить это в своем браузере. Например, в Chrome нажмите F12, щелкните Консоль и вставьте этот код. Он должен выводить

result = 6 in range [1, 4]

Ответ 2

Следующий код использует тривиальный алгоритм и работает в O (n²).

#include <iostream>
#include <bitset>
#include <utility>

typedef std::pair<unsigned, unsigned> range_t;

template <std::size_t N>
range_t max_flip(const std::bitset<N>& bs){
  int overall_score = 0;
  range_t result = range_t{0,0};

  for(std::size_t i = 0; i < N; ++i){
    int  score = bs[i] ? -1 : 1;
    auto max   = i;

    for(std::size_t j = i + 1; j < N; ++j){
      auto new_score = score + (bs[j] ? -1 : 1);

      if(new_score > score){
        score = new_score;
        max = j;
      }
    }
    if(score > overall_score){
      overall_score = score;
      result = {i,max};
    }
  }
  return result;
}

int main(){
  std::bitset<8> bitfield(std::string("10100101"));
  range_t range = max_flip(bitfield);
  std::cout << range.first << " .. " << range.second << std::endl;
}

Ответ 3

Попытка 2.0 в O (n)

Начните с начала массива. Шаг через массив. Пока вы не достигнете 0. Когда вы достигнете первого 0, установите count на 0, запомните начальную позицию и продолжите шаг при подсчете: +1 для 0 и -1 для 1. Если счетчик становится отрицательным, reset подсчитывайте и продолжайте, пока не дойдете до конца. Если вы найдете еще один счетчик нулей, равный 0, и повторите предыдущий алгоритм. В конце вы переворачиваете диапазон начального и конечного положения, если он есть.

void Flip( int* arr , int len )
{
    int s = -1 , e = -1 , c ;
    for( int i = 0 ; i < len ; i++ )
    {
        if( arr[i] == 0 )
        {
            c = 0 ;
            s = i ; 
            e = i ;
            for( int j = i ; j < len  ; j++ , i++ )
            {
                if( arr[i] == 0 )
                    c++ ;
                else
                    c-- ;

                if( c < 0 )
                {
                    s = -1 ;
                    e = -1 ;
                    break ;
                }

                if( arr[i] == 0 )
                    e = i ;
            }
        }
    }

    if( s > -1 )
        for( int i = s ; i <= e ; i++ )
            arr[i] ^= 1 ;

    for( int i = 0 ; i < len ; i++ )
        printf("%d " , arr[i] ) ;

}


int main(void) 
{
    int a[13] = {1,0,1,1,0,0,1,0,1,1,0,1,0} ;


    Flip( a , 13 ) ;

    return 0;
}

Не проверено полностью, могут быть ошибки (крайние случаи), но он работает в принципе.

Ответ 4

            void maxones(int n)
            {

                int table[n+1][n+1], i, j, totalones = 0, max = INT_MIN, start_pos = 0, end_pos =0;

                if(n == 0)
                {
                    printf("Max no of ones from 0 to %d \n",sizeof(int) * 8 -1);
                    return;
                }

                /* size of (int) * 8 bits, calculate total no of ones in every bit */
                for(i=0; i<sizeof(n) * 8; i++)
                    totalones += n & (1 >> i);

                /* Base conditions to be filled */
                for(i=0; i<n; i++)
                    table[i][i] = (n & (1 >> i)) ? totalones - 1 : totalones + 1;

                for(i=0; i<n; i++ )
                    for(j=i+1; j<n; j++)
                    {
                        table[i][j] = table[i][j-1] + ( n & (1 >> j)) ? 0 : 1;
                        if (max < table[i][j])
                        {
                            max = table[i][j];
                            start_pos = i;
                            end_pos = j;
                        }
                    }

                printf("Max no of Ones on fliping bits from pos %d to pos %d \n",start_pos, end_pos);
            }

            int main()
            {
                int n;

                printf("Enter number %d \n", &n);
                maxones(n);

                return 0;
            }

Ответ 5

Вот рекурсивный подход: https://ideone.com/Su2Mmb

public static void main(String[] args) {
    int [] input = {1, 0, 0, 1, 0, 0, 1,1,1,1, 0,1};
    System.out.println(findMaxNumberOfOnes(input,0, input.length-1));
}

private static int findMaxNumberOfOnes(int[] input, int i, int j) {     
    if (i==j)
        return 1;
    int option1 = input[i] + findMaxNumberOfOnes(input, i+1, j);
    int option2 = count(input , i , j, true);
    int option3 = count(input, i, j, false);
    int option4 =findMaxNumberOfOnes(input, i, j-1) +input[j]; 
    return Math.max(option1, Math.max(option2,Math.max(option3,option4)));
}

private static int count(int[] input, int i, int j, boolean flipped) {
    int a = flipped?0:1;
    int count = 0;
    while (i<=j){
        count += (input[i++]==a)?1:0;
    }
    return count;
}

Ответ 6

Эта проблема может быть решена с помощью динамического программирования в линейном времени и пространстве. Вы можете создать массив слева, где left [i] - это число 1 в подмассиве 0 до я (включительно). Итак, для двух индексов я и j:

case 1: i==j, result is array size sz-1 (if no 0 in array) or sz+1 (if there is at least one 0 in array)

case 2: i less than j, result is:

   left[i-1] (# of 1 on subarray 0 ~ i-1) + 
   (j-i+1-(left[j]-left[i-1])) (# of 0 on subarray i ~ j) + 
   left[sz-1]-left[j] (# of 1 on subarray j+1 ~ sz-1) 

   this equals to: (j-2*left[j])-(i-2*left[i-1])+left[sz-1]+1

Итак, согласно случаю 2, нам понадобится еще один массив temp для хранения для каждого j min{i-2*left[i-1] where i<j}

Итак, мы можем пересечь массив, при каждом индексе j мы вычисляем приведенный выше случай два (в постоянное время) и обновляем конечный результат, если он больше.

Мой код в С++:

int func(vector<int>& arr){
    int res = 0;
    int sz = arr.size();
    vector<int> left(sz, 0);
    for(int i=0; i<sz; i++){
        left[i] = (arr[i]==1?1:0)+(i==0?0:left[i-1]);
    }
    bool all_1 = true;
    for(int i=0; i<sz; i++){
        if(arr[i] == 0) all_1=false;
    }
    if(all_1) return sz-1;
    res = left[sz-1]+1;
    vector<int> temp(sz, INT_MAX);
    for(int i=1; i<sz; i++)
        temp[i] = min(temp[i-1], i-2*left[i-1]);
    for(int j=1; j<sz; j++){
        int val = j+1-left[j]+(left[sz-1]-left[j]); 
        val = max(val, j-2*left[j]-temp[j]+left[sz-1]+1);
        res = max(res, val);
    }
    return res;
}

Ответ 7

Я также думал так же, как @this сказал. Но в его решении есть ошибки. Мой код после исправления ошибки (см. Объяснение ниже):

vector<int> Solution::flip(string arr) {
int s = -1 , e = -1 , c , len = arr.size(), S = -1, E = -1, Max = 0;
for( int i = 0 ; i < len ; i++ )
{
    if( arr[i] == '0' )
    {
        c = 0 ;
        s = i ; 
        e = i ;
        for( int j = i ; j < len  ; j++, i++ )
        {
            if( arr[j] == '0' )
                c++ ;
            else
                c-- ;
            //cout << c << " ";
            if( c < 0 )
            {
                s = -1 ;
                e = -1 ;
                break ;
            }

            if( arr[j] == '0' )
                e = i ;
            if(c > Max){
                S = s;
                E = e;
                Max = c;
            }
        }
    }
}
vector<int> ans;
if( S > -1 ){
    ans.push_back(S);
    ans.push_back(E);
    return ans;
}
else
    return ans;

}

Объяснение: Начните с начала массива. Шаг через массив. Пока вы не достигнете 0. Когда вы достигнете первого 0, установите count на 0, запомните начальную позицию и продолжите шаг при подсчете: +1 для 0 и -1 для 1. Max сохраняет значение max (#zeros в весь набор [s, e]). Если c становится больше, чем Max, тогда текущий набор [s, e] содержит максимальное количество бит '0'. Следовательно, обновите Max, S, E,. Если счетчик становится отрицательным, это означает, что число "1" больше, чем число "0" в наборе [s, e], поэтому reset счетчик c, локальный запуск s, локальный конец e. и продолжайте, пока не дойдете до конца. Если вы найдете еще один счетчик нулей в 0 и повторите предыдущий алгоритм. Конечное значение s, e - это индекс диапазона, в котором биты должны быть перевернуты. Если такой диапазон не существует (все биты равны "1" ), то S = -1, E = - 1.

Ответ 8

Это решение также вдохновлено комментариями @Nabb. Я создал новый массив с заменой 0 на 1 и 1 на -1. Затем я использовал концепцию задачи о максимальном диапазоне подмассивов для ее решения. Код как ниже:

vector<int> Solution::flip(string A) {
vector<int> vec;
vector<int> res;
for(int i=0;i<A.length();i++){
    if(A[i]=='1')
        vec.push_back(-1);
    else
        vec.push_back(1);
}
int l=0,r=0,s=0;
int sum=0;
int sum_prev=INT_MIN;
for(int i=0;i<vec.size();i++){
    sum+=vec[i];
    if(sum_prev<sum){
        sum_prev=sum;
        l=s;
        r=i;
    }
    if(sum<0){
        sum=0;
        s=i+1;
    }
}
//cout<<"l: "<<l<<" r: "<<r<<endl;
if((l>=0 && r>0)||((l==0 && r==0) && A[0]=='0')){
    res.push_back(l+1);
    res.push_back(r+1);
}
return res;

}