【面试题044】扑克牌的顺子

【面试题044】扑克牌的顺子

题目：

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2~10为数字本身，A为1，J为11，Q为12，K为13，

而大小王可以看成任意的数字。

思路一：

可以吧五张牌看成是五个数字组成的数字，大小王是特殊的数字，把他填为0（为了和其他牌区分），

对数组排序
统计数组中0的个数
统计数组中相邻数字之间的空缺总数。

如果相邻数字之间的空缺总数大于0的个数说明不是顺子，如果小于0的个数说明是顺子。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <iostream>
#include <cstdlib>
using namespace std;

int compare(const void *arg1, const void *arg2)
{
    return *(int *)arg1 - *(int *)arg2;
}

bool IsContinuous(int *numbers, int length)
{
    if (numbers == NULL || length < 1)
    {
        return false;
    }
    qsort(numbers, length, sizeof(int), compare);
    int numberOfZero = 0;
    int numberOfGap = 0;

    for (int i = 0; i < length && numbers[i] == 0; ++i)
    {
        ++numberOfZero;
    }

    int small = numberOfZero;
    int big = small + 1;
    while (big < length)
    {
        if (numbers[small] == numbers[big])
        {
            return false;
        }
        numberOfGap += numbers[big] - numbers[small] - 1;
        small = big;
        ++big;
    }
    return (numberOfGap > numberOfZero) ? false : true;
}

int main()
{
    int num1[] = {1, 3, 5, 0, 4};
    int length1 = sizeof(num1) / sizeof(num1[0]);
    if (IsContinuous(num1, length1))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    int num2[] = {1, 5, 0, 4};
    int length2 = sizeof(num2) / sizeof(num2[0]);
    if (IsContinuous(num2, length2))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    return 0;
}