// 面试题61：扑克牌的顺子
// 题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
// 2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王可以看成任意数字。 #include <iostream> int Compare(const void *arg1, const void *arg2); bool IsContinuous(int* numbers, int length)
{
if (numbers == nullptr || length < )//边界判断
return false; qsort(numbers, length, sizeof(int), Compare);//使用qsort排序，虽然qsort算法复杂度O（nlongn），但是n不大，和O（n）差不多 int numberOfZero = ;
int numberOfGap = ; // 统计数组中0的个数
for (int i = ; i < length && numbers[i] == ; ++i)
++numberOfZero; // 统计数组中的间隔数目
int small = numberOfZero;
int big = small + ;
while (big < length)
{
// 两个数相等，有对子，不可能是顺子
if (numbers[small] == numbers[big])
return false; numberOfGap += numbers[big] - numbers[small] - ;
small = big;
++big;
} return (numberOfGap > numberOfZero) ? false : true;
} int Compare(const void *arg1, const void *arg2)//充当qsort谓词
{
return *(int*)arg1 - *(int*)arg2;
} // ====================测试代码====================
void Test(const char* testName, int* numbers, int length, bool expected)
{
if (testName != nullptr)
printf("%s begins: ", testName); if (IsContinuous(numbers, length) == expected)
printf("Passed.\n");
else
printf("Failed.\n");
} void Test1()
{
int numbers[] = { , , , , };
Test("Test1", numbers, sizeof(numbers) / sizeof(int), true);
} void Test2()
{
int numbers[] = { , , , , };
Test("Test2", numbers, sizeof(numbers) / sizeof(int), false);
} void Test3()
{
int numbers[] = { , , , , };
Test("Test3", numbers, sizeof(numbers) / sizeof(int), true);
} void Test4()
{
int numbers[] = { , , , , };
Test("Test4", numbers, sizeof(numbers) / sizeof(int), false);
} void Test5()
{
int numbers[] = { , , , , };
Test("Test5", numbers, sizeof(numbers) / sizeof(int), true);
} void Test6()
{
int numbers[] = { , , , , };
Test("Test6", numbers, sizeof(numbers) / sizeof(int), false);
} void Test7()
{
int numbers[] = { , , , , };
Test("Test7", numbers, sizeof(numbers) / sizeof(int), true);
} void Test8()
{
int numbers[] = { , , , , };
Test("Test8", numbers, sizeof(numbers) / sizeof(int), false);
} void Test9()
{
int numbers[] = { , , , , };
Test("Test9", numbers, sizeof(numbers) / sizeof(int), true);
} void Test10()
{
int numbers[] = { , , , , };
Test("Test10", numbers, sizeof(numbers) / sizeof(int), true);
} // 有对子
void Test11()
{
int numbers[] = { , , , , };
Test("Test11", numbers, sizeof(numbers) / sizeof(int), false);
} // 鲁棒性测试
void Test12()
{
Test("Test12", nullptr, , false);
} int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
Test9();
Test10();
Test11();
Test12();
system("pause");
return ;
}