Pow (x, n) Leetcode լուծում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon խնձոր Asana Bloomberg eBay 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) խնդրի լուծման կոպիտ մոտեցումը շատ պարզ է: Պետք է պարզապես մոդելավորել էքսպոնենտների գնահատման գործողությունը: Էքսպոնենտը հեշտությամբ կարելի է գնահատել բազային արտահայտիչի բազմակի բազմապատկումը: Այսպիսով, մենք կարող ենք հեշտությամբ նմանակել սա ՝ օգտագործելով օղակ մեր նախընտրած ծրագրավորման ցանկացած լեզվով: Մի բան պետք է նշել, որ անկյունային դեպքերն են: Երբ կամ ցուցիչը հավասար է ամբողջ թիվի կամ նվազագույն արժեքի առավելագույն արժեքին ամբողջ թիվ, Երբ մենք ունենք ցուցիչ որպես ամբողջ թիվի նվազագույն արժեք, պատասխանը կարող է լինել 1 կամ 0: Եթե հիմքը 1 է կամ -1, ունենալով էքսոնտորը որպես ամբողջ թիվի նվազագույն արժեք, ապա պատասխանը կլինի 1-ի փոխարեն: Նմանապես, մենք կարող ենք ունենալ միայն 0 էքսպոնենտով ՝ որպես ամբողջ թիվի առավելագույն արժեք, ելքի վրա կաշկանդվածության պատճառով 1-ից ցածր է: Հաշվի առնելով այս սահմանափակումները, մենք կարող ենք գրել որպես կոպիտ ուժի կոդ ՝ բազային ցուցիչ ժամանակների բազմապատկումը մոդելավորելով:

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք օղակում ենք այնքան ժամանակ, քանի դեռ բազային ցուցիչ ժամանակները չենք բազմապատկել: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

O (1), քանի որ մենք պետք է պահենք միայն պատասխանը, մենք օգտագործում ենք մեկ փոփոխական: Այսպիսով, տիեզերական բարդությունը կայուն է:

Pow (x, n) Leetcode լուծման օպտիմիզացված մոտեցում

Օպտիմիզացված մոտեցումն օգտագործում է արագ մոդուլի ցուցադրության ալգորիթմը: Մենք կարող ենք իրականացնել արագ մոդուլի ցուցադրություն կամ ռեկուրսիվ եղանակով, կամ կրկնօրինակում: Արագ մոդուլի ցուցադրության դեպքում մենք բազմապատկում ենք հիմքը 2-ի հզորության մեջ: Դրանով մենք նկատի ունեինք, որ շարունակում ենք բազային բազմապատկել ինքնին: Այսպիսով, առաջին քայլում հիմքը քառակուսի է դառնում ինքն իրենից: Ենթադրենք «բ» -ով նշվող հիմքը: Այսպիսով, առաջին քայլում այն ​​դառնում է 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (logN), որովհետև մենք օգտագործեցինք արագ մոդուլի ցուցադրություն, որը բազարի վրա կատարիչը հաշվարկելու համար տևում է լոգարիթմական ժամանակ: Մենք կարող ենք նաև ինտուիտիվ կերպով գտնել ժամանակի բարդությունը: Քանի որ մենք բաժանել ենք ցուցիչը մինչև այն դառնալը 0. Այսպիսով, պահանջվող ժամանակը կախված է logN- ից, որտեղ N- ը ցուցիչ է:

Տիեզերական բարդություն

O (1), քանի որ պատասխանը պահելու համար մենք օգտագործել ենք մեկ փոփոխական, տարածության բարդությունը կայուն է: