Title Description
Draw 5 cards randomly from the playing cards to judge whether it is A Shun Zi, that is, whether these 5 cards are continuous. 2-10 is the number itself, A is 1, J is 11, Q is 12, K is 13, and big and small Wang can be regarded as any number, and big and small Wang is 0.
algorithm analysis
First, sort the array, then count the number of zeros in the array, and finally count the total number of vacancies between adjacent numbers in the sorted array. If the total number of vacancies is less than or equal to 0, the array is continuous; otherwise, it is discontinuous. Finally, it is also important to note that if a non-zero number in an array is repeated, the array is not contiguous.
Submission Code:
class Solution {
public:
bool IsContinuous(vector<int> numbers) {
if (numbers.empty())
return false;
QSort(numbers, 0, numbers.size() - 1);
int numOfZero = 0;
int numOfGap = 0;
// Count the number of 0 in the array
for (int i = 0; i < numbers.size() && numbers[i] == 0; ++i)
++numOfZero;
int smallIndex = numOfZero;
int bigIndex = smallIndex + 1;
while (bigIndex < numbers.size())
{
if (numbers[smallIndex] == numbers[bigIndex])
return false;
numOfGap += numbers[bigIndex] - numbers[smallIndex] - 1;
smallIndex = bigIndex;
++bigIndex;
}
return numOfGap > numOfZero ? false : true;
}
void QSort(vector<int> &numbers, int beg, int end)
{
if (beg >= end)
return;
int pivot = Partition(numbers, beg, end);
QSort(numbers, beg, pivot - 1);
QSort(numbers, pivot + 1, end);
}
int Partition(vector<int> &numbers, int beg, int end)
{
int pivotkey = numbers[beg];
while (beg < end)
{
while (beg < end && pivotkey <= numbers[end])
--end;
swap(numbers[beg], numbers[end]);
while (beg < end && pivotkey >= numbers[beg])
++beg;
swap(numbers[beg], numbers[end]);
}
return beg;
}
};Test code:
// ====================Test code====================
void Test(const char* testName, vector<int> &numbers, bool expected)
{
if (testName != nullptr)
printf("%s begins: ", testName);
Solution s;
if (s.IsContinuous(numbers) == expected)
printf("Passed.\n");
else
printf("Failed.\n");
}
void Test1()
{
vector<int> numbers = { 1, 3, 2, 5, 4 };
Test("Test1", numbers, true);
}
void Test2()
{
vector<int> numbers = { 1, 3, 2, 6, 4 };
Test("Test2", numbers, false);
}
void Test3()
{
vector<int> numbers = { 0, 3, 2, 6, 4 };
Test("Test3", numbers, true);
}
void Test4()
{
vector<int> numbers = { 0, 3, 1, 6, 4 };
Test("Test4", numbers, false);
}
void Test5()
{
vector<int> numbers = { 1, 3, 0, 5, 0 };
Test("Test5", numbers, true);
}
void Test6()
{
vector<int> numbers = { 1, 3, 0, 7, 0 };
Test("Test6", numbers, false);
}
void Test7()
{
vector<int> numbers = { 1, 0, 0, 5, 0 };
Test("Test7", numbers, true);
}
void Test8()
{
vector<int> numbers = { 1, 0, 0, 7, 0 };
Test("Test8", numbers, false);
}
void Test9()
{
vector<int> numbers = { 3, 0, 0, 0, 0 };
Test("Test9", numbers, true);
}
void Test10()
{
vector<int> numbers = { 0, 0, 0, 0, 0 };
Test("Test10", numbers, true);
}
// There are pairs.
void Test11()
{
vector<int> numbers = { 1, 0, 0, 1, 0 };
Test("Test11", numbers, false);
}
// Robustness test
void Test12()
{
Test("Test12", vector<int>(), false);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
Test9();
Test10();
Test11();
Test12();
return 0;
}