[已解决]Python：每日一题 355

zltzlt

今天的题目：

给定一个非负整数 c，判断是否存在两个整数 a 和 b，使得 a² + b² = c。

示例 1：

输入：5
输出：True
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：3
输出：False

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

flamezyy

2020-3-19 21:47:36

1. import math as m
   
2. def f355(integer):
   
3.     sqrt = m.sqrt(integer)
   
4.     sqrt_int = int(sqrt)
   
5.     if sqrt % 1:
   
6.         low_lim = int(m.sqrt(integer/2))
   
7.         for i in reversed(range(low_lim,sqrt_int+1)):
   
8.             rem = m.sqrt(integer - i*i)
   
9.             if rem % 1:
   
10.                 continue
    
11.             else:
    
12.                 return True
    
13.         else:
    
14.             return False
    
15.     else:
    
16.         return True

复制代码

跳转到最佳答案楼层

qiuyouzhi

1. def f355(n):
   
2.     for i in range(n+1):
   
3.         for j in range(n+1):
   
4.             if pow(i,2) + pow(j,2) == n:
   
5.                 return True
   
6.     return False
   
7. 
   
8. print(f355(8))

复制代码

改用BIF

zltzlt

qiuyouzhi 发表于 2020-3-19 17:57
闲来无事先瞎写一个：

定会超时，待会再改改

输入 4 就有错

qiuyouzhi

zltzlt 发表于 2020-3-19 17:58
输入 4 就有错

！我滴妈
瞎写了一个居然。。。。
我去改改

zltzlt

qiuyouzhi 发表于 2020-3-19 17:59
！我滴妈
瞎写了一个居然。。。。
我去改改

4 = 0² + 2²

qiuyouzhi

zltzlt 发表于 2020-3-19 17:58
输入 4 就有错

能不能给几个测试用例，防止再次

最后的魁拔

1. import math
   
2. num = eval(input())
   
3. 
   
4. flag=0
   
5. for i in range(0,int(pow(num,1/2))+1):
   
6.         for j in range(0,int(pow(num,1/2))+1):
   
7.                 if pow(i,2)+pow(j,2)==num:
   
8.                         flag = 1
   
9.                         print("True")
   
10.                         break
    
11.         if flag==1:
    
12.                 break
    
13. if not flag:
    
14.         print("False")

复制代码

zltzlt

qiuyouzhi 发表于 2020-3-19 18:01
能不能给几个测试用例，防止再次

8 和 1 返回 True

zltzlt

最后的魁拔 发表于 2020-3-19 18:02

输入 1000000000 超时

TJBEST

1. import math
   
2. def fun355(c):
   
3.     def isSquare(num):#判断平方数
   
4.         temp = math.floor((num**(1/2)))
   
5.         if temp * temp != num:
   
6.             return False
   
7.         else:
   
8.             return True
   
9.     def isHuZhi(a,b):#判断互质 a > b
   
10.         while b:
    
11.             a,b = b,a%b
    
12.         if a == 1:
    
13.             return True
    
14.         else:
    
15.             return False
    
16.     def findHuZhi(a):#a > 2寻找所有比a小的与a互质的数 返回列表
    
17.         result = []
    
18.         for index in range(1,a):
    
19.             if isHuZhi(a,index):
    
20.                 result.append(index)
    
21.         return result
    
22.    
    
23.     if isSquare(c):
    
24.         return True  
    
25.     gate = math.floor(((c-1)**(1/2)))
    
26.     for index in range(1,gate+1):
    
27.         temp = 1 + index ** 2
    
28.         if c % temp == 0 and isSquare(c//temp):
    
29.             return True
    
30.     other = (-1+(2*c-1)**(1/2))/2
    
31.     gate = math.floor(other)
    
32.     for index in range(2,gate+1):
    
33.         HuZhiArr = findHuZhi(index)
    
34.         for each in HuZhiArr:
    
35.             other = (-each + (c-index)**(1/2))/index
    
36.             innergate = math.floor(other)
    
37.             for k in range(1,innergate+1):
    
38.                 innerNum = k * index + each
    
39.                 temp = (innerNum**2)+(index**2)
    
40.                 if c % temp == 0 and isSquare(c//temp):
    
41.                     return True
    
42.     return False

复制代码

fan1993423

这两个整数可以相同是吧，8的话是不是2**2+2**2这样的

永恒的蓝色梦想

我的代码：

1. from math import sqrt,ceil
   
2. 
   
3. class Solution:
   
4.     def judgeSquareSum(self, c: int) -> bool:
   
5.         if not sqrt(c)%1:
   
6.             return True
   
7.         for i in range(1,ceil(sqrt(c))):
   
8.             if not sqrt(c-i*i)%1:
   
9.                 return True
   
10.         return False

复制代码

力扣大神解法：(128ms)

1. from math import sqrt,floor
   
2. 
   
3. class Solution:
   
4.     def judgeSquareSum(self, c):
   
5.         left=0
   
6.         right=floor(sqrt(c))
   
7. 
   
8.         while left<=right:
   
9.             total=left*left+right*right
   
10.             
    
11.             if total>c:
    
12.                 right-=1
    
13.             elif total<c:
    
14.                 left+=1
    
15.             else:
    
16.                 return True
    
17. 
    
18.         return False

复制代码

一个账号

1. import math
   
2. def func(c):
   
3.     for a in range(c+1):
   
4.         for b in range(c+1):
   
5.            if math.pow(a, 2) + math.pow(b, 2) == c:
   
6.                return True
   
7.     return False

复制代码

wuqramy

zltzlt 发表于 2020-3-19 18:03
8 和 1 返回 True

1 = 0**2 + 1**2

kinkon

双针法

1. def fun355(c):
   
2.     r = int(c**0.5)
   
3.     if c - r <= 1:
   
4.         return True
   
5.     l = int((c - r*r)**0.5)
   
6.     for i in range(l, r+1):
   
7.         num = i*i + r*r           
   
8.         if num == c:
   
9.             return True
   
10.         elif num > c:
    
11.             r -= 1
    
12.     return False

复制代码

如果上面不对，试试下面的

1. def p355(c):
   
2.     m = int(c**0.5)
   
3.     if c - m <= 1:
   
4.         return True
   
5.     while m:   
   
6.         if c == int((c - m*m)**0.5)**2 + m*m:
   
7.             return True
   
8.         m -= 1
   
9.     return False

复制代码

fan1993423

1. def fun355(c):
   
2.     for i in range(int(c**0.5)+1):
   
3.         if not (c-i**2)**0.5%1:
   
4.             return True
   
5.     return False

复制代码

fan1993423

kinkon 发表于 2020-3-19 18:50
一行应该够了

输入8就错了

kinkon

fan1993423 发表于 2020-3-19 18:54
输入8就错了

改了

fan1993423

kinkon 发表于 2020-3-19 18:55
改了

还是错的，8是True

mdphd

1. import math
   
2. def f355(x):
   
3.     a = int(math.sqrt(x / 2))
   
4.     def f(m, n):
   
5.         i = m
   
6.         c = 0
   
7.         while i <= a:
   
8.             if int(math.sqrt(x - i ** 2)) != math.sqrt(x - i ** 2):
   
9.                 i += n
   
10.             else:
    
11.                 print('True')
    
12.                 c = 1
    
13.                 break
    
14.         if c == 0:
    
15.             print("False")
    
16.     if x % 4 == 0:
    
17.         f(0, 2)
    
18.     if x % 4 == 1:
    
19.         f(0, 1)
    
20.     if x % 4 == 2:
    
21.         f(1, 2)
    
22.     if x % 4 == 3:
    
23.         print("False")

复制代码