全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。
真题库:https://www.yuque.com/codernav.com/od
题目:整理扑克牌
知识点:贪心排序
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
给定一组数字,表示扑克牌的牌面数字,忽略扑克牌的花色,请按如下规则对这一组扑克牌进行整理:
步骤1、对扑克牌进行分组,形成组合牌,规则如下:
当牌面数字相同张数大于等于4时,组合牌为“炸弹”;
3张相同牌面数字 + 2张相同牌面数字,且3张牌与2张牌不相同时,组合牌为“葫芦”;
3张相同牌面数字,组合牌为“三张”;
2张相同牌面数字,组合牌为“对子”;
剩余没有相同的牌,则为“单张”;
步骤2、对上述组合牌进行由大到小排列,规则如下:
不同类型组合牌之间由大到小排列规则:“炸弹” > “葫芦” > “三张” > “对子” > “单张”;
相同类型组合牌之间,除“葫芦”外,按组合牌全部牌面数字加总由大到小排列;
“葫芦”则先按3张相同牌面数字加总由大到小排列,3张相同牌面数字加总相同时,再按另外2张牌面数字加总由大到小排列;
由于“葫芦”>“三张”,因此如果能形成更大的组合牌,也可以将“三张”拆分为2张和1张,其中的2张可以和其它“三张”重新组合成“葫芦”,剩下的1张为“单张”
步骤3、当存在多个可能组合方案时,按如下规则排序取最大的一个组合方案:
依次对组合方案中的组合牌进行大小比较,规则同上;
当组合方案A中的第n个组合牌大于组合方案B中的第n个组合牌时,组合方案A大于组合方案B;
输入描述:
第一行为空格分隔的N个正整数,每个整数取值范围[1,13],N的取值范围[1,1000]
输出描述:
经重新排列后的扑克牌数字列表,每个数字以空格分隔
示例1
输入:
1 3 3 3 2 1 5
输出:
3 3 3 1 1 5 2
示例2
输入:
4 4 2 1 2 1 3 3 3 4
输出:
4 4 4 3 3 2 2 1 1 3
解题思路:
有如下扑克牌:1 1 1 2 3 3 3 4 4 4 5 5 5
1、对扑克牌进行计数排序:张数多的在前;张数—样的,点数多的在前:5 5 5 4 4 4 3 3 3 1 1 1 2
2、根据题意牌要尽可能的大,所有5葫芦后面的对子也要尽可能的大,只能对4进行拆分:5 5 5 4 4 4️⃣ 3 3 3 1 1 1 2 4
3、对3葫芦后面的1也要进行拆分,这样就多了2张单排:5 5 5 4 4 3 3 3 1 1 1️⃣ 2 4 1
4、最后再对单牌进行排序:5 5 5 4 4 3 3 3 1 1 4 2 1
代码实现一:
package com.codernav.demo.hwod.exam; import java.util.*; /** * @title 整理扑克牌 * @Description 给定一组数字,表示扑克牌的牌面数字,忽略扑克牌的花色,请按如下规则对这一组扑克牌进行整理 * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/13 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] strings = sc.nextLine().split(" "); /** * 使用map来放置牌 * key:car的点数 * value:同一点数的张数 */ Map<Integer, Integer> map = new HashMap<>(); for (String string : strings) { int i = Integer.parseInt(string); map.put(i, map.getOrDefault(i, 0) + 1); } /** * map转化为list进行排序 * 1、张数多的排在前面 * 2、张数一样的,点数多的排在前面 */ List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet()); list.sort((a, b) -> { if (Objects.equals(b.getValue(), a.getValue())) { return b.getKey() - a.getKey(); } return b.getValue() - a.getValue(); }); StringBuffer sb = new StringBuffer(); List<Integer> chaiFen = new ArrayList<>(); //需要拆分的点数(有可能是2个所以需要用到集合) for (int i = 0; i < list.size(); i++) { Map.Entry<Integer, Integer> temp = list.get(i); int carNum = temp.getKey(); int carCount = temp.getValue(); /** * 当碰到前面是三张,此牌也是三张的时候,需要进行拆分了 * (因为葫芦仅次于炸弹,所以要紧葫芦后面的对子凑最大) */ if (i > 0 && list.get(i - 1).getValue() == 3 && carCount == 3) { chaiFen.add(carNum); carCount = 2; temp.setValue(2); } else if (carCount == 1 && chaiFen.size() != 0) { //到了单张的时候,需要注意拆分的牌了 for (int k = 0; k < chaiFen.size(); k++) { if (chaiFen.get(k) > carNum) { //当拆分中的牌大于此牌时,先安排拆分的牌 sb.append(chaiFen.get(k)).append(" "); chaiFen.remove(k); //用过的牌需要移除 k--; //移除后索引往前移一位 } } } for (int j = 0; j < carCount; j++) { sb.append(carNum).append(" "); } } if (chaiFen.size() != 0) { //拆分的牌还有时需要继续用完 for (int i : chaiFen) { sb.append(i).append(" "); } } System.out.println(sb.substring(0, sb.length() - 1)); } }
代码实现二:
package com.codernav.demo.hwod.exam; import java.util.ArrayList; import java.util.Scanner; /** * @title 整理扑克牌 * @Description 给定一组数字,表示扑克牌的牌面数字,忽略扑克牌的花色,请按如下规则对这一组扑克牌进行整理 * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/13 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); // 1 3 3 3 2 1 5 String[] split = s.split(" "); int[] puke = new int[14]; for (String num : split) { puke[Integer.parseInt(num)]++; } // 优先筛选出炸弹 ArrayList<String> zhadan = new ArrayList<>(); int i = 13; while (i >= 1) { if (puke[i] >= 4) { puke[i] -= 4; String num = Integer.toString(i); zhadan.add(num + num + num + num); continue; } i--; } zhadan.sort((o1, o2) -> Integer.parseInt(o2) - Integer.parseInt(o1)); // 再搞定三张 ArrayList<String> sanzhang = new ArrayList<>(); i = 13; while (i >= 1) { if (puke[i] >= 3) { puke[i] -= 3; String num = Integer.toString(i); sanzhang.add(num + num + num); continue; } i--; } //搞定对子 ArrayList<String> duizi = new ArrayList<>(); i = 13; while (i >= 1) { if (puke[i] >= 2) { puke[i] -= 2; String num = Integer.toString(i); duizi.add(num + num); continue; } i--; } // 最后统计单张 ArrayList<String> danzhang = new ArrayList<>(); i = 13; while (i >= 1) { if (puke[i] >= 1) { puke[i] -= 1; String num = Integer.toString(i); danzhang.add(num); continue; } i--; } // 三对+两对凑葫芦 ArrayList<String> hulu = new ArrayList<>(); int size = Math.min(sanzhang.size(), duizi.size()); for (int j = 0; j < size; j++) { hulu.add(sanzhang.get(0) + duizi.get(0)); sanzhang.remove(0); duizi.remove(0); } // 输出 ArrayList<String> result = new ArrayList<>(); result.addAll(zhadan); result.addAll(hulu); result.addAll(sanzhang); result.addAll(duizi); result.addAll(danzhang); for (String item : result) { char[] chars = item.toCharArray(); for (char c : chars) { System.out.print(c + " "); } } } }