首页 > 试题广场 >

刷墙

[编程题]刷墙
  • 热度指数：3751 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
最近小明搬到了新家，他正在粉刷墙壁，但是不幸的是他粉刷的墙壁并不理想。他的墙壁是一个长度为 的格子，每个格子用0表示红色，用1表示蓝色。现在墙壁是一个非常混乱的颜色。他想将墙壁涂成左边全是蓝色右边全是红色，可以将墙壁刷成全是红色或者蓝色。请问他至少需要粉刷多少个格子墙壁刷成他想要的样子？

数据范围：
进阶：时间复杂度，空间复杂度

输入描述:
第一行一个整数。
第二行个长度为的01串，0表示红色，1表示蓝色。


输出描述:
输出一个整数表示最少粉刷次数。
示例1

输入

3
001

输出

1

说明

只需要将最后一个刷成红色。
算法知识视频讲解
添加回答
Java
Vampire逊头像 Vampire逊 
 JAVA  两个最简单的【动态规划】
    说它简单是因为它简单的都不像动态规划，只能说运用了动态规划思想，但你也可以从其他思想角度得到同样的方程：

    翻译题目：蓝色是1，红色是0 => 首先题目要求序列左边都是连续的1右边都是连续的0，特殊情况下可以全为1或全为0，则：

dp[i]表示当前0~i个中有几个1 
        = 前0~i-1中1的个数为dp[i-1]，在加上第i个中1的个数
        = dp[i-1] + array[i];

min[i] 为左边i个墙块全刷蓝色，右边剩余墙块全刷红色，时所需要的刷墙次数
        = 现在需要的刷墙次数
        = 左边i个墙块中需要刷蓝的个数 + 右边length - i个墙块中需要刷红的个数
        = 左边i个元素中0的个数 + 右边length - i个元素中1的个数
        = (i - dp[i-1]) + (dp[length - 1] - dp[i-1])

再令min[i] = 各min[i]取最小 
        = MIN{min[i-1], 现在需要的刷墙次数} 
        = MIN{min[i-1], (i - dp[i-1]) + (dp[length - 1] - dp[i-1])}

即可输出最终的各刷墙方法中的最小值：min[length]
【从动态规划的集合角度来看：min[i]为左边墙面为0~i的各刷墙集合中的最少刷墙次数】 

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));
    }
}
编辑于 2022-05-19 15:09:21 回复(0)
Java
realMorty头像 realMorty
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n == 1) {
            System.out.println(0);
            return;
        } 
        String s = sc.next();
        char[] chars = s.toCharArray();
        int[] cntZero = new int[n];
        int[] cntOne = new int[n];
        cntOne[0] = chars[0] == '1' ? 1 : 0;
        for(int i = 1; i < n; i++) {
            cntOne[i] = cntOne[i - 1];
            if(chars[i]=='1') cntOne[i]++; 
        }
        cntZero[n - 1] = chars[n - 1] == '0' ? 1 : 0;
        for(int i = n - 2; i >= 0; i--) {
            cntZero[i] = cntZero[i + 1];
            if(chars[i]=='0') cntZero[i]++; 
        }
        int sameColor = Math.min(n - cntZero[0], n - cntOne[n - 1]);
        int diffColor = n;
        for (int i = 0; i < n - 1; i++) {
            int times = i + 1 - cntOne[i] + (n - i - 1) - cntZero[i+1];
            diffColor = Math.min(diffColor, times);
        }
        System.out.println(Math.min(sameColor, diffColor));
        
    }    
}
发表于 2022-02-08 13:52:22 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试开发工程师 测试工程师 2021 牛客 Java工程师
来自：【2021】牛客模考C...
上传者：小小
难度：
2条回答 6790浏览

热门推荐

通过挑战的用户

相关试题

刷墙

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号