全网最全面的华为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 + " ");
}
}
}
}
相关文章
