Μέγιστη λύση 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 στο δεδομένο αριθμό π.χ. 9999 τότε δεν θα εκτελέσουμε καμία λειτουργία αντικατάστασης.

Μπορούμε να σπάσουμε τον δεδομένο αριθμό σε μορφή πίνακα και στη συνέχεια μπορούμε να αντικαταστήσουμε εύκολα το αριστερό 6 με 9. Στη συνέχεια, θα δημιουργήσουμε ξανά τον νέο μας αριθμό από τον πίνακα και θα βγάλουμε τον αριθμό.
Υπάρχει ένας περιορισμός ότι ο αριθμός περιορίζεται σε 4 ψηφία. Έτσι θα δημιουργήσουμε μια σειρά μεγέθους 4 που θα ικανοποιήσει και όλους τους αριθμούς μικρότερου μήκους.

Έτσι, ο αλγόριθμος βασικά αποτελείται από τρία κύρια μέρη.
i) μετατροπή αριθμού σε πίνακα: το κάνουμε αυτό χρησιμοποιώντας ένα βρόχο λίγο με την κατάσταση του αριθμού> 0. Κάθε φορά, το ψηφίο στη θέση μονάδας αποθηκεύεται στον τρέχοντα δείκτη ενός πίνακα και ο αριθμός διαιρείται με 10.
ii) αλλαγή του αριστερότερου 6 έως 9 στον πίνακα.

Μέγιστη λύση 69 αριθμών Leetcode

μετά τη μετατροπή αριστερά 6 έως 9:

Μέγιστη λύση 69 αριθμών Leetcode

iii) μετατροπή πίνακα σε αριθμό: το κάνουμε χρησιμοποιώντας έναν βρόχο.

Εκτέλεση

Πρόγραμμα C ++ για Μέγιστο 69 Αριθμός Leetcode Solution

#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 Solution

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 Solution

Χρόνος πολυπλοκότητας

O (1):  Παίζουμε 3 βρόχους από 4 επαναλήψεις στο μέγιστο Επομένως, αυτός είναι επίσης σταθερός χρόνος για αυτήν την ερώτηση. Ωστόσο, εάν ο περιορισμός θα ήταν υψηλός, θα χρησιμοποιούσαμε έναν πίνακα μεγέθους ίσο με το μήκος του αριθμού. Εκείνη την εποχή η πολυπλοκότητα του χρόνου μας θα ήταν O (μήκος του αριθμού).

Διαστημική πολυπλοκότητα 

O (1): Έχουμε χρησιμοποιήσει μια επιπλέον σειρά μεγέθους 4 που είναι σταθερή. Έτσι, η πολυπλοκότητα του διαστήματος είναι Ο (1).