华为机试 ：分配房间问题 输出全排列（无重复）

问题描述

• 输入 m,n (房间数，人数) ，一间房间最多五个人
• 每间房间人数差不能超过两个
• 第1行输出未安排房间人数（如果够住输出0）
• 输出所有可能的组合（1，2 和2，1 不一样）

例子：

输入3，11

输出：
0
3，3，4
4，3，3
3，4，3

业务代码（核心代码在下面）

import java.util.Scanner;

/**
 * @Author fxs
 * @Date 2019/12/15
 **/
public class Main1 {
    static int m, n;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a;
        while (in.hasNext()) {
            a = in.nextLine();
            String[] split = a.split(",");
            if (split == null || split.length != 2) {
                System.out.println("invalid");
                return;
            }

            m = Integer.parseInt(split[0]);
            n = Integer.parseInt(split[1]);

            int i = n - 5 * m;
            if (i > 0) {
                System.out.println(i);
                StringBuilder str = new StringBuilder();
                for (int j = 0; j < m; j++) {
                    if (j == m - 1) {
                        str.append("5");
                    } else {
                        str.append("5,");
                    }
                }
                System.out.println(str.toString());
            } else {
                System.out.println(0);
                method(m, n);
            }

        }
    }


    public static void method(int m, int n) {

        float a = ((float) n) / m;
        double floor = Math.floor(a);
        double ceil = Math.ceil(a);
        if (floor == ceil) {
            StringBuilder str = new StringBuilder();
            for (int j = 0; j < m; j++) {
                if (j == m - 1) {
                    str.append(a);
                } else {
                    str.append(String.format("%s,", a));
                }
            }
            System.out.println(str.toString());
        }

        int floorNum = (int) (ceil * m - n);
        int ceilNum = m - floorNum;


        //TODO 输出排列组合内容
        int[] ints = new int[floorNum + ceilNum];
        for (int i = 0; i < floorNum; i++) {
            ints[i] = (int) floor;
        }
        for (int i = floorNum; i < floorNum + ceilNum; i++) {
            ints[i] = (int) ceil;
        }
        getAllPermutation(ints, 0);
    }
}

核心代码

public static void getAllPermutation(int[] a, int index) {
        /* 与a的元素个数相同则输出 */
        if (index == a.length - 1) {
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");//打印数组中所有元素
            }
            System.out.println();
            return;
        }
        //每次打印前先交换一次，如第一次是a[0]与a[0]交换，然后打印出23的组合
        //之后再交换回来，第二次先交换a[0]与a[1]，打印之后再还原数组
        for (int i = index; i < a.length; i++) {
            if (isSwap(a, index, i)) {
                swap(a, index, i);
                getAllPermutation(a, index + 1);
                swap(a, index, i);
            }

        }
    }

    static boolean isSwap(int[] str, int start, int end) {
        for (; start < end; start++) {
            if (str[start] == str[end])
                return false;
        }
        return true;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }