剑指offer-45、扑克牌顺⼦
<h2 id="题描述">题⽬描述</h2><p>扑克牌可以组成顺⼦，⼤\⼩ 王可以看成任何数字,并且 A 看作 1 , J 为 11 , Q 为 12 , K 为 13 。 5张牌 【A,0,3,0,5】 就可以变成“ 1,2,3,4,5 ”(⼤⼩王分别看作 2 和 4 ),这样就组成了顺⼦。（可以认为⼤⼩王是 0 。）</p>
<p>输⼊五张牌，如果牌能组成顺⼦就输出true，否则就输出 false 。</p>
<p>示例1<br>
输⼊：<br>
返回值：true</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="排序遍历">排序遍历</h3>
<p>这是最直观的解法，通过排序后分析牌之间的间隔关系来判断。</p>
<p>排序后统计大小王数量，检查非王牌之间的间隔是否可用大小王填补：先排序，0肯定是靠左边，然后统计0的个数，后⾯的数，按照第⼀个⾮0的数进⾏递增，如果不是递增，则需要使⽤ 0 牌补充，如果 0 牌不够，需要放回 false ，否则直到遍历完数组，返回true 。</p>
<pre><code class="language-java">public boolean IsContinuous(int[] numbers) {
// 数组⻓度不符合直接返回
if (numbers == null || numbers.length < 5) {
return false;
}
// 先排序
Arrays.sort(numbers);
// 统计0的个数
int numOfZero = 0;
// 初始化索引
int start;
// 统计0的个数
for (start = 0; start < numbers.length; start++) {
if (numbers == 0) {
numOfZero++;
} else {
// ⾮0的时候跳出
break;
}
// 暂存0的个数
int n = numOfZero;
// 当前的数值
int cur = numbers;
// 从0的下两个位置开始
for (start++; start < numbers.length;) {
// 如果可变的牌数量为0
if (numOfZero == 0) {
// 和前⾯的⼀个对⽐
if (numbers != cur + 1) {
// 不等于当前数值+1的话，直接返回false
return false;
} else {
// 当前数值+1
cur++;
}
} else {
// 不等于当前数值+1的话，直接返回false
if (numbers != cur + 1) {
// 可变牌数量-1
numOfZero--;
//当前值+1
cur++;
// 遍历下⼀张牌
continue;
} else {
// 相等则直接将当前值+1
cur++;
}
}
// 索引滑动到下⼀张牌
start++;
}
return true;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n log n)，主要来自排序操作</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数级别额外空间</li>
</ul>
<h3 id="哈希集合法推荐">哈希集合法（推荐）</h3>
<p>利用HashSet实现去重，同时记录最大值和最小值。</p>
<p>初始化⼀个最⼩牌 14 ，最⼤牌 0 ，直接使⽤ set 保存数组的元素，如果 set 中已经存在该元素，那么我们直接放回 false ，如果 set 中不存在该元素，则将该元素放进 set 中，判断该元素是否⼩于最⼩牌，⼩于则更新最⼩牌，判断该元素是否⼤于最⼤牌，如果⼤于最⼤牌，则更新当前最⼤牌。</p>
<p><strong>为什么 <code>max - min < 5</code>是充分必要条件？</strong></p>
<p>对于5张牌组成的顺子：</p>
<ul>
<li>如果是连续5张不同数字：max - min = 4</li>
<li>如果有空缺，但能被大小王填补：max - min ≤ 4</li>
<li>如果空缺太大：max - min ≥ 5，即使有4个大小王也无法填补</li>
</ul>
<p><strong>示例验证：</strong></p>
<ul>
<li><code></code>：max=5, min=1, 5-1=4<5 ✓</li>
<li><code></code>：max=6, min=1, 6-1=5≥5 ✗</li>
</ul>
<pre><code class="language-java">public class Solution45 {
public boolean IsContinuous(int[] numbers) {
if (numbers == null || numbers.length < 5) {
return false;
}
HashSet <Integer> set = new HashSet <> ();
int min = 14;
int max = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers != 0) {
if (set.contains(numbers)) {
return false;
}
set.add(numbers);
max = Math.max(max, numbers);
min = Math.min(min, numbers);
}
}
// 关键条件：最大牌-最小牌 < 5 才能组成顺子
return max - min < 5;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，只需遍历数组一次</li>
<li><strong>空间复杂度</strong>：O(n)，HashSet的空间开销</li>
</ul>
<h3 id="位运算法空间最优">位运算法（空间最优）</h3>
<p>利用整数的二进制位来标记牌值是否出现，实现O(1)空间复杂度。</p>
<p><strong>二进制位标记原理：</strong></p>
<ul>
<li>整数<code>flag</code>的32位中，用第i位表示数字i是否出现</li>
<li>例如：数字3出现 → 将第3位置1：<code>flag |= 1 << 3</code></li>
<li>检查数字3是否出现：<code>(flag >> 3) & 1 == 1</code></li>
</ul>
<pre><code class="language-java">public class Solution {
public boolean isStraight(int[] nums) {
if (nums == null || nums.length != 5) {
return false;
}
int flag = 0; // 用二进制位标记牌值出现情况
int max = 0;// 非王牌最大值
int min = 14; // 非王牌最小值
for (int num : nums) {
if (num == 0) {
continue; // 跳过大小王
}
// 检查牌值是否已出现（检查第num位是否为1）
if (((flag >> num) & 1) == 1) {
return false; // 有重复牌
}
// 标记牌值已出现（将第num位置为1）
flag |= (1 << num);
// 更新最值
if (num > max) max = num;
if (num < min) min = num;
// 提前判断：如果已经不可能组成顺子，直接返回
if (max - min >= 5) {
return false;
}
}
return max - min < 5;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，线性遍历</li>
<li><strong>空间复杂度</strong>：O(1)，只使用固定数量的整数变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19285855
頁:
[1]