Pow (x, n) Leetcode 솔루션  


난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 아사 블룸버그 게시물에서 이베이 페이스북 서비스 골드만 삭스 구글 링크드 인 Microsoft 신탁 페이팔 동네 짱 VM웨어 월마트 연구소
알고리즘 이진 검색 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 수학

“Pow (x, n) Leetcode Solution”문제는 두 개의 숫자가 주어 졌음을 나타냅니다. 그 중 하나는 부동 소수점 숫자이고 다른 하나는 정수입니다. 정수는 지수를 나타내고 밑은 부동 소수점 숫자입니다. 기수에 대한 지수를 평가 한 후 값을 찾으라는 지시를 받았습니다. 밑은 음수, 양수 또는 10000 일 수 있습니다. 지수는 정수 범위 사이에있을 수 있습니다. 출력에 대한 제약도 주어집니다. 출력은 -10000에서 +XNUMX 사이입니다. 자, 몇 가지 예를 살펴 보겠습니다.

Pow (x, n) Leetcode 솔루션

예  

Base: 2
Exponent: 10
Answer: 1024

설명 : 2 ^ 10 = 104의 값이므로 답입니다. 이것은 또한 2 10 번의 반복적 인 곱셈으로 확인할 수 있습니다.

Base: 2
Exponent: -10
Answer: 0.00098

설명 : 지수 값도 -10으로 변경 되었기 때문에 답변이 변경되었습니다.

무차별 대입 접근  

문제 Pow (x, n) Leetcode Solution에 대한 무차별 대입 접근 방식은 매우 간단합니다. 지수를 평가하는 작업을 시뮬레이션하면됩니다. 지수는 기본 지수 횟수를 곱하여 쉽게 계산할 수 있습니다. 따라서 선호하는 프로그래밍 언어의 루프를 사용하여이를 쉽게 시뮬레이션 할 수 있습니다. 한 가지 주목할 점은 코너 케이스입니다. 지수가 정수의 최대 값 또는 최소값과 같을 때 정수. 정수의 최소값으로 지수가있을 때 답은 1 또는 0이 될 수 있습니다. 밑이 1 또는 -1이면 정수의 최소값으로 지수를 갖는 지수는 1이 아니면 0입니다. 마찬가지로 1 만 가질 수 있습니다. 지수를 정수의 최대 값으로 사용합니다. 출력에 대한 제약이 10000 미만이기 때문입니다. 이러한 제약을 고려하여 기본 지수 시간의 곱셈을 시뮬레이션하여 무차별 대입 코드로 작성할 수 있습니다.

참조
홍수 채우기 LeetCode

Pow (x, n) Leetcode 솔루션에 대한 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    for(int i=0;i<n;i++)
        ans = ans*x;
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        for(int i=0;i<n;i++)
            ans = ans*x;
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024.0

복잡성 분석

시간 복잡성

의 위에), 기본 지수 시간을 곱할 때까지 반복하기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

O (1), 답만 저장해야하므로 단일 변수를 사용합니다. 따라서 공간 복잡성은 일정합니다.

Pow (x, n) Leetcode 솔루션에 대한 최적화 된 접근 방식  

최적화 된 접근 방식은 빠른 모듈로 지수화 알고리즘을 사용합니다. 재귀 적 또는 반복적으로 빠른 모듈로 지수화를 구현할 수 있습니다. 빠른 모듈로 지수화에서 우리는 2의 거듭 제곱으로 밑수를 곱합니다. 이것은 우리가 계속해서 밑수를 곱한다는 것을 의미합니다. 따라서 첫 번째 단계에서 밑변은 그 자체의 제곱이됩니다. "b"로 표시된 밑을 가정 해 봅시다. 따라서 첫 번째 단계에서는 b ^ 2가되고, 다음 단계에서는 b ^ 4, b ^ 8, b ^ 16 등이됩니다. 이제 우리는 지수의 3에 해당하는 기본 거듭 제곱 만 곱합니다. 따라서 지수를 이진 형식으로 변환하고 지수 이진 형식에 따라 기본을 계속 곱하십시오. 예를 들어 6 ^ 3을 계산합니다. 여기서 base = 6, exponent = 6. 110을 이진 형식으로 변환하면 1이됩니다. 이제 첫 번째 단계에서 지수에 6이 있는지 확인합니다. 0은 첫 번째 최하위 비트로 2이 있으므로이를 건너 뜁니다. b ^ 6가됩니다. 이제 1은 두 번째 최하위 비트로 2을 가지므로 b ^ 2를 답에 곱합니다. 이제 답은 b ^ 2와 같습니다. 그러면 밑이 b ^ 4가됩니다. 6은 1 번째 최하위 비트로 3을 가지므로 b ^ 4를 답에 곱합니다. 이제 답은 b ^ 2 * b ^ 4 = b ^ 6이됩니다. 그리고 이것이 우리가 원했던 것입니다. 알고리즘 구현 방법을 찾으려면 아래 구현을 확인하십시오.

참조
스크램블 문자열

Pow (x, n) Leetcode 솔루션에 최적화 된 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    while(n>0){
        if(n&1)
            ans *= x;
        x = x*x;
        n = n>>1;
    }
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        while (n>0){
            if(n%2 == 1) ans = ans*x;
            x = x*x;
            n = n>>1;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024

복잡성 분석

시간 복잡성

O (logN), 베이스에 대한 지수를 계산하는 데 로그 시간이 걸리는 빠른 모듈로 지수를 사용했기 때문입니다. 또한 시간 복잡성을 직관적으로 찾을 수 있습니다. 지수를 0이 될 때까지 나누었으므로 필요한 시간은 logN에 따라 달라집니다. 여기서 N은 지수입니다.

공간 복잡성

O (1), 답을 저장하기 위해 단일 변수를 사용했기 때문에 공간 복잡도는 일정합니다.