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);
}
}