牛客網 2018校招真題 愛奇藝 紅和綠

Description

牛客網 2018校招真題 紅和綠

Solving Ideas

題目沒有要求塗染後’R’、'G’的數量要與塗染前一緻，如"GGGGRRR"的最優解為"GGGGGGG"

以每個字元為中點，左邊的塗成R，右邊的塗成G，得到塗染個數，在多個塗染個數中取最小的。

Time complexity : O ( n 2 ) O(n^2) O(n2)

Space complexity : O ( 1 ) O(1) O(1)

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();

        int res = Integer.MAX_VALUE, count;
        for (int i = 0; i < str.length; i++) {
            count = 0;
            for (int j = 0; j < i; j++) {
                if (str[j] != 'R') count++;
            }
            for (int j = i + 1; j < str.length; j++) {
                if (str[j] != 'G') count++;
            }
            res = Math.min(res, count);
        }
        System.out.println(res);
    }
}