首页 > 试题广场 >

刷墙

[编程题]刷墙

热度指数：3751 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

最近小明搬到了新家，他正在粉刷墙壁，但是不幸的是他粉刷的墙壁并不理想。他的墙壁是一个长度为 $\mathit n$ 的格子，每个格子用0表示红色，用1表示蓝色。现在墙壁是一个非常混乱的颜色。他想将墙壁涂成左边全是蓝色右边全是红色，可以将墙壁刷成全是红色或者蓝色。请问他至少需要粉刷多少个格子墙壁刷成他想要的样子？

数据范围： $1\le n \le 10000\$

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

输入描述:

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

输出描述:

输出一个整数表示最少粉刷次数。

示例1

输入

3
001

输出

说明

只需要将最后一个刷成红色。

算法知识视频讲解

JavaScript

HGHGHG

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)

加一个隔板，从左到右遍历隔板的位置。首先隔板在最左边，进行初始化。隔板每向右移动一次，就更新left0的个数和right1的个数。复杂度是O(n)

发表于 2021-12-09 15:59:45 回复(0)