leetcode排列硬币

 求根公式解法

    public static int arrangeCoins(int n) {
        return (int) ((Math.sqrt((long) n * 8 + 1) - 1) / 2);
    }

二分法

边界问题依然不懂

    public int arrangeCoins(int n) {
        int l = 1,r = n;
        while(l < r) {
            int m = (r - l + 1) / 2 + l;
            if((long)m * (m + 1) <= (long)2 * n) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l;
    }

    public int arrangeCoins(int n) {
        int l = 0,r = n;
        while(l <= r) {
            int m = (r - l) / 2 + l;
            if((long)m * (m + 1) < (long)2 * n) {
                l = m + 1;
            } else if((long)m * (m + 1) > (long)2 * n){
                r = m - 1;
            } else {
                return m;
            }
        }
        return r;
    }

牛顿迭代

    //大值会溢出
    public int arrangeCoins(int n) {
        if(n == 0) return -1;
        return (int)sqrt(n, n);
    }

    //y ^ 2 = x -> y = (y + x/y)/2
    //r = (x+(2n-x)/x)/2
    //2r = x + 2n/x -1
    //2r * x = x ^ 2 + 2n -x
    //2r = 2n + x * x - x

    //2n - x * x - x = 0
    //2n + x * x - x = 2 * x * x
    //2n + x * x - x = 2 * r
    //(2n + x * x - x)/2 = r
    //n + x * x/2 -x/2 = r
    public double sqrt(int n, double x) {
        double r = (x+(2*n+x)/x)/2;
        if(r == x) {
            return r;
        } else {
            return sqrt(n, r);
        }
    }

    public int arrangeCoins(int n) {
        long m = n * 2L, x = n;
        while (x * (x + 1) > m) {
            //x = (x * x + m) / (2 * x + 1)
            //x * x + m = 2 * x * x + x
            //m = x * x + x
            x = (x * x + m) / (2 * x + 1);
        }
        return (int) x;
    }