引言
上一段时间笔者所在的甲方公司大规模裁员，笔者也不幸失业了，为了尽快找到新的工作，只好在Boss直聘上一个劲地投简历。不得不说今年的就业行情非常严峻，笔者面试了大半个月竟然一个offer都没收到，很多外包岗位招的虽然是高级开发却要求应聘人员具备架构师才具备的技能和处理生产问题的经验，面试官也不愿冒着一定的风险给我发放offer。
由于今年很多公司裁员，即使很多外包岗位竞争都很激烈。更糟糕的是码农这一行业，过了35岁没做到管理层就会被很多公司嫌弃了，基层码农干到40岁很可能就要被强制退休转行干别的事情去了。笔者自己有时候也很沮丧，明明入行还不足10年，却要思考未来不做程序员了该靠什么赚钱养活自己和一家人？干过这么多年的项目，突然发现作为一名程序员不进入一些大公司不参与一些核心有技术含量的大项目开发，靠平时的自学很难让自己的技术栈提升到能在大公司里独当一面的层次。这次面试就发现一些很好的岗位要求熟练掌握Spark、Flink、Hive和ClickHouse等大数据技术框架，但是自己以往的项目中压根就没用过到过这些技术框架，自己也就没去学过。还有一些优质招聘岗位要求有电商项目和社交IM即时通讯等项目经验或者会安卓App项目开发，这些因为笔者在之前的工作中也没做过同类的项目，因此简历投出去连一个初试的机会都很难收到。
在Boss直聘上投简历的时候收到了很华为OD岗位的面试邀请，看他们的待遇都很不错，都是20-30k 14薪以上，但是却要在面试前参加他们的机考考试，机考有三道题，前两道题100分，最后一道题200分，总分400分，考试总时长150分钟，要考满300分才能参加后面的面试和办理入职手续，对于不常刷算法的码农来说难度还挺大。笔者准备了有一个多礼拜，刷了3-5天的题后于是参加了一场机考，在此之前笔者已经考过两次了，那两次连第一道题都没有完整地做处理，而且第一道题就花了很长时间，以至于后面的题目都没时间做了。
这次参加机考依然没过，但是第一道题却完整地做出来了拿了100分，可是却花了我一个半小时才做出来，后面第二、第三道题却只剩60分钟了，第二道题没想到也有难度，自己写出的代码只通过1/8的测试用例拿了12.5分，第三道200分的题目自己看了一下，没想到竟然非常简单，非常遗憾的却是由于自己没提前看这道题导致完全没时间去做了。这次笔者把第一道题的解答思路和详细代码记录到博客上来，一方面给自己复个盘，另一方面也希望对最近要参加此类机考的读者朋友们一个解题思路的参考。
题目描述
这次抽到的第一道机考题是：斗地主游戏中计算玩家手上可能存在的最大顺子, 该题的详细描述如下：
斗地主游戏中一副扑克由3-4-5-6-7-8-9-10-J-Q-K-A-2 各4个和两个大小王组成, 共54张牌, 输入两行牌，第一行为玩家手上的牌，第二行为所有玩家已经打出来的牌
案例一：输入下面这两行
3-3-3-4-4-5-6-6-7-8-9-10-J-Q-K-A
3-4-4-5-5-5-6-6-7-7-7-8-9-10-J-Q-K-A
输出：8-9-10-J-Q-K-A
案例二：输入下面这两行
3-3-4-4-5-5-6-6-7-7-9-10-J-Q
3-3-8-8-8-8-K-K-K-K
解题思路
1、使用一个HashMap的key和value分别存放3-4-5-6-7-8-9-10-J-Q-K-A 这 12 个牌和每张牌的总个数4；
2、先后遍历玩家手上的牌和已经打出的牌，HashMap中遍历的牌对应的key的话则其value值减1，减到0则表示对手玩家手上不会有这张牌;
3、遍历踢除玩家自己和所有人已经打出的牌后的HashMap, 找出value值不为0的key，并将其中的J、Q、K、A分别用11、12、13、14代替后组成一个新的HashSet集合，该集合中的牌即是对手玩家手上可能存在的牌的集合;
4、遍历第三步处理后的HashSet 集合中的元素并放入一个新的List集合中， 并将此集合按数字大小升序排序；
5、找出第4步处理后的List集合中所有组成5-12个连续数字的列表集合，并将该列表集合排序，长度不一样的按长度大的降序排列，长度相同列表的按第一个牌的数字大小降序排列，然后将排序后的列表集合中的下标为0的集合以"-"分隔符拼接起来，超过10的数字字符使用J-A中对应的字母替换。不过这种方式笔者发现自己用代码实现不了，于是改为使用下面这种方式；
6、将经过第4步处理后的List集合中的元素将其中数字大于11的元素替换成J、Q、K、A中对应的字母后以"-"分隔符拼接起来组成一个对手玩家手上存在的所有牌的大字符串String；
7、将3-4-5-6-7-8-9-10-J-Q-K-A 12个字符按长度由大到小，牌面由大到小组成的12-5位顺子字符串（牌号之间使用"-"分隔）放到集合List2中；
8、遍经过第7步处理后的List2集合中的所有顺子字符串，并设置一个标识符初始值为false, 若遍历的顺子字符串包含在经过第6步处理后的大顺子字符串String中则标识符便为true， 打印该顺子字符串后跳出循环体，若遍历完List2集合中的所有顺子字符串后标识符仍然为false则标识对手玩家手上不存在顺子，打印出NO-CHAINS字符串。
代码实现
import java.util.*;
/**
* 三人斗地主游戏计算两位对家手上可能存在的最大的顺子
* 一副扑克由3-4-5-6-7-8-9-10-A-J-Q-K-A-2 各4个和两个大小王组成, 共54张牌
* 一个顺子至少由5张连续的牌组成，最小的顺子为3-4-5-6-7；最大有12张连续的牌，最大的顺子为3-4-5-6-7-8-9-10-J-Q-K-A
* 输入两行牌，第一行为玩家手上的牌，第二行为所有玩家已经打出来的牌，如下面两行
* 3-3-3-4-4-5-6-6-7-8-9-10-J-Q-K-A
* 3-4-4-5-5-5-6-6-7-7-7-8-9-10-J-Q-K-A
* 上面这种情况对家手上可能存在的最大顺子为：8-9-10-J-Q-K-A, 则输出该最大顺子
* 下面这种情况对家手上不存在顺子则输出：NO-CHAINS
* 3-3-4-4-5-5-6-6-7-7-9-10-J-Q
* 3-3-8-8-8-8-K-K-K-K
* 现在需要你根据输入的两行牌计算对家手上可能存在的最大顺子，并在屏幕上输出该最大顺子
*/
public class CardGame {
public static void main(String[] args) {
// 将3-A这12张牌每张作为一个key放入到一个HashMap中，对应的value值为4
String[] cardNumsArray = new String[]{"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
Map cardNumMap = new HashMap();
for(String cardNum: cardNumsArray){
cardNumMap.put(cardNum, 4);
}
Scanner scanner = new Scanner(System.in);
String line1 = scanner.nextLine().trim();
String[] card1Nums = line1.split("-");
// 玩家手上的牌有在cardNumMap中每有一张则减1
for(String cardNum: card1Nums){
if(cardNumMap.containsKey(cardNum)){
cardNumMap.put(cardNum, cardNumMap.get(cardNum)-1);
}
}
String line2 = scanner.nextLine().trim();
String[] card2Nums = line2.split("-");
// 所有玩家打出的的牌有在cardNumMap中每有一张也减1
for(String cardNum: card2Nums){
if(cardNumMap.containsKey(cardNum)){
cardNumMap.put(cardNum, cardNumMap.get(cardNum)-1);
}
}
List cardNumList = new ArrayList();
Set keySet = cardNumMap.keySet();
Map charNumMap = new HashMap(4);
charNumMap.put("J", "11");
charNumMap.put("Q", "12");
charNumMap.put("K", "13");
charNumMap.put("A", "14");
Set cardNumSet = new HashSet();
for(String cardNum: keySet){
if(cardNumMap.get(cardNum).intValue()==0){
continue; // 过滤掉对手玩家手上没有的牌
}
if(charNumMap.containsKey(cardNum)){
// cardNum为J,Q,K,A的转成对应的数字
cardNumSet.add(charNumMap.get(cardNum));
}else{
cardNumSet.add(cardNum);
}
}
for(String key: cardNumSet){
cardNumList.add(key);
}
if(cardNumList.size()>2){
// 对手手上的牌按牌面数字的大小升序排序
cardNumList.sort(Comparator.comparing(Integer::parseInt));
}
Map numCharMap = new HashMap(4);
numCharMap.put("11", "J");
numCharMap.put("12", "Q");
numCharMap.put("13", "K");
numCharMap.put("14", "A");
// 统计对手玩家手中的所有牌
StringBuilder cardNumBuilder = new StringBuilder();
for(int i=0; i longestSequence.size()) {
longestSequence = sequence;
}
}
return longestSequence;
}
// 获取最长的顺子
private static String getCardString(List cards) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < cards.size(); i++) {
int card = cards.get(i);
if (card == 1) {
sb.append("A");
} else if (card == 11) {
sb.append("J");
} else if (card == 12) {
sb.append("Q");
} else if (card == 13) {
sb.append("K");
} else {
sb.append(card);
}
if (i < cards.size() - 1) {
sb.append("-");
}
}
return sb.toString();
}
}
测试结果
首先运行CardGame类中的main方法, 然后在控制台中输入用例一中的两行输入参数
3-3-3-4-4-5-6-6-7-8-9-10-J-Q-K-A
3-4-4-5-5-5-6-6-7-7-7-8-9-10-J-Q-K-A
回车后看到控制台输出：8-9-10-J-Q-K-A
然后重新运行main函数继续输入用例二中的两行输入参数：
3-3-4-4-5-5-6-6-7-7-9-10-J-Q
3-3-8-8-8-8-K-K-K-K
回车后看到控制台输出：NO-CHAINS
然后运行 CardGameGPT类中的main方法后在控制台中输入用例一中的两行输入参数：
3-3-3-4-4-5-6-6-7-8-9-10-J-Q-K-A
3-4-4-5-5-5-6-6-7-7-7-8-9-10-J-Q-K-A
结果输出：NO-CHAINS
说明chatGPT生成的代码有bug，需要我们手动修改，修改后的代码如下：
import java.util.*;
public class CardGameGPT {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String playerCards = scanner.nextLine();
String playedCards = scanner.nextLine();
List playerCardList = parseCardString(playerCards);
List playedCardList = parseCardString(playedCards);
List remainingCards = getRemainingCards(playerCardList, playedCardList);
List sequences = getSequences(remainingCards);
List longestSequence = getLongestSequence(sequences);
if (longestSequence.size() >= 5) {
System.out.print(getCardString(longestSequence));
} else {
System.out.print("NO-CHAINS");
}
}
private static List parseCardString(String cardString) {
List cardList = new ArrayList();
String[] cards = cardString.split("-");
for (String card : cards) {
switch (card) {
case "A":
cardList.add(14);
break;
case "J":
cardList.add(11);
break;
case "Q":
cardList.add(12);
break;
case "K":
cardList.add(13);
break;
default:
cardList.add(Integer.parseInt(card));
break;
}
}
return cardList;
}
// 统计对手玩家手上的牌
private static List getRemainingCards(List playerCards, List playedCards) {
List remainingCards = new ArrayList();
Map carNumMap = new HashMap(12);
String[] cardNumArray = new String[]{"3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14"};
for(String cardNum: cardNumArray){
carNumMap.put(cardNum, 4);
}
for(Integer cardNum: playerCards){
String key = String.valueOf(cardNum);
if(carNumMap.containsKey(key)){
carNumMap.put(key, carNumMap.get(key)-1);
}
}
for(Integer cardNum: playedCards){
String key = String.valueOf(cardNum);
if(carNumMap.containsKey(key)){
carNumMap.put(key, carNumMap.get(key)-1);
}
}
Set keySet = carNumMap.keySet();
for(String key: keySet){
if(carNumMap.get(key)>0){
remainingCards.add(Integer.valueOf(key));
}
}
Collections.sort(remainingCards);
return remainingCards;
}
// 统计对手玩家手上所有的顺子组合
private static List getSequences(List cards) {
List sequences = new ArrayList();
int count = 1;
for (int i = 0; i 1) {
if (count >= 5) {
sequences.add(new ArrayList(cards.subList(i - count + 1, i + 1)));
}
count = 1;
}
}
if (count >= 5) {
sequences.add(new ArrayList(cards.subList(cards.size() - count, cards.size())));
}
return sequences;
}
// 获取最长最大的顺子
private static List getLongestSequence(List sequences) {
if(sequences.size()==0){
// 没有顺子返回空数组
return new ArrayList();
} else if(sequences.size()==1){
// 只有一个顺子直接返回下标为0的顺子
return sequences.get(0);
} else {
sequences.sort((list1, list2)->{
if(list1.size()!=list2.size()){
// 长度不同，长度大的排在前面
return list2.size() - list1.size();
} else {
// 长度相同比较第一牌的大小
return list2.get(0) - list1.get(0);
}
});
return sequences.get(0);
}
}
private static String getCardString(List cards) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < cards.size(); i++) {
int card = cards.get(i);
if (card == 14) {
sb.append("A");
} else if (card == 11) {
sb.append("J");
} else if (card == 12) {
sb.append("Q");
} else if (card == 13) {
sb.append("K");
} else {
sb.append(card);
}
if (i < cards.size() - 1) {
sb.append("-");
}
}
return sb.toString();
}
}
重新运行 CardGameGPT类中的main方法后在控制台中输入用例一中的两行输入参数：
3-3-3-4-4-5-6-6-7-8-9-10-J-Q-K-A
3-4-4-5-5-5-6-6-7-7-7-8-9-10-J-Q-K-A
输出：8-9-10-J-Q-K-A
再次运行 CardGameGPT类中的main方法后在控制台中输入用例二中的两行输入参数：
3-3-4-4-5-5-6-6-7-7-9-10-J-Q
3-3-8-8-8-8-K-K-K-K
输出：NO-CHAINS
再次运行 CardGameGPT类中的main方法后在控制台中输入用例三中的两行输入参数：
3-3-5-5-6-7-7-8-9-9-10-J-Q-K-A
3-4-5-6-7-8-8-8-9-9-10-J-Q-K-A
用例三位笔者新添加的测试用例，为了测试存在2个相同位数的数字时应该输出牌面最大的顺子
此时对手玩家手上存在两个5位顺子，分别是：3-4-5-6-7 和 10-J-Q-K-A
结果输出：10-J-Q-K-A
小结
本文主要研究了如何用Java代码解决**斗地主时根据玩家自己手中的牌和所有玩家打出的牌计算对手玩家手上可能存在的最大顺子**的算法题，主要用到了Map和List等数据结构以及集合的排序等算法，难点在于拿到对手玩家手上存在的所有牌后如何找到到可能的顺子集合， 笔者当时用了一种笨方法， 那就是枚举出3-4-5-6-7-8-9-10-J-Q-K-A中所有的 5-12位顺子集合并按长度和牌面由大到小排序。同时用对手手中的所有牌从小到大排序后按"-"分隔符连接组成一个大字符串然后遍历该顺子集合，然后遍历顺子集合，若对手玩家手中的牌组成的大字符串包含遍历的顺子，则输出该顺子。
但是后面``chatGPT提供的解题代码实现了笔者想实现却很难实现的建模，不得不说借助chatGPT可以很大地提高我们程序员的编程效率。虽然可能会存在一点小Bug, 但是一般经过我们的手动修改后程序都能正常地跑起来！所以最为一名程序员，我们还是在平时的工作和学习中尽可能地把chatGPT用起来吧！
现在还年青（30岁之前）想要进互联网大厂的同学可以去牛客网或者利扣 网上多刷一刷算法题，用代码实现解题的过程也是一个数据建模的过程，算法思维好的同学这一道题应该也容易做出来，华为OD的很多机考题其实也是来源与LeetCode上面的算法题，也就是怎么使用Java里面的数据结构通过编码把问题给解决了。其实机考时对提交的代码还有最大时间复杂度和组大空间复杂度的要求，一般要求跑完一个测试用例耗时不超过1s，内存不超过256M。这也就要求我们不仅要会编码解题，还要学会优化解题的代码实现，使得最大时间复杂度和空间复杂度做到最小，至少要能保证在题目的要求范围内。
本文首发个人微信公众号【阿福谈Web编程】，欢迎喜欢我的文章的读者朋友们加个公众号关注，第一时间阅读笔者的原创文章，大家一起在技术精进的路上同行不孤单！
