Максималдуу 69 сандык Leetcode чечими  


Кыйынчылык деңгээли жеңил
Көп суралган HRT
Алгоритмы коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions Math

Маселени билдирүү  

Бул маселеде бизге 6 же 9 цифраларынан турган сан берилет, биз бул сандын цифрасынын бирин алмаштырып, башка цифрасына өзгөртө алабыз. Башкача айтканда, биз 6дан 9га чейин же 9дан 6га чейин алмаштыра алабыз, биз алган максималдуу санды эң көп дегенде бир жолу алмаштырышыбыз керек.

мисал

num = 9669
9969

Explanation:

Биринчи цифраны өзгөрткөндө 6669 чыгат.
Экинчи цифраны өзгөрткөндө 9969 чыгат.
Ушундай эле үчүнчү цифраны өзгөртүү 9699 натыйжасын берет.
Төртүнчү орунду өзгөртүү 9666-жылга алып келет.
Максималдуу саны - 9969.

9996
9999

Explanation:

Акыркы цифраны 6дан 9га чейин өзгөртсөңүз, эң жогорку сан пайда болот.

жакындоо  

Санды максималдуу кылуу үчүн цифраны алмаштыра алабыз, бул жерде бир нерсени түшүнүү керек, биз 6дан 9га чейин гана алмаштырышыбыз керек, анткени 9дан 6га чейин алмаштырсак, ал санды кичирейтет.
Бул жерде дагы бир нерсени түшүнөбүз, мүмкүн болушунча сол жактагы цифраны алмаштырыш керек. Келгиле, ушул нерсени мисал менен түшүнүп алалы.

Бизде 6666 берилген бир сан бар дейли
Биз 6дан 9га чейинки цифраны алмаштырышыбыз керек, ошондо пайда болгон сан максималдуу болот. Эгерде биз эң туура 6ны алмаштырсак, анда 6669 чыгат.
Эгерде биз сол жактагы 6ны алмаштырсак, анда 9666 чыгат, бул албетте, ушул санга алмаштыруунун натыйжасында алынган бардык сандардын эң чоңу.
Ошентип, биз эң солго 6ны алмаштырууга аракет кылабыз. Эгерде 6 сандарында 9999 жок болсо, анда биз эч кандай алмаштыруу операциясын жасабайбыз.

ошондой эле
Alien Dictionary

Берилген санды массив түрүндө бузуп, андан соң оң жактагы 6 менен 9ду оңой алмаштыра алабыз. Андан кийин биз жаңы номерибизди массивден калыбына келтирип, номерин чыгарабыз.
Номер 4 цифра менен чектелет деген чектөө бар. Ошентип, биз көлөмү 4 массивди түзөбүз, ал кичинекей узундуктагы бардык сандарды да канааттандырат.

Ошентип, алгоритм негизинен үч негизги бөлүктөн турат.
и) санды массивге айландыруу: биз муну a аркылуу жасайбыз while цикл > 0 санынын шарты менен. Ар бир жолу, бирдиктин цифрасы массивдин учурдагы индексинде сакталат жана сан 10го бөлүнөт.
II) массивдеги эң солго 6дан 9га чейин өзгөртүү.

Максималдуу 69 сандык Leetcode чечими

солго 6дан 9га которгондон кийин:

Максималдуу 69 сандык Leetcode чечими

iii) массивди санга өткөрүү: биз муну циклдин жардамы менен жасап жатабыз.

ишке ашыруу  

Максималдуу 69 сандык Leetcode чечимине арналган C ++ программасы

#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

Максималдуу 69 сандык Leetcode чечимине арналган Java программасы

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

Максималдуу 69 сандык Leetcode чечиминин татаалдыгын талдоо  

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

O (1):  Биз 3 аткарып жатабыз циклдар максимум боюнча 4 кайталоонун Ошентип, бул дагы ушул суроо үчүн туруктуу убакыт. Бирок, эгерде чектөө жогору болсо, анда сандын узундугуна барабар массив колдонмокпуз. Ошол учурда биздин убакыттын татаалдыгы O (сандын узундугу) болмок.

ошондой эле
Максималдуу орточо мааниси бар жол

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

O (1): Биз туруктуу көлөмдөгү 4 кошумча массивди колдондук. Ошентип космостун татаалдыгы O (1) болот.