鸡鸭分类问题

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)