上篇文章中一道数学问题 - 自除数,今天我们接着分析 LeetCode 中的另一道数学题吧~ img 系列教程索引 传送门:https://enjoy233.cnblogs.com/articles/leetcode_csharp_index.html C#刷遍Leetcode面试题系列连载(1) - 入门与工具简介 C#刷遍Leetcode面试题系列连载(2): No.38 - 报数 C# 刷遍 Leetcode 面试题系列连载(3): No.728 - 自除数 C#刷遍Leetcode面试题系列连载(4):No.633 - 平方数之和 今天要给大家分析的面试题是 LeetCode 上第 633 号问题, Leetcode 633 - 平方数之和 https://leetcode.com/problems/sum-of-square-numbers/ 题目描述 给定一个非负整数 c ,你要判断是否存在两个整数 a和 b,使得 a2+b2=c。 示例1: 输入: 5 输出: True 解释: 1 * 1 + 2 * 2 = 5 示例2: 输入: 3 输出: False Input: 5 2 100 Expected answer: true true true 题目难度: 简单 贡献者: Stomach_ache 相关话题 数学 https://leetcode-cn.com/tag/math 相似题目 有效的完全平方数 https://leetcode-cn.com/problems/valid-perfect-square 解题思路: 做一次循环,用目标和减去循环变量的平方,如果剩下的部分依然是完全平方的情形存在,就返回true;否则返回false。 假定 i≤a≤b,根据数据的对称性,循环变量 i 只需取到 i2⋅2≤c 即可覆盖所有情形. 已AC代码: 最初版本: C# 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: 执行用时: 56 ms, 在所有 csharp 提交中击败了68.18%的用户. 优化1: C# 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: 执行用时: 52 ms, 在所有 csharp 提交中击败了90.91%的用户. 优化2(根据文末参考资料[1]中MPUCoder 的回答改写): C# 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) //TRUE only if n mod 16 is 0, 1, 4, or 9 { int t = (int)Math.Floor(Math.Sqrt((double)num) + 0.5); return t * t == num; } return false; } } Rank: 执行用时: 44 ms, 在所有 csharp 提交中击败了100.00%的用户. LeetCode-dotNET匠人 优化3(根据文末参考资料[1]中 Simon 的回答改写): C# 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: 执行用时: 48 ms, 在所有 csharp 提交中击败了100.00%的用户. 另外,stackoverflow上还推荐了一种写法: C# 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; } } 事实上,速度并不快~ Rank: 执行用时: 68 ms, 在所有 csharp 提交中击败了27.27%的用户. 二分法 解法: 时间复杂度 log(n), 感谢 @msp的昌伟哥哥 的补充和指正~ C# 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: 执行用时: 40 ms, 在所有 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.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/ [2] Shortest way to check perfect Square? - C# https://stackoverflow.com/questions/4885925/shortest-way-to-check-perfect-square/4886006#4886006 作者简介:Bravo Yeung,计算机硕士,知乎干货答主(获81K 赞同, 38K 感谢, 235K 收藏)。曾在国内 Top3互联网视频直播公司工作过,后加入一家外企做软件开发至今。 如需转载,请加微信 iMath7 申请开白! 欢迎在留言区留下你的观点,一起讨论提高。如果今天的文章让你有新的启发,学习能力的提升上有新的认识,欢迎转发分享给更多人。 欢迎各位读者加入 .NET技术交流群,在公众号后台回复“加群”或者“学习”即可。 dotNET匠人 公众号名片 文末彩蛋 微信后台回复“asp”,给你:一份全网最强的ASP.NET学习路线图。 回复“cs”,给你:一整套 C# 和 WPF 学习资源! 回复“core”,给你:2019年dotConf大会上发布的.NET core 3.0学习视频! 作者:Bravo Yeung 出处:https://enjoy233.cnblogs.com/ 如果,您希望更容易地发现我的新文章,不妨点击一下绿色通道的【关注我】,亦可微信搜索公众号「dotNET匠人」关注我。 如果您觉得阅读本文对您有帮助,请点击一下右下方的推荐按钮,您的推荐将是我写作的最大动力! 版权声明:本文为博主原创或转载文章,欢迎转载,但转载文章之后必须在文章页面明显位置注明出处,否则保留追究法律责任的权利。如您有任何疑问或者授权方面的协商,请 .https://www.cnblogs.com/enjoy233/p/csharp_leetcode_series_4.html