Leetcode【781、869】
问题描述：【Math】781. Rabbits in Forest
解题思路：
森林中的兔子。每个兔子都有颜色，其中一些兔子（可能全部）告诉你还有多少其他的兔子和自己有相同的颜色，将它们的回答放在 answers 数组里。返回森林中兔子的最少数量。
通过观察规律可知：
- 同一种颜色的兔子的答案一定是相同的（但是答案相同的兔子不一定就是一种颜色），答案不同的兔子一定颜色不同。
- 对于每组答案相同的兔子，如果它们都属于同一种颜色，那么参与回答的兔子次数一定不会超过它们的答案 +1，如 answers = [4] 和 answers = [4,4,4,4,4] 的结果都是 5。
- 如果每组答案相同的兔子超过它们的答案 + 1，如 answers = [2,2,2,2]，回答 2 的次数 4 超过了 2 + 1 个，那么剩下的那个 2 肯定属于不同的颜色，则结果就为 3 + 3 = 6。
因此，我们可以得出解题算法：先统计每一种回答的次数；对于每一种回答，如果次数小于等于答案 +1，说明这些回答是属于同一种颜色的兔子，则结果累加答案 + 1；否则，其中必有一些属于不同颜色的兔子，因此我们以答案 +1 大小分组（向上取整），再乘以答案 +1 累加到结果中。
举例：answers = [1,2,1,3,2,2,2,2,2,2,3]，ans = 0 记录结果
- 先统计各个回答的次数，得到 dic = {1: 2, 2: 7, 3:2}
- 回答为 1 的次数 2 <= 1 + 1，说明两个 1 是同一种颜色兔子，则 ans += 2 = 2；
- 回答为 2 的次数 7 <= 2 + 1，我们对这七个 2 以大小为 3 分组，得到 [2,2,2]、[2,2,2]、[2]，分为 3 组（向上取整），每一组分别代表一种不同颜色的兔子，因此 ans += 3 * 3 = 11；
- 回答为 3 的次数 2 <= 3 + 1，说明两个 3 是同一种颜色兔子，则 ans += 4 = 15。
- 最终，结果为 ans = 15。
Python3 实现：
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
问题描述：【Hash Table、Sort】869. Reordered Power of 2
解题思路：
这道题是给一个数字，将数字重新排序（不能有前导 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
