C++LeetCode 구현(69.제곱 근 구하 기)

[LeetCode]69.Sqrt(x)제곱 근 구하 기
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.
이 문 제 는 제곱 근 을 요구 합 니 다.우리 가 생각 할 수 있 는 방법 은 바로 후보 값 의 제곱 을 계산 한 다음 에 x 와 크기 를 비교 하 는 것 입 니 다.검색 시간 을 단축 시 키 기 위해 우 리 는 2 분 검색 법 으로 제곱 근 을 찾 습 니 다.마지막 으로 목표 치 보다 크 지 않 은 수 를 찾 습 니 다.여기 서 세심 한 어린이 신발 은 의문 이 있 을 수 있 습 니 다.요약 판 에서 세 번 째 블 로 거들 의 right 는 구간 을 사용 합 니 다.그렇다면 여 기 는 왜 right 가 x+1 이 아 닌 x 로 초기 화 되 었 습 니까?요약 글 에 있 는 left 와 right 는 모두 배열 아래 표 시 된 것 이기 때문에 여기 있 는 left 와 right 는 바로 숫자 자체 입 니 다.한 숫자의 제곱 근 은 그 자체 보다 클 수 없 기 때문에 1 을 추가 하지 않 아 도 됩 니 다.그리고 여기 서 x 가 정형 최대 치 라면 1 을 더 하면 넘 칠 수 있 습 니 다.마지막 으로 반환 값 은 right-1 입 니 다.제목 에서 소수 부분 을 빼 야 한다 고 했 기 때문에 1 을 빼 야 정확 한 값 을 얻 을 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 0, right = x;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x / mid >= mid) left = mid + 1;
            else right = mid;
        }
        return right - 1;
    }
};

이 문 제 는 또 다른 해법 이 있다.뉴턴 교체 법 을 이용 한 것 이다.고수 에서 이 방법 을 말 한 것 처럼 접근 법 으로 방정식 뿌리 를 구 하 는 신기 이다.여기 서도 빌려 쓸 수 있다.왜냐하면 x2 를 요구 하기 때문이다. = n 의 해,령 f(x)=x2-n 은 f(x)=0 의 해 를 구 하 는 것 과 같 습 니 다.전달 식 은 다음 과 같 습 니 다.
xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2
해법 2:

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        double res = 1, pre = 0;
        while (abs(res - pre) > 1e-6) {
            pre = res;
            res = (res + x / res) / 2;
        }
        return int(res);
    }
};

또한 뉴턴 교체 법 으로 쓰기 가 더욱 간결 하 다.경 계 를 넘 지 않도록 긴 정형 으로 성명 하고 코드 는 다음 과 같다.
해법 3:

class Solution {
public:
    int mySqrt(int x) {
        long res = x;
        while (res * res > x) {
            res = (res + x / res) / 2;
        }
        return res;
    }
};

C++구현 LeetCode(69.제곱 근 구하 기)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 제곱 근 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!