iT邦幫忙

2024 iThome 鐵人賽

DAY 27
0

解題程式碼

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)

參考資料

Yes


上一篇
131. Palindrome Partitioning
下一篇
678. Valid Parenthesis String
系列文
向 NeetCode、官神看齊! 分享自己的解題筆記和影片。30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言