-
发表于 2024.05.28
-
类似于题目2007,使用贪心法从小到大处理数字。但该题涉及到负数,因此,排序的逻辑需要改为按绝对值递增处理。先使用哈希表
cnt_map
对数字计数。然后按绝对值从小到大遍历数字num
,尝试抽取cnt_map[num]
次组(num, num * 2)
,如果数字num * 2
的计数小于cnt_map[num]
,则无法完成题目要求,直至所有的牌处理完毕。对于特殊情况num == 0
,需要特殊处理,即判断cnt_map[0]
是否为偶数。class Solution: def canReorderDoubled(self, arr: List[int]) -> bool: cnt_map = {} for num in arr: cnt_map[num] = cnt_map.get(num, 0) + 1 for num in sorted(cnt_map.keys(), key=lambda _item: abs(_item)): if num == 0: if cnt_map[0] % 2: return False continue if cnt_map[num] == 0: continue double = num * 2 if double not in cnt_map or cnt_map[double] < cnt_map[num]: return False cnt_map[double] -= cnt_map[num] return True
- LC 题目链接
-