# C#版 - Leetcode 633. 平方数之和 - 题解

### C#版 - Leetcode 633. 平方数之和 - 题解

Leetcode 633 - Sum of square number

## 题目描述

输入: 5

输入: 3

Input: 5 2 100

public class Solution
{
public bool JudgeSquareSum(int c)
{
for (int i = 0; c - 2 * i * i >= 0; i++)
{
double diff = c - i*i;
if ((int)(Math.Ceiling(Math.Sqrt(diff))) == (int)(Math.Floor(Math.Sqrt(diff))))
return true;
}

return false;
}
}

Rank:

You are here! Your runtime beats 56.14% of csharp submissions. 优化1：

public class Solution
{
public bool JudgeSquareSum(int c)
{
for (int i = 0; c - 2 * i * i >= 0; i++)
{
int diff = c - i*i;
if (IsPerfectSquare(diff))
return true;
}

return false;
}
private bool IsPerfectSquare(int num)
{
double sq1 = Math.Sqrt(num);
int sq2 = (int)Math.Sqrt(num);
if (Math.Abs(sq1 - (double)sq2) < 10e-10)
return true;
return false;
}
}

Rank: You are here! Your runtime beats 85.96% of csharp submissions.

public class Solution
{
public bool JudgeSquareSum(int c)
{
for (int i = 0; i <= c && c - i * i >= 0; i++)
{
int diff = c - i*i;
if (IsPerfectSquare(diff))
return true;
}

return false;
}
public bool IsPerfectSquare(int num)
{
if ((0x0213 & (1 << (num & 15))) != 0)
{
int t = (int)Math.Floor(Math.Sqrt((double)num) + 0.5);
return t * t == num;
}
return false;
}
}

Rank: You are here! Your runtime beats 85.96% of csharp submissions.

public class Solution
{
public bool JudgeSquareSum(int c)
{
for (int i = 0; c - i * i >= 0; i++)
{
long diff = c - i*i;
if (IsSquareFast(diff))
return true;
}

return false;
}

bool IsSquareFast(long n)
{
if ((0x2030213 & (1 << (int)(n & 31))) > 0)
{
long t = (long)Math.Round(Math.Sqrt((double)n));
bool result = t * t == n;
return result;
}
return false;
}
}

Rank: You are here! Your runtime beats 85.96% of csharp submissions.

public class Solution
{
public bool JudgeSquareSum(int c)
{
for (int i = 0; c - 2 * i * i >= 0; i++)
{
double diff = c - i*i;
if (Math.Abs(Math.Sqrt(diff) % 1) < 0.000001)
return true;
}

return false;
}
}

Reference:

Fast way to test whether a number is a square https://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/

0 条评论

• ### C#版 - Leetcode 593. 有效的正方形 - 题解

在线提交: https://leetcode.com/problems/valid-square/

• ### 滴滴2016.09.06校招 在线笔试 - 2道编程题

一个数组有N个元素，求连续子数组的最大和。例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为3。

• ### C#刷遍Leetcode面试题系列连载（4）: No.633 - 平方数之和

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 欧拉计划 Problem10

题目； 素数的和 所有小于10的素数的和是2 + 3 + 5 + 7 = 17。

• ### C#版 - Leetcode 593. 有效的正方形 - 题解

在线提交: https://leetcode.com/problems/valid-square/

• ### ECJTUACM16 Winter vacation training #4 题解&源码

https://vjudge.net/contest/149692#overview 这周一VJ比赛，题解&源码已完成！ A.....................

• ### 扩展随机数

随机数生成 （1）可使用random等系统函数，构造函rand 15 ：在[1,5]范围，均匀分布随机函数  （2）不可使用random，仅仅基于rand15构...

• ### 1089 狼人杀-简单版 (20 分)

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### 【leetcode刷题】T159-爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/