Pow (x, n) Leetcode Solution  


Кыйынчылык деңгээли орто
Көп суралган Adobe Amazon алма асана Bloomberg Окшош Facebook Goldman Sachs Гугл LinkedIn Microsoft Oracle PayPal Uber VMware Walmart Labs
Алгоритмы Binary Search коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions Math

"Pow (x, n) Leetcode Solution" маселеси сизге эки сан берилгенин, алардын бири өзгөрүлмө чекиттүү, экинчиси бүтүн сан экендигин билдирет. Бүтүн көрсөткүчтү көрсөтөт, ал эми калкыма чекит саны болот. Көрсөткүчтү базанын үстүнөн баалагандан кийин баасын табуу керектиги айтылды. Негиз терс, оң же нөл болушу мүмкүн. Көрсөткүч бүтүндөй бир диапазондун аралыгында болушу мүмкүн. Ошондой эле, бизге чыгууга чектөө коюлган. Чыгуу -10000 ден +10000ге чейин болот. Ошентип, бир нече мисалдарды карап көрөлү.

Pow (x, n) Leetcode Solutionтөөнөч

мисал  

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) 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 Code

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 ^ 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ге ээ болгондуктан, биз жоопко b ^ 3 көбөйтүп жатабыз. Жооп эми b ^ 4 * b ^ 2 = b ^ 4 болуп калат. Бул биздин эңсегенибиз эле. Алгоритмди кандайча ишке ашыруу керектигин билүү үчүн төмөндөгү ишке ашырууну текшериңиз.

ошондой эле
Scramble String

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

Комплекстик анализ

Убакыт татаалдыгы

O (logN), анткени биз көрсөткүчтү эсептөө үчүн логарифмдик убакытты талап кылган тез модулдук көрсөткүчтү колдондук. Ошондой эле, убакыттын татаалдыгын интуитивдүү түрдө таба алабыз. Биз көрсөткүчтү 0 болгонго чейин бөлгөндүктөн, талап кылынган убакыт logNге көз каранды, мында N көрсөткүч.

Космостун татаалдыгы

O (1), жоопту сактоо үчүн бир гана өзгөрмө колдонгонубуз үчүн, мейкиндиктин татаалдыгы туруктуу.