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:
初读此题,想都没想直接暴力求解 暴力固然简单,但只适用于不重复数字且不相隔的情况,若遇到 [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;
}
};