那天面了一道java排列数字组合面试题

Question

前几天参加面试，其中有一道排列组合题，大意是要求用java语言编写程序，输出数字1,2,2,3,4,5的所有可能的排列组合,而且4不能在第三位,3和5不能相邻，例如122345是正确的，12435是错误的。参考答案 http://www.jfox.info/java-pai-lie-shu-zi-zu-he-mian-shi-tiJava面试题面试

Answer 1

最笨的就是用for循环把所有的5位数的数字打出来,用正则匹配一下...  估计考官也就是想考个正则而已..

Answer 2

import java.util.ArrayList;
import java.util.List;
public class CombinationTest
{    //数组长度
    public static final int LENTH = 6;    public static void main(String[] args)
    {
        char[] values = {'1', '2', '2', '3', '4', '5'};        List<String> result = getCombinations(values);        System.out.println("排列组合总数：" + result.size());
        System.out.println("符合要求的排列如下：");
        for (String str : result)
        {
            System.out.println(str);
        }
    }    /**
     * 获取排列的方法
     * @param values
     * @return
     */
    private static List<String> getCombinations(char[] values)
    {
        List<String> result = new ArrayList<String>();        //递归排序
        int lenth = values.length;
        //循环开头；递归方法调用前，基本数据准备
        for (int i = 0; i < lenth; i++)
        {
            //以此为排列第一个字符
            String headStr = String.valueOf(values[i]);            //将当前字符去掉得到一个新的数组
            char[] temp = removeIndexArray(values, i);            processList(headStr, temp, result);
        }        return result;
    }    /**
     * 核心递归方法
     * @param headStr
     * @param temp
     * @param result
     */
    private static void processList(String headStr, char[] temp, List<String> result)
    {
        int lenth = temp.length;
        if (lenth == 0)
        {
            return;
        }        //递归收敛处
        if (lenth == 1)
        {
            String strTmp = headStr + temp[0];            //校验规则
            processStr(strTmp, result);
            return;
        }        for (int i = 0; i < lenth; i++)
        {
            //拼装字符串
            String strTmp = headStr + temp[i];
            //将当前字符去掉得到一个新的数组
            char[] temp2 = removeIndexArray(temp, i);            //递归调用
            processList(strTmp, temp2, result);
        }
    }    /**
     * 字符串合法性校验
     * @param strTmp
     * @param result
     */
    private static void processStr(String strTmp, List<String> result)
    {
        //4不能在第三位,3和5不能相邻
        if (result.contains(strTmp) || strTmp.length() < LENTH || strTmp.charAt(2) == '4'
            || Math.abs(strTmp.indexOf("3") - strTmp.indexOf("5")) == 1)
        {
            return;
        }        result.add(strTmp);
    }    /**
     * 去掉指定下标字符，构成新数组
     * @param values
     * @param index
     * @return
     */
    private static char[] removeIndexArray(char[] values, int index)
    {
        char[] charArray = new char[values.length - 1];
        int index2 = 0;
        for (int i = 0; i < values.length; i++)
        {
            if (i == index)
            {
                continue;
            }
            charArray[index2++] = values[i];
        }
        return charArray;
    }
}