鸡鸭分类问题

2019年招商信用卡中心笔试的编程第一题,当时还没想好这个问题,后来才想到了。

鸡鸭分类问题

题目

1
大致问题就是:鸡鸭不能串这挨着。鸡用C表示,鸭用D表示。例如:CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻,需要调整队形两次。

示例

输入描述:输入一个长度为N,且只包含C和D的非空字符串。

1
输入:CCDCC

输出描述:使得最后仅有一对鸡鸭相邻,最少的交换次数。

1
输出:2

解释思想:

  • 把第一个字母记录下来,然后统计和第一字母相同的字母前面有几个不同的字母,然后把每次的数字加起来就可以了。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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)

文章目录
  1. 1. 鸡鸭分类问题