JZ-C-44

剑指offer第四十四题:扑克牌的顺子:从扑克牌中随机抽5张牌,判断是不是顺子,大小鬼以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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//============================================================================
// Name        : JZ-C-44.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 扑克牌的顺子:从扑克牌中随机抽5张牌,判断是不是顺子,大小鬼以0表示,可代替任何牌
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
int compare(const void *arg1, const void *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;
 
    // 统计数组中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 compare(const void *arg1, const void *arg2) {
    return *(int*) arg1 - *(int*) arg2;
}
 
// ====================测试代码====================
void Test(char* testName, int* numbers, int length, bool expected) {
    if (testName != NULL)
        printf("%s begins: ", testName);
 
    if (IsContinuous(numbers, length) == expected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}
 
void Test1() {
    int numbers[] = { 1, 3, 2, 5, 4 };
    Test("Test1", numbers, sizeof(numbers) / sizeof(int), true);
}
 
void Test2() {
    int numbers[] = { 1, 3, 2, 6, 4 };
    Test("Test2", numbers, sizeof(numbers) / sizeof(int), false);
}
 
void Test3() {
    int numbers[] = { 0, 3, 2, 6, 4 };
    Test("Test3", numbers, sizeof(numbers) / sizeof(int), true);
}
 
void Test4() {
    int numbers[] = { 0, 3, 1, 6, 4 };
    Test("Test4", numbers, sizeof(numbers) / sizeof(int), false);
}
 
void Test5() {
    int numbers[] = { 1, 3, 0, 5, 0 };
    Test("Test5", numbers, sizeof(numbers) / sizeof(int), true);
}
 
void Test6() {
    int numbers[] = { 1, 3, 0, 7, 0 };
    Test("Test6", numbers, sizeof(numbers) / sizeof(int), false);
}
 
void Test7() {
    int numbers[] = { 1, 0, 0, 5, 0 };
    Test("Test7", numbers, sizeof(numbers) / sizeof(int), true);
}
 
void Test8() {
    int numbers[] = { 1, 0, 0, 7, 0 };
    Test("Test8", numbers, sizeof(numbers) / sizeof(int), false);
}
 
void Test9() {
    int numbers[] = { 3, 0, 0, 0, 0 };
    Test("Test9", numbers, sizeof(numbers) / sizeof(int), true);
}
 
void Test10() {
    int numbers[] = { 0, 0, 0, 0, 0 };
    Test("Test10", numbers, sizeof(numbers) / sizeof(int), true);
}
 
// 有对子
void Test11() {
    int numbers[] = { 1, 0, 0, 1, 0 };
    Test("Test11", numbers, sizeof(numbers) / sizeof(int), false);
}
 
// 鲁棒性测试
void Test12() {
    Test("Test12", NULL, 0, false);
}
 
int main(int argc, char* argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
    Test8();
    Test9();
    Test10();
    Test11();
    Test12();
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注