[关闭]
@Ggmatch 2018-02-11T02:47:21.000000Z 字数 3670 阅读 1382

扑克牌的顺子——给我的启示

剑指offer c++ 算法

题       目

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2~10为数字本身，A为1，J为11，Q为12，K为13，而大、小王可以看成任何数字（这里看成0）。

解题经过

1.第一个版本：少了异常情况的处理

  1. #include "stdafx.h"
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. bool comp(int, int);
  7. /*
  8.     目的：判断当前序列的5个元素能够构成一个顺子
  9.     思路：1. 5张牌全在1-13中。排序，判断是否连续
  10.           2. 5张牌部分在1-13中，有大小王。排序后，计算出断掉的元素个数，若==大小王个数，则连续；否则，不连续
  11. */
  12. bool IsContinuous(vector<int> numbers)
  13. {
  14.     // 1.排序
  15.     sort(numbers.begin(),numbers.end(), comp);
  16.     // 2.计算出0的个数
  17.     vector<int>::iterator iter = numbers.begin();
  18.     int numbersOf0 = 0;
  19.     for (;(*iter) == 0 && iter != numbers.end();++iter)
  20.     {
  21.         numbersOf0++;
  22.     }
  23.     // 3.计算出断掉的元素个数
  24.     int uncontinuousElements = 0;
  25.     int big,small;
  26.     big = small = *iter;
  27.     while (++iter != numbers.end())
  28.     {
  29.         big = *iter;
  30.         if (big != small + 1)
  31.             uncontinuousElements+=big-small-1;
  32.         small = big;
  33.     }
  34.     // 4.判断两者大小关系
  35.     if (numbersOf0 == uncontinuousElements)
  36.         return false;
  37.     return true;
  38. }
  40. bool comp(int param1, int param2)
  41. {
  42.     // 升序
  43.     return param1<param2;
  44. }

2.第二个版本：少了大小王个数>间隔元素的个数

  1. #include "stdafx.h"
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. bool comp(int, int);
  7. /*
  8.     目的：判断当前序列的5个元素能够构成一个顺子
  9.     思路：1. 5张牌全在1-13中。排序，判断是否连续
  10.           2. 5张牌部分在1-13中，有大小王。排序后，计算出断掉的元素个数，若==大小王个数，则连续；否则，不连续
  11. */
  12. bool IsContinuous(vector<int> numbers)
  13. {
  14.     // 0.处理异常情况
  15.     if (numbers.size() < 5)
  16.         return false;
  17.     // 1.排序
  18.     sort(numbers.begin(),numbers.end(), comp);
  19.     // 2.计算出0的个数
  20.     vector<int>::iterator iter = numbers.begin();
  21.     int numbersOf0 = 0;
  22.     for (;(*iter) == 0 && iter != numbers.end();++iter)
  23.     {
  24.         numbersOf0++;
  25.     }
  26.     // 3.计算出断掉的元素个数
  27.     int uncontinuousElements = 0;
  28.     int big,small;
  29.     big = small = *iter;
  30.     while (++iter != numbers.end())
  31.     {
  32.         big = *iter;
  33.         if (big != small + 1)
  34.             uncontinuousElements+=big-small-1;
  35.         small = big;
  36.     }
  37.     // 4.判断两者大小关系
  38.     if (numbersOf0 == uncontinuousElements)
  39.         return false;
  40.     return true;
  41. }

3.第三个版本：少了对子的情况

  1. #include "stdafx.h"
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. bool comp(int, int);
  7. /*
  8.     目的：判断当前序列的5个元素能够构成一个顺子
  9.     思路：1. 5张牌全在1-13中。排序，判断是否连续
  10.           2. 5张牌部分在1-13中，有大小王。排序后，计算出断掉的元素个数，若<=大小王个数，则连续；否则，不连续
  11. */
  12. bool IsContinuous(vector<int> numbers)
  13. {
  14.     // 0.处理异常情况
  15.     if (numbers.size() < 5)
  16.         return false;
  17.     // 1.排序
  18.     sort(numbers.begin(),numbers.end(), comp);
  19.     // 2.计算出0的个数
  20.     vector<int>::iterator iter = numbers.begin();
  21.     int numbersOf0 = 0;
  22.     for (;(*iter) == 0 && iter != numbers.end();++iter)
  23.     {
  24.         numbersOf0++;
  25.     }
  26.     // 3.计算出断掉的元素个数
  27.     int uncontinuousElements = 0;
  28.     int big,small;
  29.     big = small = *iter;
  30.     while (++iter != numbers.end())
  31.     {
  32.         big = *iter;
  33.         if (big != small + 1)
  34.             uncontinuousElements+=big-small-1;
  35.         small = big;
  36.     }
  37.     // 4.判断两者大小关系
  38.     if (numbersOf0 < uncontinuousElements)
  39.         return false;
  40.     return true;
  41. }

4.最终版本

  1. #include "stdafx.h"
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. bool comp(int, int);
  7. /*
  8.     目的：判断当前序列的5个元素能够构成一个顺子
  9.     思路：1. 5张牌全在1-13中。排序，判断是否连续
  10.           2. 5张牌部分在1-13中，有大小王。排序后，计算出断掉的元素个数，若<=大小王个数，则连续；否则，不连续
  11. */
  12. bool IsContinuous(vector<int> numbers)
  13. {
  14.     // 0.处理异常情况
  15.     if (numbers.size() < 5)
  16.         return false;
  17.     // 1.排序
  18.     sort(numbers.begin(),numbers.end(), comp);
  19.     // 2.计算出0的个数
  20.     vector<int>::iterator iter = numbers.begin();
  21.     int numbersOf0 = 0;
  22.     for (;(*iter) == 0 && iter != numbers.end();++iter)
  23.     {
  24.         numbersOf0++;
  25.     }
  26.     // 3.计算出断掉的元素个数
  27.     int uncontinuousElements = 0;
  28.     int big,small;
  29.     big = small = *iter;
  30.     while (++iter != numbers.end())
  31.     {
  32.         big = *iter;
  33.         // 处理对子的情况
  34.         if (big == small)
  35.             return false;
  36.         if (big != small + 1)
  37.             uncontinuousElements+=big-small-1;
  38.         small = big;
  39.     }
  40.     // 4.判断两者大小关系
  41.     if (numbersOf0 < uncontinuousElements)
  42.         return false;
  43.     return true;
  44. }
  46. bool comp(int param1, int param2)
  47. {
  48.     // 升序
  49.     return param1<param2;
  50. }

测试案例

  1. int main()
  2. {
  3.     // 测试
  4.     vector<int> vec1 = { 3,2,5,6,7 };
  5.     vector<int> vec2 = { 3,0,5,6,7 };
  6.     vector<int> vec3 = {2,5,6,7};
  7.     vector<int> vec4 = { 4,0,0,0,0 };
  8.     vector<int> vec5 = { 1,1,0,0,0 };
  9.     // 无大小王
  10.     bool result1 = IsContinuous(vec1);
  11.     // 有大小王
  12.     bool result2 = IsContinuous(vec2);
  13.     bool result4 = IsContinuous(vec4);
  14.     // 不足5个元素
  15.     bool result3 = IsContinuous(vec3);
  16.     // 出现对子
  17.     bool result5 = IsContinuous(vec5);
  19.     // 打印结果
  20.     printf("%d %d %d %d %d\n", result1, result2, result3,result4,result5);
  21.     return 0;
  23. }

个人感悟

解决现实问题，很重要的一点就是要把问题可能出现的情况考虑周全，这道题的解题经过充分揭露了我考虑问题严密性的不足，也揭示了测试优先编程思想的重要性，每一种测试案例都代表一种情况的出现，把所有情况都考虑进来，这个程序的鲁棒性才会好，所以以后编程的时候在有了大致思路的时候，就要懂得自己寻找测试案例，然后边编程边修改程序。
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注