40.撲克牌的順子[Continuous cards]

【題目】

從撲克牌中隨機抽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數字重復出現，則該數組不是連續的。換成撲克牌的描述方式，就是如果一副牌裡含有對子，則不可能是順子。

【代碼】

 C++ Code  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39  
/*
sort cards
get zeroCount and gapCount
*/
bool IsContinuous(int cards[], int length)
{
    if(NULL == cards || length <= 0)
        return false;

    sort(cards, cards + length);
    int zeroCount = 0;
    int gapCount = 0;
    int i = 0, j = 0;
    for (; i < length; ++i)
    {
        if (cards[i] == 0)
        {
            zeroCount++;
        }
    }

    int prevCard = cards[i];
    for (j = i + 1; j < length; ++j)
    {
        int curCard = cards[j];
        if (curCard == prevCard)
        {
            return false;
        }
        else
        {
            gapCount += (curCard - prevCard - 1);
        }
        // update previous card
        prevCard = curCard;
    }
    return gapCount <= zeroCount ? true : false;
}

【參考】

http://zhedahht.blog.163.com/blog/static/25411174200951262930831/

http://blog.csdn.net/wuzhekai1985/article/details/6639919