ដំណោះស្រាយលេខ Leetcode ចំនួន ៦៩ អតិបរមា


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ អរ
គណិតវិទ្យា

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់លេខដែលបង្កើតឡើងដោយខ្ទង់ ៦ ឬ ៩។ យើងអាចជំនួសលេខមួយនៃខ្ទង់លេខនេះហើយប្តូរលេខនេះទៅជាខ្ទង់មួយទៀត។ ឧទាហរណ៍យើងអាចជំនួសលេខ ៦ ដល់ ៩ ឬយើងអាចជំនួសលេខ ៩ ដល់លេខ ៦ ។ យើងត្រូវបង្កើតចំនួនអតិបរមាដែលយើងអាចទទួលបានដោយជំនួសមួយ។

ឧទាហរណ៍

num = 9669
9969

ការពន្យល់:

ការផ្លាស់ប្តូរលទ្ធផលខ្ទង់ទី ១ គឺ ៦៦៦៩ ។
ការផ្លាស់ប្តូរលទ្ធផលខ្ទង់ទីពីរក្នុងឆ្នាំ ៩៩៦៩ ។
ស្រដៀងគ្នានេះដែរការផ្លាស់ប្តូរលទ្ធផលខ្ទង់ទីបីក្នុងឆ្នាំ ៩៦៩៩ ។
ការផ្លាស់ប្តូរលទ្ធផលខ្ទង់ទី ៤ ក្នុង ៩៦៦៦ ។
ចំនួនអតិបរមាគឺ ៩៩៦៩ ។

9996
9999

ការពន្យល់:

ការផ្លាស់ប្តូរខ្ទង់ចុងក្រោយពី ៦ ទៅ ៩ លទ្ធផលជាចំនួនអតិបរមា។

វិធីសាស្រ្ត

ដូចដែលយើងអាចជំនួសខ្ទង់មួយដើម្បីធ្វើឱ្យចំនួនអតិបរិមារឿងមួយដែលយើងអាចយល់បាននៅទីនេះគឺយើងគួរតែជំនួសលេខ ៦ ដល់លេខ ៩ ពីព្រោះលេខ ៩ ដល់លេខ ៦ នឹងធ្វើឱ្យលេខតូចជាង។
រឿងមួយទៀតដែលយើងអាចយល់បាននៅទីនេះគឺយើងគួរតែជំនួសខ្ទង់ដែលនៅសេសសល់តាមដែលអាចធ្វើទៅបាន។ ចូរយើងយល់ពីរឿងនេះជាមួយឧទាហរណ៍។

ឧបមាថាយើងមានលេខដែលបានផ្តល់លេខ ៦៦៦៦
យើងត្រូវជំនួសខ្ទង់ពីលេខ ៦ ដល់លេខ ៩ ដែលលេខដែលបានបង្កើតឡើងមានចំនួនអតិបរមា។ ប្រសិនបើយើងជំនួសលេខ ៦ ដែលត្រឹមត្រូវនោះយើងនឹងទទួលបាន ៦៦៦៩ ។
ប្រសិនបើយើងជំនួសលេខខាងឆ្វេង ៦ នោះយើងនឹងទទួលបាន ៩៦៦៦ ដែលជាចំនួនអតិបរមានៃលេខទាំងអស់ដែលទទួលបានដោយការជំនួសលើលេខនេះ។
ដូច្នេះយើងនឹងព្យាយាមជំនួសផ្នែកខាងឆ្វេងបំផុត ៦. ហើយប្រសិនបើគ្មានលេខ ៦ ដែលមាននៅក្នុងលេខដែលបានផ្តល់ឧទាហរណ៍ ៩៩៩៩ នោះយើងនឹងមិនអនុវត្តប្រតិបត្តិការជំនួសទេ។

យើងអាចបំបែកលេខដែលបានផ្តល់ឱ្យជាទំរង់នៃអារេហើយបន្ទាប់មកយើងអាចជំនួសខាងឆ្វេង 6 ដោយ 9 យ៉ាងងាយស្រួល។ បន្ទាប់មកយើងនឹងបង្កើតលេខថ្មីរបស់យើងឡើងវិញពីអារេហើយចេញលទ្ធផល។
មានឧបសគ្គដែលចំនួនត្រូវបានកំណត់ត្រឹម 4 ខ្ទង់។ ដូច្នេះយើងនឹងបង្កើតអារេនៃទំហំ ៤ ដែលនឹងបំពេញគ្រប់ចំនួនប្រវែងតូចជាងនេះផងដែរ។

ដូច្នេះក្បួនដោះស្រាយជាមូលដ្ឋានមានបីផ្នែកសំខាន់ៗ។
i) បំលែងលេខទៅជាអារេៈយើងកំពុងធ្វើវាដោយប្រើរង្វិលជុំមួយពេលជាមួយនឹងស្ថានភាពលេខ> ០ ។ រាល់ពេលដែលខ្ទង់នៅឯកន្លែងឯកតាត្រូវបានរក្សាទុកនៅសន្ទស្សន៍បច្ចុប្បន្ននៃអារេហើយលេខត្រូវបានបែងចែកដោយ ១០ ។
ii) ការផ្លាស់ប្តូរខាងឆ្វេង ៦ ទៅ ៩ ក្នុងអារេ។

ដំណោះស្រាយលេខ Leetcode ចំនួន ៦៩ អតិបរមា

បន្ទាប់ពីបំលែងលេខ ៦ ទៅ ៩៖

ដំណោះស្រាយលេខ Leetcode ចំនួន ៦៩ អតិបរមា

iii) បំលែងអារេទៅជាលេខ៖ យើងកំពុងធ្វើវាដោយប្រើរង្វិលជុំ។

ការអនុវត្តន៍

កម្មវិធី C ++ សំរាប់ដំណោះស្រាយលេខ Leetcode អតិបរមាចំនួន ៦៩

#include <iostream>
using namespace std;
int maximum69Number (int num) 
{
    int arr[4];
    fill(arr,arr+4,0);
    int i=3;
    while(num!=0){
        arr[i--]=num%10;
        num/=10;
    }
    for(i=0;i<=3;i++){
        if(arr[i]==6){arr[i]=9;break;}
    }

    int ans=0,mul=1;
    for(i=3;i>=0;i--){
        ans+=(mul*arr[i]);
        mul*=10;
    }
    return ans;

}
int main()
{
    cout << maximum69Number(9669);
}
9969

កម្មវិធីចាវ៉ាសម្រាប់ដំណោះស្រាយលេខឡៃលេខកូដអតិបរមា ៦៩

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int maximum69Number (int num) 
    {
        int[] arr=new int[4];
        int i=3;
        while(num!=0){
            arr[i--]=num%10;
            num/=10;
        }
        for(i=0;i<=3;i++){
            if(arr[i]==6){arr[i]=9;break;}
        }
        int ans=0,mul=1;
        for(i=3;i>=0;i--){
            ans+=(mul*arr[i]);
            mul*=10;
        }
        return ans;
    }
    public static void main(String args[])
    {
        System.out.println(maximum69Number(9669));
    }
}
9969

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយលេខ Leetcode អតិបរមាចំនួន ៦៩

ស្មុគស្មាញពេលវេលា

O (១)៖  យើងកំពុងសម្តែង ៣ រង្វិលជុំ នៃការធ្វើម្តងទៀតចំនួន ៤ ដង។ ដូច្នេះនេះក៏ជាពេលវេលាថេរសម្រាប់សំណួរនេះដែរ។ ទោះយ៉ាងណាក៏ដោយប្រសិនបើឧបសគ្គនឹងខ្ពស់យើងនឹងប្រើអារេទំហំស្មើនឹងប្រវែងនៃលេខ។ នៅពេលនោះភាពស្មុគស្មាញនៃពេលវេលារបស់យើងគឺ O (ប្រវែងនៃចំនួន) ។

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

O (១)៖ យើងបានប្រើអារេបន្ថែមនៃទំហំ ៤ ដែលជាចំនួនថេរ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺអូ (១) ។