分治-2016-07-19

[zhaokuohaha]

50 : https://leetcode.com/problems/powx-n/

69 : https://leetcode.com/problems/sqrtx/

[SnackMen]

参考：http://blog.csdn.net/liupan1114250779/article/details/51917999

/*
[AC] 50. Pow(x, n)   快速幂
*/
  public class Solution {
     public static double myPow(double x, int n) {
        if(n==0 || x==1)
            return 1;
        long n1=(long)n;
        if(n<0){
            n1=-1l*n;
            x=1/x;
        }
        double sum=1;
        double pre=x;
        while(n1!=0){
            if((n1&1)==1){
                sum*=pre;
            }
            pre*=pre;
            n1=n1>>1;
        }
        return sum;
    }
  }

[SnackMen]

/*
    [AC]69.Sqrt(x) 牛顿迭代法
*/
public class Solution {
    public int mySqrt(int x) {
        double num=0;
        double now=1;
        if(x==0)
            return 0;
        else{
            while(num!=now) {
                num=now;
                now=(num+x/num)/2;
            }
        }
        return (int)now;
    }
}

[dayang]

/**
 * [AC] 69  Sqrt(x)  牛顿迭代法
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if(x === 0)
        return 0;
    var e = 0.0000001;
    var x1 = x;
    do{
        x0 = x1;
        x1 = x0 / 2 + x / 2 / x0;
    }while(Math.abs(x0 - x1) > e);

    return Math.floor(x1);
};

[wolfogre]

JS的位运算效率很低，再者我不知道怎么用位运算写……

//[AC] 50. Pow(x, n)
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if(n === 0)
        return 1;
    if(x === 1 || x === 0)
        return x;
    if(x === -1)
        return n % 2 === 0 ? 1 : -1;
    var flag = false;
    if(n < 0){
        flag = true;
        n = -n;
    }
    var result = 1;
    while(n-- > 0 && (!flag && Math.abs(result) > 0 || flag && Math.abs(1 / result) > 0))
        result *= x;

    return flag ? 1 / result : result;
};

[wolfogre]

// [AC] 69  Sqrt(x)  牛顿迭代法
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if(x === 0)
        return 0;
    var e = 0.1;
    var s = x / 2, s0 = 0;

    while(Math.abs(s0 - s) > e){
        s0 = s;
        //s = s - (s * s - x)　/ (2 * s);
        s = (s * s + x)　/ (2 * s);
    }
    return  Math.floor(s);
};

[dayang]

/**
 * [AC] LeetCode 50 Pow(x, n)  快速幂
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if(n === 0 || x === 1)
        return 1;
    if(n < 0){
        x = 1 / x;
        n = -n;
    }

    var res = 1;
    var cur = x;
    while(n !== 0){
        if((n & 1) === 1){
            res *= cur;
        }
        cur *= cur;
        n = Math.floor(n / 2);   // js 用n = n>>1 位移 对于-2147483648会超时，why? 好吧 用 n = n >>> 1可以，区别在哪?
    }
    return res;
};
/*
* >>是算数右移，>>>是逻辑右移
* console.log(2147483648 >> 1);
* console.log(2147483648 >>> 1);
* console.log(-2147483648 >> 1);
* console.log(-2147483648 >>> 1);
* console.log((2147483648).toString(2));
* console.log((-2147483648).toString(2));
*
* -1073741824
* 1073741824
* -1073741824
* 1073741824
* 10000000000000000000000000000000
* -10000000000000000000000000000000
*/

[zhaokuohaha]

50 - 快速幂 - C

public class Solution {
    public double MyPow(double x, int intn) {
        bool tag = false;
        long n = (long)intn;
        if(n<0){
            tag = true;
            n = Math.Abs(n);
        }
        double temp = x;
        double sum = 1;
        while(n>0){
            if((n & 1) == 1){
                sum*=temp;
            }
            temp*=temp;
            n >>= 1;
        }
        if(tag)
            return 1/sum;
        return sum;
    }
}

[zhaokuohaha]

69 - 牛顿迭代法 - 看不太懂

public class Solution {
    public int MySqrt(int x) {
        double eps = 1e-6;
        if(x==0) return 0;
        double result = x;
        double lastvalue;
        do{
            lastvalue = result;
            result = result / 2.0 + x / 2.0 / result;
        }while(Math.Abs(result - lastvalue) > eps);
        return (int) result;
    }
}