LeetCode每日一題--有效的完全平方數（三種方法）
2021.11.4
1.題目概述
不虧簡單題，簡單的表述，簡單的輸出
2.題目了解
在給出數字的某一個範圍内，有一個數字的平方等于它
三種方法
- 1使用庫函數
- 2.二分法求解
- 3.使用牛頓疊代法（現學現賣）
3.解題代碼
使用庫函數
class Solution {
public boolean isPerfectSquare(int num)
{
//撈的辦法，使用庫函數
double sq=Math.sqrt(num);
return sq-(int)sq==0;
}
}
二分法查找
class Solution {
public boolean isPerfectSquare(int num)
{
//不太撈的辦法，建立一個100以内的小表，另外100以上就在/10的範圍内二分法查找
int []Table=new int [10];
for(int i=1;i<=10;i++)
Table[i-1]=i*i;
//先對進來的數字進行檢查
if(num>=1&&num<=100)
{
for(int i=0;i<10;i++)
if(num==Table[i])
return true;
}
//大于100的數字做/10範圍的内的二分法查找
long left=11;
long right=num/10;
long mid=0;
while(left<=right)
{
mid=(right-left)/2+left;
//System.out.println("left: "+left+" right: "+right+" "+mid+"-->"+num/mid);
if(mid*mid==num) return true;
else if(num<mid*mid ) right=mid-1;
else left=mid+1;
}
return false;
}
}
這個做法我還是有些說的，首先說我為什麼要建立一個100内的表吧，其實是為了快速，因為sqrt(100)=10，也就是在1-10的範圍内其實就可以查找到1-100内的完全平方數，而如果我一開始不建表，在二分法的時候将right=num/2，其實還是有些緩慢，在建表之後，我的寫法就可以是num/10開始查找了，算是把記憶體和速度平均一下。
一開始的時候，我沒有使用long，使用的是int，但是我判斷部分寫的是if(num/mid==mid)，但是這樣會有精度問題，是以我将二分查找的資料類型換成了double ，并且在if(Math.abs(num/mid-mid)<0.01))來判斷，但是由于後面對于left和right的步長是1，是以導緻一直跳不到，是以後面使用了long類型，因為long的最大值2^64-1，可以避免整數溢出，但是其實這樣以來在判斷64位整數的時候就仍然會溢出。
牛頓疊代法
一篇介紹這個的文章：urlhttps://www.zhihu.com/question/20690553
class Solution {
public boolean isPerfectSquare(int num)
{
if(num==1) return true;
//起始點為num的中點
int x=num/2;
//50次疊代範圍内
for(int i=0;i<20;i++)
{
x=(x-(x-num/x)/2);
}
System.out.println(x+" -> "+num);
double t=x;
if(num/t==t)return true;
return false;
}
}
昨天的困難題晚上有時間在整理吧