联想8.5技术笔试---栅栏涂色 题解

问题：

第一题
问题描述
小A的门前有n个排成一排的栅栏，编号分别为1,2，...，n。每个栅栏都是红色或者蓝色的。但小A觉得目前的上色方案看起来有些杂乱，便想要重新对栅栏进行涂色。具体地，小A认为，如果栅栏的颜色交替次数多于1次，那么就是杂乱的，否则就是整齐的。换言之，如果栅栏是全红/全蓝/前一段红后一段蓝/前一段蓝后一段红，那么都能符合小A的要求。请问小A至少需要对几个栅栏进行重新涂色，才能满足他的要求呢？

输入描述
第一行是一个整数n，表示有n个栅栏，1<=n<=100000。
第二行是一个字符串s，字符串只包含’r’和’b’，对于第i个字符，若为’r’表示第i个栅栏为红色，若为’b’则表示第i个栅栏为蓝色。

输出描述
一行一个整数，表示小A需要进行重新涂色的最少栅栏数。

思路：对于每一个栅栏，计算其左右r还有b的数量，一共4个数组lb,lr,rb,rr去存。遍历每一个元素，计算{全r，全b，rb，br}四种情况下的最小值，并取最小，用这个最小值再去更新答案res。

代码：

#栅栏涂色
while(1):
    line = input().strip()
    if len(line)<=0:break
    
    s = line
    res = 0
    n = len(s)
    lb,lr,rb,rr = [0]*n,[0]*n,[0]*n,[0]*n
    for i in range(1,n):
        lb[i] = lb[i-1]+(1 if s[i-1]=='b' else 0)
        lr[i] = lr[i-1]+(1 if s[i-1]=='r' else 0)
    for i in range(n-2,-1,-1):
        rb[i] = rb[i+1]+(1 if s[i+1]=='b' else 0)
        rr[i] = rr[i+1]+(1 if s[i+1]=='r' else 0)
    res = float('inf')
    for i in range(n):
        if s[i]=='b':
            res = min(1+lb[i]+rb[i],lr[i]+rr[i],lb[i]+rr[i],lr[i]+rb[i])
        else:
            res = min(lb[i]+rb[i],1+lr[i]+rr[i],lb[i]+rr[i],lr[i]+rb[i])
    print(res)