学习记录：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 的连续序列。这是因为如果我们要组成连续的序列，那么数量最多的牌（频率最高）应该尽可能放在序列的中间，而频率较低的牌则放在序列的两端，这样更容易组成连续的序列。

1. 统计牌的频率：使用一个 Map 或对象来统计每张牌出现的次数。
2. 排序牌的种类：根据牌的数值从小到大排序这些牌的种类。
3. 尝试组成连续序列：从最小的牌开始，尝试组成大小为 groupSize 的连续序列。如果某一张牌的数量不足以形成一个完整的序列，那么就无法满足题目要求，返回 false 。
4. 重复尝试直至所有牌都被分组：如果所有牌都能被分组，返回 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];
};

讲解

1. 统计牌的数量
   • 目的：创建一个对象 count，用于统计每种牌的数量。
   • 细节：遍历 hand 数组，更新每种牌的计数。
2. 获取唯一牌并排序
   • 目的：获取所有不同的牌并进行排序。
   • 细节：使用 Object.keys(count) 获取不同的牌，并将其转换为数字类型和排序。
3. 初始化动态规划数组
   • 目的：创建一个动态规划数组 dp，用于记录是否可以形成特定数量的组。
   • 细节：dp 数组的长度为总组数加一，初始值为 false，dp[0] = true 表示可以形成 0 组。
4. 动态规划填充
   • 目的：更新 dp 数组，检查是否可以形成目标组数。
   • 细节：遍历每种牌，利用其数量更新 dp 数组，检查是否可以通过使用当前牌形成新的组数。
5. 返回结果
   • 目的：返回是否可以形成所需数量的组。
   • 细节：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;
};

讲解

1. 检查组大小
   • 目的：确保牌组的长度可以被 groupSize 整除。
   • 细节：如果 hand.length % groupSize !== 0，则返回 false，表示无法分组。
2. 统计牌的数量
   • 目的：创建一个对象 count，用于统计每种牌的数量。
   • 细节：遍历 hand 数组，更新每种牌的计数。
3. 获取唯一牌并排序
   • 目的：获取所有不同的牌并进行排序。
   • 细节：使用 Object.keys(count) 获取不同的牌，并将其转换为数字类型和排序。
4. 构造顺子
   • 目的：检查是否可以构造出所需的顺子。
   • 细节：
     • 遍历每种牌 card。
     • 使用 while 循环，直到当前牌的计数为 0。
     • 尝试从 card 开始，连续取出 groupSize 张牌。
     • 如果在构造过程中发现某张牌不存在或计数不足，返回 false。
5. 返回结果
   • 目的：如果所有牌都成功构造出顺子，则返回 true。
   • 细节：如果循环结束且未返回 false，则说明可以构造出所需的顺子，返回 true。