SqrtX [source code]

public class SqrtX {
static
/******************************************************************************/
public class Solution {
    public int mySqrt(int x) {
        long root = x;
        while (root * root > x) {
            root = (root + x / root) >> 1;
        }
        return (int) root;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SqrtX.Solution tester = new SqrtX.Solution();
        int[] inputs = {
            2147395599, 46339,
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int x = inputs[2 * i];
            int expected = inputs[1 + 2 * i];
            System.out.println(Printer.seperator());
            Printer.openColor("magenta");
            System.out.print(x);
            Printer.closeColor();
            int output = tester.mySqrt(x);
            System.out.print(" -> " + output);
            Printer.openColor(output == expected ? "green" : "red");
            System.out.println(", expected: " + expected);
            Printer.closeColor();
        }
    }
}

这题穷举感觉会超时, 所以尝试用Newton算法来做; 不过还是碰到了overflow的case;

这里唯一的一个小难点就是这个就是这个root的buffer要用long, 应为在计算的过程中这个值要不停的加. 其实你看到循环里面这么一个加法var的时候就应该想到了, 不过记住的话也可以, 在Newton算法里面这个long其实是一个常规的点了;

最后的速度是2ms (71%), 还算一般; 好像其实是最优解了, 因为这个题目比较老而且知道最优解的人也很多了反正. 最快的是一帮直接调用API的瓜批.

另外真正面试的时候如果碰到这个题目, 你只知道Newton的话是肯定不行的, 我们说过, 尤其是这种math问题, 掌握笨办法远比掌握这些数学上的巧办法要重要;

这题如果自己搜索其实也不难, 直接一个Binary Search就行了;

public int mySqrt(int x) {  
    int left = 1, right = x;  
    while (left <= right) {  
        int mid = left + (right - left) / 2;  
        if (mid == x / mid) {  
            return mid;  
        } else if (mid < x / mid) {  
            left = mid + 1;  
        } else {  
            right = mid - 1;  
        }  
    }  
    return right;  
}

注意他们这里判断相等的时候使用的是除法而不是乘法, 也是为了避免overflow; 再者乘法也未必就比除法快;

另外注意这里, 在最后unfound的情况下返回的是什么. 这里有人采用了另外一种思路:

class Solution {  
public:  
    int sqrt(int x) {  
        if (0 == x) return 0;  
        int left = 1, right = x, ans;  
        while (left <= right) {  
            int mid = left + (right - left) / 2;  
            if (mid <= x / mid) {  
                left = mid + 1;  
                ans = mid;  
            } else {  
                right = mid - 1;  
            }  
        }  
        return ans;  
    }  
};

Firstly, the rationale behind mid <= x / mid instead of using mid * mid <= x is just for preventing from overflow (multiply two int numbers may not fit in int as well).

Secondly, the meaning of ans in my code is used to keep the biggest integer which satisfies ans * ans <= x and then it'll be the answer at the end of binary search procedure.

可以看到这个人的思路很清晰; 与其自己在index上碰运气, 不如自己maintain a variable with a know invariant, 这样最后就有把握知道发生了什么;

I noticed that you made mid as the final answer at the last line in your code, which may not satisfy mid mid <= x cause you never know which branch of conditions mid will go at the last round of binary search.
And btw, the input is not necessary a perfect square number, so that's why you should keep the largest integer that satisfies ans ans <= x.

他这个做法跟直接return mid是不一样的(直接return mid是不对的). 他就是主动选择只在某些情况下才更新ans, 这跟mid不一样: mid每一个iteration必然更新;

Binary Search在最后miss的情况下的index分析确实有点复杂;
在想Binary Search的时候, 脑子里不要一直想着一个整个的array, 然后两个指针移动什么的. 如果单纯是为了思考最后一个iteration的指针的运动情况, 脑子里只要考虑最后最小的那个iteration就行了(有点类似recursion的观点, 只考虑当前的subproblem).
首先考虑一个这种标准代码的情形下, invariant是什么? always have left ≤ key ≤ right. 因为上一个iteration是在mid(which is not equal to key)的基础上(朝正确的方向)移动了1, 所以现在的左右是可能取到等号的;
最后一个iteration, 如果是长度为2, 那么自己举两个例子, 分别是left hit, right hit, no hit三种情况分析一下, 可以看到最后left就是你想要的existence position or insertion position: left hit直接找到, 如果是right hit, 下一个区间就是[right, right], 也是直接找到, 注意这两种情况下都肯定是last iteration, 因为左右已经相等了, header只能最后yes这一次了; 如果是miss(一定是在(left, right)这个开区间里面), 那么我们最后得到的left其实是array里面key的ceiling(下一个iteration才是last iteration), ceiling的位置其实就是insertion position, 这个自己想一下其实很简单(注意最后一个iteration是left == right的情况, 但是这个结束之后左右其实还是有更新的, 最后的情况其实是left == right + 1, 这个也是terminating condition, 所以最后指向ceiling的其实是left);
本来说, base case是不是还要考虑长度为3的情况, 不过想想长度为3的下一个iteration肯定还是转换成了长度为2的情况, 所以是没有必要考虑的. 理解最后的Edge Case的核心就是理解最后一个长度为2的iteration; ;

这一题我们也可以这样考虑, 我们只考虑最后一个长度为2的iteration(这里的key其实就是真实的平方根, 也就是double类型的).
这一题其实就是binary search for the (double) root, 然后你按照我们上面的例子你看出来什么: 其实最后termination的时候, left就是key的ceiling, 然后right就是key的floor. 我们这里要找的是平方根被truncate之后的值, 所以要找的是floor, 这也是为什么最后上面的第一个Binary Search直接返回right就行了: 这些经典算法的边边角角你都要了解清楚, 这样要用的时候就可以直接照搬了, 别尼玛面试的时候还自己那这个Edge Case一个iteration一个iteration的看;

当然这里这个第二Binary Search这个人这个算法也有点奇葩, 也不是不行吧, 他非要用把Binary Search写成两个branch, 也可以. 不过能够真正对Binary Search算法本身举一反三我认为更重要一些;

discussion上面还有一个用bit做的:

public class Solution {  
     public int mySqrt(int x) {  
        int res = 0;  
        for (int mask = 1 << 15; mask != 0; mask >>>= 1) {  
            int next = res | mask; //set bit  
            if (next <= x / next) res = next;  
        }  
        return res;  
    }  
}

感觉其实也就是逼格高一点的穷举; mask是用来decide current bit (to process)的, 就类似你平时做array时候的index一样的;
这里其实就是一个bit一个bit的做(用 | 来组合, 保证不同的bit之间互相不影响);

这里总结一下 | 的用法: 一般就是用来set操作的: 两个操作数当中一般有一个是有1的, 这个是你想要set的1. 当然了这个1是有其固定的bit位置的, 所以除此以外的意思就是: 除了这个位置以外的部分, 保持原状.

另外注意这里为什么他只考虑了16位的就够了, 因为int是32位, 平方根是不可能超过16位的;

Problem Description

Implement int sqrt(int x).

Compute and return the square root of x.

Difficulty:Easy
Total Accepted:159.9K
Total Submissions:576.8K
Contributor: LeetCode
Companies
bloomberg apple facebook
Related Topics
binary search math
Similar Questions
Pow(x, n) Valid Perfect Square