Максимум 69 Ҳалли рақами Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад HRT
Матем

Изҳороти мушкилот

Дар ин масъала ба мо рақаме иборат аст, ки аз рақамҳои 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 вуҷуд надошта бошад, пас мо ягон амали ивазкуниро иҷро намекунем.

Мо метавонем адади додашударо дар шакли массив шикаста, пас 6 - 9ро ба осонӣ иваз намоем. Он гоҳ мо рақами нави худро аз массив барқарор мекунем ва рақамро мебарорем.
Маҳдудият вуҷуд дорад, ки рақам бо 4 рақам маҳдуд аст. Ҳамин тариқ, мо массиви андозаи 4 месозем, ки он ҳамаи рақамҳои дарозии хурдро низ қонеъ мекунад.

Ҳамин тавр, алгоритм асосан аз се қисми асосӣ иборат аст.
i) табдил додани рақам ба массив: мо инро бо истифода аз ҳалқаи while бо шарти рақами> 0 анҷом медиҳем. Ҳар дафъа, рақам дар ҷои воҳид дар индекси ҷории массив нигоҳ дошта мешавад ва рақам ба 10 тақсим карда мешавад.
ii) тағир додани аз чап ба 6 то 9 дар массив.

Максимум 69 Ҳалли рақами Leetcode

пас аз ба чап табдил додани 6 ба 9:

Максимум 69 Ҳалли рақами Leetcode

iii) табдил додани массив ба рақам: мо инро бо истифода аз ҳалқа анҷом медиҳем.

татбиќи

Барномаи C ++ барои ҳалли максималии 69 рақами 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

Барномаи Java барои Ҳалли максималии 69 рақами Leetcode

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

Мураккабии вақт

О (1):  Мо 3 иҷро карда истодаем ҳалқаҳо аз 4 такрори ҳадди аксар. Ҳамин тариқ, ин вақти доимӣ барои ин савол аст. Аммо, агар маҳдудият баланд мебуд, мо массиви андозаи ба дарозии рақам баробарро истифода мебурдем. Дар он вақт мураккабии вақти мо O (дарозии рақам) хоҳад буд.

Мураккабии фазо 

О (1): Мо массиви изофии андозаи 4 -ро истифода кардем, ки доимист. Ҳамин тавр мураккабии фазо O (1) мебошад.