leetcode 846.Hand of Straights

对于一个数组中的数分为W组且在每一组内的数是连续存在的。

考虑使用map映射来记录每个数的个数的，并且对于数组中的数进行从小到大的排列的。同时每次需要更新最开始的那个起始数的，可能是以及出现的也可能是没有出现过的，这些都是需要考虑到的。

class Solution {

public:

    bool isNStraightHand(vector<int>& hand, int W) {

        int n=hand.size();

        if(n%W!=) return false;

        map<int,int> m;

        for(int i=;i<n;i++){

            if(!m.count(hand[i])){

                m[hand[i]]=;

            }else{

                m[hand[i]]++;

            }

        }

        sort(hand.begin(),hand.end());

        //int cnt=0;

        int start=hand[];

        for(int i=;i<n/W;i++){

            //int start=hand[cnt];

            for(int j=;j<W;j++){

                cout<<start+j<<endl;

                if(!m.count(start+j))

                    return false;

                m[start+j]--;

                if(m[start+j]<)

                    return false;

            }

            int flag=; // 考虑如果所有的数都被用完的话就需要取得新的数的

            for(int j=;j<W;j++){

                if(m[start+j]!=){

                    start=start+j;

                    flag=;

                    break;

                }

            }

            if(!flag){

                start=hand[(i+)*W];

            }

        }

        return true;

    }

};

其实是可以不用排序的，因为map本身就会按照关键字进行排序的，并且需要满足其数量相等的即可的。

class Solution {

public:

    bool isNStraightHand(vector<int>& hand, int W) {

        int n=hand.size();

        if(n%W!=) return false;

        map<int, int> m;

        for(int i=;i<n;i++) m[hand[i]]++;

        map<int,int>::iterator it;

        for(it=m.begin();it!=m.end();it++){

            int n=it->second;

            if(n!=){

                for(int i=it->first; i<it->first+W; i++){

                    if(!m.count(i) || m[i]<n)

                        return false;

                    m[i]-=n;

                }

            }

        }

        return true;

    }

};

巴特西

leetcode 846.Hand of Straights

最新文章

热门文章