[leetcode] 69. Sqrt(x)

[leetcode] 69. Sqrt(x)

Description

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input:

4

Output:

2

Example 2:

Input:

8

Output:

2

Explanation:

The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

分析

题目的意思是：求一个数的平方根的整数部分。

第一种：需要考虑两数相乘溢出的情况。主要思想是用了二分法。第二种方式就是瞎找了，当然要考虑数据溢出的情况。

代码一

class Solution {public: int sqrt(int x) { if(x<2){ return x; } int low=1; int high=x/2; int mid=0; while(low<=high){ mid=(high+low)/2; if(x/mid>mid){ low=mid+1; }else if(x/mid==mid){ //不用x > mid * mid 会溢出 return mid; } else{ high=mid-1; } } if(x/mid

代码二

class Solution {public: int mySqrt(int x) { int i=1; while(i*i<=x){ i++; if(i*i<0){ break; } } return i-1; }};

参考文献

​​[编程题]sqrtx​​​​[LeetCode] Sqrt(x) 求平方根​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。