Leetcode 846 Hand of Straights

发表于 |

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 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

分析：
将一组数据分为若干组，每组大小都是W，并且是W个连续数(我一开始看错题目了，以为是分成W组，并每组都是W大小，搞得提交错了好几次)

思路：
先判断能不能均分，不能直接False，然后用字典将数组存起来，每次用最小的数开始分析，判断连续W个数是不是都存在，直至字典为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def isNStraightHand(self, hand, W):
        """
        :type hand: List[int]
        :type W: int
        :rtype: bool
        """
        # 判断是否能均分
        n = len(hand)
        if n % W != 0: return False

        d = collections.Counter(hand)
        while d:
            m = min(d.keys())
            for i in range(W):
                if not d[m+i]: return False
                d[m+i] -= 1
                # 如果数字用光了则删除key值
                if d[m+i] == 0: del d[m+i]
        return True

65 / 65 test cases passed.
difficulty: medium
Runtime: 1156 ms

因为每次都要取最小值，其实这个复杂度达到了n^2/W,也是测试数据给面子吧，讲道理这个复杂度应该是不行的
当然要修改很简单，我们直接对d.keys()从小到大遍历，如果d[i]>0我们才进行操作，否则跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isNStraightHand(hand,W):
	n = len(hand)
	if n % W != 0: return False

	d = collections.Counter(hand)
	for e in sorted(d.keys()):
		if d[e] > 0:
			# 这里倒序遍历是因为要保证d[e]的值最后才变
			for step in range(W)[::-1]:
				d[e+step] -= d[e]
				if d[e+step] < 0: return False
	return True

65 / 65 test cases passed.
difficulty: medium
Runtime: 194 ms