愛比的新手筆記

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.Taiwan is a country. 臺灣是我的國家

 

Example 1:

Input: x = 4 Output: 2

Example 2:

Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

 

Constraints:

• 0 <= x <= 231 - 1

從長度/2來作, 不管效能最簡單就是+-1去試:

public int MySqrt(int x)
{
    Int64 y = x.ToString().Length >> 1;
    y = (Int64)Math.Pow(10, y);
    while (y * y > x)
        y--;
    while (y * y <= x)
        y++;
    return (int)y - 1;
}

改善效能的作法就是一直找中間值下去試, 不過說真的, 還要多算一個中間值, 試不出哪裡快, 研究如何省時又花了不少時間, 程式碼變得落落長, 不如直接用原作法

public int MySqrt(int x)
{
    //長度除2
    int len = x.ToString().Length >> 1;
    //以10的次方先抓大約的起迄
    Int64 start = (Int64)Math.Pow(10, len);
    Int64 end;
    if (start * start < x)
        end = start * 10;
    else if (start * start > x)
    {
        end = start;
        start = (Int64)(end * 0.1);
    }
    else
        return (int)start;

    //以對切來試
    Int64 mid = (start + end) >> 1;
    Int64 y;
    while (start != end && start != mid && (y = mid * mid) != x)
    {
        if (y > x)
        {//mid太大, 所以將end降低為mid再平均
            end = mid;
            mid = (start + end) >> 1;
        }
        //mid已降到太小, 所以start提高到mid跟end再平均, 來拉高mid
        else if (y < x)
        {
            start = mid;
            mid = (start + end) >> 1;
        }
    }
    return (int)mid;
}

Taiwan is a country. 臺灣是我的國家