程序員面試題精選100題(40)-撲克牌的順子

時間:2019-09-22 編輯:范文亭
 題目:從撲克牌中隨機抽5張牌,判斷是不是一個順子,即這5張牌是不是連續的。2-10為數字本身,A為1,J為11,Q為12,K為13,而大小王可以看成任意數字。

         分析:這題目很有意思,是一個典型的寓教于樂的題目。

         我們需要把撲克牌的背景抽象成計算機語言。不難想象,我們可以把5張牌看成由5個數字組成的數組。大小王是特殊的數字,我們不妨把它們都當成0,這樣和其他撲克牌代表的數字就不重復了。

         接下來我們來分析怎樣判斷5個數字是不是連續的。最直觀的是,我們把數組排序。但值得注意的是,由于0可以當成任意數字,我們可以用0去補滿數組中的空缺。也就是排序之后的數組不是連續的,即相鄰的兩個數字相隔若干個數字,但如果我們有足夠的0可以補滿這兩個數字的空缺,這個數組實際上還是連續的。舉個例子,數組排序之后為{0,1,3,4,5}。在1和3之間空缺了一個2,剛好我們有一個0,也就是我們可以它當成2去填補這個空缺。

         于是我們需要做三件事情:把數組排序,統計數組中0的個數,統計排序之后的數組相鄰數字之間的空缺總數。如果空缺的總數小于或者等于0的個數,那么這個數組就是連續的;反之則不連續。最后,我們還需要注意的是,如果數組中的非0數字重復出現,則該數組不是連續的。換成撲克牌的描述方式,就是如果一副牌里含有對子,則不可能是順子。

         基于這個思路,我們可以寫出如下的代碼:

// Determine whether numbers in an array are continuous

// Parameters: numbers: an array, each number in the array is between

//             0 and maxNumber. 0 can be treeted as any number between

//             1 and maxNumber

//             maxNumber: the maximum number in the array numbers

bool IsContinuous(std::vector<int> numbers, int maxNumber)

{

    if(numbers.size() == 0 || maxNumber <=0)

        return false;

 

    // Sort the array numbers.

    std::sort(numbers.begin(), numbers.end());

 

    int numberOfZero = 0;

    int numberOfGap = 0;

 

    // how many 0s in the array?

    std::vector<int>::iterator smallerNumber = numbers.begin();

    while(smallerNumber != numbers.end() && *smallerNumber == 0)

    {

        numberOfZero++;

        ++smallerNumber;

    }

 

    // get the total gaps between all adjacent two numbers

    std::vector<int>::iterator biggerNumber = smallerNumber + 1;

    while(biggerNumber < numbers.end())

    {

        // if any non-zero number appears more than once in the array,

        // the array can't be continuous

        if(*biggerNumber == *smallerNumber)

            return false;

 

        numberOfGap += *biggerNumber - *smallerNumber - 1;

        smallerNumber = biggerNumber;

        ++biggerNumber;

    }

 

    return (numberOfGap > numberOfZero) ? false : true;

}

         本文為了讓代碼顯得比較簡潔,上述代碼用C++的標準模板庫中的vector來表達數組,同時用函數sort排序。當然我們可以自己寫排序算法。為了有更好的通用性,上述代碼沒有限定數組的長度和允許出現的最大數字。要解答原題,我們只需要確保傳入的數組的長度是5,并且maxNumber為13即可。

測試程序:
//在編程的過程中,我們可以利用最大值和最小值的差來進行簡單的判斷,利用
//set的不重復性可以避免排序。
#include<iostream>
#include<set>
#include<vector>
using namespace std;


void GetMaxMin(const set<int> &setNum,int &nMax,int &nMin)
{
  set<int>::const_iterator iter=setNum.begin();
  for(;iter!=setNum.end();iter++)
  {
    if(*iter<nMin)
nMin=*iter;
    if(*iter<nMax)
nMax=*iter;
  }
}


int Del0Num(set<int>& setNum,const vector<int> &data)
{
  int Num0=0;
  vector<int>::const_iterator iter=data.begin();
  for(;iter!=data.end();iter++)
  {
    if(*iter!=0)
setNum.insert(*iter);
else
Num0++;
  }
  return Num0;
}


bool IsContinuous(vector<int> data)
{
  int nMax=0,nMin=0;
  set<int> setNum;
  int num0=Del0Num(setNum,data);
  //下面判斷有沒有對子
  if(num0+setNum.size()<data.size())
 return false;
   GetMaxMin(setNum,nMax,nMin);
   return nMax-nMin<=data.size()-1;
}


int main()
{
  vector<int> vec;
  for(int i=0;i<5;i++)
  {
    int temp;
cin>>temp;
vec.push_back(temp);
  }
  cout<<IsContinuous(vec);
  return 0;
}
本文已影響
相關文章
大亨pk10计划苹果版