Максимальна кількість рішень для штрих-кодів 69


Рівень складності Легко
Часто запитують у 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, наприклад 9999, тоді ми не будемо виконувати жодної операції заміни.

Ми можемо розбити дане число у вигляді масиву, а потім ми можемо легко замінити ліві 6 на 9. Потім ми відтворимо нове число з масиву і виведемо число.
Існує обмеження, що кількість обмежена 4 цифрами. Таким чином, ми створимо масив розміром 4, який також задовольнить усі числа меншої довжини.

Отже, алгоритм в основному складається з трьох основних частин.
i) перетворення числа в масив: ми робимо це, використовуючи цикл while з умовою число> 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

Програма Java для розв’язання штрих-кодів з максимальним числом 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 рішень Leetcode

Складність часу

O (1):  Ми виконуємо 3 петлі з 4 ітерацій при макс. Таким чином, це також постійний час для цього питання. Однак, якщо обмеження було б високим, ми використовували б масив розміром, рівний довжині числа. У той час наша складність часу буде O (довжина числа).

Складність простору 

O (1): Ми використали додатковий масив розміром 4, який є постійним. Таким чином, складність простору дорівнює O (1).