算法-面試題系列(一)??題目四??數(shù)組涂色

有一些排成一行的正方形。每個(gè)正方形已經(jīng)被染成紅色或者綠色?，F(xiàn)在可以選擇任意一個(gè)正方形然后用這兩種顏色的任意一種進(jìn)行染色，這個(gè)正方形的顏色將會(huì)被覆蓋。

目標(biāo)是在完成染色之后,每個(gè)紅色R都比每個(gè)綠色G距離最左側(cè)近。返回最少需要涂染幾個(gè)正方形。

image-20210514205250468

如樣例所示:s = RGRGR我們涂染之后變成RRRGG滿足要求了,涂染的個(gè)數(shù)為2,

沒有比這個(gè)更好的涂染方案？

image-20210514205804946

技巧~使用預(yù)處理數(shù)據(jù)

image-20210514210141110

image-20210514210426104

數(shù)組的預(yù)處理技巧題

LeetCode-42-接雨水(Trapping Rain Water) 這種都是通過一次遍歷準(zhǔn)備好左右兩邊滿足一定條件數(shù)組，遇到數(shù)組題目，可以想想，是否可以使用，提高敏感度。

• 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; // 如果數(shù)組所有的范圍，都是右側(cè)范圍，都變成G
        int left = 0;
        for (int i = 0; i < N - 1; i++) { // 0..i 左側(cè) 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 一共有多少個(gè)
    str.forEach { ch ->
        when (ch) {
            'R' -> rAll += 1
        }
    }

    //RRGGGRR
    var ans = rAll //如果數(shù)組所有的范圍，都是右側(cè)范圍，都變成G,//ex 一共4個(gè)R，如果全部屬于右側(cè)范圍 ans=4
    var left: Int = 0;
    
    for (i in 0 until N - 1) { // 0..i 左側(cè) 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
}