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

本文主要是介绍【华为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，所以索引小于等于8if (!checkedSZ(i)) continue;int lstScore = score;//回溯时，恢复上次计算的scorefor (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;}}