Pow (x, n) Leetcode решение


Ниво на трудност M
Често задавани в Кирпич Амазонка ябълка Асана Bloomberg иБей Facebook Goldman Sachs Google LinkedIn Microsoft Оракул PayPal Uber VMware Walmart Labs
Двоично търсене Математически

Проблемът „Pow (x, n) Leetcode Solution“ гласи, че са ви дадени две числа, едно от които е число с плаваща запетая, а друго цяло число. Цялото число означава степента, а основата е числото с плаваща запетая. Казва ни се да намерим стойността, след като изчислим степента над основата. Базата може да бъде отрицателна, положителна или нулева. Експонентата може да лежи навсякъде между диапазона на цяло число. Също така ни е дадено ограничение за изхода. Изходът ще бъде някъде между -10000 до +10000. Така че, нека да разгледаме няколко примера.

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. Като се имат предвид тези ограничения, можем да напишем като груба сила код със симулиране на умножението на базовите експонентни времена.

Код за решение на 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

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

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

Сложност във времето

НА), защото циклираме, докато умножим основните експонентни времена. По този начин сложността на времето е линейна.

Сложност на пространството

O (1), тъй като трябва да съхраняваме само отговора, използваме една променлива. По този начин космическата сложност е постоянна.

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

Оптимизираният подход използва алгоритъма за бързо модулиране на степенуване. Можем да реализираме бързо модулиране на степенуване или по рекурсивен начин, или итеративно. С бързо модулирано степенуване умножаваме основата в степен 2. С това имахме предвид, че продължаваме да умножаваме основата сама по себе си. И така, в първата стъпка основата става на квадрат от себе си. Да предположим, че основата, обозначена с „b“. Така че в първата стъпка тя става b ^ 2, в следващата стъпка ще стане b ^ 4, след това b ^ 8, след това b ^ 16 и т.н. Сега умножаваме само базовите степени, съответстващи на тези в степента. Така че, конвертирайте експонента в двоичен формат и продължете да умножавате базите според експонентен двоичен формат. Например изчислете 3 ^ 6. Тук base = 3, експонента = 6. Преобразуването на 6 в двоичен формат го прави 110. Сега, в първата стъпка проверяваме дали степента има 1. Тъй като 6 има 0 като първия си най-нисък значителен бит, го пропускаме и основата става b ^ 2. Сега 6 има 1 като втория си най-нисък значим бит, така че умножаваме b ^ 2 към отговора. Сега отговорът е равен на b ^ 2. Тогава основата става b ^ 2. Тъй като 4 има 6 като 1-тия си най-нисък значим бит, умножаваме b ^ 3 към отговора. Отговорът сега става b ^ 4 * b ^ 2 = b ^ 4. И това искахме. Проверете изпълнението по-долу, за да намерите как да внедрите алгоритъма.

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

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

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

Сложност във времето

O (logN), тъй като използвахме бързо модулиране на степенуване, което отнема логаритмично време за изчисляване на степента на база. Можем също така интуитивно да намерим сложността на времето. Тъй като сме разделили степента, докато тя стане 0. Така необходимото време зависи от logN, където N е степента.

Сложност на пространството

O (1), тъй като сме използвали една променлива за съхраняване на отговора, сложността на пространството е постоянна.