算法-面试题系列(一)➡️题目四➡️数组涂色

有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色，这个正方形的颜色将会被覆盖。

目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。返回最少需要涂染几个正方形。

image-20210514205250468

如样例所示:s = RGRGR我们涂染之后变成RRRGG满足要求了,涂染的个数为2,

没有比这个更好的涂染方案？

image-20210514205804946

技巧~使用预处理数据

image-20210514210141110

image-20210514210426104

数组的预处理技巧题

LeetCode-42-接雨水(Trapping Rain Water) 这种都是通过一次遍历准备好左右两边满足一定条件数组，遇到数组题目，可以想想，是否可以使用，提高敏感度。

• Java

public class Solution {

    // RGRGR -> RRRGG
    public static int minPaint(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int rAll = 0;
        for (int i = 0; i < N; i++) {
            rAll += str[i] == 'R' ? 1 : 0;
        }
        int ans = rAll; // 如果数组所有的范围，都是右侧范围，都变成G
        int left = 0;
        for (int i = 0; i < N - 1; i++) { // 0..i 左侧 n-1..N-1
            left += str[i] == 'G' ? 1 : 0;
            rAll -= str[i] == 'R' ? 1 : 0;
            ans = Math.min(ans, left + rAll);
        }
        // 0...N-1 左全部 右无
        ans = Math.min(ans, left + (str[N - 1] == 'G' ? 1 : 0));
        return ans;
    }

    public static void main(String[] args) {
        String test = "GGGGGR";
        System.out.println(minPaint(test));
    }

}

• Kotlin

fun minPaint(s: String?): Int {
    if (s == null || s.length < 2) {
        return 0
    }

    val str = s.toCharArray()

    val N = str.size

    var rAll = 0 //R 一共有多少个
    str.forEach { ch ->
        when (ch) {
            'R' -> rAll += 1
        }
    }

    //RRGGGRR
    var ans = rAll //如果数组所有的范围，都是右侧范围，都变成G,//ex 一共4个R，如果全部属于右侧范围 ans=4
    var left: Int = 0;
    
    for (i in 0 until N - 1) { // 0..i 左侧 n-1..N-1
        left += if (str[i] === 'G') 1 else 0
        rAll -= if (str[i] === 'R') 1 else 0
        ans = Math.min(ans, left + rAll)
    }

    // 0...N-1 左全部 右无
    // 0...N-1 左全部 右无
    ans = Math.min(ans, left + if (str[N - 1] === 'G') 1 else 0)
    
    return ans
}