剑指Offer61.扑克牌中的顺子 C++

1、题目描述

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True

2、VS2019上运行

排序的方法

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:/*** 判断给定的扑克牌数组是否是一个顺子* @param nums 给定的扑克牌数组* @return 如果是顺子，返回true；否则，返回false*/bool isStraight(vector<int>& nums) {sort(nums.begin(), nums.end());  // 对扑克牌数组进行排序int zero = 0;  // 记录0的数量（大小王的数量）for (int i = 0; i < 4; i++) {if (nums[i] == 0) {zero++;  // 统计0的数量continue;}if (nums[i] == nums[i + 1]) {return false;  // 存在对子，不是顺子，返回false}zero -= nums[i + 1] - nums[i] - 1;  // 计算间隔并减去大小王的数量}return zero >= 0;  // 如果剩余的大小王数量可以填补所有间隔，返回true；否则，返回false}
};int main() {vector<int> nums = { 1, 2, 3, 4, 5 };Solution solution;bool result = solution.isStraight(nums);cout << (result ? "true" : "false") << endl;return 0;
}

运行结果：
true

3、解题思路

• 1.首先对给定的扑克牌数组进行排序，使其按照牌面大小升序排列。
• 2.统计大小王的数量，即统计数组中0的个数。
• 3.遍历排序后的数组，从第一个非0的数字开始（nums[i] != 0），判断后续数字是否连续。具体步骤如下：
  ~如果遇到相同的数字，说明存在对子，不满足顺子的要求，直接返回false。
  ~计算相邻数字之间的间隔（排除了0），如果间隔大于1，则需要使用大小王来填补空缺。将大小王的数量减去该间隔值减1。如果大小王数量不足以填补空缺，说明不是顺子，返回false。
• 4.如果遍历完所有数字都满足连续关系，且大小王的剩余数量足够填补空缺，则返回true。

4、题目理解

• 从一副扑克牌中随机抽取5张牌，要判断这5张牌是否是一个顺子，即这些牌是否是连续的。
• 给定的扑克牌规则如下：
  1.数字2～10对应牌面上的数字本身。
  2.A表示1。
  3.J表示11。
  4.Q表示12。
  5.K表示13。
  6.大、小王可看作任意数字，大、小王分别用0表示。
• 要判断这5张牌是否是一个顺子，可以按照以下步骤：
• 1.对这5张牌进行排序，确保它们按照牌面的大小排列。
  2.统计大、小王（即0）的数量。
  3.在排序后的牌中，找到第一个非0的数字，记作x。
  4.从x+1开始，判断后面的数字是否依次递增，即是否连续。如果存在非连续的数字（除了0之外），则不是顺子。
  5.最后，考虑大、小王的数量。如果大、小王的数量多于等于缺失的数字数量（非0的间隔数量），则可以使用大、小王来填补间隔，使得牌依旧连续。否则，无法凑成一个顺子。