小朋友排顺序

一个热爱技术的菜鸟...用点滴的积累铸就明日的达人

CSDN博客链接： http://blog.csdn.net/my_confesser

今天在网上看到一道编程测验题，感觉挺有意思的，于是顺手写了写。记录下来与大家一起交流交流，如果有更好的办法，请告知，一起学习

题目

　　幼儿园老师要带小朋友们出去玩，要求小朋友们自己排好队伍(比如这样"GGGBBG")，但是老师发现如果男孩子旁边有个小女孩的话，男孩子会欺负小女孩，所以老师想达到这样的一种效果：男孩子都在一起，女孩子也都在一起(比如这样"BBGGGG"或者"GGGGBB")，每次交换小朋友位置的时候只能将小朋友和旁边的小朋友交换(也就是不能这样换"GGGBBG"-->"GGGGBB"，只能这样"GGGGBBG"-->"GGGGBGB"-->"GGGGGBB")。最后老师想知道如果随意给出一个小朋友的顺序(因为小朋友排队都比较随意)，那么将小朋友排号顺序至少要多少次交换。

例如：

　　一开始队伍的顺序是：GGGGBBG

　　那么期望顺序有两种：GGGGGBB与BBGGGGG

　　对于第一种：GGGGBBG-->GGGGBGB-->GGGGGBB

　　对于第二种：GGGGBBG-->GGGBGBG-->GGBGGBG-->GBGGGBG-->BGGGGBG-->BGGGBGG-->BGGBGGG-->BGBGGGG-->BBGGGGG

　　很明显第一种只需要两步，第二种需要八步，那么最佳答案是2

思路

　　首先大家要注意一下，题目的意图是让我们求出最佳交换次数，而不是交换顺序(我一开始就在顺序上纠结了好久...写了好长的一段代码)。

那么现在考虑了，其实每种队列都有两种最佳情况，一种是B在G前面，一种是G在B前面。不妨把每种的情况都计算一次，之后比较两个次数的大小就可以得出最佳答案了。

    public int getMinFrequency(char[] queue) {
        int gFrequency = getMinGBF(queue);//G在B前面的最佳次数
        int bFrequency = getMinBGF(queue);//B在G前面的最佳次数
        return gFrequency < bFrequency ? gFrequency : bFrequency;
    }

　先以G在前B在后去考虑问题，那么现在的问题已经被细化成了G在B前时需要几次能交换完成(有人会问这有细化问题吗？我的理解：其实我们无论遇到什么问题，能化成子问题的先化成子问题，即使这个子问题只是迈出了一个很小的步子，那也是进步，例如本题中，一开始可能要考虑到底是G在B前面，还是B在G前面呢？而此时，我们已经避免了这个问题...这已经有很大进步了)。对于GGGGBBG要转换成GGGGGBB，其实只需要考虑每个G前面有多少个B就可以了，因为我们总是假设左边已经是排好序了，然后判断下一个如何交换到排好序的队列里面(其实这里面的思想就是我们熟悉的插入排序的思想，因为前面排好序的队列始终都是G在B前面的，下一个元素只需要交换B的数量的交换即可交换到指定位置)。因此只需要从队列开始的位置扫描一下每个G前面有多少个B，之后将所有的G前面的B的数目相加就得到次数了。

    private int getMinGBF(char[] queue) {
        int count = 0;
        int sum = 0;
        for (char gb : queue) {
            if (gb == 'B') {
                count++;
            } else {
                sum += count;
            }
        }
        return sum;
    }

　　最后我们再考虑一下，我们的程序在极端情况下有没有问题(例如：GGG,BBB,空这几种情况)，很幸运，经过推理都没有问题~~

程序

public class Main {

    public int getMinFrequency(char[] queue) {
        int gFrequency = getMinF(queue, 'G');//G在B前面的最佳次数
        int bFrequency = getMinF(queue, 'B');//B在G前面的最佳次数
        return gFrequency < bFrequency ? gFrequency : bFrequency;
    }

    /**
     * @param firstChar 最终队列中第一个char，如果是G的话，那么意味G在B前，反之亦然
     */
    private int getMinF(char[] queue, char firstChar) {
        int count = 0;
        int sum = 0;
        for (char gb : queue) {
            if (gb == firstChar) {
                count++;
            } else {
                sum += count;
            }
        }
        return sum;
    }
}