Pow (x, n) Рішення Leetcode  


Рівень складності Medium
Часто запитують у саман Амазонка Apple Асана Bloomberg eBay Facebook Goldman Sachs Google LinkedIn Microsoft оракул PayPal Убер VMware Лабораторії Walmart
алгоритми Двійковий пошук кодування інтерв'ю інтерв'юпідготовка LeetCode LeetCodeSolutions Математика

У задачі “Pow (x, n) Leetcode Solution” зазначено, що вам дано два числа, одне з яких - число з плаваючою крапкою, а інше - ціле число. Ціле число позначає показник ступеня, а основа - число з плаваючою точкою. Нам пропонують знайти значення після обчислення показника ступеня над основою. База може бути від’ємною, додатною або нульовою. Показник може знаходитись де завгодно між діапазоном цілого числа. Нам також дано обмеження на вихід. Вихід буде в діапазоні від -10000 до +10000. Отже, давайте розглянемо кілька прикладів.

Pow (x, n) Рішення LeetcodePin

Приклад  

Base: 2
Exponent: 10
Answer: 1024

Пояснення: Оскільки значення 2 ^ 10 = 104, звідси і відповідь. Це також можна перевірити шляхом повторного множення в 2 10 разів.

Base: 2
Exponent: -10
Answer: 0.00098

Пояснення: Відповідь змінено, оскільки значення показника ступеня також змінено на -10.

Підхід грубої сили  

Грубий підхід до проблеми Poet (x, n) Leetcode Solution дуже простий. Нам потрібно просто імітувати операцію оцінювання показників. Показник можна легко оцінити, помноживши базовий показник на кількість разів. Отже, ми можемо легко змоделювати це за допомогою циклу на будь-якій улюбленій мові програмування. Зауважимо одне - це кутові кейси. Коли або показник ступеня дорівнює максимальному цілому чи мінімальному значенню ціле. Коли ми маємо показник степеня як мінімальне значення цілого числа, відповідь може бути або 1, або 0. Якщо основа дорівнює 1 або -1, маючи показник як мінімальне значення цілого числа, буде відповідати як 1, інакше 0. Аналогічно ми можемо мати лише 1 з показником як максимальне значення цілого числа, оскільки обмеження на виході нижче 10000. Враховуючи ці обмеження, ми можемо записати код грубої сили з імітацією множення базового часу експоненти.

Дивись також
Потоп Заповніть LeetCode

Код рішення Poet (x, n) Leetcode

Код С ++

#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 (N), тому що ми циклічні, поки не помножимо базові показники експоненти. Таким чином, складність часу є лінійною.

Складність простору

O (1), оскільки ми маємо зберігати лише відповідь, ми використовуємо одну змінну. Таким чином, космічна складність постійна.

Оптимізований підхід до рішення Poet (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 як 2-й найнижчий значущий біт, тому ми множимо b ^ 2 до відповіді. Тепер відповідь дорівнює b ^ 2. Тоді основа стає b ^ 4. Оскільки 6 має 1 як 3-й найнижчий значущий біт, ми множимо b ^ 4 до відповіді. Відповідь тепер стає b ^ 2 * b ^ 4 = b ^ 6. І це було те, що ми хотіли. Перевірте реалізацію нижче, щоб дізнатись, як реалізувати алгоритм.

Дивись також
Скремблюючий рядок

Оптимізований код для рішення Poet (x, n) Leetcode

Код С ++

#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), оскільки ми використовували одну змінну для зберігання відповіді, складність простору є постійною.