ផូ (x, n) ដំណោះស្រាយឡេឡេកូដ  


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម Asana ទីភ្នាក់ងារ Bloomberg របស់ eBay Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle បានតាមរយៈការ Uber VMware បន្ទប់ពិសោធន៍វ៉លម៉ាត
ក្បួនដោះស្រាយ ការស្វែងរកគោលពីរ ការសរសេរកូដ សំភាសន៍ កិច្ចសម្ភាសន៍ LeetCode LeetCodeSolutions គណិតវិទ្យា

បញ្ហា“ ផូ (x, n) ដំណោះស្រាយឡេឡេកូដ” បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់លេខពីរដែលលេខមួយជាលេខអណ្តែតទឹកនិងលេខគត់។ ចំនួនគត់បង្ហាញនិទស្សន្តនិងគោលគឺជាលេខអណ្តែត។ យើងត្រូវបានគេប្រាប់ឱ្យរកតម្លៃបន្ទាប់ពីវាយតម្លៃនិទស្សន្តលើមូលដ្ឋាន។ មូលដ្ឋានអាចជាអវិជ្ជមានវិជ្ជមានឬសូន្យ។ និទស្សន្តអាចស្ថិតនៅគ្រប់ទីកន្លែងរវាងជួរនៃចំនួនគត់។ យើងក៏ត្រូវបានផ្តល់នូវឧបសគ្គចំពោះលទ្ធផល។ លទ្ធផលនឹងមាននៅគ្រប់ទីកន្លែងចន្លោះ -១០០០០ ទៅ + ១០០០០ ។ ដូច្នេះតោះមើលឧទាហរណ៍ខ្លះ។

ផូ (x, n) ដំណោះស្រាយឡេឡេកូដ

ឧទាហរណ៍  

Base: 2
Exponent: 10
Answer: 1024

ការពន្យល់: ចាប់តាំងពីតម្លៃសម្រាប់ 2 ^ 10 = 104 ដូច្នេះចម្លើយ។ នេះក៏អាចត្រូវបានត្រួតពិនិត្យដោយគុណដដែលៗ ២ ១០ ដង។

Base: 2
Exponent: -10
Answer: 0.00098

ការពន្យល់៖ ចម្លើយត្រូវបានផ្លាស់ប្តូរពីព្រោះតម្លៃនិទស្សន្តក៏ត្រូវបានប្តូរទៅ -១០ ។

វិធីសាស្រ្ត Brute Force  

វិធីសាស្រ្តកម្លាំងដុសខាត់សម្រាប់បញ្ហាផូវ (x, n) ឡេឡេហ្សិចសូលុយស្យុងគឺសាមញ្ញណាស់។ យើងត្រូវគ្រាន់តែក្លែងធ្វើប្រតិបត្តិការវាយតម្លៃនិទស្សន្ត។ និទស្សន្តអាចត្រូវបានវាយតម្លៃយ៉ាងងាយដោយគុណចំនួននិទស្សន្តមូលដ្ឋាន។ ដូច្នេះយើងអាចក្លែងធ្វើវាយ៉ាងងាយស្រួលដោយប្រើរង្វិលជុំនៅក្នុងភាសាកម្មវិធីដែលយើងចូលចិត្ត។ រឿងមួយដែលត្រូវកត់សម្គាល់គឺករណីជ្រុង។ នៅពេលនិទស្សន្តស្មើនឹងតម្លៃអតិបរមានៃចំនួនគត់ឬតម្លៃអប្បបរមានៃ integer។ នៅពេលដែលយើងមាននិទស្សន្តជាតម្លៃអប្បបរមានៃចំនួនគត់ចម្លើយអាចជា ១ ឬ ០ បើមូលដ្ឋានគឺ ១ ឬ ១ មាននិទស្សន្តជាតម្លៃអប្បបរមារបស់លេខគត់នឹងមានចម្លើយដូច ១ បើមិនដូច្នេះទេ ០ ។ ស្រដៀងគ្នាដែរយើងអាចមាន ១ ដោយនិទស្សន្តជាតម្លៃអតិបរិមានៃចំនួនគត់ពីព្រោះឧបសគ្គនៅលើលទ្ធផលគឺទាបជាង ១០០០០។ ដោយពិចារណាលើឧបសគ្គទាំងនេះយើងអាចសរសេរកូដកម្លាំងដុសខាត់ជាមួយនឹងការធ្វើត្រាប់តាមគុណនៃគុណស្វ័យគុណនៃមូលដ្ឋាន។

សូម​មើល​ផង​ដែរ
ទឹកជំនន់លិចឡេតខេត

លេខកូដសំរាប់ផូ (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), ពីព្រោះយើងរង្វិលជុំរហូតដល់យើងគុណនឹងស្វ័យគុណអិចស្ប៉ូណង់ចែកមូលដ្ឋាន។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ពីព្រោះយើងត្រូវរក្សាទុកតែចម្លើយយើងប្រើអថេរតែមួយ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺថេរ។

វិធីសាស្រ្តល្អប្រសើរបំផុតសម្រាប់ផូល (x, n) ដំណោះស្រាយឡេឡេកូដ  

វិធីសាស្រ្តដែលប្រសើរបំផុតប្រើក្បួនដោះស្រាយនិទស្សន្តអក្សរកាត់ម៉ូទ័ររហ័ស។ យើងអាចអនុវត្តនិទស្សន្តម៉ូឌុលយ៉ាងរហ័សទាំងក្នុងការនិយាយឡើងវិញឬដដែលៗ។ នៅក្នុងនិទស្សន្តម៉ូឌុលលឿនយើងគុណនឹងមូលដ្ឋានដោយស្វ័យគុណ ២ ។ ដោយនេះយើងមានន័យថាយើងបន្តគុណនឹងមូលដ្ឋានដោយខ្លួនវា។ ដូច្នេះនៅជំហានដំបូងមូលដ្ឋានក្លាយជាការ៉េនៃខ្លួនវា។ ឧបមាថាមូលដ្ឋានតាងដោយ“ ខ” ។ ដូច្នេះក្នុងជំហ៊ានដំបូងវាក្លាយជាខ ^ ២ នៅជំហ៊ានបន្ទាប់វានឹងក្លាយជា b ^ 2 បន្ទាប់មក b ^ 2 បន្ទាប់មក b ^ 4 ។ ល។ ឥលូវនេះយើងគុណតែអំណាចមូលដ្ឋានទាក់ទងនឹងស្វ័យគុណក្នុងនិទស្សន្ត។ ដូច្នេះចូរបំលែងនិទស្សន្តជាទ្រង់ទ្រាយគោលពីរហើយបន្តគុណនឹងមូលដ្ឋានយោងតាមទ្រង់ទ្រាយគោលពីរនិទស្សន្ត។ ឧទាហរណ៍គណនា 8 ^ 16 ។ ត្រង់នេះមូលដ្ឋាន = ៣ និទស្សន្ត = ៦ ។ ការបម្លែង ៦ ជាទ្រង់ទ្រាយគោលពីរធ្វើឱ្យវា ១១០។ ឥឡូវជំហានដំបូងយើងពិនិត្យមើលថានិទស្សន្តមាន ១ ។ ចាប់តាំងពី ៦ មាន ០ ជាប៊ីតសំខាន់ទាបបំផុតយើងរំលងវានិងគោល ក្លាយជា b ^ 3 ។ ឥឡូវ ៦ មាន ១ ជាប៊ីតសំខាន់ទាបបំផុតទី ២ របស់វាដូច្នេះយើងគុណនឹងខ ២ នឹងចម្លើយ។ ឥឡូវចម្លើយគឺស្មើនឹង b ^ 6 ។ មូលដ្ឋានបន្ទាប់មកក្លាយជាខ ^ ៤ ។ ដោយសារលេខ ៦ មាន ១ ជាប៊ីតសំខាន់ទាបបំផុតទី ៣ របស់យើងយើងគុណនឹងខ ៤ ទៅនឹងចម្លើយ។ ចំលើយឥឡូវនេះក្លាយជាខ ^ 3 * ខ ^ ៤ = ខ ^ ៦ ។ ហើយនេះគឺជាអ្វីដែលយើងចង់បាន។ ពិនិត្យការអនុវត្តដូចខាងក្រោមដើម្បីរកវិធីអនុវត្តក្បួនដោះស្រាយ។

សូម​មើល​ផង​ដែរ
ខ្សែអក្សរច្របាច់

លេខសម្ងាត់ប្រសើរបំផុតសំរាប់ផូ (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

កូដចាវ៉ា

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), ពីព្រោះយើងប្រើនិទស្សន្តម៉ូឌុលលឿនដែលត្រូវការពេលវេលាលោការីតដើម្បីគណនានិទស្សន្តលើមូលដ្ឋានមួយ។ យើងក៏អាចរកឃើញនូវពេលវេលាស្មុគស្មាញផងដែរ។ ចាប់តាំងពីយើងបានចែកនិទស្សន្តរហូតដល់វាក្លាយជាលេខ ០ ។ ដូច្នេះពេលវេលាដែលត្រូវការគឺពឹងផ្អែកទៅលើ logN ដែល N ជានិទស្សន្ត។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដោយសារយើងបានប្រើអថេរតែមួយដើម្បីរក្សាទុកចម្លើយភាពស្មុគស្មាញនៃលំហគឺថេរ។