sqrt (x) 함수 구현;$ (i ^ 2 \ leq x) \ 랜드 ((((i + 1) ^ 2> x) $ 확인?
-
29-09-2020 - |
문제
최근에 나는 leetcode 질문 ko
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.
.
여기에 한 줄을 제외하고는 정말로 원하는 및 이해하는 솔루션입니다.바이너리 검색을 사용하여 솔루션에 도달합니다.
int mySqrt(int x) {
if (x == 0) return x;
int left = 1, right = INT_MAX, mid;
while(left < right) {
mid = left + (right - left)/2;
if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
return mid;
}
if (mid < x/mid) {
left = mid + 1;
} else { // mid > x/mid
right = mid;
}
}
return right;
}
.
개념적 질문은 다음과 같습니다. $ i $ , $$ (i ^ 2 \ leq x) \ 랜드 ((i + 1) ^ 2> x) $$ $ i $ 이 잘립니다. $ x $ 의 정수 표현?(위의 코드 블록은 동일한 조건에서 반환되지만 불평등은 정수 오버플로 피해야하도록 재 배열됩니다)
해결책
가독성 : $ i ^ 2 \ leq x <(i + 1) ^ 2 $ .
양수의 양의 정사각형을 복용하는 것은 모노톤 기능입니다.그 후, $$ i ^ 2 \ Leq x <(i + 1) ^ 2 \ \ leq | \ sqrt {x}을 암시합니다 |
그런 다음 $ | \ sqrt {x}의 중간 부분이 $ i $ .
제휴하지 않습니다 cs.stackexchange