连续数组分段,map的使用

846. Hand of Straights

Medium

29443FavoriteShare

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

 

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

 

Note:

  1. 1 <= hand.length <= 10000
  2. 0 <= hand[i] <= 10^9
  3. 1 <= W <= hand.length
class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        map<int,int> HashMap;
        for(auto c : hand){
            HashMap[c] ++;
        }
        for(auto i : HashMap){
            if(i.second > 0){
                for(int j = W - 1;j >= 0;j --){
                    HashMap[i.first + j] = HashMap[i.first + j] - HashMap[i.first];
                    if(HashMap[i.first + j] < 0){
                        return 0;
                    }
                }
            }
        }
        return true;
    }
};

 心得:注意即使key没有被压入map容器,也有map[key]=0,也可以对map[key]做运算!

上一篇:codeforces round 99 A~C题


下一篇:基于区块链的防护物资捐赠监管系统