阿里3.20 面试题一

有一叠扑克牌，每张牌介于1和10之间
有四种出牌方法：

1. 单出1张
2. 出2张对子
3. 出五张顺子，如12345
4. 出三连对子，如112233

给10个数，表示1-10每种牌有几张，问最少要多少次能出完

思路:

        根据剩余牌数, 找出最长可行的出牌方法, 若相同出牌方法有不同的组合, 则分别计算每种组合所对应的解, 取最小的解

        当最长可行解为一张牌时, 出牌次数等于已出的次数加上剩余牌的个数

        分别计算相同出牌方法的不同组合时, 必须在进行下一次计算时恢复当前计算所改变的每种牌的张数及剩余牌数和已出牌数状态

import java.util.Arrays;
import java.util.Scanner;

public class Poke {
    /**
     * 有一叠扑克牌，每张牌介于1和10之间
     * 有四种出牌方法：
     * 单出1张
     * 出2张对子
     * 出五张顺子，如12345
     * 出三连对子，如112233
     * 给10个数，表示1-10每种牌有几张，问最少要多少次能出完
     */
    
    public static int res = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
    
        int remain = 7;
        int[] nums = {2, 1, 1, 1, 1, 1, 0, 0, 0, 0};
        
//        第一行输入共有多少张牌, 第二行输入每一种牌的张数,
        Scanner sc = new Scanner(System.in);
        remain = sc.nextInt();
        for (int i = 0; i < 10; i++) {
            nums[i] = sc.nextInt();
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
//        System.out.println(sum);
//        System.out.println(remain);
        if (sum != remain) {
            System.out.println("输入错误!");
            return;
        }
        
        for (int i = 1; i < 11; i++) {
            System.out.print(i + " ");
        }
        dfs(remain, 0, nums);
        System.out.println("最少出牌次数为: " + res);
    }
    
    public static void dfs(int remain, int cnt, int[] nums) {
        
        if (remain == 0) {
            System.out.println("本次出牌次数为: " + cnt);
            res = cnt < res ? cnt : res;
            return;
        }
        System.out.println();
        boolean flag = false;
        int[] tempNums = Arrays.copyOf(nums, 10);
        int tempCnt = cnt;
        int tempRemain = remain;

//      判断剩余牌数
        if (remain >= 6) {

//            判断是否可以出连对
            for (int k = 0; k < 8; k++) {
                if (nums[k] >= 2) {
                    if (nums[k + 1] >= 2 && nums[k + 2] >= 2) {
//                        可以出连对
                        nums[k] -= 2;
                        nums[k + 1] -= 2;
                        nums[k + 2] -= 2;
                        System.out.printf("第%d次: 可以出连对: 两个%d, 两个%d, 两个%d\n\n", cnt + 1, k + 1, k + 2, k + 3);
                        print(nums);
                        cnt += 1;
                        remain -= 6;
                        dfs(remain, cnt, nums);
//                        状态恢复
                        cnt = tempCnt;
                        remain = tempRemain;
                        nums = Arrays.copyOf(tempNums, 10);
                        flag = true;
                    }
                }
            }
            if (flag) return;
        }
        
        if (remain >= 5) {
//            判断是否可以出顺子
            for (int k = 0; k < 6; k++) {
                if (nums[k] >= 1 && nums[k + 1] >= 1 && nums[k + 2] >= 1 && nums[k + 3] >= 1 && nums[k + 4] >= 1) {
//                        可以出连对
                    nums[k]--;
                    nums[k + 1]--;
                    nums[k + 2]--;
                    nums[k + 3]--;
                    nums[k + 4]--;
                    System.out.printf("第%d次: 可以出顺子: %d, %d, %d, %d, %d\n\n", cnt + 1, k + 1, k + 2, k + 3, k + 4, k + 5);
                    print(nums);
                    cnt += 1;
                    remain -= 5;
                    dfs(remain, cnt, nums);
//                        状态恢复
                    cnt = tempCnt;
                    remain = tempRemain;
                    nums = Arrays.copyOf(tempNums, 10);
                    System.out.println("状态恢复");
                    flag = true;
                }
            }
            if (flag) return;
        }
        if (remain >= 2) {
//            判断是否可以出对子
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] >= 2) {
                    nums[i] -= 2;
                    System.out.printf("第%d次: 可以出对子: 对%d\n\n", cnt + 1, i + 1);
                    print(nums);
                    cnt++;
                    remain -= 2;
                    dfs(remain, cnt, nums);
//                              状态恢复
                    cnt = tempCnt;
                    remain = tempRemain;
                    nums = Arrays.copyOf(tempNums, 10);
                    flag = true;
                }
            }
            if (flag) return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                nums[i]--;
                System.out.printf("第%d次: 只能单走一张%d\n\n", cnt + 1, i + 1);
                print(nums);
                cnt++;
                remain--;
            }
        }
        //        只能单走一张, 如果只能单走一张牌的时候, 那剩下的出牌可能就是剩余牌数, remain为0, cnt += nums[i] != 0 的元素个数
        dfs(remain, cnt, nums);
    }
    
    private static void print(int[] nums2) {
        for (int i : nums2) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i = 1; i < 11; i++) {
            System.out.print(i + " ");
        }
        System.out.println('\n');
    }
}