AI-generated summary
Title: Square Root of X
Date: 2020/10/22 20:00:00
Comments: true
Tags: Algorithm, C
Categories: LeetCode
Description:
Implement the function int sqrt(int x).
Calculate and return the square root of x, where x is a non-negative integer.
Since the return type is an integer, the result will only retain the integer part, and the decimal part will be discarded.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., but since the return type is an integer, the decimal part will be discarded.
Approach:
Brute force solution, incrementally calculate squares starting from 1, return the value one less than x when the result is greater than x.
int mySqrt(int x){
for(long i=1;;i++) {
if(i*i > x)
return (int)i-1;
}
}
Approach two:
Building on the previous approach, increase the increment step to widen the search range, then decrement to find the final value.
int mySqrt(int x){
long first = 1;
for(;first = x)
break;
for(long second = first;;second--)
if(second * second <= x)
return second;
}
Approach three:
