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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 只有想不到,「99」种扩展Jupyter功能的好方法

    当有人说:「你可以用 Jupyter 扩展解决这个问题」,他们可能没有说清楚是什么样的扩展。Jupyter 生态系统是非常模块化且具有扩展性的,所以有很多种扩展...

    用户2769421
  • Python String 方法详解一(史上最全)

    官网文档地址:https://docs.python.org/3/library/stdtypes.html#string-methods 官网文档里的所有S...

    软测小生
  • Python——关于path的坑

    学习语言,基本都会碰到关于路径拼接的语法,对于业余选手来讲,可能会比较困惑,包括我在内,直到某一天才顿悟…… 雷爆了。。

    Ed_Frey
  • 柳暗花明又一村——Python前序

    今天再推荐一个新的工具,PyCharm,虽然它是一款收费的开发工具,而且是英文版的,但是着实好用,比上一篇的anaconda更好用。

    Ed_Frey
  • Python处理图片九宫格,炫酷朋友圈

    在日常的生活中,大家偶尔会看到朋友圈发的照片由一张被切成九张的效果,有时由一张照片被切成九张照片所带来的视觉盛宴是不一样的!

    用户2769421
  • Python—字符串常用的格式化方法

    其实如果要通读字符串的所有方法,只需要在pycharm中输入st.就会自动弹出字符串的方法列表,挨个试过去就知道了

    Ed_Frey
  • Python——关于排序算法(快速排序法)

    最近一直在写排序的算法,可能讲到合并排序法,很多人就会有点晕乎了,还是要多多研究练习,才能得法。包括我也是,看教程的时候感觉懂了,开始写的时候感觉都忘记了,再复...

    Ed_Frey
  • Python语言快速上手

    最近在学习Python,后面搞机器人项目需要用到,所以要快速上手,我使用的是PyCharm这个IDE,看起来就舒服,学习起来就有劲啦,作为一名有工作经验...

    morixinguan
  • docker学习2-快速搭建centos7-python3.6环境

    当我们在一台电脑上搭建了python3.6的环境,下次换了个电脑,或者换成linux的系统了,又得重新搭建一次,设置环境变量、下载pip等操作。 好不容易安装好...

    上海-悠悠
  • Python——神奇的闭包(装饰器的应用)

    Ed_Frey

扫码关注云+社区

领取腾讯云代金券