Решение Powet (x, n) Leetcode


Ниво на тешкотија Медиум
Често прашувано во Adobe Амазон Јаболко Асана Блумберг eBay Facebook Голдман Сакс Google Скопје Мајкрософт Oracle PayPal Uber VMware Лаборатории Walmart
Бинарно пребарување Математика

Проблемот „Pow (x, n) Leetcode Solution“ наведува дека ви се дадени два броја, од кои едниот е број со подвижна точка и другиот цел број. Целиот број го означува експонентот и основата е број со подвижна точка. Ни е речено да ја најдеме вредноста откако ќе го оцениме експонентот над основата. Основата може да биде негативна, позитивна или нула. Експонентот може да лежи каде било помеѓу опсегот на цел број. Исто така, ни се дава ограничување на излезот. Излезот ќе биде помеѓу -10000 и +10000. Значи, да погледнеме неколку примери.

Решение Powet (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) Решение за лет код е многу едноставен. Треба само да ја симулираме работата на проценка на експонентите. Експонент лесно може да се процени со множење на основниот експонент неколку пати. Значи, можеме лесно да го симулираме ова користејќи јамка во кој било од нашите омилени програмски јазици. Едно нешто што треба да се забележи, се аголните случаи. Кога или експонентот е еднаков на максималната вредност на цел број или минималната вредност на број. Кога имаме експонент како минимална вредност на цел број, одговорот може да биде или 1 или 0. Ако основата е 1 или -1, имајќи го експонентот како минимална вредност на цел број, ќе има одговор како 1 во спротивно 0. Слично на тоа, можеме да имаме само 1 со експонент како максимална вредност на цел број, поради ограничувањето на излезот е под 10000. Со оглед на овие ограничувања, можеме да напишеме како код за брутална сила со симулирање на множење на времињата на основните експоненти.

Код за решение на буквата Pow (x, n)

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

Java код

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

Анализа на сложеност

Временска комплексност

НА), затоа што јамка се додека не ги умножиме експонентните времиња на основата. Така, сложеноста на времето е линеарна.

Комплексноста на просторот

О (1), бидејќи мораме да го зачуваме само одговорот, ние користиме единствена променлива. Така, комплексноста на просторот е постојана.

Оптимизиран пристап за решение (Leetcode) на Pow (x, n)

Оптимизираниот пристап го користи алгоритмот за брзо експонирање на модулите. Можеме да спроведеме брза експоненцијација на модулот или на рекурзивен начин или итеративно. При експоненцијација на брз модул, ние ја множиме основата во моќност од 2. Со ова, мислевме дека продолжуваме да ја множиме основата сама по себе. Значи, во првиот чекор, основата станува квадрат за себе. Да претпоставиме дека основата е означена со „b“. Значи, во првиот чекор, станува b ^ 2, во следниот чекор ќе стане b ^ 4, потоа b ^ 8, потоа b ^ 16 и така натаму. Сега, ние ги множиме само основните моќности што одговараат на оние во експонентот. Значи, претворете го експонентот во бинарен формат и продолжете да ги множите основите според бинарниот формат на експонентот. На пример, пресметајте 3 ^ 6. Овде основа = 3, експонент = 6. Претворањето на 6 во бинарен формат го прави 110. Сега, во првиот чекор, проверуваме дали експонентот има 1. Бидејќи 6 го има 0 како прв најнизок значаен бит, ние го прескокнуваме тоа и основата станува б ^ 2. Сега, 6 го има 1 како втор најнизок значаен бит, така што множиме b ^ 2 на одговорот. Сега одговорот е еднаков на b ^ 2. Основата тогаш станува b ^ 2. Бидејќи 4 го има 6 како трет најнизок значаен бит, ние множиме b ^ 1 на одговорот. Одговорот сега станува b ^ 3 * b ^ 4 = b ^ 2. И ова беше она што го сакавме. Проверете ја имплементацијата подолу за да пронајдете како да го имплементирате алгоритмот.

Оптимизиран код за решение (Leetcode) на Pow (x, n)

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

Java код

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

Анализа на сложеност

Временска комплексност

О (најаваН), затоа што користевме експоненцијација на брз модул, за што е потребно логаритамско време за да се пресмета експонентот над основата. Ние исто така можеме интуитивно да ја пронајдеме временската комплексност. Бидејќи го поделивме експонентот се додека тој не стане 0. Така, потребното време зависи од logN, каде што N е експонент.

Комплексноста на просторот

О (1), бидејќи користевме единствена променлива за складирање на одговорот, комплексноста на просторот е постојана.