題型解說
這是一題難度為簡單的題目
需要設計一個方法,此方法會傳入一個整數 x
計算出最接近 x 平方根的整數答案後回傳
簡單說就是去掉小數點只回傳整數部分
範例:
x = 8,則回傳 2,雖然 8 的平方根介於 2 和 3 之間,但題目只要我們取整數就好
解題思路
如果你有搜尋過這個題目的話,大概知道主要的解題方向就是二分搜尋法的變種
更厲害的就會用 牛頓迭代法 來求根,但那已經是數學領域的東西,我自己是怎麼都看不懂
後來就自己簡單的寫了一個類似 十分逼近法 的解法,一樣可以過關
一開始用一個比較大的區間計算,我是設定 100
利用迴圈每次加 100 後計算平方直到大於 x
再慢慢扣 1 直到小於等於 x
程式碼
Java
class Solution {
public int mySqrt(int x) {
if (x == 0) return 0;
long result = 0;
do
result += 100;
while (result * result < x);
for (int i = 0; i < 101; i++) {
result -= 1;
if (result * result <= x) {
return (int)result;
}
}
return 0;
}
}