华为OD机试 双机位C卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
一、题目描述
斗地主起源于湖北十堰房县，据说是一位叫吴修全的年轻人根据当地流行的扑克玩法”跑得快”改编的，如今已风靡整个中国，并流行于互联网上。
牌型:单顺，又称顺子，最少5张牌，最多12张牌(3…A)不能有2，也不能有大小王，不计花色。
例:3-4-5-6-7-8，7-8-9-10-J-Q，3-4-5-6-7-8-9-10-J-Q-K-A可用的牌3<4<5<6<7<8<9<10<J<Q<K<A<2<B(小王)C(大王)，每种牌除大小王外有四种花色(共有13x4+2张牌)。
1、输入
- 手上有的牌
- 已经出过的牌(包括对手出的和自己出的牌)
2、输出
对手可能构成的最长的顺子(如果有相同长度的顺子，输出牌面最大的那一个)
如果无法构成顺子，则输出NO-CHAIN
二、输入描述
输入的第一行为当前手中的牌
输入的第二行为已经出过的牌
三、输出描述
最长的顺子
| 输入 | 输出 | 说明 |
|---|---|---|
| 3-3-3-3-4-4-5-5-6-7-8-9-10-J-Q-K-A A-4-5-6-7-8-8-8 | 9-10-J-Q-K-A |
四、解题思路
- 定义jqkaMap，进行JQKA的映射转换，便于排序；
- 第一行输入当前手中的牌；
- 第二行输入已经出过的牌；
- 定义集合list，存储当前手中的牌 + 已经出过的牌；
- 定义map，存储对手的牌；
- 全部牌 - 当前手中的牌 - 已经出过的牌；
- key：3-A，value：每张牌的数量；
- 获取最大的龙；
- 定义集合dragonList，存储符合要求的最大的龙；
- map倒序遍历，获取符合要求的最大的龙；
- 有剩余牌时，拼接龙；
- 当没有牌时，表示能获取到的最大的龙；
- 如果获取的龙，符合斗地主要求，则直接返回，否则清空dragonList，重新计算；
- 如果能获取到的最大的龙，不符合斗地主要求，直接返回NO-CHAIN；
- 按指定格式输出。
五、测试用例
1、输入
3-3-4-4-5-A-5-6-2-8-3-9-10-Q-7-K-J-10-B
A-4-5-8-8-10-C-6-7-8
2、输出
9-10-J-Q-K-A
3、说明
- 拼接两个字符串，排除掉不能成龙的2和大小王；
- [3, 3, 4, 4, 5, 14, 5, 6, 8, 3, 9, 10, 12, 7, 13, 11, 10, 14, 4, 5, 8, 8, 10, 6, 7, 8]
- 获取对手的牌，{3=1, 4=1, 5=1, 6=2, 7=2, 8=0, 9=3, 10=1, 11=3, 12=3, 13=3, 14=2}；
- 获取对手的牌能组成的最大的龙，[14, 13, 12, 11, 10, 9]；
- 数值映射转换9-10-J-Q-K-A。
六、Python算法源码
defmain():# 获取输入：当前手中的牌 + 已经出过的牌，并合并my_pokers=input().strip()already_pokers=input().strip()merge_pokers=my_pokers+"-"+already_pokers merge_pokers=merge_pokers.split("-")# 为方便后续判断顺子，将JQKA转为int，reverse_map供后续打印顺子使用char2int={'J':11,'Q':12,'K':13,'A':14}reverse_map={v:kfork,vinchar2int.items()}# 定义数组表示对手的牌，遍历前面合并牌数组（当前手中的牌 + 已经出过的牌），每遍历到一张牌，对手的牌对应的数组元素 - 1# 注意: 数组长度由来：顺子有效的牌为3-14，所以长度为14 - 3 + 1# 注意：为什么-3：有效的顺子牌从3开始，而数组下标需要从0开始their_pokers=[0]*(14-3+1)forpokerinmerge_pokers:iflen(poker)>1:# 10their_pokers[int(poker)-3]-=1elifpokerinchar2int:# JQKAtheir_pokers[char2int[poker]-3]-=1elifpokernotin['2','B','C']:their_pokers[int(poker)-3]-=1# 动态规划获取最长的顺子，当前牌的顺子长度只与前一个牌的顺子长度和当前牌是否可用有关prev=1iftheir_pokers[0]>-4else0max_len=float('-inf')current=0start=1foriinrange(1,len(their_pokers)):iftheir_pokers[i]>-4:# 有剩余牌时，拼接顺子current=prev+1ifcurrent>max_len:max_len=current start=i+3-max_len+1# 注意这里+3，是由于数组下标和扑克牌之间差了3else:# 无剩余牌，顺子长度置为0current=0prev=current# 符合条件ifmax_len>=5:straight="-".join(str(reverse_map.get(poker,poker))forpokerinrange(start,start+max_len))print(straight)else:print("NO-CHAIN")if__name__=="__main__":main()七、JavaScript算法源码
functionmain(){constreadline=require('readline-sync');// 获取输入：当前手中的牌 + 已经出过的牌，并合并letmyPokers=readline.question().trim();letalreadyPokers=readline.question().trim();letmergePokers=myPokers+"-"+alreadyPokers;mergePokers=mergePokers.split("-");// 为方便后续判断顺子，将JQKA转为int, reverseMap供后续打印顺子使用constchar2int={'J':11,'Q':12,'K':13,'A':14};constreverseMap=Object.fromEntries(Object.entries(char2int).map(([k,v])=>[v,k]));// 定义数组表示对手的牌consttheirPokers=newArray(14-3+1).fill(0);mergePokers.forEach(poker=>{if(poker.length>1){// 10theirPokers[parseInt(poker)-3]--;}elseif(char2int.hasOwnProperty(poker)){//JQKAtheirPokers[char2int[poker]-3]--;}elseif(poker!=='2'&&poker!=='B'&&poker!=='C'){theirPokers[parseInt(poker)-3]--;}});// 动态规划获取最长的顺子，当前牌的顺子长度只与前一个牌的顺子长度和当前牌是否可用有关letprev=theirPokers[0]>-4?1:0;letcurrent=0;letmax=-Infinity;letstart=1;for(leti=1;i<theirPokers.length;i++){if(theirPokers[i]>-4){current=prev+1;if(current>max){max=current;start=i+3-max+1;// 注意这里+3，是由于数组下标和扑克牌之间差了3}}else{current=0;}prev=current;}// 符合条件if(max>=5){conststraight=Array.from({length:max},(_,i)=>{constpoker=start+i;returnpoker>10?reverseMap[poker]:poker;}).join('-');console.log(straight);}else{console.log("NO-CHAIN");}}// 执行主函数main();八、C算法源码
#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_LEN100// 字符转换为整数映射intchar2int(charc){switch(c){case'J':return11;case'Q':return12;case'K':return13;case'A':return14;default:returnc-'0';}}// 整数转换为字符映射charint2char(intn){switch(n){case11:return'J';case12:return'Q';case13:return'K';case14:return'A';default:returnn+'0';}}intmain(){charmyPokers[MAX_LEN];charalreadyPokers[MAX_LEN];// 获取输入：当前手中的牌 + 已经出过的牌，并合并scanf("%s",myPokers);scanf("%s",alreadyPokers);charmergePokers[MAX_LEN*2];snprintf(mergePokers,sizeof(mergePokers),"%s-%s",myPokers,alreadyPokers);inttheirPokers[14-3+1]={0};// 记录对手的牌char*token=strtok(mergePokers,"-");while(token!=NULL){if(strlen(token)>1){theirPokers[atoi(token)-3]--;}elseif(token[0]!='2'&&token[0]!='B'&&token[0]!='C'){intvalue=char2int(token[0]);theirPokers[value-3]--;}token=strtok(NULL,"-");}// 动态规划获取最长的顺子intprev=theirPokers[0]>-4?1:0;intcurrent=0;intmax=-1;intstart=1;for(inti=1;i<sizeof(theirPokers)/sizeof(theirPokers[0]);i++){if(theirPokers[i]>-4){current=prev+1;if(current>max){max=current;start=i+3-max+1;}}else{current=0;}prev=current;}// 符合条件if(max>=5){for(inti=0;i<max;i++){intcard=start+i;if(card>10){printf("%c",int2char(card));}else{printf("%d",card);}if(i<max-1){printf("-");}}printf("\n");}else{printf("NO-CHAIN\n");}return0;}九、C++算法源码
#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>usingnamespacestd;// 字符转换为整数映射intchar2int(charc){switch(c){case'J':return11;case'Q':return12;case'K':return13;case'A':return14;default:returnc-'0';}}// 整数转换为字符映射charint2char(intn){switch(n){case11:return'J';case12:return'Q';case13:return'K';case14:return'A';default:returnn+'0';}}intmain(){string myPokers,alreadyPokers;// 获取输入：当前手中的牌 + 已经出过的牌，并合并cin>>myPokers>>alreadyPokers;string mergePokers=myPokers+"-"+alreadyPokers;inttheirPokers[14-3+1]={0};// 记录对手的牌char*token=strtok(&mergePokers[0],"-");while(token!=NULL){if(strlen(token)>1){theirPokers[atoi(token)-3]--;}elseif(token[0]!='2'&&token[0]!='B'&&token[0]!='C'){intvalue=char2int(token[0]);theirPokers[value-3]--;}token=strtok(NULL,"-");}// 动态规划获取最长的顺子intprev=theirPokers[0]>-4?1:0;intcurrent=0;intmax=-1;intstart=1;for(inti=1;i<sizeof(theirPokers)/sizeof(theirPokers[0]);i++){if(theirPokers[i]>-4){current=prev+1;if(current>max){max=current;start=i+3-max+1;}}else{current=0;}prev=current;}// 符合条件if(max>=5){vector<string>straight;for(inti=0;i<max;i++){intcard=start+i;if(card>10){straight.push_back(string(1,int2char(card)));}else{straight.push_back(to_string(card));}}for(size_t i=0;i<straight.size();i++){cout<<straight[i];if(i<straight.size()-1){cout<<"-";}}cout<<endl;}else{cout<<"NO-CHAIN"<<endl;}return0;}🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 新系统 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。
