| 题目：从扑克牌中随机抽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去填补这个空缺。
于是我们需要做3件事：首先把数组排序，再统计数组中的0的个数，最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。最后，我们还需要注意一点：如果数组中的非0数字重复出现，则该数组不是连续的。
基于这个思路，实现代码如下：
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; //升序排序} qsort函数的用法见。
测试代码：
#include#include 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;}