Pow (x, n) Solution Leetcode  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon себ Асано Блумберг мехаранд Facebook Голдман Sachs Google LinkedIn Microsoft Oracle PayPal Uber VMware Озмоишгоҳҳои Walmart
алгоритмҳо Ҷустуҷӯи бинарӣ рамзгузорӣ мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions Матем

Масъалаи "Sol (x, n) Leetcode Solution" мегӯяд, ки ба шумо ду рақам дода мешавад, ки яке рақами нуқтаи шинокунанда ва дигаре бутун аст. Бутун нишондиҳандаро нишон медиҳад ва асос рақами нуқтаи шинокунанда мебошад. Ба мо гуфта мешавад, ки пас аз арзёбии нишондиҳанда аз болои пойин арзиши онро пайдо кунем. Пойгоҳ метавонад манфӣ, мусбат ё сифр бошад. Нишондиҳанда метавонад дар ҳама ҷо дар байни диапазони бутун ҷойгир шавад. Ба мо инчунин дар натиҷаи маҳдудият дода мешавад. Натиҷа дар ҳама ҷо аз -10000 то +10000 хоҳад буд. Пас, биёед ба якчанд мисол назар кунем.

Pow (x, n) Solution 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 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;
    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), зеро мо давр мезанем, то даме ки нишондиҳандаҳои асосиро зарбҳои зарбро зиёд кунем. Ҳамин тариқ, мураккабии вақт хатӣ аст.

Мураккабии фазо

О (1), зеро мо бояд танҳо ҷавобро нигоҳ дорем, мо як тағирёбандаро истифода мебарем. Ҳамин тариқ, мураккабии фазо доимӣ аст.

Усули оптимизатсия барои ҳалли Pow (x, n) Leetcode  

Усули оптимизатсияшуда алгоритми экспоненсатсияи модулро зуд истифода мебарад. Мо метавонем экспедитатсияи модулҳои зудро ба тариқи рекурсивӣ ё такрорӣ амалӣ кунем. Дар экспонентацияи модули зуд, мо пойгоҳро бо қудрати 2 афзоиш медиҳем. Бо ин, дар назар доштем, ки пойгоҳро худ ба худ афзоиш медиҳем. Ҳамин тавр, дар қадами аввал, пойгоҳ аз худ чоркунҷа мешавад. Фарз мекунем, ки пойгоҳе, ки бо "b" нишон дода шудааст. Пас дар қадами аввал он b ^ 2, дар қадами оянда b ^ 4, баъд b ^ 8, баъд b ^ 16 ва ғайра мешавад. Ҳоло, мо танҳо қудратҳои асосиеро, ки ба нишондиҳандаҳои дар дараҷа мувофиқ мебошанд, зарб мекунем. Ҳамин тавр, нишондиҳандаро ба формати дуӣ табдил диҳед ва афзоиш додани пойгоҳҳоро мувофиқи формати дараҷаи бинарӣ идома диҳед. Масалан, 3 ^ 6 ҳисоб кунед. Дар ин ҷо base = 3, exponent = 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 мешавад. Ва ин ҳамон чизест, ки мо мехостем. Барои амалӣ кардани алгоритм, татбиқи зерро санҷед.

ҳамчунин нигаред
Сатр Scramble

Рамзи беҳтарин барои 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), зеро мо экспедитатсияи модулии зудро истифода бурдем, ки барои ҳисоб кардани нишондиҳанда аз рӯи замин вақти логарифмиро талаб мекунад. Мо инчунин метавонем беихтиёрона мураккабии вақтро ёбем. Азбаски мо нишондиҳандаро то он даме ки тақсим кардем, тақсим кардем. Ҳамин тариқ, вақти зарурӣ аз logN вобаста аст, ки дар он N нишондиҳанда мебошад.

Мураккабии фазо

О (1), азбаски мо барои тағир додани ҷавоб як тағирёбандаро истифода кардем, мураккабии фазо доимист.