題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入一個整數 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;
    }
}