专栏首页木又AI帮【leetcode刷题】T208-平方数之和

【leetcode刷题】T208-平方数之和

木又连续日更第80天(80/100)


木又的第208篇leetcode解题报告

数学类型第24篇解题报告

leetcode第633题:平方数之和

https://leetcode-cn.com/problems/sum-of-square-numbers


【题目】

给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a^2 + b^2 = c。

示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

示例2:
输入: 3
输出: False

【思路】

i从0到sqrt(num)+1,判断i ** 2 + sqrt(num-i*i) ** 2是否等于num
另一个想法,生成0到sqrt(num)+1所有数的平方,那么问题就变成了two-sum:在数组中,找到两个元素,使之和为num

【代码】

python版本

暴力破解

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        for i in range(int(math.sqrt(c)) + 1):
            tmp1 = i * i
            tmp2 = int(round(math.sqrt(c - tmp1))) ** 2
            if tmp1 + tmp2 == c:
                return True
        return False

转换为two-sum类型

class Solution(object):
    def judgeSquareSum(self, c):
        ls = [i ** 2 for i in range(int(math.sqrt(c)) + 1)]
        a, b = 0, len(ls) - 1
        while a <= b:
            if ls[a] + ls[b] == c:
                return True
            if ls[a] + ls[b] > c:
                b -= 1
            else:
                a += 1
        return False

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

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

原始发表时间:2019-12-06

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T193-各位相加

    https://leetcode-cn.com/problems/add-digits/

    木又AI帮
  • 【leetcode刷题】T55-强整数

    给定两个正整数 x 和 y,如果某一整数等于 x^i + y^j,其中整数 i >= 0 且 j >= 0,那么我们认为该整数是一个强整数。

    木又AI帮
  • 【leetcode刷题】T44-两个数组的交集 II

    Given two arrays, write a function to compute their intersection.

    木又AI帮
  • [C语言]N阶勒让德公式

    雨落凋殇
  • 装载问题——BFS(队列式)分支界限法

    AI那点小事
  • Java工具集-数学(阶乘函数)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • BZOJ 3932: [CQOI2015]任务查询系统(主席树)

    attack
  • 力扣79——单词搜索

    单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    健程之道
  • C#版 - ZJNUoj1259 - 幸运数字——中高级 - 题解

    Time Limit: 1000 ms       Memory Limit: 65536 KB Total Submissions: 116    Ac...

    Enjoy233
  • 【leetcode算法-搜索插入位置】

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    用户5640963

扫码关注云+社区

领取腾讯云代金券