当前位置:首页(Home) >> 新闻资源(News List)

时间:2015-01-19 来源:

【leetcode】69Sqrt(x) 【编程语言】

问题描述:

a better method Since sqrt(x) is composed of binary bits, I calculate sqrt(x) by deciding every bit from the most significant to least significant. 

Implement int sqrt(int x).

基本思路: 采用二分查找法; 犹豫输入x是int型 ,int最大范围是2147483647 ,所以返回结果的范围0-46340. 注意要根据确定的区间去查找正确的返回值,如果大于46340的数的平方将超出int的表示范围。

public int sqrt(int x) { if(x==0) return 0; int h=0; while((long)(1<<h)*(long)(1<<h)<=x) // firstly, find the most significant bit h++; h--; int b=h-1; int res=(1<<h); while(b>=0){ // find the remaining bits if((long)(res | (1<<b))*(long)(res |(1<<b))<=x) res|=(1<<b); b--; } return res; }

代码:

Compute and return the square root of x.

int sqrt(int x) { if(x==0||x==1) return x; if(x >=2147395600) return 46340; int high = 46339*2-1; int low = 1; while(low <= high){ int mid = (high+low)/2; int hpow = (mid+1)*(mid+1); int lpow = mid*mid; if(x>=lpow && x<hpow) return mid; else if(x<lpow) high = mid-1; else low = mid+1; } }

点击次数:1360
作者: