Рашэнне Pow (x, n) Leetcode


Узровень складанасці серада
Часта пытаюцца ў Саман амазонка яблык асана Bloomberg eBay facebook Goldman Sachs Google LinkedIn Microsoft Аракул PayPal Uber VMware Лабараторыі Walmart
Двайковы пошук Матэматыка

У задачы «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. Улічваючы гэтыя абмежаванні, мы можам напісаць як грубы код з імітацыяй множання асноўных паказчыкаў.

Код для рашэння 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;
    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), паколькі мы павінны захоўваць толькі адказ, мы выкарыстоўваем адну зменную. Такім чынам, касмічная складанасць пастаянная.

Аптымізаваны падыход да рашэння Leetcode Pow (x, n)

Аптымізаваны падыход выкарыстоўвае алгарытм хуткага ўзмацнення ступені. Мы можам рэалізаваць хуткае ўзмацненне па ступені ступені альбо рэкурсіўна, альбо ітэратыўна. Хутка па модуляванаму ўзмацненню ступені мы памнажаем базу ў ступені 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. І гэта было тое, што мы хацелі. Праверце рэалізацыю ніжэй, каб даведацца, як рэалізаваць алгарытм.

Аптымізаваны код для рашэння 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

Аналіз складанасці

Складанасць часу

O (logN), таму што мы выкарыстоўвалі хуткае ўзмацненне ступені, якое патрабуе лагарыфмічнага часу, каб вылічыць паказчык па базе. Мы таксама можам інтуітыўна знайсці складанасць часу. Паколькі мы падзялілі паказчык, пакуль ён не стаў 0. Такім чынам, неабходны час залежыць ад logN, дзе N - паказчык.

Касмічная складанасць

O (1), паколькі мы выкарыстоўвалі адну зменную для захоўвання адказу, складанасць прасторы сталая.