[leetcode] 846. Hand of Straights

[leetcode] 846. Hand of Straights

Description

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 = 3Output: trueExplanation: 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 = 4Output: falseExplanation: Alice's hand can't be rearranged into groups of 4.

Note:

1 <= hand.length <= 100000 <= hand[i] <= 10^91 <= W <= hand.length

分析

题目的意思是：给你一个卡片数组，和W。现在问能不能把卡片数组分为W个小数组，每个小数组都是等差数列，每个小数组里有W个数。

如果数组的大小n不是W的整数倍，则直接返回false。这道题用hashmap来解决，先统计每个数的频率，遍历hash表，每次减去m[it.first]就行了，等于减去W序列中第一个值的count，这个解法很妙，我想不到。注意：map内部本身就是按序存储的（比如红黑树）。在我们插入键值对时，就会按照key的大小顺序进行存储。

我们看看其中一个例子的运算过程： hand = [1,2,3,6,2,3,4,7,8], W = 3 m 1:1 2:2 3:2 4:1 6:1 7:1 8:1 第一次循环：m 1:0 2:1 3:1 4:1 6:1 7:1 8:1 第二次循环：m 1:0 2:0 3:0 4:0 6:1 7:1 8:1 第三次循环：m 1:0 2:0 3:0 4:0 6:0 7:0 8:0 返回true

代码

class Solution {public: bool isNStraightHand(vector& hand, int W) { int n=hand.size(); if(n%W!=0) return false; map m; for(int num:hand){ m[num]++; } for(auto it:m){ if(m[it.first]>0){ for(int i=W-1;i>=0;i--){ if((m[it.first+i]-=m[it.first])<0){ return false; } } } } return true; }};

参考文献

​​846. Hand of Straights​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。