经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
力扣刷题笔记 (1) - HM-7
来源:cnblogs  作者:HM-7  时间:2021/12/31 9:04:15  对本文有异议

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

 

原文链接:http://www.cnblogs.com/LWHCoding/p/15747941.html

 友情链接:直通硅谷  点职佳  北美留学生论坛