2019年招商信用卡中心笔试的编程第一题，当时还没想好这个问题，后来才想到了。
鸡鸭分类问题
题目
大致问题就是：鸡鸭不能串这挨着。鸡用C表示，鸭用D表示。例如：CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻，需要调整队形两次。
示例
输入描述：输入一个长度为N，且只包含C和D的非空字符串。
输入：CCDCC
输出描述：使得最后仅有一对鸡鸭相邻，最少的交换次数。
输出：2
解释思想：
- 把第一个字母记录下来，然后统计和第一字母相同的字母前面有几个不同的字母，然后把每次的数字加起来就可以了。
image.png
package com.zhoujian.solutions.didi;
import java.util.Scanner;
/**
* @author zhoujian123@hotmail.com 2018/8/30 20:20
*/
public class Main1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
char[] array = s.toCharArray();
int n = steps(array);
System.out.println(n);
}
private static int steps(char[] array) {
if (array == null) {
return 0;
}
int[] tmpArr = new int[array.length];
int tmpNum = 0;
int min = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] != array[0]) {
tmpNum++;
}
if (array[i] == array[0]) {
tmpArr[i]=tmpNum;
}
}
for (int i: tmpArr) {
min +=i;
}
return min;
}
}
结果如下：
image.png
时间复杂度为O(n)
