森林中的兔子。每个兔子都有颜色,其中一些兔子(可能全部)告诉你还有多少其他的兔子和自己有相同的颜色,将它们的回答放在 answers 数组里。返回森林中兔子的最少数量。
通过观察规律可知:
因此,我们可以得出解题算法:先统计每一种回答的次数;对于每一种回答,如果次数小于等于答案 +1,说明这些回答是属于同一种颜色的兔子,则结果累加答案 + 1;否则,其中必有一些属于不同颜色的兔子,因此我们以答案 +1 大小分组(向上取整),再乘以答案 +1 累加到结果中。
举例:answers = [1,2,1,3,2,2,2,2,2,2,3],ans = 0 记录结果
class Solution:
def numRabbits(self, answers: List[int]) -> int:
ans = 0
dic = collections.Counter(answers)
for answer, cnt in dic.items():
least = answer + 1 # 一种颜色的兔子最少数量
if cnt <= least:
ans += least
else: # 同一回答次数超过answer+1,分组
ans += math.ceil(cnt/least) * least
return ans
这道题是给一个数字,将数字重新排序(不能有前导 0),如果排序后的数字是 2 的幂次方,返回 True,否则返回 False。
这道题刚开始的想法就是将数字转化为字符串,然后使用 DFS 回溯法求解所有不同的排列,再判断每个数字是否是 2 的幂次方(为了加快查找速度,可以先将 <= 10 ** 9
的 2 的幂结果存在集合中),但是超时了。改为使用 Python 的 itertools.permutations(S, len(S))
先求出所有排列,再判断每个数,可以勉强 AC,代码如下:
class Solution:
def reorderedPowerOf2(self, N: int) -> bool:
pow2dic = dict()
num = 1
while num <= 10 ** 9:
pow2dic[num] = True
num *= 2
S = str(N)
lens = len(S)
for i in itertools.permutations(S, lens):
if i[0] != '0' and int("".join(i)) in pow2dic:
return True
return False
但是,上述做法显然不是理想的。
方法1(Hash Table):
实际上,我们可以先统计数字 N 中每个数字出现的次数,存在一个字典中,然后,我们计算 2 的幂的结果,也计算 2 的幂的结果中每个数字出现的次数,存在一个字典中。如果两字典相等,说明数字 N 可以以某种排序变成 2 的幂的结果,返回 True,否则,继续计算 2 的幂的结果,直到 2 的幂的结果超过 10 ** 9
结束,返回 False。
Python3 实现:
class Solution:
def reorderedPowerOf2(self, N: int) -> bool:
ori = collections.Counter(str(N))
num = 1
while num < 10 ** 9:
if collections.Counter(str(num)) == ori:
return True
num *= 2
return False
方法2(Sort):
当然,还有一种做法,就是我们可以先对数字 N 各个数字从小到大排序,然后对于 2 的幂的结果,各个数字也进行从小到大排序。如果排序结果相同,说明数字 N 可以以某种排序变成 2 的幂的结果,返回 True,否则,继续计算 2 的幂的结果,直到 2 的幂的结果超过 10 ** 9
结束,返回 False。
Python3 实现:
class Solution:
def reorderedPowerOf2(self, N: int) -> bool:
ori = "".join(sorted(str(N)))
num = 1
while num <= 10 ** 9:
if "".join(sorted(str(num))) == ori:
return True
num *= 2
return False