专栏首页五分钟学算法图解LeetCode第 279 号问题: 完全平方数

图解LeetCode第 279 号问题: 完全平方数

总第63篇/程序员小吴

LeetCode上第 279 号问题:Perfect Squares

题目描述

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4

示例 2:

输入: n = 13 输出: 2 解释: 13 = 4 + 9

思路解析

使用广度优先搜索方法,将 n 依次减去比 n 小的所有平方数,直至 n = 0 ,此时的层数即为最后的结果。

动画演示

动画演示 Made by 王琛

参考代码

/// @五分钟学算法
class Solution(object):
    def numSquares(self, n):
        Q = collections.deque([n])
        visited, level = set(), 0
        while Q:
            # 按层处理
            for i in range(len(Q)):
                n = Q.popleft()
                # 若n==0,则返回当前层数
                if n == 0: return level
                # 依次减去所有比n小的平方数
                for i in range(1,int(n**0.5)+1):
                    val = n - i**2
                    if val in visited: continue
                    Q.append(val)
                    visited.add(val)
            level = level + 1

代码截图

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:五分钟学算法

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-19

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 10% + 10% = 0.11 ?是 bug 还是 feature ?微软开源的计算器项目告诉你答案!

    近日,关于手机计算器10%+10%=0.11的事情火热,多个品牌的手机未能幸免,基本“阵亡”,同时还包括了windows10的自带标准计算器。你的手机阵亡了吗?

    五分钟学算法
  • 五分钟小知识:布隆过滤器原理和应用分析

    Wikipedia 上面提到布隆过滤器早在 1970 年就被提出来,很难想象在当时那个年代它的主要用途是什么,估计当时提出也是一个数据模型吧。

    五分钟学算法
  • GitHub 标星 3w+,很全面的算法和数据结构知识

    今天分享一个开源项目,里面汇总了程序员技术面试时需要了解的 算法和数据结构知识,并且还提供了相应的代码,目前 GitHub 上标星 35000 star,值得一...

    五分钟学算法
  • 【python-leetcode269-拓扑排序】火星字典

    现有一种使用字母的全新语言,这门语言的字母顺序与英语顺序不同。假设,您并不知道其中字母之间的先后顺序。但是,会收到词典中获得一个 不为空的 单词列表。因为是从词...

    绝命生
  • 如何优雅判断属性值为空

    假设我们现在需要取出 a.b.c,但是并不清楚它们是否都存在,那么代码会写成这样:

    前端达人
  • Spring Boot:定制自己的starter

    在学习Spring Boot的过程中,接触最多的就是starter。可以认为starter是一种服务——使得使用某个功能的开发者不需要关注各种依赖库的处理,不需...

    阿杜
  • 一步步成为linux大神——bash shell中管道和其他命令分隔符的优先级

    一般在bash中,用“|”作为管道,即pipeline,还可以用“;”之类的分隔符连接多个命令。那么下面这个命令的输出是什么呢? date; who |wc 根...

    大神带我来搬砖
  • Spring BeanFactory 容器

    BeanFactory简称bean工厂,是整个spring的核心父类,也是IOC容器或对象的工厂,类是:org.springframework.beans.fa...

    逍遥壮士
  • Python根据字符分组数量判断密码安全强度

    标准库itertools.groupby类用来根据指定的规则对序列中的元素进行分类,官方介绍如下:

    Python小屋屋主
  • Python进阶学习笔记【干货分享】(二)

    print(id(a))a = 4print(id(a))# 重新赋值之后,内存地址发生改变

    商业新知

扫码关注云+社区

领取腾讯云代金券