C#版 - Leetcode367. 有效的完全平方数 - 题解
C#版 - Leetcode367. 有效的完全平方数 - 题解
Enjoy233
发布于 2019-03-05 15:55:57
发布于 2019-03-05 15:55:57
文章被收录于专栏：大白技术控的技术自留地
C#版 - Leetcode367. 有效的完全平方数 - 题解
Leetcode 367 - Valid Perfect Square
在线提交: https://leetcode.com/problems/valid-perfect-square/
题目描述
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
注意：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入： 16
输出： True
示例 2：
输入： 14
输出： False
归功于:
特别感谢 @elmirap 添加此问题并创建所有测试用例。
思路：
首先题目明确要求不能使用内置的sqrt及其他相关的库函数，于是解此题常见的几种方法如下：
1.利用数学公式 k2=1+3+⋯+(2⋅k−1)k2=1+3+⋯+(2⋅k−1)k^2 = 1 + 3 + \cdots +(2\cdot k - 1) .
2.自己实现sqrt函数的功能，最快的方法当属 Babylonian method.
3.二分查找
方法1 已AC代码：
public class Solution
{
public bool IsPerfectSquare(int num)
{
int i = 1;
while (num > 0)
{
num -= i;
i += 2;
}
if (num == 0)
return true;
return false;
}
}Rank: You are here! Your runtime beats 94.68 % of csharp submissions.
方法2 已AC代码:
public class Solution
{
public const double eps = 1e-10;
public bool IsPerfectSquare(int num)
{
double sq1 = SquareRoot(num);
int sq2 = (int)SquareRoot(num);
if (sq1 - (double)sq2 < eps && sq1 - (double)sq2 > -eps)
return true;
return false;
}
public double SquareRoot(double x)
{
if (x == 0)
return 0;
double r = x / 2;
double last = 0;
int maxIters = 100;
for (int i = 0; i < maxIters; i++)
{
r = (r + x / r) / 2;
if (r - last < eps && r - last > -eps)
break;
last = r;
}
return r;
}
}Rank: You are here! Your runtime beats 94.68 % of csharp submissions
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018年07月28日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
