木又连续日更第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