2021-12-30
LeetCode T846
希望自己可以堅持寫博客的習慣??
題目描述：
Alice 手中有一把牌，她想要重新排列這些牌，分成若干組，使每一組的牌數都是 groupSize ，并且由 groupSize 張連續的牌組成，給你一個整數陣列 hand 其中 hand[i] 是寫在第 i 張牌，和一個整數 groupSize，如果她可能重新排列這些牌，回傳 true；否則，回傳 false，
Input:
hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output:
true
初讀此題，想都沒想直接暴力求解 暴力固然簡單，但只適用于不重復數字且不相隔的情況，若遇到 [1,1,2,2,3,3] 則出錯，
class Solution { public: bool isNStraightHand(vector<int>& hand, int groupSize) { if(hand.size() % groupSize != 0) return false; sort(hand.begin(), hand.end()); bool ans = true; for(int j = 0; j < hand.size(); j += groupSize) { ans = pd(j, groupSize, hand); }//劃分多組進入判斷 return ans; } bool pd(int start, int groupSize, vector<int>& hand) { for(int i = start + 1; i < start + groupSize; i++) { if(hand[i - 1] + 1 != hand[i]) { return false; }//逐個判斷是否符合情況 } return true; } };
為了解決這種問題，便去想第二種：用取余判斷，貌似精簡，但遇到 [8,10,12] 這種隔數的情況會誤判，
class Solution { public: bool isNStraightHand(vector<int>& hand, int groupSize) { if(hand.size() % groupSize != 0) return false; sort(hand.begin(), hand.end()); vector<int> res(groupSize); for(int i: hand) { res[i % groupSize]++; }//將重復部分存入新陣列 for(int i = 1; i < groupSize; i++) { if(res[i - 1] != res[i]) return false; }//若連續則各位置牌數應該相等 return true; } };
最后相當于兩種結合求解，采用unordered_map這一高科技??
class Solution { public: bool isNStraightHand(vector<int>& hand, int groupSize) { if(hand.size() % groupSize != 0) return false; if(groupSize == 1) return true; unordered_map<int, int> res; sort(hand.begin(), hand.end()); for(int i: hand) { res[i]++; }//在每個Key值記憶體入該Key出現的次數 for(int t: hand) { if(res[t] == 0) continue; for(int i = 0; i < groupSize; i++) { if(res[t + i]-- <= 0) return false; }//進行判斷統計出次數 } return true; } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/398374.html
標籤：C++