C# : chaîne répétée

Aug 20 2020

Du défi "Chaîne répétée" de HackerRank :

Lilah a une chaîne, \$s\$, de lettres anglaises minuscules qu'elle répétait à l'infini.

Étant donné un entier, \$n\$, trouvez et imprimez le nombre de lettres a dans le premier \$n\$lettres de la chaîne infinie de Lilah.

Par exemple, si la chaîne \$s=abcac\$et \$n=10\$, la sous-chaîne que nous considérons est \$abcacabcac\$, le premier \$10\$caractères de sa chaîne infinie. Il y a \$4\$occurrences de a dans la sous-chaîne.

Cas d'essai 1 :

        string input = "aba";
        long n = 10;

Cas d'essai 2 :

        string input = "a";
        long n = 1000000000000;

Ma solution :

        string input = "aba";
        long n = 10;
        long numAs = input.Count(c => c.Equals('a'));

        if (input.Length == 0)
        {
            return 0;
        }

        long rem = n % input.Length;
        long reps = (n - rem) / input.Length;
        long count = reps * numAs;

        string sRem = input.Substring(0, (int)rem);

        if (rem != 0)
        {
            count += sRem.Count(c => c.Equals('a'));
        }

Les résultats devraient être 7 et 1000000000000. Cette solution a réussi tous les cas de test sur HackerRank. Il est basé sur d'autres solutions, en particulier une que j'ai votée.

Réponses

4 MartinVerjans Aug 20 2020 at 21:46
  1. Avez-vous besoin de valider des entrées ?

Si oui, vous devriez tester tous les cas :

  • l'entrée peut être nulle
  • l'entrée peut être une chaîne vide
  • n peut être négatif ou 0
  1. Noms des variables

Les noms de variables sont importants, ils aident à mieux comprendre le code. Vous n'êtes pas obligé de les rendre aussi petits que possible. Surtout lorsque vous avez un IDE comme VisualStudio qui vous aidera à sélectionner le bon avec InteliSense.

  • numAs -> unCompte
  • rem -> reste
  • répétitions -> répétitions
  • sRem -> chaînerestante
  1. Échec rapide

Il est généralement préférable de laisser une méthode "dès que possible". Vous souhaitez donc effectuer la validation des entrées avant de faire tout travail et quitter la méthode si elle ne valide pas. De la même manière, si votre reste est 0, vous pouvez retourner votre résultat tout de suite.

  1. Division entière

Pour calculer votre répétition, vous soustrayez le reste de n. Si vous vérifiez la division entière en C# , vous n'avez pas à :

long repetitions = n / input.length;
  1. Utiliser Linq

Selon la solution tinstaafl , vous pouvez utiliser Linq pour enregistrer une variable et une ligne :

count += remainderString.Take((int)remainder).Count(c => c.Equals('a'));

Donc, dans l'ensemble, vous obtenez :

long aCount = input.Count(c => c.Equals('a'));

if (input == null || input.Length == 0 || n <= 0)
{
    return 0;
}

long repetitions = n / input.Length;
long remainder = n % input.Length;
long count = repetitions * aCount;

if (remainder == 0)
{
    return count;
}

return count + remainderString.Take((int)remainder).Count(c => c.Equals('a'));
2 tinstaafl Aug 20 2020 at 05:06

Je ne vois pas grand chose à améliorer. Cependant, j'ai remarqué deux ou trois choses :

Le raccourci conditionnel :

if (input.Length == 0)
{
    return 0;
}

devrait être la toute première chose dans votre code juste aprèsinput

De même avec :

string sRem = input.Substring(0, (int)rem);

if (rem != 0)
{
    count += sRem.Count(c => c.Equals('a'));
}

Vous n'avez pas besoin de cette chaîne à moins que rem> 0, alors incluez-la dans le bloc conditionnel. Mieux encore, utilisez l'extension LINQ Takeet faites tout en une seule instruction :

if (rem != 0)
{
    count += sRem.Take((int)rem).Count(c => c.Equals('a'));
}
2 iSR5 Aug 21 2020 at 07:25

Mêmes points que les autres réponses, mais il existe une solution plus simple à cela, vous pouvez simplement remplacer Apar une chaîne vide et comparer la longueur des deux chaînes, ce qui vous donnerait le nombre de A.

Voici un exemple :

public static long RepeatedString(string s, long n)
{
    if (string.IsNullOrWhiteSpace(s) || n <= 0) { return 0; }
    
    // Local function that would return the number of A's 
    long CountA(string input) => input.Length - input.Replace("a", "").Length;
    
    var aCount = CountA(s);
    
    var reminder = n % s.Length; 
    
    var repetition = (n - reminder) / s.Length;
    
    var count = repetition * aCount;

    var reminderStr = s.Substring(0, (int)reminder);
    
    var result = count + CountA(reminderStr);
    
    return result;
}
1 Noname Aug 22 2020 at 01:50

Je ne peux pas ajouter grand-chose à ce qui a déjà été écrit, à part en ce qui concerne les performances, vous trouverez souvent que Linq ( long numAs = input.Count(c => c.Equals('a'));) est plutôt lent par rapport à une boucle forou plus traditionnelle. whileMais si vous insistez sur Linq, vous pouvez vous lancer comme suit :

long CountChars(string data, long length, char c = 'a')
{
  if (string.IsNullOrEmpty(data) || length <= 0) return 0;

  long repetitions = length / data.Length;
  long remSize = length % data.Length;

  return data
    .Select((ch, i) => (ch, i))
    .Where(chi => chi.ch == c)
    .Sum(chi => chi.i < remSize ? repetitions + 1 : repetitions);
}

Ici est utilisée la surcharge de Select()qui fournit l'index avec chaque élément à mapper sur un tuple de valeur, à partir duquel il est possible de filtrer 'a'et finalement de résumer les répétitions : si l'index est inférieur à la taille du rappel, alors repetitions + 1doit être additionné sinon que les répétitions pour chaque trouvé 'a'.


Une approche traditionnelle utilisant des whileboucles - utilisant essentiellement la même approche que ci-dessus pourrait ressembler à :

long CountChars(string data, long length, char c = 'a')
{
  if (string.IsNullOrEmpty(data) || length <= 0) return 0;

  long count = 0;
  long repetitions = length / data.Length + 1; // + 1 for the possible extra 'a' in the reminder
  long remSize = length % data.Length;

  int i = 0;

  while (i < remSize)
  {
    if (data[i++] == c)
      count += repetitions;
  }

  repetitions--;
  while (i < data.Length)
  {
    if (data[i++] == c)
      count += repetitions;
  }

  return count;
}

Avec cette approche, la chaîne s( data) n'est analysée qu'une seule fois.