Pow (x, n) Leetcode Solution  


Რთული ტური საშუალო
ხშირად ეკითხებიან Adobe Amazon Apple ასანა Bloomberg eBay Facebook Goldman Sachs Google LinkedIn microsoft Oracle PayPal Uber VMware Walmart Labs
ალგორითმები ორობითი ძებნა კოდირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions მათემატიკის

პრობლემა ”Pow (x, n) Leetcode Solution” აცხადებს, რომ თქვენ გეძლევათ ორი რიცხვი, რომელთაგან ერთი არის მცურავი წერტილის ნომერი და მეორე მთელი რიცხვი. მთელი რიცხვი აღნიშნავს ექსპონენტს და ფუძე არის მცურავი წერტილის რიცხვი. გვეუბნებიან, რომ მნიშვნელობას მივაგნებთ ბაზისზე არსებული ექსპონენტის შეფასების შემდეგ. ფუძე შეიძლება იყოს უარყოფითი, დადებითი ან ნულოვანი. ექსპონენტს შეუძლია მოთავსდეს სადმე მთელი რიცხვის დიაპაზონში. ჩვენ ასევე გვაძლევენ შეზღუდვას გამომავალზე. გამომავალი იქნება -10000-დან +10000-მდე. მოდით, გადავხედოთ რამდენიმე მაგალითს.

Pow (x, n) Leetcode SolutionPin

მაგალითი  

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) კოდექსის ამოხსნის კოდი

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

ჯავის კოდი

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-ს აქვს პირველი ყველაზე დაბალი მნიშვნელოვანი ბიტი, ჩვენ გამოტოვებთ მას და ფუძეს ხდება b ^ 0. ახლა 2-ს აქვს მე -6 ყველაზე დაბალი მნიშვნელოვანი ბიტი, ასე რომ, ჩვენ ვამრავლებთ პასუხს b ^ 1. ახლა პასუხი ტოლია b ^ 2. ამის შემდეგ ფუძე ხდება b ^ 2. მას შემდეგ, რაც 2-ს აქვს 4, როგორც მე -6 ყველაზე დაბალი მნიშვნელოვანი ბიტი, ჩვენ ვამრავლებთ პასუხს b ^ 1. ახლა პასუხი ხდება b ^ 3 * b ^ 4 = b ^ 2. ეს ის იყო, რაც გვინდოდა. შეამოწმეთ ქვემოთ მოცემული განხორციელება, რათა იპოვოთ ალგორითმის დანერგვა.

იხილეთ ასევე
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

ჯავის კოდი

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), რადგან პასუხის შესანახად გამოვიყენეთ ერთი ცვლადი, სივრცის სირთულე მუდმივია.