刷墙

预处理

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[] wall = br.readLine().toCharArray();
        int[] left = new int[n];     // 包括自己，左边0的个数，这些是要被刷成1的
        int[] right = new int[n];    // 包括自己，右边1的个数，这些是要被刷成0的
        for(int i = 0; i < n; i++){
            if(i == 0){
                left[i] = wall[i] == '0'? 1: 0;
                right[n - i - 1] = wall[n - i - 1] == '1'? 1: 0;
            }else{
                left[i] = left[i - 1] + (wall[i] == '0'? 1: 0);
                right[n - i - 1] = right[n - i] + (wall[n - i - 1] == '1'? 1: 0);
            }
        }
        int cost = n;
        for(int i = 0; i < n; i++){
            cost = Math.min(cost, left[i] + right[i] - 1);
        }
        System.out.println(cost);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String s = in.nextLine();
        int len = s.length();
        int count = 0;
        int min = len;
        for(int i = 0; i < len; i++){ // 遍历统计1的个数
            if(s.charAt(i) == '1'){
                count++;
            }
        }
        min = Math.min(count,n-count); // 全刷成一种颜色，需要的最小次数
        int left1 = 0;
        for(int i = 0; i < len; i++){  // 再次遍历，把第i个元素当成分割点（包括i）
            if(s.charAt(i) == '1'){
                left1++;               // i左边的1个数（包括i），则左边0个数有：（i+1）-left1 【即左边总元素个数-1的个数】，这些0需要刷成1
            }                          // 则右边还有count-left1个1，这些1需要刷成0，
            int sum = i + 1 - left1 + count - left1;
            if(sum < min){ // 所以总共需要刷 （i+1）-left1 + count - left1
                min = sum; // 保存最小刷新次数
            }
        }
        System.out.println(min);
    }
}

考虑第 个格子的左边线作为分界，左 1 右 0 ，左边假设全涂好了，右边

假如 第 i + 1 个房间是 1，那现在就不用涂了，反之要补上。

DP 的初值是一共几个 1

dp[i] 的意义是，选第 i 个时的花费。最后取 min 即可

input()
room = input()
dp = [0] * (1 + len(room))
dp[0] = room.count("1")
for i in range(1, len(room) + 1):
    dp[i] = dp[i - 1] + int(room[i - 1] == "0") - int(room[i - 1] == "1")
print(min(dp))

 JAVA  两个最简单的【动态规划】 

import java.util.*;
import java.io.*;

public class Main{
    int paint(int length, int[] array){
        int[] dp = new int[length], min = new int[length+1];
        dp[0] = array[0];
        for(int i = 1 ; i<length ; i++)
            dp[i] = dp[i-1] + array[i];
        min[0] = dp[length - 1];            //左边留0个墙面刷蓝，右边剩余所有墙面刷红（即1的个数）
        for(int i = 1 ; i<=length ; i++)
            min[i] = Math.min(min[i-1], (i - dp[i-1]) + (dp[length-1] - dp[i-1]));
        return min[length];
    }

        // 单纯处理输入数据，不用看
    public static void main(String[] args) throws IOException{
        Main main = new Main();
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int i = 0, len = Integer.parseInt(buf.readLine());
        int[] ar = new int[len];
        for(char c : buf.readLine().toCharArray()){
            ar[i] = c - '0';
            i++;
        }
        System.out.println(main.paint(len, ar));
    }
}

string str;
int num;
cin>>num>>str
int numRightAll_0 = 0;
int numLeftAll_1 = 0;
for(int i=0; i<num; i++){
    if(str[i] != '0') numRightAll_0++;
}
int minNum = numRightAll_0;
for(int i=0; i<num; i++){
    if (str[i] != '0'){
        numRightAll_0--;
    }
    else{
        numLeftAll_1++;
    }
    minNum = min(minNum, numRightAll_0 + numLeftAll_1);  
}
cout<<minNum<<endl;

public static void main(String[] args) {  Scanner scanner = new Scanner(System.in);  int s1 = Integer.valueOf(scanner.nextLine());  String s2 = scanner.nextLine();  if (s2.startsWith("1") || s2.endsWith("0")) {  System.out.println(0);  return;  }  char[] ss = s2.toCharArray();  int start = -1, end = -1;  for (int i = 0, j = ss.length - 1; i != j -1 || i < j; i++, j--) {  if (ss[i] == '1') {  start = i;  break;  }  if (ss[j] == '0') {  end = j;  break;  }  }   if (start == -1) {  System.out.println(s1 - end - 1);  } else if (end == -1) {  System.out.println(start);  } else {  System.out.println(s1/2);  } }

简单双指针


import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = Integer.parseInt(sc.nextLine());
            char[] cs = sc.nextLine().toCharArray();
            sc.close();
            int left0 = 0, left1 = 0;
            int right0 = 0, right1 = 0;
            for (int i = n - 1; i >= 0; i--) {
                if (cs[i] == '1') {
                    right1++;
                } else {
                    right0++;
                }
            }
            int min = right1;
            for (int i = 0; i < n; i++) {
                if (cs[i] == '1') {
                    right1--;
                    left1++;
                } else {
                    left0++;
                    right0--;
                }
                min = Math.min(min, left0 + right1);
            }
            System.out.println(min);
        }
    }

let n = Number(readline())
let rawStr = readline()
let min = n
let left0=0,right1=0
for(let i = 0;i<n;++i){
    if(rawStr[i]=='1')++right1
}
for(let i = 0;i<=n;++i){
    if(i>0){
        if(rawStr[i-1]=='0')left0++
        else right1--
    }
    if(left0+right1<min)min = left0+right1
}
print(min)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String s = sc.nextLine();
        int[] dp = new int[n + 1];
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                count++;
            }
        }
        dp[0] = count;

        for (int i = 1; i < n + 1; i++) {
            if (s.charAt(i - 1) == '0') {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = dp[i - 1] - 1;
            }
        }
        System.out.println(Arrays.stream(dp).min().getAsInt());
    }
}

var n=parseInt(readline())
    var str=readline()
    function rush(n,str){
    str=str.split('')
    var arr0 = []
    var arr1 = []
    var count=0
    var min =0
    for(var i=0;i<n;i++){
        if(str[i]=='1'){
            arr1.push(str[i])
            count++
        }
    }
    min=Math.min(count,n-count)
    var left1=0
    for(var i =0;i<n ;i++){
        if(str[i]=='1'){
            left1++
        }
        var sum = i + 1-left1+count-left1
        if(sum<min){
            min=sum
        }
    }
    console.log(min);
}
    rush(n,str)