Pow (x, n) פתרון Leetcode


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ Asana בלומברג eBay פייסבוק גולדמן זאקס Google לינקדין מיקרוסופט אורקל פייפאל סופר VMware מעבדות וולמארט
חיפוש בינארי מתמטיקה

הבעיה "Pow (x, n) Solution 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. בהתחשב באילוצים אלה אנו יכולים לכתוב כקוד כוח בוטה עם הדמיית הכפל של זמני האקספוננט הבסיסיים.

קוד לפתרון 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), מכיוון שעלינו לאחסן את התשובה בלבד, אנו משתמשים במשתנה יחיד. לפיכך, מורכבות החלל קבועה.

גישה אופטימלית לפתרון Leetcode של Pow (x, n)

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

קוד אופטימלי לפתרון 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;
    while(n>0){
        if(n&1)
            ans *= x;
        x = x*x;
        n = n>>1;
    }
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

קוד ג'אווה

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), מכיוון שהשתמשנו במשתנה יחיד לאחסון התשובה, מורכבות החלל קבועה.