알고리즘 에 서 는 넘 치지 않도록 부등식 변환 을 사용 할 수 있 습 니 다. leetcode: Sqrt (x), BigInteger 처리 넘 침

2229 단어
leetcode 제목 Sqrt 를 할 때 분 치 법 을 사용 할 때 mid 의 제곱 과 x 의 크기 관 계 를 비교 해 야 합 니 다. 만약 에 mid 의 제곱 이 x 보다 크 면 right = mid - 1, 작 으 면 left = mid + 1 을 사용 해 야 합 니 다. 이런 방식 에서 mid 의 제곱 을 요구 해 야 합 니 다. mid 의 제곱 은 Integer 의 범 위 를 초과 할 수 있 습 니 다. 이것 은 넘 치 는 문제 가 발생 했 습 니 다. 곰 곰 이 생각해 보 세 요. 제곱 을 구 해 야 합 니까?충분히 피 할 수 있어!
Math. pow (mid, 2) 와 x 의 크기 를 비교 하면 mid 와 x / mid 의 비교 로 대체 할 수 있 는데 이것 은 초등학교 수학 에서 습득 할 수 있 는 문제 이다.
이분법 과정 에서 넘 칠 수 있 는 상황 은 mid = (left + right) / 2 입 니 다. 만약 left + right 의 합 이 정수 범 위 를 초과 하면 완전히 넘 칠 수 있 습 니 다. 어떻게 합 니까?
조금 만 바 꿔 주세요 (left + right) / 2 = left + (right - left) / 2, 넘 치지 않 습 니 다!
문 제 를 풀 때 머리 를 쓰 면 문 제 를 해결 할 수 있 을 것 같다.
다음은 Sqrt 를 처리 하 는 코드 (이분법) 입 니 다.
    public int mySqrt(int x) {
    	if(x <= 0) return 0;
        int r = x/2+1;
        int l = 1;
        int mid=0;
        while(l<=r){
        	mid = (l+r)/2;
        	if(mid==x/mid){
        		return mid;
        	}else if(mid>x/mid){
        		r = mid-1;
        	}else{
        		l = mid+1;
        	}
        }
        if(Math.pow(mid, 2)>x){
        	return mid-1;
        }
        return mid;
    }

가끔 우 리 는 BigInteger 를 사용 하여 넘 치 는 것 을 처리 할 수 있 습 니 다. 이것 은 비장의 무기 로 모든 문 제 를 해결 할 수 있다 고 생각 했 지만 leetcode 는 BigInteger 를 모 릅 니 다. 다음은 BigInteger 를 사용 하여 해결 하 는 코드 입 니 다.
    public int mySqrtUseBigInteger(int x) {
    	BigInteger xb = new BigInteger(x+"");
        BigInteger r = new BigInteger((x/2+1)+"");
        BigInteger l = new BigInteger("0");
        BigInteger mid = new BigInteger("0");
        BigInteger two = new BigInteger("2");
        BigInteger one = new BigInteger("1");
        
        while(l.compareTo(r)<0 || l.compareTo(r)==0){
        	mid = (l.add(r)).divide(two);
        	BigInteger pow = mid.multiply(mid);
        	if(pow.compareTo(xb)==0){
        		return mid.intValue();
        	}else if(pow.compareTo(xb)>0){
        		r = mid.subtract(one);
        	}else{
        		l = mid.add(one);
        	}
        }
        if(mid.multiply(mid).compareTo(xb)>0){
        	return mid.intValue()-1;
        }
        return mid.intValue();
    }
CSS3의 다양한 속성의 의미
Python의 창고 데이터 구조

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage