【华为OD题库-094】最佳的出牌方法-java

题目

手上有一副扑克牌，每张牌按牌面数字记分(J=11,Q=12,K=13，没有大小王)，出牌时按照以下规则记分:
出单张，记牌面分数，例如出一张2，得分为2
出对或3张，记牌面分数总和再x2，例如出3张3，得分为(3+3+3)x2=18
出5张顺，记牌面分数总和再x2，例如出34567顺，得分为(3+4+5+6+7)×2=50
出4张炸弹，记牌面分数总和再x3，例如出4张4，得分为4x4x3=48
求出—副牌最高的得分数。
输入描述
按顺序排好的一副牌，最少1张，最多15张。
1-9输入为数字1-9，10输入为数字0，JQK输入为大写字母JQK.
无需考虑输入非法的情况，例如输入字符不在[0-9JQK]范围或某—张牌超过4张
输出描述
最高的得分数
备注
积分规则中没有的出牌方式不支持，例如不支持3带1、4带2，不支持5张以上的顺，且10JQKA(OJQK1)不算顺.
示例1:
输入:
33445677
输出
67
说明
出对3、对4、对7，单张5、6，得分为67；
出34567顺，再出单张3、4、7，得分为64
输出结果67
因此最高得分是按对出，可得到最高分67，

思路

这道题比较难，我这边思考了很久，解法如下：

使用int[] freq存放每种牌存放的数量，freq[0]代表A（1）出现的数量，freq[i]代表i+1出现的数量
当freq[i]==1时，单张出得分：x，顺子出：2x,可以多得x分（x即牌面值,此处等于i+1）
当freq[i]==2时，一对出得分：2*2*x=4x，顺子出：x+2*x,少了x分
当freq[i]==3时，三张出得分：2*3*x=6x，顺子出：2*2*x+2*x=6x，不多不少
当freq[i]==4时，四张出得分：4*x*3=12x，顺子出：2*3*x+2*x=8x，少了4x
根据题意，在不考虑顺子的情况，有几张出几张的出法得分肯定最高，此时计算出一个初始的res。
接着，在考虑顺子的情况下，每计算一个顺子，按上述讨论，得出增益量。
假设最后得到的最大增益量为正数，那么res结果加上它即可（说明拆成顺子出可以使得分更高）
以数据3445566778为例，不考虑顺子时，得分：res=3+4*2*2+5*2*2+6*2*2+7*2*2+8=99
抽出3,4,5,6,7作为顺子的增益量：+3-4-5-6-7=-19
抽出4,5,6,7,8作为顺子的增益量：-4-5-6-7+8=-14
抽2个顺子(34567,45678)的增益量：第一个增益量为-19，在第一个的基础上再抽第二个（此时freq的数据发生了变更），-19+4+5+6+7+8=11
所以最后结果为99+11=110（网上很多解法此用例无法通过，很多没考虑同时拆两个顺子的情况，第一个顺子虽然是负增益，但是第二个顺子会是正增益，两者抵消后结果可能就是正增益）
到这里，问题转化为：对于给定牌，考虑拆成顺子的所有可能，能够得到一个最大增量量？回溯法即可

题解

package hwod;

import java.util.*;

public class BestPoker {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        int len = input.length();
        int[] nums = new int[len];
        final char[] chars = input.toCharArray();
        for (int i = 0; i < len; i++) {
            if (chars[i] == '0') nums[i] = 10;
            else if (chars[i] == 'J') nums[i] = 11;
            else if (chars[i] == 'Q') nums[i] = 12;
            else if (chars[i] == 'K') nums[i] = 13;
            else nums[i] = chars[i] - '0';
        }

        System.out.println(bestPoker(nums));
    }

    private static int szAdd = 0;//最大的顺子增益
    private static int[] freq = new int[13];

    private static int bestPoker(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            freq[nums[i] - 1]++;
        }
        int res = 0;
        //不考虑顺子能得多少分
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] == 0 || freq[i] > 4) {
                continue;
            }
            if (freq[i] == 1) {
                res += i + 1;
            } else if (freq[i] == 2) {
                res += 2 * (i + 1) * 2;
            } else if (freq[i] == 3) {
                res += 3 * (i + 1) * 2;
            } else if (freq[i] == 4) {
                res += 4 * (i + 1) * 3;
            }
        }
        dfs(0, 0);
        //如果拆成顺子后，得分能够增加
        if (szAdd > 0) res += szAdd;
        return res;

    }

    /**
     *
     * @param idx freq中的索引位置
     * @param score 顺子的得分增益
     */
    private static void dfs(int idx, int score) {
        szAdd = Math.max(szAdd, score);
        for (int i = idx; i < 9; i++) {
        //要组成顺子，起始值不能超过9，所以索引小于等于8
            if (!checkedSZ(i)) continue;
            int lstScore = score;//回溯时，恢复上次计算的score
            for (int k = 0; k < 5; k++) {
                if (freq[i + k] == 1) score += i + k + 1;
                else if (freq[i + k] == 2) score -= i + k + 1;
                else if (freq[i + k] == 4) score -= 4 * (i + k + 1);
                freq[i + k]--;
            }
            dfs(i, score);
            for (int k = 0; k < 5; k++) {
                freq[i + k]++;
                score = lstScore;
            }
        }
    }

    /**
     *
     * @param idx
     * @return 判断给定idx开始，能否组成顺子
     */
    private static boolean checkedSZ(int idx) {
        for (int i = 0; i < 5; i++) {
            if (freq[idx + i] == 0) {
                return false;
            }
        }
        return true;
    }


}

解法二：也可以不分析那么多，直接回溯列出所有可能的出法，最后得到最高得分，参考的伏城之外的博客

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。