846. Hand of Straights

harry xie
2024-10-11 07:34:53

解題程式碼

var isNStraightHand = function (hand, groupSize) {
  const handMap = new Map();
  hand.sort((a, b) => a - b);

  for (let i = 0; i < hand.length; i++) {
    handMap.set(hand[i], (handMap.get(hand[i]) || 0) + 1);
  }

  for (let i = 0; i < hand.length; i++) {
    if (handMap.get(hand[i]) === 0) continue;

    for (let j = 0; j < groupSize; j++) {
      if ((handMap.get(hand[i] + j) ?? 0) === 0) return false;
      handMap.set(hand[i] + j, handMap.get(hand[i] + j) - 1);
    }
  }
  return true;
};

解題思路演算法

題目要求將一些卡片整理成 groupSize 為一組，且每組的卡片數值都會連續，如果無法組出這樣的結果，回傳 false

可以將每個卡片值和出現的次數都存在 hashMap，然後將 hand 進行排序，這樣重頭開始遍歷 hand 時，只要碰到當前遍歷到的卡片值 num 在 hashMap 內大於 0 時，代表接下來的 num + 1, num + 2, ..., num + (groupSize - 1) 在 hashMap 也都要大於 1 才能組成一組連續的卡片，所以過程中沒找到就代表無法分組，回傳 false

解法的時間空間複雜度

時間複雜度: O(n * log n)
空間複雜度: O(n)

參考資料