漫画：从赌神梭哈中衍化而来的算法面试题
- 2020 年 3 月 30 日
- 筆記
01 PART
扑克牌中的顺子
拿到题目的小伙伴，可能觉得“我次奥”，这特么也能出一道题 ？不得不说《贱止offer》，嗯….不错！
从扑克牌中随机抽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
限制：
数组长度为 5
数组的数取值为 [0, 13]
02 PART
题目分析
题目就是找一个顺子….啥？你不知道什么是顺子，看下面这个。
(顺子长这样)
因为此题本身属于简单到要屎系列，所以直接给题解。数组长度限制了是5，非常省事，意味着我们不需要一些额外的处理。拿到牌，第一个想法是啥？排序！我想打过牌的人，都会知道这点（想象那个插插插的过程）。因为是5连，无论接没接到大小王，最小值和最大值之间，一定小于5。
排序后，我们通过累积每两张牌之间的差值，来计算最小值和最大值中间的总差值。
拿到了王，就相当于拿到了通行证，直接跳过。
因为是排序的牌，如果接到对子，也就意味着不是五连，直接返回false。（怎么每次说到五连，我就想到“penta kill” ）
根据分析，得出代码：（翻个go的牌子吧）
//go func isStraight(nums []int) bool { sort.Ints(nums) sub := 0 for i := 0; i < 4; i++ { if nums[i] == 0 { continue } if nums[i] == nums[i+1] { return false } sub += nums[i+1] - nums[i] } return sub < 5 }
郑重申明（读我的文章必看）：
- 本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用啥语言纯属本人翻牌子心情。
- 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
- 算法思想才是最重要的。
03 PART
不排序咋整
“没吃过猪肉，也见过猪跑”这句话来源于《红楼梦》第十六回，有云：“偏你又怕他不在行了。谁都是在行的？孩子们这么大了，没吃过猪肉，也见过猪跑。”
没吃过猪肉还没见过猪跑么，一模一样的整法！和排序本质上没啥区别，还是通过计算最大值和最小值之间的差值，来判断是否为五连。唯一的区别，是需要记录一些数据。包括：用数组或者map记录下是否有重复牌，记录下最大值和最小值用来做最终差值计算。
直接给代码：（好奇c++有木有人看？）
//C++ class Solution { public: bool isStraight(vector<int>& nums) { vector<int> arr(14,0); for(int i = 0; i < nums.size();++i){ arr[nums[i]]++; } for(int i = 1;i < 14;++i){ if(arr[i] > 1) return false; } int min = 1,max = 13; while(min < 14 && arr[min] == 0) min++; while(max >= 0 && arr[max] == 0) max--; return max - min <= 4; } };
