学习记录:js算法(七十六):一手顺子
文章目录
- 一手顺子
- 思路一:贪心算法
- 思路二:动态规划
- 思路三:排序 + 计数
一手顺子
Alice 手中有一把牌,她想要重新排列这些牌,分成若干组,使每一组的牌数都是 groupSize ,并且由 groupSize 张连续的牌组成。
给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌,返回 true ;否则,返回 false 。
示例 1:
输入:hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出:true
解释:Alice 手中的牌可以被重新排列为 [1,2,3],[2,3,4],[6,7,8]。
示例 2:
输入:hand = [1,2,3,4,5], groupSize = 4
输出:false
解释:Alice 手中的牌无法被重新排列成几个大小为 4 的组。
思路一:贪心算法
function isNStraightHand(hand, groupSize) {
if (hand.length % groupSize !== 0) {
return false;
}
const cardCounts = {};
hand.forEach(card => {
cardCounts[card] = (cardCounts[card] || 0) + 1;
});
const keys = Object.keys(cardCounts).map(Number).sort((a, b) => a - b);
while (keys.length) {
const currentKey = keys[0];
for (let i = 0; i < groupSize; i++) {
const key = currentKey + i;
if (!cardCounts[key]) {
return false;
}
cardCounts[key]--;
if (cardCounts[key] === 0) {
delete cardCounts[key];
keys.splice(keys.indexOf(key), 1);
}
}
}
return true;
}
讲解
这道题目的关键在于理解“连续的牌”和“每组牌数都是 groupSize” 的要求。为了满足这些条件,我们首先需要统计每张牌出现的次数,然后从最小的牌开始,尝试组成大小为 groupSize 的连续序列。这是因为如果我们要组成连续的序列,那么数量最多的牌(频率最高)应该尽可能放在序列的中间,而频率较低的牌则放在序列的两端,这样更容易组成连续的序列。
- 统计牌的频率:使用一个 Map 或对象来统计每张牌出现的次数。
- 排序牌的种类:根据牌的数值从小到大排序这些牌的种类。
- 尝试组成连续序列:从最小的牌开始,尝试组成大小为 groupSize 的连续序列。如果某一张牌的数量不足以形成一个完整的序列,那么就无法满足题目要求,返回 false 。
- 重复尝试直至所有牌都被分组:如果所有牌都能被分组,返回 true 。
思路二:动态规划
var isNStraightHand = function (hand, groupSize) {
if (hand.length % groupSize !== 0) return false;
const count = {};
for (const card of hand) {
count[card] = (count[card] || 0) + 1;
}
const uniqueCards = Object.keys(count).map(Number).sort((a, b) => a - b);
const dp = new Array(hand.length / groupSize + 1).fill(false);
dp[0] = true;
for (const card of uniqueCards) {
const neededGroups = count[card];
for (let g = 1; g <= neededGroups; g++) {
for (let j = dp.length - 1; j >= g; j--) {
dp[j] = dp[j] || dp[j - g];
}
}
}
return dp[dp.length - 1];
};
讲解
- 统计牌的数量
- 目的:创建一个对象 count,用于统计每种牌的数量。
- 细节:遍历 hand 数组,更新每种牌的计数。
- 获取唯一牌并排序
- 目的:获取所有不同的牌并进行排序。
- 细节:使用 Object.keys(count) 获取不同的牌,并将其转换为数字类型和排序。
- 初始化动态规划数组
- 目的:创建一个动态规划数组 dp,用于记录是否可以形成特定数量的组。
- 细节:dp 数组的长度为总组数加一,初始值为 false,dp[0] = true 表示可以形成 0 组。
- 动态规划填充
- 目的:更新 dp 数组,检查是否可以形成目标组数。
- 细节:遍历每种牌,利用其数量更新 dp 数组,检查是否可以通过使用当前牌形成新的组数。
- 返回结果
- 目的:返回是否可以形成所需数量的组。
- 细节:dp[dp.length - 1] 表示是否可以形成总组数。
思路三:排序 + 计数
var isNStraightHand = function (hand, groupSize) {
if (hand.length % groupSize !== 0) return false;
const count = {};
for (const card of hand) {
count[card] = (count[card] || 0) + 1;
}
const uniqueCards = Object.keys(count).map(Number).sort((a, b) => a - b);
for (const card of uniqueCards) {
while (count[card] > 0) {
for (let i = 0; i < groupSize; i++) {
if (count[card + i] === undefined || count[card + i] <= 0) {
return false;
}
count[card + i]--;
}
}
}
return true;
};
讲解
- 检查组大小
- 目的:确保牌组的长度可以被 groupSize 整除。
- 细节:如果 hand.length % groupSize !== 0,则返回 false,表示无法分组。
- 统计牌的数量
- 目的:创建一个对象 count,用于统计每种牌的数量。
- 细节:遍历 hand 数组,更新每种牌的计数。
- 获取唯一牌并排序
- 目的:获取所有不同的牌并进行排序。
- 细节:使用 Object.keys(count) 获取不同的牌,并将其转换为数字类型和排序。
- 构造顺子
- 目的:检查是否可以构造出所需的顺子。
- 细节:
- 遍历每种牌 card。
- 使用 while 循环,直到当前牌的计数为 0。
- 尝试从 card 开始,连续取出 groupSize 张牌。
- 如果在构造过程中发现某张牌不存在或计数不足,返回 false。
- 返回结果
- 目的:如果所有牌都成功构造出顺子,则返回 true。
- 细节:如果循环结束且未返回 false,则说明可以构造出所需的顺子,返回 true。