论坛 › Python交流 › Python：每日一题 355

zltzlt 发表于 2020-3-19 17:51:48

Python：每日一题 355

本帖最后由 zltzlt 于 2020-3-19 17:55 编辑

今天的题目：

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

示例 1：

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

输入：3
输出：False

{:10_298:}欢迎大家一起答题！{:10_298:}

qiuyouzhi 发表于 2020-3-19 17:57:22

本帖最后由 qiuyouzhi 于 2020-3-19 18:07 编辑

def f355(n):
    for i in range(n+1):
      for j in range(n+1):
            if pow(i,2) + pow(j,2) == n:
                return True
    return False

print(f355(8))
改用BIF

zltzlt 发表于 2020-3-19 17:58:15

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

定会超时，待会再改改

输入 4 就有错{:10_277:}

qiuyouzhi 发表于 2020-3-19 17:59:23

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

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

zltzlt 发表于 2020-3-19 18:00:39

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

4 = 02 + 22

qiuyouzhi 发表于 2020-3-19 18:01:21

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

能不能给几个测试用例，防止再次{:10_269:}

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

import math
num = eval(input())

flag=0
for i in range(0,int(pow(num,1/2))+1):
      for j in range(0,int(pow(num,1/2))+1):
                if pow(i,2)+pow(j,2)==num:
                        flag = 1
                        print("True")
                        break
      if flag==1:
                break
if not flag:
      print("False")

zltzlt 发表于 2020-3-19 18:03:20

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

8 和 1 返回 True

zltzlt 发表于 2020-3-19 18:05:43

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


输入 1000000000 超时

TJBEST 发表于 2020-3-19 18:20:22

本帖最后由 TJBEST 于 2020-3-19 21:17 编辑

import math
def fun355(c):
    def isSquare(num):#判断平方数
      temp = math.floor((num**(1/2)))
      if temp * temp != num:
            return False
      else:
            return True
    def isHuZhi(a,b):#判断互质 a > b
      while b:
            a,b = b,a%b
      if a == 1:
            return True
      else:
            return False
    def findHuZhi(a):#a > 2寻找所有比a小的与a互质的数 返回列表
      result = []
      for index in range(1,a):
            if isHuZhi(a,index):
                result.append(index)
      return result
   
    if isSquare(c):
      return True
    gate = math.floor(((c-1)**(1/2)))
    for index in range(1,gate+1):
      temp = 1 + index ** 2
      if c % temp == 0 and isSquare(c//temp):
            return True
    other = (-1+(2*c-1)**(1/2))/2
    gate = math.floor(other)
    for index in range(2,gate+1):
      HuZhiArr = findHuZhi(index)
      for each in HuZhiArr:
            other = (-each + (c-index)**(1/2))/index
            innergate = math.floor(other)
            for k in range(1,innergate+1):
                innerNum = k * index + each
                temp = (innerNum**2)+(index**2)
                if c % temp == 0 and isSquare(c//temp):
                  return True
    return False

fan1993423 发表于 2020-3-19 18:35:17

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

永恒的蓝色梦想 发表于 2020-3-19 18:37:57

本帖最后由 永恒的蓝色梦想 于 2020-3-19 19:12 编辑

我的代码：from math import sqrt,ceil

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
      if not sqrt(c)%1:
            return True
      for i in range(1,ceil(sqrt(c))):
            if not sqrt(c-i*i)%1:
                return True
      return False

力扣大神解法：(128ms)from math import sqrt,floor

class Solution:
    def judgeSquareSum(self, c):
      left=0
      right=floor(sqrt(c))

      while left<=right:
            total=left*left+right*right
            
            if total>c:
                right-=1
            elif total<c:
                left+=1
            else:
                return True

      return False

一个账号 发表于 2020-3-19 18:44:30

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

wuqramy 发表于 2020-3-19 18:45:00

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

1 = 0**2 + 1**2

kinkon 发表于 2020-3-19 18:50:05

本帖最后由 kinkon 于 2020-3-20 08:46 编辑

双针法
def fun355(c):
    r = int(c**0.5)
    if c - r <= 1:
      return True
    l = int((c - r*r)**0.5)
    for i in range(l, r+1):
      num = i*i + r*r         
      if num == c:
            return True
      elif num > c:
            r -= 1
    return False

如果上面不对，试试下面的
def p355(c):
    m = int(c**0.5)
    if c - m <= 1:
      return True
    while m:   
      if c == int((c - m*m)**0.5)**2 + m*m:
            return True
      m -= 1
    return False

fan1993423 发表于 2020-3-19 18:51:47

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

fan1993423 发表于 2020-3-19 18:54:14

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

输入8就错了{:10_256:}

kinkon 发表于 2020-3-19 18:55:58

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

改了

fan1993423 发表于 2020-3-19 18:57:27

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

还是错的，8是True

mdphd 发表于 2020-3-19 18:58:55

本帖最后由 mdphd 于 2020-3-19 19:53 编辑

import math
def f355(x):
    a = int(math.sqrt(x / 2))
    def f(m, n):
      i = m
      c = 0
      while i <= a:
            if int(math.sqrt(x - i ** 2)) != math.sqrt(x - i ** 2):
                i += n
            else:
                print('True')
                c = 1
                break
      if c == 0:
            print("False")
    if x % 4 == 0:
      f(0, 2)
    if x % 4 == 1:
      f(0, 1)
    if x % 4 == 2:
      f(1, 2)
    if x % 4 == 3:
      print("False")

查看完整版本: Python：每日一题 355