数列最小次数翻转

问题描述

他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：
1.单点修改：将位置x上的数翻转（0变1,1变0）；
2.前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。
他现在想要最小化翻转次数，使得数列上的所有数都变为0。

输入输出

第一行，输入一个数n。
第二行，输入n个数，第i个数表示aia_iai​。

输出最小翻转次数。

代码

import java.util.*;
public class Main{

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        System.out.println(solution(arr));
    }

    private static int solution(int[] arr) {
        int count = 0;
        boolean flag = true;
       // 从后往前
        for (int i = arr.length-1; i >= 0; i--) {
            if (flag && arr[i] == 0 || !flag && arr[i] == 1) continue;
            else if (flag && arr[i] == 1) {  // 从0到1
                if (i == 0 || arr[i - 1] == 0) count++;  // 下一个又变回0
                else {
                    flag = !flag;
                    count++;
                }
            } else {   // 从1到0
                if (i == 0 || arr[i - 1] == 1) count++;  // 下一个又变回1
                else {
                    flag = !flag;
                    count++;
                }
            }
        }
        return count;
    }
}