【去哪儿旅行笔试题】德州扑克

题目描述

德州扑克的花型由N张扑克牌组成（N<8），可以组成的牌型按照价值从高到低来区分分别为：

1. 皇家同花顺：最高为Ace（一点）的同花顺。
   如：A K Q J 10的同花顺
2. 同花顺：同一花色，顺序的牌。
   如：K Q J 10 9的同花顺
3. 四条：有四张同一点数的牌。
   如：4 4 4 4 9
4. 葫芦：三张同一点数的牌，加一对其他点数的牌。
   如：3 3 3 10 10
5. 同花：五张同一花色的牌。
   如：J 10 8 7 5的全是红桃的牌
6. 顺子：五张顺连的牌。
   如：5 4 3 2 A的非同花牌（此牌型为最小的顺子）
7. 三条：仅有三张同一点数的牌，其余两张点数不同。
   如：9 9 9 5 3
8. 两对：两张相同点数的牌，加另外两张相同点数的牌。
   如：K K 5 5 2
9. 一对：仅有两张相同点数的牌。
   如：10 10 9 4 2
10. 高牌：不符合上面任何一种牌型的牌型，由单牌且不连续不同花的组成，以点数决定大小。
    如：A 10 9 5 3的非同花的牌

这十种牌型分别输出“HuangJiaTongHuaShun”、“TongHuaShun”、“SiTiao”、“HuLu”、“TongHua”、“ShunZi”、“SanTiao”、“LiangDui”、“YiDui”、“GaoPai”。

扑克牌有4种花色，分别为（S表示黑桃，H表示红心，C表示草花，D表示方片）

本题的输入为任意小于8的N张牌，得到的结果为这些牌中排序最靠前的类型。

代码如下

import java.util.*;

public class Solution {
    // 用于表示牌的类型权重，最大的牌型权重为10，然后依次递减
    static class Level {
        String name;
        int weight;

        Level(String n, int w) {
            name = n;
            weight = w;
        }
    }

    private static final int M = 5;
    private static final Map<String, Integer> mp = new HashMap<>();

    static {
        for (int i = 2; i <= 10; i++) {
            mp.put(Integer.toString(i), i);
        }
        mp.put("J", 11);
        mp.put("Q", 12);
        mp.put("K", 13);
        mp.put("A", 1);
    }

    /**
     * 翻牌
     *
     * @param inHand string字符串 一组以单空格间隔的手牌(例如：SA HK H9 D8 C5 S5 H4)
     * @return string字符串
     */
    public String showDown(String inHand) {
        String[] s = inHand.split(" ");

        // 求出所有5张的组合牌
        List<int[]> com = combinations(s.length);

        // 用优先级队列选出最大的类型
        Queue<Level> pq = new PriorityQueue<>((o1, o2) -> o2.weight - o1.weight);
        int[] point = new int[M];
        for (int[] i : com) {
            Set<Character> color = new HashSet<>();
            for (int j = 0; j < M; j++) {
                color.add(s[i[j]].charAt(0));
                point[j] = mp.get(s[i[j]].substring(1));
            }
            Arrays.sort(point);
            if (color.size() == 1) {
                tongHua(point, pq);
            } else {
                feiTongHua(point, pq);
            }
        }

        return pq.size() != 0 ? pq.poll().name : "";
    }

    private void tongHua(int[] point, Queue<Level> pq) {
        if (isShunZi(point)) {
            if (point[M - 1] == 13 && point[0] == 1) {
                pq.offer(new Level("HuangJiaTongHuaShun", 10));
            } else {
                pq.offer(new Level("TongHuaShun", 9));
            }
        } else {
            pq.offer(new Level("TongHua", 6));
        }
    }

    private void feiTongHua(int[] point, Queue<Level> pq) {
        if (point[0] == point[3] || point[1] == point[4]) {
            pq.offer(new Level("SiTiao", 8));
        } else if ((point[0] == point[2] && point[3] == point[4])
                || (point[0] == point[1] && point[2] == point[4])) {
            pq.offer(new Level("HuLu", 7));
        } else if (point[0] == point[2] || point[1] == point[3] || point[2] == point[4]) {
            pq.offer(new Level("SanTiao", 4));
        } else {
            Set<Integer> ps = new HashSet<>();
            for (int p : point) {
                ps.add(p);
            }
            if (ps.size() == 3) {
                pq.offer(new Level("LiangDui", 3));
            } else if (ps.size() == 4) {
                pq.offer(new Level("YiDui", 2));
            } else {
                if (isShunZi(point)) {
                    pq.offer(new Level("ShunZi", 5));
                } else {
                    pq.offer(new Level("GaoPai", 1));
                }
            }
        }
    }

    private boolean isShunZi(int[] point) {
        for (int i = M - 2; i >= 1; i--) {
            if (point[i] != point[i + 1] - 1) {
                return false;
            }
        }
        if (point[1] == 10 && point[0] == 1) {
            return true;
        }
        return point[0] + 1 == point[1];
    }

    private List<int[]> combinations(int n) {
        List<int[]> com = new ArrayList<>();
        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            in[i] = i;
        }
        int[] out = new int[M];
        dfs(com, in, out, 0, 0);
        return com;
    }

    private void dfs(List<int[]> com, int[] in, int[] out, int idx, int cur) {
        if (idx == out.length) {
            int[] t = new int[out.length];
            System.arraycopy(out, 0, t, 0, out.length);
            com.add(t);
            return;
        }
        for (int j = cur; j < in.length; j++) {
            out[idx] = in[j];
            dfs(com, in, out, idx + 1, j + 1);
        }
    }
}

测试：

class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println("1: " + solution.showDown("SA SK SQ SJ S10 H10 C9").equals("HuangJiaTongHuaShun"));
        System.out.println("2: " + solution.showDown("SK SQ SJ S10 H10 C9 S9").equals("TongHuaShun"));
        System.out.println("3: " + solution.showDown("S3 HK H3 S7 DK D3 C3").equals("SiTiao"));
        System.out.println("4: " + solution.showDown("H3 D6 S3 SJ S10 H10 C3").equals("HuLu"));
        System.out.println("5: " + solution.showDown("S9 H7 D8 H2 H8 H9 HK").equals("TongHua"));
        System.out.println("6: " + solution.showDown("S3 H7 D4 S5 S7 H6 C7").equals("ShunZi"));
        System.out.println("7: " + solution.showDown("S3 H7 D4 S5 S7 HA C2").equals("ShunZi"));
        System.out.println("8: " + solution.showDown("S3 H7 DA S5 S7 H10 C7").equals("SanTiao"));
        System.out.println("9: " + solution.showDown("S9 HK H9 D8 C5 S5 H4").equals("LiangDui"));
        System.out.println("10: " + solution.showDown("S9 HK H9 D8 C10 S5 H4").equals("YiDui"));
        System.out.println("11: " + solution.showDown("SQ HK H9 D8 C10 S5 H4").equals("GaoPai"));
    }
}