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;
- }
- };