常州网站制作公司有哪些,蚌埠集团网站建设,建站程序排名,wordpress links点击蓝字“dotNET匠人”关注我哟加个“星标★”#xff0c;每日 7:15#xff0c;好文必达#xff01;前文传送门:上篇文章中一道数学问题 - 自除数#xff0c;今天我们接着分析 LeetCode 中的另一道数学题吧~今天要给大家分析的面试题是 LeetCode 上第 633 号问题#xff… 点击蓝字“dotNET匠人”关注我哟加个“星标★”每日 7:15好文必达前文传送门:上篇文章中一道数学问题 - 自除数今天我们接着分析 LeetCode 中的另一道数学题吧~今天要给大家分析的面试题是 LeetCode 上第 633 号问题Leetcode 633 - 平方数之和https://leetcode.com/problems/sum-of-square-numbers/题目描述给定一个非负整数c 你要判断是否存在两个整数a和 b使得。示例1:输入: 5
输出: True
解释: 1* 1 2* 2 5示例2:输入: 3
输出: FalseInput:5
2
100Expected answer:true
true
true题目难度: 简单贡献者Stomach_ache相关话题数学https://leetcode-cn.com/tag/math相似题目有效的完全平方数https://leetcode-cn.com/problems/valid-perfect-square解题思路:方法1: 遍历做一次循环用目标和减去循环变量的平方如果剩下的部分依然是完全平方的情形存在就返回true否则返回false。假定根据数据的对称性循环变量 i 只需取到 即可覆盖所有情形.时间复杂度: O(n)方法2: 双指针法左指针 l0右指针 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% 的用户.优化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 squarehttps://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#4886006End作者简介Bravo Yeung计算机硕士知乎干货答主(获81K 赞同, 37K 感谢, 234K 收藏)。曾在国内 Top3互联网视频直播公司工作过后加入一家外企做软件开发至今。欢迎各位读者加入 .NET技术交流群在公众号后台回复“加群”或者“学习”即可。朕已阅
