栅栏涂色题

题目：

注意：
在使用 nextInt() 后再使用nextLine() ，则需要将中间的换行符用 nextLine() 提取出来，然后才是输入的字符串，也就是说 要用两次 nextLine() ！

思路：

1. 遍历两次，
   第一次从左边出发，遍历到 i 位置，用lr数组记录将 i 左边全修改为红色的次数，用lb数组记录将 i 左边全修改为蓝色的次数；
   第二次从右边出发，遍历到 i 位置，用rr数组记录将 i 左边全修改为红色的次数，用rb数组记录将 i 左边全修改为蓝色的次数；

2. 符合题意的是颜色一边一半，或者全为一种颜色，那么需要求出 每个位置对应的 左右两边各修改为红 或 蓝的次数中的最小值，并按索引位置记录在 res数组中；

3. 最后遍历res数组，找出哪个位置需要修改的次数最少的，就算答案

特殊情况：

如果输入为 r r b r r 时，当遍历到 i=2 ，即 ’ b‘ 时，左边修改为全红次数是0，全蓝次数是2；右边修改为全红次数是0，全蓝次数是2，两边各选取最小值，即0+0 ，最后答案是0 ；
显然 0 不对！因为忽略了 ’b‘ 本身和两侧都不一样！
所以对这种情况先进行判断 ： if(i>1 && c[i]!=c[i-1] && c[i]!=c[i+1]) 即 当前元素和两边都不同时，就将结果+1 ！

Java实现：

public class Main{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        String blank=in.nextLine();
        String s=in.nextLine();
        char[] c = s.toCharArray();

        int[] lr=new int[n]; // 左边出发，i 位置需要改为红的次数
        int[] lb=new int[n]; // 左边出发，i 位置需要改为蓝的次数

        int[] rr=new int[n]; // 左边出发，i 位置需要改为红的次数
        int[] rb=new int[n]; // 左边出发，i 位置需要改为蓝的次数
        // lr lb 左边出发 ，记录i个位置左边都改为全红/蓝的 次数
        for(int i=0;i<n;i++){ //遍历每个 i
            for(int j=0;j<i;j++){ // 遍历 i 左边改的次数
                if(c[j]=='b'){ // 为蓝则需要改一次
                    lr[i]=lr[i]+1; // 存储 第i个位置左边全改为 红r的次数
                }
                if(c[j]=='r'){ // 为红则需要改一次
                    lb[i]=lb[i]+1; // 存储 第i个位置左边全改为 blue的次数
                }
            }
        }


        // rr rb 右边出发 ，记录i个位置左边都改为全红/蓝的 次数
        for(int i=n-1;i>=0;i--){ //遍历每个 i
            for(int j=n-1;j>i;j--){ // 遍历右边 改的次数
                if(c[j]=='b'){ // 为蓝则需要改一次
                    rr[i]=rr[i]+1; // 存储 第i个位置左边全改为 红r的次数
                }
                if(c[j]=='r'){ // 为红则需要改一次
                    rb[i]=rb[i]+1; // 存储 第i个位置左边全改为 红r的次数
                }

            }
        }
        
        // 用left和right记录每个位置 左起改为某色最小次数、和右起改为某色最小次数
        // res[]记录每个位置修改成功共需要的次数
        int[] res=new int[n];
        for(int i=0;i<n;i++){
            int left=Math.min(lr[i],lb[i]); // 左改为全红or全蓝 最小
            int right=Math.min(rr[i],rb[i]);// 右改为全红or全蓝 最小
            if(i>1 && c[i]!=c[i-1] && c[i]!=c[i+1]){ // 如果是 r b r 情况，遍历到b时要+1
                res[i]=left+right+1;
            }else{
                res[i]=left+right;
            }
        }
        //最后求最小
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            min=Math.min(min,res[i]);
        }
        System.out.println(min);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59