剑指Offer面试题28：字符串的排列之相关题目

小灰灰 2022-05-28 22:20 181阅读 0赞

1.输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点上，使得正方体三组相对的面上的4个顶点的和都相等  
![这里写图片描述][70]  
其实这道题跟字符串的排列是一样的，相当于先得到a1,a2,a3,a4,a5,a6,a7,a8这8个数字的所有排列，然后判断有没有某一个排列符合题目给定的条件，即  
a1 + a2 + a3 + a4 == a5 + a6 + a7 + a8  
a1 + a3 + a5 + a7 == a2 + a4 + a6 + a8  
a1 + a2 + a5 + a6 == a3 + a4 + a7 + a8

package swordoffer.chapter4;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Interview28About1 { 
        public static void main(String[] args){
            Interview28About1 i = new Interview28About1();
            ArrayList<String> list = new ArrayList<>();
            int[] num = {
       1,2,3,4,5,6,7,8};
            i.isEightPoint(num,list);
        }
        public void isEightPoint(int[] num,ArrayList<String> list){
            if (num == null)
                return;
            Permutation(num,0,list);
        }
        private void Permutation(int[] num,int begin,ArrayList<String> list){
            int end = num.length - 1;
            if (begin == end) {
                int a1 = num[0],a2 = num[1],a3=num[2],a4=num[3],a5 = num[4],a6 = num[5],a7 = num[6],a8 = num[7];
                if (list.contains(Arrays.toString(num))) {
                    if ((a1 + a2 + a3 + a4 == a5 + a6 + a7 + a8) && (a1 + a3 + a5 + a7 == a2 + a4 + a6 + a8) && (a1 + a2 + a5 + a6 == a3 + a4 + a7 + a8))
                        list.add(Arrays.toString(num));
                    return;
                }
            }
            for(int i = begin;i<= end;i++){
                int temp = num[begin];
                num[begin] = num[i];
                num[i] = temp;
                Permutation(num,begin+1,list);
                temp = num[begin];
                num[begin] = num[i];
                num[i] = temp;
            }
        }
    }

2.在8\*8的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后不得处在同一行、同一列或者同一对角线上。请问一共有多少种符合条件的摆法？  
思路分析：由于8个皇后任意两个不能处在同一行，那么肯定每个皇后占据一行。于是我们可以定义一个数组ColumnIndex\[8\]，数组的第i个数字表示位于第i行皇后的列号。先把数组的8个数字用0~7初始化，接下来是对数组ColumnIndex的全排列。因为我们是用不同的数字初始化数组，所以任意两个皇后肯定不同列。我们只需要判断每一排列对应的8个皇后是不是在同一对角线上，也就是对于数组的两个下标i和j，是不是i-j = ColumIndex\[i\] - ColumnIndex\[j\]或者j - i =ColumIndex\[i\] - ColumnIndex\[j\]

package swordoffer.chapter4;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Interview28About2 { 
        public static void main(String[] args){
            Interview28About2 i = new Interview28About2();
            ArrayList<String> list = new ArrayList<>();
            int[] queen = {
       0,1,2,3,4,5,6,7};
            i.EightQueen(queen,list);
            System.out.println(list.size());
        }
        public void EightQueen(int[] queen,ArrayList<String> list){
            Permutation(queen,0,list);
        }
        private void Permutation(int[] queen,int begin,ArrayList<String> list){
            if (begin == queen.length - 1){
                for (int i=0;i < queen.length;i++){
                    for (int j =i + 1;j < queen.length;j++){
                        if ((i - j == queen[i] - queen[j]) ||(j - i == queen[i] - queen[j]))
                            return;
                    }
                }
                list.add(Arrays.toString(queen));
                return;
            }
            for (int i = begin;i < queen.length;i++){
                int temp = queen[begin];
                queen[begin] = queen[i];
                queen[i] = temp;
                Permutation(queen,begin+1,list);
                temp = queen[begin];
                queen[begin] = queen[i];
                queen[i] = temp;
            }
        }
    }

[70]: /images/20220529/b9ec1a0d64cc4265b26646e173768d67.png