牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
输入包括一个字符串s,字符串s长度length(1 ≤ length ≤ 50),其中只包括'R'或者'G',分别表示红色和绿色。
输出一个整数,表示牛牛最少需要涂染的正方形数量
RGRGR
2
#include<stdio.h> #include<string.h> #define min(a,b) a<b?a:b int main(){ char s[100]; scanf("%s",s); int i,j,Min=1e8,n=strlen(s); for(i=0;i<n;i++){ int cnt=0; for(j=0;j<i;j++) if(s[j]!='R') cnt++; for(j=i;j<n;j++) if(s[j]!='G') cnt++; Min=min(Min,cnt); } printf("%d\n",Min); }
import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); String s=sc.nextLine(); int ans=Integer.MAX_VALUE; for(int i=0;i<s.length();i++) { int r=0; for(int j=0;j<i;j++) { if(s.charAt(j)!='R') r++; } for(int k=i;k<s.length();k++) { if(s.charAt(k)!='G') r++; } ans=Math.min(ans, r); } System.out.println(ans); } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); System.out.println(getColorWayPreprocess(s)); } public static int getColorWayPreprocess(String s) { char[] chs = s.toCharArray(); int n = chs.length; int[] leftG = new int[n]; int[] rightR = new int[n]; for (int i = 0; i < n; i++) { if (chs[i] == 'G') { leftG[i] = i == 0 ? 1 : leftG[i - 1] + 1; } else { leftG[i] = i == 0 ? 0 : leftG[i - 1]; } } for (int i = n - 1; i >= 0; i--) { if (chs[i] == 'R') { rightR[i] = i == n - 1 ? 1 : rightR[i + 1] + 1; } else { rightR[i] = i == n - 1 ? 0 : rightR[i + 1]; } } int res = Integer.MAX_VALUE; for (int r = -1; r < n; r++) { int tmp; if (r == -1) { tmp = rightR[0]; } else if (r == n - 1) { tmp = leftG[n - 1]; } else { tmp = leftG[r] + rightR[r + 1]; } res = Math.min(res, tmp); } return res; } }
使用预先构建数组, 使得时间复杂度为O(n)