Максимум 69 број на решение за лет код  


Ниво на тешкотија Лесно
Често прашувано во ХРТ
алгоритми кодирање интервју интервју подготви LeetCode LeetCodeSolutions Математика

Изјава за проблем  

Во овој проблем, ни е даден број составен од цифри 6 или 9. Можеме да замениме една цифра од овој број и да ја смениме во друга цифра. т.е. можеме да замениме од 6 до 9 или можеме да замениме од 9 до 6. Мораме да го дадеме максималниот број што можеме да го добиеме најмногу со една замена.

пример

num = 9669
9969

објаснување:

Промената на првата цифра резултира во 6669 година.
Промената на втората цифра резултира во 9969 година.
Слично на промена на третата цифра резултира во 9699 година.
Промената на четвртата цифра резултира во 9666 година.
Максималниот број е 9969.

9996
9999

објаснување:

Менувањето на последната цифра од 6 до 9 резултира во максимален број.

Пристап  

Бидејќи можеме да замениме цифра за да го направиме бројот максимум, една работа што можеме да ја разбереме тука е дека, треба да замениме само од 6 до 9, бидејќи замената од 9 до 6 ќе го направи бројот помал.
Друга работа што можеме да ја разбереме тука е, треба да замениме цифра што е можно лево. Ајде да ја разбереме оваа работа со пример.

Да претпоставиме дека имаме даден број, 6666
Треба да замениме цифра од 6 до 9 таква што формираниот број е максимален. Ако ги замениме правите 6 тогаш добиваме 6669.
Ако ја замениме левата 6 тогаш добиваме 9666 што е секако максимум од сите броеви добиени со таквата замена на овој број.
Така, ќе се обидеме да ја замениме левата 6. И ако во дадениот број нема 6, на пр. 9999, тогаш нема да извршиме никаква операција за замена.

Видете исто така
Речник за вонземјани

Можеме да го скршиме дадениот број во форма на низа и потоа можеме да го замениме левиот 6 со 9 лесно. Потоа ќе го пресоздадеме нашиот нов број од низата и ќе го излеземе бројот.
Постои ограничување дека бројот е ограничен на 4 цифри. Така, ќе создадеме низа со големина 4 што ќе ги задоволи и сите помали должини.

Значи, алгоритмот во основа се состои од три главни делови.
з) претворање број во низа: ова го правиме со помош на a додека јамка со состојба на број> 0. Секој пат, цифрата на единицата се чува на тековниот индекс на низа и бројот се дели со 10.
ii) промена на левата страна од 6 до 9 во низата.

Максимум 69 број на решение за лет код

откако претвори лево 6 во 9:

Максимум 69 број на решение за лет код

iii) конвертирање на низата во број: ова го правиме со употреба на јамка.

Имплементација  

Програма C ++ за максимум 69 број на решение за леткод

#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 број на решение за леткод

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 број на решение за леткод  

Временска комплексност

О (1):  Ние изведуваме 3 петелки од 4 повторувања на максимум. Така, ова е исто така постојано време за ова прашање. Меѓутоа, ако ограничувањето би било големо, би користеле низа со големина еднаква на должината на бројот. Во тоа време, нашата временска сложеност би била О (должина на бројот).

Видете исто така
Патека со максимална просечна вредност

Комплексноста на просторот 

О (1): Користевме дополнителна низа со големина 4 што е постојана. Така, комплексноста на просторот е О (1).