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