Problem statement:

问题陈述：

Given a binary string (containing only 0s and 1s). We need to make this string a sequence of alternate characters (0 and 1) by flipping some of the bits, our goal is to minimize the number of bits to be flipped. Write a program to determine the minimum number of bits to reach the goal.

给定一个二进制字符串(仅包含0和1)。 我们需要通过翻转一些位来使此字符串成为交替字符序列(0和1)，我们的目标是最大程度地减少要翻转的位数。 编写程序以确定达到目标的最小位数。

Examples:

例子：

Input:    0000 (binary string)    Output:     2    Input:    110 (binary string)    Output:    1

Example explanations:

示例说明：

Input:    0000    Output strings possible from the input string,     which satisfies the constraints:    0101    1010    Both strings are valid and both require 2 bits to be flipped.     Thus minimum no of flipping needed is 2    Input:    110    Output strings possible from the input string,     which satisfies the constraints:    010    101    The first one needs only one flips    While the second one need two flips    Hence minimum flip required is 1

Solution:

解：

Observation reveals that the converted string can be of two types:

观察发现，转换后的字符串可以有两种类型：

1. Starts with a 0

   以0开头

2. Starts with a 1

   以1开头

What we need to do is to convert the input string into both of this two category. Calculate corresponding flips needed to convert. Return the minimum flips.

我们需要做的是将输入字符串转换为这两个类别。 计算转换所需的相应翻转。 返回最小的翻转。

Pre-requisite:

先决条件：

Input string s

输入字符串s

Algorithm:

算法：

1) Declare variables and initialize like below.

1)声明变量并按如下所示进行初始化。

flip0 = 0, flip1 = 0, flag0 = 0, flag1 = 1    flip0=number of flips needed when converted string starts with 0    flip1=number of flips needed when converted string starts with 1    flag0=the current character value that should be at current string index,    incase converted string starts from 0, value changes from 0 to 1,    1 to 0 alternatively    flag1 = the current character value that should be at current string index,    incase converted string starts from 1,    value changes from 0 to 1, 1 to 0 alternatively

2) Count number of flips needed for converting input string to the valid string starting with 0

2)计算将输入字符串转换为以0开头的有效字符串所需的翻转次数

for i=0:s.length()-1        iF (flag0 != s[i]-'0')            flip0++;        END IF        flag0=1-flag0;    END FOR

3) Count number of flips needed for converting input string to the valid string starting with 1

3)计算将输入字符串转换为以1开头的有效字符串所需的翻转次数

for i=0:s.length()-1        iF (flag1 != s[i]-'0')            flip1++;        END IF        flag1=1-flag1;    END FOR

4) return minimum of flip0 and flip1;

4)返回flip0和flip1的最小值；

C++ implementation

C ++实现

#include 
    
     using namespace std;void print(vector
     
       a,int n){
   	for(int i=0;i
      
       flip1?flip1:flip0; //returnig minimum}int main(){
   	string s;	cout<<"Enter input string\n";	cin>>s;	cout<<"minimum no of flip required is: "<
       
        <
       
      
     
    

Output

输出量

First run:Enter input string0000minimum no of flip required is: 2Second run:Enter input string110minimum no of flip required is: 1

翻译自: