加个“星标★”,每日 7:15,好文必达! ![](http://image109.360doc.com/DownloadImg/2020/02/0217/181660996_1_20200202053428767)
前文传送门: C# 刷遍 Leetcode 面试题系列连载(1) - 入门与工具简介 C#刷遍Leetcode面试题系列连载(2): No.38 - 报数 C#刷遍Leetcode面试题系列连载(3): No.728 - 自除数 上篇文章中一道数学问题 - 自除数,今天我们接着分析 LeetCode 中的另一道数学题吧~ ![](http://image109.360doc.com/DownloadImg/2020/02/0217/181660996_2_20200202053428860_wm)
今天要给大家分析的面试题是 LeetCode 上第 633 号问题, Leetcode 633 - 平方数之和 https:///problems/sum-of-square-numbers/ 题目描述给定一个非负整数c ,你要判断是否存在两个整数a和 b,使得 。 示例1: 输入: 5
输出: True
解释: 1* 1+ 2* 2= 5
示例2: 输入: 3
输出: False
Input: 5
2
100
Expected answer: true
true
true
相关话题 相似题目
解题思路: 方法1: 遍历 做一次循环,用目标和减去循环变量的平方,如果剩下的部分依然是完全平方的情形存在,就返回true;否则返回false。 假定 ,根据数据的对称性,循环变量 i 只需取到 即可覆盖所有情形. 时间复杂度: O(n) 方法2: 双指针法 左指针 l=0,右指针 r = √C,夹逼条件是 ll + rr = C 感谢 博客园园友 msp的昌伟哥哥 的补充和指正~ 时间复杂度: log(n) 方法1 已AC代码: 最初版本: 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: 执行用时: 56ms , 在所有 csharp 提交中击败了 68.18% 的用户. 优化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:
执行用时: 52ms , 在所有 csharp 提交中击败了 90.91% 的用户. 优化2(根据文末参考资料[1]中MPUCoder 的回答改写,16进制下mod16减少比较次数): 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)
{
//TRUE only if n mod 16 is 0,1,4,or 9
if ((0x0213 & (1 << (num & 15))) != 0)
{
int t = (int)Math.Floor(Math.Sqrt((double)num) + 0.5);
return t * t == num;
}
return false;
}
}
Rank: 执行用时: 44ms , 在所有 csharp 提交中击败了 100.00% 的用户. ![](http://image109.360doc.com/DownloadImg/2020/02/0217/181660996_6_20200202053429376_wm)
优化3(根据文末参考资料[1]中 Simon 的回答改写): 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: 执行用时: 48ms , 在所有 csharp 提交中击败了 100.00% 的用户. 方法2 已AC代码: public class Solution
{
public bool JudgeSquareSum(int c)
{
var r = (int)Math.Sqrt(c);
var l = 0;
while (l <= r)
{
var sum = l * l + r * r;
if (sum == c)
return true;
if (sum < c)
l++;
else
r--;
}
return false;
}
// 以下为测试
public static void Main(string[] args)
{
var sol = new Solution();
var res = sol.JudgeSquareSum(25);
Console.WriteLine(res);
}
}
Rank: 执行用时: 40ms , 在所有 csharp 提交中击败了 100.00% 的用户. 相比较而已,双指针法确实更快一些~
相应代码已经上传到github: https://github.com/yanglr/Leetcode-CSharp/tree/master/leetcode633 参考资料: [1] Fast way to test whether a number is a square https://www./blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/ [2] Shortest way to check perfect Square? - C# https:///questions/4885925/shortest-way-to-check-perfect-square/4886006#4886006 作者简介:Bravo Yeung,计算机硕士,知乎干货答主(获81K 赞同, 37K 感谢, 234K 收藏)。曾在国内 Top3互联网视频直播公司工作过,后加入一家外企做软件开发至今。
|