//一个数组中只有两种字符'G'和'B',
//想要所有的G都放左边, 所有的B都放右边或者所有的B都放左边, 所有的G都放右边
//但只能在相邻字符之间进行交换操作
//返回至少需要交换几次
//方法1
public static int minSteps1(String s) {
if(s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int gi = 0;
for(int i = 0;i<str.length;i++) {
if(str[i] == 'G') {
step1 +=i -(gi++);//每次遇到G就放到gi的后面就行了,距离gi位置差多少就换几次
}
}
int step2 = 0;
int bi = 0;
for(int i=0;i<str.length;i++) {
if(str[i] == 'B') {
step2 += i - (bi++);
}
}
return Math.min(step1,step2);//返回GB最少交换次数
}
//方法2
public static int minSteps2(String s) {
if(s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int step2 = 0;
int gi = 0;
int bi = 0;
for(int i = 0;i<str.length;i++) {
if(str[i] == 'G') {
step1 +=i-(gi++);
}else {
step2 +=i-(bi++);
}
}
return Math.min(step1,step2);
}
public static String randomString(int maxLen) {
char[] str = new char[(int)(Math.random()*maxLen)];
for(int i=0;i<str.length;i++) {
str[i]=Math.random() < 0.5 ? 'G' : 'B';
}
return String.valueOf(str);
}
public static void main(String[] args) {
int maxLen = 100;
int testTime = 1000000;
System.out.println("测试开始");
for(int i =0;i<testTime;i++) {
String str = randomString(maxLen);//生成1000000个随机字符串
int ans1 = minSteps1(str);
System.out.println(ans1);
int ans2 = minSteps2(str);
System.out.println(ans2);
if(ans1 != ans2) {
System.out.println("Oops!");
}
}
System.out.println("测试结束");
}
标签:str,int,step2,char,算法,GB,step1,gi,大厂
From: https://www.cnblogs.com/15078480385zyc/p/17658834.html