欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【leetcode】633. Sum of Square Numbers(Python & C++)

程序员文章站 2022-04-12 21:30:34
633. Sum of Square Numbers 633.1 题目描述: Given a non-negative integer c, your task is to d...

633. Sum of Square Numbers

633.1 题目描述:

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:

Input: 5
Output: True

Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

633.2 解题思路:

思路一:首先获取第一个平发后不大于c的平方根i = sqrt(c),以此为起点,以i*i 大于等于c/2为终点遍历。获取t=c-i*i,然后,获取第一个平方后不大于t的平方根j=sqrt(t),然后以j为起点,以j小于等于=i为终点,遍历。如果,t==j*j,则返回true,如果t小于j*j,则break。内外遍历都结束,则返回false。

思路二:同思路一相同。不过进行优化,外循环相同,不同的是去掉内训化,直接判断j*j与t是否相等,相等则返回true。遍历结束后,返回false。

思路三:利用set。将平方后不大于c的所有平方根都insert进s,然后遍历平方根i,如果c-i*i在set中,则返回true。遍历结束,返回false。

思路四:设置两个指针同时遍历。a=0,b=sqrt(c)。循环条件,a小于等于b,如果a*a+b*b==c,则返回true,如果大于,则b–;如果小于,则a++。遍历结束,返回false。

633.3 C++代码:

1、思路一代码(6ms):

class Solution116 {
public:
    bool judgeSquareSum(int c) {
        int s = int(sqrt(c));
        if (s*s == c)
            return true;
        for (int i = s; i*i >= c/2;i--)
        {
            int a1 = c - i*i;
            int e = int(sqrt(a1));
            for (int j = e; j <= s;j++)
            {
                if (a1 == j*j)
                    return true;
                else if (a1

2、思路二代码(3ms)

class Solution116_1 {
public:
    bool judgeSquareSum(int c) {
        for (int i = int(sqrt(c)); i*i >= c/2; i--)
        {
            if (i*i == c)
                return true;
            int s = c - i*i;
            int j = int(sqrt(s));
            if (j*j == s)
                return true;
        }
        return false;       
    }
};

3、思路三代码(262ms):

class Solution116_2 {
public:
    bool judgeSquareSum(int c) {
        sets;
        for (int i = 0; i <= sqrt(c);i++)
        {
            s.insert(i*i);
            if (s.count(c - i*i))
                return true;
        }
        return false;
    }
};

4、思路四代码(6ms)

class Solution116_3 {
public:
    bool judgeSquareSum(int c) {
        int a = 0;
        int b = sqrt(c);
        while (a<=b)
        {
            if (a*a + b*b == c)
                return true;
            else if (a*a + b*b < c)
                a++;
            else
                b--;
        }
        return false;
    }
};

633.4 Python代码:

2、思路二代码(132ms)

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        i=int(math.sqrt(c))
        while i*i>=c/2:
            t=c-i*i
            j=int(math.sqrt(t))
            if j*j==t:
                return True
            i-=1
        return False        

4、思路四代码(152ms)

class Solution1(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        a=0
        b=int(math.sqrt(c))
        while a<=b:
            if a*a+b*b==c:
                return True
            elif a*a+b*b
*j)>