Pow (x, n) Leetcode шешімі


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon алма Asana Bloomberg еВау Facebook Голдман Сакс Google LinkedIn Microsoft Oracle PayPal қиятын 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-ға өзгертілді.

Күш қолдану тәсілі

Power (x, n) Leetcode Solution шешіміне қатал күш қолдану әдісі өте қарапайым. Көрсеткіштерді бағалау операциясын модельдеуіміз керек. Көрсеткішті негізгі дәрежелік көрсеткішті бірнеше рет көбейту арқылы оңай бағалауға болады. Сонымен, біз кез-келген сүйікті бағдарламалау тілдеріндегі циклды пайдаланып, оны оңай модельдей аламыз. Назар аударатын бір нәрсе - бұрыштық жағдай. Кез-келген дәреже бүтін санның немесе минималды мәннің максималды мәніне тең болғанда бүтін сан. Егер біз бүтін санның минималды мәні ретінде көрсеткішке ие болсақ, онда жауап 1 немесе 0 болуы мүмкін. Егер негіз 1 немесе -1 болса, бүтін санның минималды мәні ретінде дәрежеге ие болса, әйтпесе 1-ге тең болады, сол сияқты бізде тек 0 болуы мүмкін. бүтін санның максималды мәні ретінде көрсеткішпен, шығыс шектелуіне байланысты 1-ден төмен. Осы шектеулерді ескере отырып, негізгі дәрежелік уақытты көбейтуді имитациялай отырып, қатал күш коды ретінде жаза аламыз.

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 (N), өйткені біз негізгі көрсеткіштік уақытты көбейткенше цикл жасаймыз. Осылайша уақыттың күрделілігі сызықтық болып табылады.

Ғарыштың күрделілігі

O (1), біз тек жауабын сақтауымыз керек болғандықтан, біз бір айнымалыны қолданамыз. Сонымен, ғарыштың күрделілігі тұрақты болады.

Pow (x, n) Leetcode Solution үшін оңтайландырылған тәсіл

Оңтайландырылған тәсіл жылдам модульді дәрежелеу алгоритмін қолданады. Біз жылдам модульді дәрежелеуді рекурсивті түрде немесе итеративті түрде жүзеге асыра аламыз. Жылдам модулді дәрежелеуде біз базисті 2 дәрежесінде көбейтеміз, осымен біз негізді өздігінен көбейтуді жалғастырамыз дегенді білдірдік. Сонымен, бірінші қадамда базаның өзі квадратқа айналады. «B» деп белгіленген негізді алайық. Сонымен бірінші қадамда ол b ^ 2, келесі қадамда b ^ 4, сосын b ^ 8, сосын b ^ 16 және т.с.с. Енді, біз тек дәрежелік дәрежеге сәйкес келетін негізгі қуаттарды көбейтеміз. Сонымен, көрсеткішті екілік форматқа түрлендіріп, негіздік көрсеткіштік екілік форматқа сәйкес көбейте беріңіз. Мысалы, 3 ^ 6 есептеңіз. Мұнда негіз = 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 болады. Бұл біздің қалағанымыз болды. Алгоритмді қалай жүзеге асыруға болатындығын білу үшін төмендегі іске асыруды тексеріңіз.

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), жауабын сақтау үшін бір айнымалыны қолданғандықтан, кеңістіктің күрделілігі тұрақты.