მაქსიმალური 69 რიცხვის ლეეტკოდის ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან 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 ზომის მასივს, რომელიც დააკმაყოფილებს ყველა მცირე ზომის სიგრძესაც.

ასე რომ, ალგორითმი ძირითადად შედგება სამი ძირითადი ნაწილისგან.
ი) რიცხვის გარდაქმნა მასივში: ჩვენ ამას ვაკეთებთ დროის მარყუჟის გამოყენებით, რიცხვის პირობით> 0. ყოველ ჯერზე, ციფრი ერთეულის ადგილზე ინახება მასივის მიმდინარე ინდექსში და რიცხვი იყოფა 10-ზე.
ii) მასივიდან მარცხნივ 6-დან 9-ის შეცვლა.

მაქსიმალური 69 რიცხვის ლეეტკოდის ამოხსნა

მარცხნივ 6 – დან 9 – მდე გადაქცევის შემდეგ:

მაქსიმალური 69 რიცხვის ლეეტკოდის ამოხსნა

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 რიცხვის ლეეტკოდ ამოხსნისთვის

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 რიცხვის ლეეტკოდული ამოხსნისთვის

დროის სირთულე

O (1):  ჩვენ ვასრულებთ 3-ს loops მაქსიმუმ 4 განმეორებისგან. ამრიგად, ეს მუდმივი დროა ამ კითხვისთვის. ამასთან, თუ შეზღუდვა მაღალი იქნებოდა, გამოვიყენებდით ზომის მასივს, რომელიც ტოლია სიგრძის სიგრძისა. ამ დროს ჩვენი დროის სირთულე იქნება O (რიცხვის სიგრძე).

სივრცის სირთულე 

O (1): ჩვენ გამოვიყენეთ მე –4 ზომის დამატებითი მასივი, რომელიც მუდმივია. ამრიგად, სივრცის სირთულე არის O (1).