Maximiser les valeurs manquantes sur une période de temps donnée, au format HH:MM

Représente la chaîne donnée de longueur cinq sous forme d'heure au format HH:MM. La chaîne peut contenir des "?" et nous devons les remplacer par n'importe quel nombre pour que le résultat soit une heure valide et probablement la plus grande possible. De plus, les numéros de chaîne donnés seront valides et le « : » apparaîtra à la position exacte de la chaîne. Nous utiliserons d’abord les méthodes de force brute, puis utiliserons des méthodes efficaces.

Exemple Exemple

Entrez 1

Given string: 12:5?
Output: 12:59

La traduction chinoise de

Explication

est :

Explication

Nous n'avons qu'une seule place à pourvoir et le temps maximum que nous pouvons obtenir est de 12h59.

Entrez 2

Given string: ?0:?9
Output: 20:59

La traduction chinoise de

Explication

est :

Explication

Nous avons ici deux emplacements vides, nous allons d'abord nous concentrer sur la partie heures, nous avons trois options 0, 1 et 2 pour les remplir. Pour la partie minutes nous avons des choix de 0 à 5, pour maximiser nous pouvons remplir 5.

Méthode

Nous avons examiné des exemples, regardons maintenant les différents types de situations auxquelles nous pourrions être confrontés −

• Nous avons deux parties de la chaîne, la partie heure et la partie minute.

• La partie heure va de 0 à 23 et la partie minute va de 0 à 59.

• Il y a plus de situations dans la partie horaire−

• « x ? » où x peut être 0, 1 et 2. Pour 0, nous pouvons choisir 0 comme meilleur choix, pour 1, nous pouvons choisir 9 comme meilleur choix, et pour 2, nous pouvons choisir 3 comme meilleur choix.

• '?x', où x peut aller de 0 à 9. Si x est compris entre 0 et 3, on peut le remplacer par 2, sinon 1 sera le meilleur.

• '??' Puisqu'il faut maximiser, nous le remplaçons par 23.

• Procès-verbaux des réunions, certains ont d'autres cas −

• « x ? » où x peut être compris entre 0 et 5. 9 serait notre meilleur choix pour remplacer « ? ».

• '?x' où x peut être compris entre 0 et 9. 5 serait notre meilleur choix pour remplacer « ? ».

• "??" car il faut maximiser et ensuite on le remplace par 59.

Jetons un coup d'œil au code qui implémente les étapes ci-dessus -

La traduction chinoise de

Exemple

est :

Exemple

#include <iostream>
using namespace std;
// function to replace hours
string replaceHours(string s){
   if(s[0] == '?' && s[1] == '?'){
      //Both hour characters are '?'
      // replace with the maximum hour we can achieve 
      s[0] = '2';
      s[1] = '3';
   }
   else if(s[0] == '?'){
      // if the second number of hours is in the range 0 to 3
      // replace by 2
      if(s[1] < 4){
         s[0] = '2';
      }
      else{
         s[0] = '1'; // otherwise replace by one 
      }
   }
   else if(s[1] == '?'){
      // if the first character is '2' we can go only upto 3
      if(s[0] == '2'){
         s[1] = '3';
      }
      else{
         s[1] = '9'; // else we can go for 9 
      }
   }
   return s;
}
// function to replace minutes
string replaceMinutes(string s){
   if(s[3] == '?' && s[4] == '?'){
      // both minutes characters are '?'
      // replace with maximum minutes we can acheive 
      s[3] = '5';
      s[4] = '9';
   }
   else if(s[3] == '?'){
      // we can maximum get 5 here 
      s[3] = '5';
   }
   else if(s[4] == '?'){
      // we can get maximum 9 here
      s[4] = '9';
   }
   return s;
}
int main(){
   string str = "2?:3?"; // given string 
   // calling the function for updation of the minutes 
   str = replaceMinutes(str);
   // calling to the function for updation of the hours
   str = replaceHours(str);
   // printing the final answer
   cout<<"The maximum time we can get by replacing ? is: "<< str<<endl;
   return 0;
}

Sortie

The maximum time we can get by replacing ? is: 23:39

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(1) ou constante car nous n'utilisons aucune boucle ou appel récursif, vérifiant simplement les conditions if-else

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire. De plus, pour cette fonction, la taille de la chaîne que nous transmettons est toujours un 5 fixe.

Remarque : Pour rendre le code plus beau ou plus lisible, vous pouvez utiliser des instructions switch, elles n'affecteront pas la complexité temporelle ou spatiale et rendront la lecture plus efficace.

De plus, le retour en arrière et la revérification sont une solution, mais cela vérifiera chaque cas et n'est pas efficace à mettre en œuvre ici.

Conclusion

Dans ce tutoriel, on nous donne une chaîne qui représente l'heure au format 24 heures. Il y a des "?" dans la chaîne qui doivent être remplacés pour obtenir la durée de validité maximale, et il est garanti que les caractères de la chaîne pointent toujours vers l'heure de validité. Nous avons utilisé une condition if-else et deux fonctions pour remplacer le « ? » par la casse appropriée. Puisque nous n'utilisons aucune boucle ou fonction récursive, la complexité temporelle et spatiale du code ci-dessus est constante.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!