面试题38：字符串的全排列和组合

题型1：排列
/**

  • 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
    */

固定第一个字符，递归取得首位后面的各种字符串组合；
再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；
递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。

代码如下：

/**
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；
     *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     * @param str
     * @return
     */
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if (str == null || str.length() <= 0){
            return list;
        }
        permutate(str.toCharArray(),0,list);
        Collections.sort(list);
        return list;

    }

    private void permutate(char[] str, int begin, ArrayList<String> list) {
        if (begin == str.length-1){
            String s = String.valueOf(str);
            //去除重复的字符串
            if (!list.contains(s)){
                list.add(s);
            }
            return;
        }
        //递归依次交换
        for (int i=begin;i<str.length;i++){
            swap(str,begin,i);
            permutate(str,begin+1,list);
            //回退出来后，尝试这种情况下的其他情况
            swap(str,begin,i);
        }
    }

    private void swap(char[] str, int begin, int i) {
        char temp = str[begin];
        str[begin] = str[i];
        str[i] = temp;
    }
    public static void main(String[] args) {
        Permutation a = new Permutation();
        System.out.println(a.Permutation("aab"));
    }

题型二：组合

  • 求字符的所有组合,允许组合中有重复元素
    如：其实就是求C(n, m) 其中n == str.length; m == num
    思路：把问题分解为1，如果当前组合包括第一个元素，则需要再从剩下的n-1个元素中以同样的方式找出m-1个与第一个元素组成一个组合,2，如果当前组合不包括目前的第一个元素，则需要再从剩下的n-1个元素中找出m个元素凑成组合，以这样的方式递归寻找下去，直到找到m个元素为止。如果一直到字符串为空，仍然没有找齐元素则直接停止。
    代码如下：
package jzOffer.chap4;
import java.util.ArrayList;
import java.util.List;

/**
 * 求字符的所有组合,允许组合中有重复元素
 */
public class combination {

    /**
     * 其实就是求C(n, m) 其中n == str.length; m == num
     *
     * @param str 字符序列
     * @param num 选几个字符进行组合
     * @return C(n, m)的集合
     */
    public List<String> combinationAccordingToNum(String str, int num) {
        List<String> list = new ArrayList<>();
        if (str == null || str.length() <= 0 || num > str.length()){
            return list;
        }
        StringBuilder sb = new StringBuilder();
        collect(str, num , sb , list);
        return list;
    }

    /**
     * 求所有组合
     * @param str
     * @return
     */
    public List<String> combination(String str){
        List<String> list = new ArrayList<>();
        if (str == null || str.length() == 0){
            return list;
        }
        StringBuilder sb = new StringBuilder();
        //1到字符长度的所有单位
        for (int i=1;i<=str.length();i++){
            collect(str, i , sb, list);
        }
        return list;
    }
    private void collect(String str, int num, StringBuilder sb, List<String> list) {
        //还剩下0位，到达最后一位，结束
        // 两个if顺序不可交换，否则C(n, n)不会存入到list中：即collect("", sb, 0)时，要先判断num==0存入后，再判断str.length ==0决定不再递归
        if (num == 0){
            //字符已经去重
            list.add(sb.toString());
            return;
        }
        //// 当str为""时候直接返回，不然下一句charAt(0)就会越界
        if (str.length() == 0){
            return;
        }

        // 公式C(n, m) = C(n-1, m-1)+ C(n-1, m)
        // 第一个字符是组合中的第一个字符，在剩下的n-1个字符中选m-1个字符
        sb.append(str.charAt(0));
        collect(str.substring(1), num-1, sb , list);
        // 第一个字符不是组合中的第一个字符，在剩下的n-1个字符中选m个字符
        sb.deleteCharAt(sb.length()-1);  //取消选中的第一个字符
        collect(str.substring(1), num, sb , list);

    }
    public static void main(String[] args) {
        combination c = new combination();
        System.out.println(c.combination("abcca"));
        System.out.println(c.combination("abc"));
        System.out.println(c.combinationAccordingToNum("aabbc", 2));
    }
}

题型3：正方体数字和

  • 输入一个含有八个数的数组，判断有没有可能把这8个数字分别加到正方形的八个定点上，使得正方体上三组相对面的四个顶点的和都相等
    思路：全排列找出所有a数组的排列，判断是否满足正方体点的特性
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 输入一个含有八个数的数组，判断有没有可能把这8个数字分别加到正方形的八个定点上，使得正方体上三组相对面的四个顶点的和都相等
 */
public class PermutationExt {
    public List<int[]> possibilitiesOfCube(int[] array){
         List<int[]> list = new ArrayList<>();
         if (array == null && array.length <= 0){
             return list;
         }

         //先得到所有的全排列组合
         List<int[]> All = permution(array);
         //检查对立面值是否相等
         for (int[] one : All){
             if (checkSum(one)){
                 list.add(one);
             }
         }
         return list;
    }

    private boolean checkSum(int[] array) {
        if ((array[0] + array[1] + array[2] + array[3] == array[4] + array[5] + array[6] + array[7]) &&
                (array[0] + array[1] + array[4] + array[5] == array[2] + array[3] + array[6] + array[7])
                && (array[0] + array[2] + array[4] + array[6] == array[1] + array[3] + array[5] + array[7])){
            return true;
        }
        return false;
    }

    public List<int[]> permution(int[] array) {
        List<int[]> list = new ArrayList<>();
        collect(array, 0 , list);
        return list;
    }

    private void collect(int[] array, int index, List<int[]> list) {
        if (index == array.length-1){
            if (!has(list,array)){
                // 必须使用副本，不能直接传入引用，否则list所有的int[]对象最后都一样
                // !!!!
                list.add(Arrays.copyOf(array,array.length));
            }
        }
        //递归从传入的起始值开始
        for (int i=index;i<array.length;i++){
            swap(array, index, i);
            collect(array, index+1, list);
            swap(array, index, i);
        }
    }

    private boolean has(List<int[]> list, int[] array) {
        for (int[] one : list) {
            if (equal(one,array)) {
                return true;
            }
        }
        return false;
    }

    private boolean equal(int[] a, int[] b){
        for (int i=0;i<a.length;i++){
            //如果遇到不相等的则可以提前返货
            if (a[i] != b[i]){
                return false;
            }
        }
        return true;
    }
    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        PermutationExt p = new PermutationExt();
        int[] a = {8, 3, 5, 4, 1, 2, 5, 6};
        List<int[]> list = p.possibilitiesOfCube(a);
        System.out.println("有" + list.size() + "种可能");
        for (int[] arr : list) {
            System.out.println(Arrays.toString(arr));
        }
        int[] b = Arrays.copyOfRange(a,1,a.length);
        System.out.println(Arrays.toString(b));
    }
}

题型四：八皇后

  • 8X8的国际棋盘上，有8个皇后，使其不能相互攻击，即它们不能在同一行、同一列、且同一条对角。
    • 1、保证不同行：使用一个数组表示不同行的皇后，八个皇后则int[] queens = new int[8]，其中queens[i]表示位于第i行的皇后，这保证了皇后不位于同一行
    • 2、保证不同列：为queens[i]赋值各不相同的数值，queens[i] = j表示位于i行的皇后也位于j列，每个i赋予了不同的j值保证了不同行的皇后也不位于不同列
    • 3、保证在同一条对角线：如果在同一条对角线，说明正方形的行数等于列数，即当j > i时:
    • j - i == queens[j] -queens[i]（第j行的皇后在第i行的皇后右下方）；或者j - i == queens[i] -queensj 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 8X8的国际棋盘上，有8个皇后，使其不能相互攻击，即它们不能在同一行、同一列、且同一条对角
 */
public class EightQueens {

    /**
     * 1、保证不同行：使用一个数组表示不同行的皇后，八个皇后则int[] queens = new int[8]，其中queens[i]表示位于第i行的皇后，这保证了皇后不位于同一行
     * 2、保证不同列：为queens[i]赋值各不相同的数值，queens[i] = j表示位于i行的皇后也位于j列，每个i赋予了不同的j值保证了不同行的皇后也不位于不同列
     * 3、保证在同一条对角线：如果在同一条对角线，说明正方形的行数等于列数，即当j > i时:
     * j - i == queens[j] -queens[i]（第j行的皇后在第i行的皇后右下方）；或者j - i == queens[i] -queens[j](第j行的皇后在第i行的皇后左下方)
     * <p>
     * 这又是一个全排列的扩展问题，先求出所有的排列可能，从中排除不符合要求的摆放方法即可
     */
    public List<int[]> possibilitiesOfQueensPlaced() {
        List<int[]> list = new ArrayList<>();
        // 大小为8的数组，且数值各不相同，任意排列都保证了不同行不同列
        int[] array = {0,1,2,3,4,5,6,7};
        //调用之前的全排列函数
        PermutationExt permutationExt = new PermutationExt();
        List<int[]> all = permutationExt.permution(array);
        //去除满足对角线的情况
        for (int[] one : all){
            if (!isLocatedSameDiagonal(one)){
                list.add(one);
            }
        }
        return list;
    }

    //检查任意两个皇后是否在同一条对角线上
    private boolean isLocatedSameDiagonal(int[] array) {
        //双重循环按照每个依次与之后行元素位置的判断
        for (int i=0;i<array.length;++i){
            for (int j=i+1;j<array.length;++j){
                if ((j - i == array[j] - array[i]) && (j - i == array[i] - array[j])){
//                if ((Math.abs(j - i) == Math.abs(array[j] - array[i]))){
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        EightQueens queens = new EightQueens();
        List<int[]> l = queens.possibilitiesOfQueensPlaced();
        System.out.println("共有" + l.size() + "种放置方法");
        for (int[] arr : l) {
            System.out.println(Arrays.toString(arr));
        }
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,776评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,527评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,361评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,430评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,511评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,544评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,561评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,315评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,763评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,070评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,235评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,911评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,554评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,173评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,424评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,106评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,103评论 2赞 352