【LeetCode】 367. Valid Perfect Square

Description

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

給予正整數 num ，寫一個函式回傳 num 是否為完美平方數。

提示：不要使用任何內建函式庫的函式，例如sqrt。

Example:

Example 1:

Input: 16
Output: true


Example 2:

Input: 14
Output: false

Solution

• 既然不能使用內建的sqrt，那就自己實作一個就好了。
  • 這邊有實作sqrt的方法。
• 實作完成之後，就做開根號再平方看看有沒有一樣即可。

Code

class Solution {
public:
    int mySqrt(int x) {
//      x1 = x0 - f(x)/f'(x)
//      f(x) = x^2 - a = 0
//      x1 = x0 - x^2 - a / 2x
        if(x == 0) return 0;
        
        double a = x, a2 = x;
        do
        {
            a = a2;
            a2 = a - (a * a - x) / (2 * a);
        } while(abs(a - a2) > 0.00001);
        
        return (int)floor(a2);
    }
    
    bool isPerfectSquare(int num) {
        int temp = mySqrt(num);
        return temp * temp == num;
    }
};

tags: LeetCode C++