平方和

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def square(self , c: int) -> bool:
        # write code here
        if c==1:
            return False
        for a in range(1,int(c**0.5)+1):
            b = c - a**2
            # 检查b是否为平方数
            if b**0.5 == int(b**0.5):
                return True
        return False

bool square(int c ) 
{
    int i=(int)sqrt(c);
    int j= 0;
    for (; i >= 1; i--)
    {
        j = (int) sqrt(c - i * i);
        if ((c == i * i + j * j) && (j != 0))
        {
            return true;
            break;
        }
        
    }
        return false;
}

class Solution:
    def square(self , c: int) -> bool:
        # write code here
        if c==1:
            return False
        for a in range(1,int(c**0.5)+1):
            b = c - a**2
            # 检查b是否为平方数
            if b**0.5 == int(b**0.5):
                return True
        return False

设a，b分别为1和c的平方根，然后进行二分搜索
时间复杂度:
空间复杂度: 

import math
class Solution:
    def square(self, c):
        # write code here
        a = 1
        b = int(math.sqrt(c)) + 1

        while a <= b:
            curr = a ** 2 + b ** 2

            if curr == c:
                return True
            if curr < c:
                a += 1
            if curr > c:
                b -= 1

        return False

#include <cmath>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param c int整型 
     * @return bool布尔型
     */
    bool square(int c) {
        // write code here
        int m=sqrt(INT_MAX);
        int i,j;
        for(i=1;i<m;i++){
            for(j=1;j<m;j++){
                if(i*i+j*j==c){
                    return true;
                }
                if(i*i+j*j>c){
                    break;
                }
                
            }
        }
        return false;
    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param c int整型 
     * @return bool布尔型
     */
    public boolean square (int c) {
        // write code here
        long num=c;
        for(long i=1;i<=10000;i++){
            if(Math.pow(i,2)>c){
                break;
            }
            for(long j=1;j<=10000;j++){
                if(Math.pow(i,2)+Math.pow(j,2)==c){
                    return true;
                }
                if(Math.pow(j,2)>c){
                    break;
                }
            }
        }
        return false;
    }
}

bool square(int c ) {
    // write code here
    for(int i=1; i<=c/2; i++)
    {
        if(i*i > c)
            break;
        for(int j=1; j<=c/2; j++)
        {
            if(j*j > c)
                break;
            if(c == i*i+j*j)
                return true;
        }
    }
    return false;
}

import java.util.*;


public class Solution {
    public boolean square (int c) {
        if (c == 1) return false;
        int a = 1;
        while(a * a <= c) {
            a++;
        }
        a--;
        for (int i = 1, j = a; i <= j; ) {
            int sum = i * i + j * j;
            if (sum > c) j--;
            else if (sum < c) i++;
            else return true;
        }
        return false;
    }
}

class Solution:
    def square(self , c: int) -> bool:
        # write code here
        s = int(c**0.5)
        for i in range(1, s+1):
            # 整数
            if int((c-i**2)**0.5) == (c-i**2)**0.5:
                return True if c != 1 else False
        return False

# -*- coding: utf-8 -*-

import math


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param c int整型
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/6eade96172be4c8ba492747156481b9b?tpId=196&tqId=40562&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        枚举x，取值范围[1, sqrt(c)]，m = c - x * x，如果y^2 == m，y为整数，那么说明有解，返回True
    复杂度：
        时间复杂度：O(n), n = sqrt(c)
        空间复杂度：O(1)
    """

    def square(self, c):
        # write code here
        sqrtC = int(math.sqrt(c))

        for x in range(1, sqrtC + 1):
            m = c - x * x
            if m == 0:
                break
            y = int(math.sqrt(m))
            if y * y == m:
                # print x, y
                return True

        return False


if __name__ == "__main__":
    sol = Solution()

    # c = 5

    # c = 25

    c = 24

    res = sol.square(c)

    print res

bool square(int c ) {
    int i;
    for (i = 1; i < sqrt(c); i++) {
          int temp = c - i * i;   
          int k = sqrt(temp);   
           //用整型接收某个数的平方根或近似平方根
          if (k * k == temp)    
             //若这个整型平方后可以还原成求平方根之前的数，
             //说明是完全平方
                return true;
          }
    return false;
    }