首页 > 试题广场 >

红和绿

[编程题]红和绿

热度指数：7537 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。

输入描述:

输入包括一个字符串s,字符串s长度length(1 ≤ length ≤ 50),其中只包括'R'或者'G',分别表示红色和绿色。

输出描述:

输出一个整数,表示牛牛最少需要涂染的正方形数量

示例1

输入

RGRGR

输出

算法知识视频讲解

Java

成程晨

import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            System.out.println(helper(in.nextLine()));
        }
    }
    public static int helper(String s){
        char[] a = s.toCharArray();
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < a.length;i++){
            int s1 = 0,e1 = i,s2 = i,e2 = a.length,count = 0;
            while(s1 < e1){
                if(a[s1] == 'G') count++;
                s1++;
            }
            while(s2 < e2){
                if(a[s2] == 'R') count++;
                s2++;
            }
            min = Math.min(count,min);
        }
        return min;
    }
}

发表于 2019-01-18 16:16:19 回复(0)