Pow (x, n) לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל אַסאַנאַ בלומבערג עבייַ facebook גאָלדמאַן סאַקס גוגל לינקעדין מייקראָסאָפֿט אָראַקל פּייַפּאַל ובער וומוואַרע וואַלמאַרט לאַבס
אַלגערידאַמז ביינערי זוכן קאָדירונג אינטערוויו interviewprep LeetCode LeetCodeSolutions מאַט

די פּראָבלעם "Pow (x, n) לעעטקאָדע סאַלושאַן" שטייט אַז איר האָט צוויי נומערן, איינער פון וואָס איז אַ פלאָוטינג פונט נומער און די אנדערע איז אַ גאַנץ נומער. דער גאנצער נומער דאַמאַנייץ די עקספּאָנענט און די באַזע איז די פלאָוטינג-נומער נומער. מיר זייַנען געזאָגט צו געפֿינען די ווערט נאָך יוואַליוייטינג די עקספּאָנענט איבער די באַזע. די באַזע קען זיין נעגאַטיוו, positive אָדער נול. דער עקספּאָנענט קען ליגן ערגעץ צווישן די ריי פון אַ גאַנץ נומער. מיר אויך האָבן אַ קאַנסטריינץ פֿאַר די פּראָדוקציע. דער רעזולטאַט וועט זיין ערגעץ צווישן -10000 צו +10000. לאָמיר נעמען עטלעכע ביישפילן.

Pow (x, n) לעעטקאָדע סאַלושאַן

בייַשפּיל  

Base: 2
Exponent: 10
Answer: 1024

דערקלערונג: זינט די ווערט פֿאַר 2 ^ 10 = 104, דערפאר דער ענטפער. דאָס קען אויך זיין אָפּגעשטעלט דורך ריפּעטיטיוו קייפל פון 2 10 מאל.

Base: 2
Exponent: -10
Answer: 0.00098

דערקלערונג: דער ענטפער איז געביטן ווייַל די ווערט פון די עקספּאָנענט איז אויך געביטן צו -10.

ברוט פאָרס אַפּפּראָאַטש  

די ברוט קראַפט צוגאַנג פֿאַר דעם פּראָבלעם Pow (x, n) Leetcode סאַלושאַן איז זייער פּשוט. מיר דאַרפֿן צו סימולירן די אָפּעראַציע פון ​​עוואַלואַטינג עקספּאָנענץ. א עקספּאָנענט קען זיין לייכט עוואַלואַטעד דורך מאַלטאַפּלייינג די באַזע עקספּאָנענט נומער פון מאָל. מיר קענען סימפּלי סימולירן דעם מיט אַ שלייף אין קיין פון אונדזער באַליבסטע פּראָגראַממינג שפּראַכן. איין זאַך צו טאָן איז ווינקל קאַסעס. ווען דער עקספּאָנענט איז גלייַך צו די מאַקסימום ווערט פון גאַנץ אָדער מינימום ווערט פון ינטעגער. ווען מיר האָבן עקספּאָנענט ווי די מינימום ווערט פון ינטאַדזשער, די ענטפער קענען זיין 1 אָדער 0. אויב די באַזע איז 1 אָדער -1, ווייל עקספּאָנענט ווי די מינימום ווערט פון גאַנץ נומער, וועט האָבן ענטפער ווי 1 אַנדערש 0. פּונקט אַזוי מיר קענען האָבן בלויז 1 מיט עקספּאָנענט ווי מאַקסימום ווערט פון ינטאַדזשער, ווייַל די קאַנסטריינט פון דער רעזולטאַט איז ווייטער 10000. קאָנסידערינג די קאַנסטריינץ מיר קענען שרייַבן ווי אַ ברוט קראַפט קאָד מיט סימיאַלייטינג די קייפל פון די באַזע עקספּאָנענט מאָל.

זע אויך
מבול פּלאָמבירן לעעטקאָדע

קאָד פֿאַר 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), ווייַל מיר שלייפן ביז מיר מערן די באַזע עקספּאָנענט מאָל. אזוי די צייט קאַמפּלעקסיטי איז לינעאַר.

ספעיס קאַמפּלעקסיטי

אָ (1), ווייַל מיר האָבן צו קראָם בלויז די ענטפער, מיר נוצן אַ איין בייַטעוודיק. אַזוי, די פּלאַץ קאַמפּלעקסיטי איז קעסיידערדיק.

אָפּטימיזעד אַפּפּראָאַטש פֿאַר Pow (X, N) Leetcode סאַלושאַן  

די אָפּטימיזעד צוגאַנג ניצט די שנעל מאָדולאָ עקספּאָונענשייישאַן אַלגערידאַם. מיר קענען ינסטרומענט שנעל מאָדולאָ עקספּאָנענטיאַטיאָן אָדער אויף אַ רעקורסיווע שטייגער אָדער יטעראַטיוולי. אין שנעל מאָדאָ עקספּאָנענטיאַטיאָן, מיר מערן די באַזע אין דער מאַכט פון 2. דורך דעם, מיר מענט אַז מיר האַלטן אויף מערינג די באַזע דורך זיך. אַזוי, אין דער ערשטער שריט, די באַזע איז סקווערד פון זיך. זאל ס רעכן די באַזע דינאָוטאַד דורך “b”. אַזוי אין דער ערשטער שריט, עס ווערט b ^ 2, אין דער ווייַטער שריט עס וועט ווערן b ^ 4, דעמאָלט b ^ 8, דעמאָלט b ^ 16, און אַזוי אויף. איצט מיר מערן בלויז די באַזע כוחות קאָראַספּאַנדינג צו די אין די עקספּאָנענט. דעריבער, גער עקספּאָנענט אין ביינערי פֿאָרמאַט און פאָרזעצן צו מאַלטאַפּלייינג די באַסעס לויט די עקספּאָנענט ביינערי פֿאָרמאַט. למשל, רעכענען 3 ^ 6. דאָ באַזע = 3, עקספּאָנענט = 6. קאָנווערטינג 6 אין ביינערי פֿאָרמאַט מאכט עס 110. איצט, אין דער ערשטער שריט, מיר קאָנטראָלירן אויב דער עקספּאָנענט האט 1. זינט 6 האט 0 ווי דער ערשטער לאָואַסט באַטייטיק ביסל, מיר האָפּקען עס און די באַזע ווערט ב ^ 2. איצט, 6 האט 1 ווי זייַן 2 לאָואַסט באַטייטיק ביסל, אַזוי מיר מערן b ^ 2 צו דעם ענטפער. איצט דער ענטפער איז גלייַך צו b ^ 2. דער באזע ווערט ב ^ 4. זינט 6 האט 1 ווי זייַן 3 לאָואַסט באַטייטיק ביסל, מיר מערן b ^ 4 צו דעם ענטפער. דער ענטפער ווערט איצט b ^ 2 * b ^ 4 = b ^ 6. און דאָס איז וואָס מיר געוואלט. קאָנטראָלירן די ימפּלאַמענטיישאַן אונטן צו געפֿינען ווי צו ינסטרומענט די אַלגערידאַם.

זע אויך
סקראַמבלע סטרינג

אָפּטימיזעד קאָד פֿאַר 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (לאָגן), ווייַל מיר געוויינט שנעל מאָדאָ עקספּאָנענטיאַטיאָן וואָס נעמט לאָגאַריטמיק צייט צו רעכענען די עקספּאָנענט איבער אַ באַזע. מיר קענען אויך ינטויטיוולי געפֿינען די קאַמפּלעקסיטי פון דער צייט. זינט מיר האָבן צעטיילט די עקספּאָנענט ביז עס איז 0. די צייט וואָס איז פארלאנגט איז אָפענגיק אויף logN, ווו N איז דער עקספּאָנענט.

ספעיס קאַמפּלעקסיטי

אָ (1), זינט מיר האָבן געוויינט אַ איין בייַטעוודיק צו קראָם דעם ענטפער, די פּלאַץ קאַמפּלעקסיטי איז קעסיידערדיק.