找牌中最大的顺子长度

最近面试遇到一个找最大顺子长度的笔试题，当时没做出来，回来后把思路理了理重新记录一下。

题目的大意

把牌编号：0， 1， 2， …. , 51， 52， 53；
其中52， 53是大小王，可以作为任意数插入顺子中；0－12， 13－25， 26－38， 39－51分别代表四种花色从A开始到K的牌。
满足顺子的条件，牌点数连续的个数大于5。

输入：一组牌和牌的个数，找出其中可组成的最大顺子长度

思路

使用一个szVec来记录连续牌的区域，然后放入王牌，更新王牌位置，计算出最大所连区域的长度，即顺子的长度。
关键思路就是区域的连接。

比如牌的点数为 2， 3， 5， 6， 7， 9， 10， J， Q， 大小王

代码如下：

#include <iostream>
#include <vector>
using namespace std;
#define MIN_SHUNZI_LEN 5
#define MAX_CARD_NUM 13
#define SMALL_KING_CARD_NUM 52
#define BIG_KING_CARD_NUM 53
/*
*find the max length of shunzi
*/
int findMaxLenOfShunZi(int* cardArr, int cardCount){
//检查参数
if(cardCount < MIN_SHUNZI_LEN ){
return 0;
}
//用来记录连续区域与区域长度, +2用来加上左右两个端点，方便后续计算
vector<int> szLenVec(MAX_CARD_NUM+2, 0);
//记录大小王牌的个数
int kingCardCount = 0;
//依次放入牌，更新连续区域的长度
for(int i = 0; i < cardCount; ++i){
//如果是大小王牌则不做处理，记录大小王牌的张数
if(cardArr[i] == SMALL_KING_CARD_NUM || cardArr[i] == BIG_KING_CARD_NUM){
kingCardCount++;
continue;
}
//获取牌的点数;cardNum >= 1 && <= MAX_CARD_NUM
int cardNum = cardArr[i] % MAX_CARD_NUM + 1;
//如果是重复的牌，则不做处理
if(szLenVec[cardNum] != 0){
continue;
}
//计算放入这张牌后，所连结的左右区域的总长度
szLenVec[cardNum] = 1 + szLenVec[cardNum-1] + szLenVec[cardNum+1];
//更新该区域左端点的区域长度
int endPoint = cardNum - szLenVec[cardNum-1];
szLenVec[endPoint] = szLenVec[cardNum];
//更新该区域右端点点区域长度
endPoint = cardNum + szLenVec[cardNum+1];
szLenVec[endPoint] = szLenVec[cardNum];
}
//test
// cout << kingCardCount << endl;
// for(int i = 1; i <= MAX_CARD_NUM; ++i){
//
cout << i+1 << ": " <<
szLenVec[i] << endl;
// }
int maxShunZiLen = 0;
int shunZiLen = 0;
int startIndex = 0;
vector<int> kingIndexVec;
//放入大小王牌
int i = 0;
while(i <= MAX_CARD_NUM){
//作为一个连续区域的左端点
if(szLenVec[i] != 0){
i += szLenVec[i];
continue;
}
//....empty slot
//如果王牌没有用尽， ＋1是用来记录开始端点
if(kingIndexVec.size() < kingCardCount + 1){
//放入连续区域的左端点，用来记录放入点右边的长度
kingIndexVec.push_back(i+1);
//顺子长度加上右边连结区域的长度
shunZiLen += szLenVec[i+1];
// cout << "add shunZiLen: " << szLenVec[i+1] << " " << shunZiLen << endl;
maxShunZiLen = shunZiLen;
}else{ //如果王牌用尽，开始挪动第一个放入点到现在放入点
//move the first slot to the now slot and update the sunZiLen

//顺子长度－第一个放入点右边的长度＋现在放入点连结点右边的长度

shunZiLen += szLenVec[i+1] - szLenVec[kingIndexVec[startIndex]];
// cout << "move slot " << kingIndexVec[startIndex]-1 << 
//
" to " << i << " shunziLen: " << shunZiLen << endl;
//记录最大顺子长度
if(shunZiLen > maxShunZiLen){
maxShunZiLen = shunZiLen;
}
//保存放入点的位置
kingIndexVec[startIndex] = i+1;
//更新第一个放入点的序号
startIndex = ++startIndex % (kingCardCount + 1);
}
//进入下一个放入点
++i;
}
//加上所放入的王牌个数
maxShunZiLen += kingIndexVec.size() - 1;
return maxShunZiLen < MIN_SHUNZI_LEN ? 0 : maxShunZiLen;
}
int main(){
int n = 0;
cin >> n;
int* a = new int[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
cout << "MaxShunZiCount: " << findMaxLenOfShunZi(a, n) << endl;
}

最后

以上就是丰富毛巾为你收集整理的找牌中最大的顺子长度找牌中最大的顺子长度的全部内容，希望文章能够帮你解决找牌中最大的顺子长度找牌中最大的顺子长度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。