10个免费货源网站,建站平台的基础概念,udacity wordpress,用ps做网站得多大像素题目 手上有一副扑克牌#xff0c;每张牌按牌面数字记分(J11,Q12,K13#xff0c;没有大小王)#xff0c;出牌时按照以下规则记分: 出单张#xff0c;记牌面分数#xff0c;例如出一张2#xff0c;得分为2 出对或3张#xff0c;记牌面分数总和再x2#xff0c;例如出3张3…题目 手上有一副扑克牌每张牌按牌面数字记分(J11,Q12,K13没有大小王)出牌时按照以下规则记分: 出单张记牌面分数例如出一张2得分为2 出对或3张记牌面分数总和再x2例如出3张3得分为(333)x218 出5张顺记牌面分数总和再x2例如出34567顺得分为(34567)×250 出4张炸弹记牌面分数总和再x3例如出4张4得分为4x4x348 求出—副牌最高的得分数。 输入描述 按顺序排好的一副牌最少1张最多15张。 1-9输入为数字1-910输入为数字0JQK输入为大写字母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]代表A1出现的数量freq[i]代表i1出现的数量 当freq[i]1时单张出得分x顺子出2x,可以多得x分x即牌面值,此处等于i1 当freq[i]2时一对出得分2*2*x4x顺子出x2*x,少了x分 当freq[i]3时三张出得分2*3*x6x顺子出2*2*x2*x6x不多不少 当freq[i]4时四张出得分4*x*312x顺子出2*3*x2*x8x少了4x 根据题意在不考虑顺子的情况有几张出几张的出法得分肯定最高此时计算出一个初始的res。 接着在考虑顺子的情况下每计算一个顺子按上述讨论得出增益量。 假设最后得到的最大增益量为正数那么res结果加上它即可说明拆成顺子出可以使得分更高 以数据3445566778为例不考虑顺子时得分res34*2*25*2*26*2*27*2*2899 抽出3,4,5,6,7作为顺子的增益量3-4-5-6-7-19 抽出4,5,6,7,8作为顺子的增益量-4-5-6-78-14 抽2个顺子(34567,45678)的增益量第一个增益量为-19在第一个的基础上再抽第二个此时freq的数据发生了变更-194567811 所以最后结果为9911110网上很多解法此用例无法通过很多没考虑同时拆两个顺子的情况第一个顺子虽然是负增益但是第二个顺子会是正增益两者抵消后结果可能就是正增益 到这里问题转化为对于给定牌考虑拆成顺子的所有可能能够得到一个最大增量量回溯法即可 题解
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;}}
解法二也可以不分析那么多直接回溯列出所有可能的出法最后得到最高得分参考的伏城之外的博客
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
说明
本专栏所有文章均为原创欢迎转载请注明文章出处https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信搜索请谨慎鉴别。技术类文章一般都有时效性本人习惯不定期对自己的博文进行修正和更新因此请访问出处以查看本文的最新版本。
