No.69 Sqrt

    xiaoxiao2021-03-26  6

    深入理解并灵活运用分治思想。

    1、思路一

    从1到x遍历一遍,判断标准为i的平方小于等于x,而i+1的平方大于x。 

    int mySqrt(int x) { int i=0; for (i=0;i<=x;i++){ if(i*i<=x&&(i+1)*(i+1)>x) break; } return i; } 结果:Wrong Answer,当input为2147395600时,output为289398,expected answer为46340。原因分析,当i=46340时,(i+1)*(i+1)发生溢出。将代码简单进行修改,方法一是将int i=0;换成long i=0;,结果为Accepted;方法二是将i*i<=x改为i<=x/i,用来确保不会发生溢出,但是第二种方法最后一个测试用例显示Time Limit Exceeded,所以需要更换算法。

    2、思路二 因为求x的根号相当于1到x个数求一个数是x的根号,由于数列是有序的,适合用二分查找,时间复杂度为O(logn)。 class Solution { public: int mySqrt(int x) { if(x==0) return 0; int left = 1,right = x; while(1){ int mid = left+(right-left)/2; if(mid>x/mid){ right = mid-1; } else{ if((mid+1)>x/(mid+1)) return mid; left = mid+1; } } } }; 3、思路三 class Solution { public: int mySqrt(int x) { long ans = 0; long bit = 1l << 16; while(bit > 0) { ans |= bit; if (ans * ans > x) { ans ^= bit; } bit >>= 1; } return (int)ans; } }; 思路理解:int类型为16位,则从最右侧的最高有效位开始算起,如果最高有效位为1的数的平方大于x,则位数减一,当确定位数之后,再逐一确定每一位的数字的是否为1,bit是从最左一位为1,其余全是0的数,ans先将bit中的1加上,然后如果ans的平方超出x,则ans与bit做异或操作就将ans刚刚加上的1删除掉了。

    转载请注明原文地址: https://ju.6miu.com/read-500279.html

    最新回复(0)