Pow (x, n) Leetcode шийдэл  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн asana Bloomberg Ebay Facebook-ийн Goldman Sachs Google-ийн LinkedIn Microsoft- Oracle-ийн PayPal Uber VMware Walmart лабораторууд
алгоритмууд Хоёртын хайлт кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions Математик

“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) Leetcode Solution шийдлийн хувьд харгис хүчний арга нь маш энгийн. Бид зөвхөн экспонентуудыг үнэлэх ажиллагааг дууриах хэрэгтэй. Үндсэн үзүүлэлтийг хэд дахин үржүүлснээр үзүүлэлтийг хялбархан үнэлэх боломжтой. Тиймээс бид үүнийг дуртай програмчлалын хэлнийхээ аль нэгэнд давталт ашиглан хялбархан дууриаж болно. Анхаарах зүйл бол булангийн хэргүүд юм. Илтгэгчийн аль нь бүхэл тоо буюу хамгийн бага утгатай тэнцүү байх үед бүхэл тоо. Хэрэв бид бүхэл тоонуудын хамгийн бага утга болох экспоненттэй бол хариулт нь 1 эсвэл 0 байж болно. Хэрэв суурь нь 1 эсвэл -1 бол бүхэл тооны хамгийн бага утга болох экспоненттэй бол өөрөөр 1 гэж хариулах болно. Үүнтэй адил бид зөвхөн 0 Бүтээгдэхүүний хязгаарлалт нь бүхэл тоон хамгийн дээд утга болох экспонентын хувьд 1-аас бага байна. Эдгээр хязгаарлалтыг харгалзан үндсэн экспонентын хугацааг үржүүлж дууриаж харгис хүчний код болгон бичиж болно.

мөн үзнэ үү
Үерийн дүүргэлт LeetCode

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 шийдлийн оновчтой арга  

Оновчтой арга нь хурдан модулийн экспоненциал алгоритмыг ашигладаг. Бид хурдан модулийн экспоненсацийг рекурсив хэлбэрээр эсвэл давталтаар хэрэгжүүлж болно. Хурдан модулийн экспоненциалд бид суурийг 2-ын хүчээр үржүүлдэг. Ингэснээр бид суурийг өөрөө үржүүлсээр байх болно гэсэн үг юм. Тиймээс эхний алхам дээр суурь нь өөрөө дөрвөлжин болно. Суурийг “b” гэж тэмдэглэсэн гэж үзье. Тиймээс эхний алхам дээр b ^ 2 болж, дараагийн шатанд b ^ 4, дараа нь b ^ 8, b ^ 16 гэх мэт болно. Одоо бид зөвхөн экспонентын хүчин чадалтай харгалзах үндсэн хүчийг үржүүлж байна. Тэгэхээр экспонентыг хоёртын форматаар хөрвүүлж, экспонентын хоёртын форматын дагуу суурийг үржүүлж байгаарай. Жишээлбэл, 3 ^ 6-г тооцоолох хэрэгтэй. Энд base = 3, exponent = 6. 6-ыг хоёртын форматаар хөрвүүлснээр үүнийг 110 болгоно. Одоо эхний шатанд экспонент 1 байгаа эсэхийг шалгана уу. b ^ 6 болно. Одоо 0 нь 2-ийг 6-р хамгийн бага утга болох тул хариултанд b ^ 1-ийг үржүүлнэ. Одоо хариулт b ^ 2-тэй тэнцүү байна. Үүний дараа суурь нь b ^ 2 болно. 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

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), Хариултыг хадгалахын тулд бид ганц хувьсагч ашигласан тул орон зайн нарийн төвөгтэй байдал тогтмол байна.