C# : chaîne répétée
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
- 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
- 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
- É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.
- 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;
- 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'));
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 Take
et faites tout en une seule instruction :
if (rem != 0)
{
count += sRem.Take((int)rem).Count(c => c.Equals('a'));
}
Mêmes points que les autres réponses, mais il existe une solution plus simple à cela, vous pouvez simplement remplacer A
par 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;
}
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 for
ou plus traditionnelle. while
Mais 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 + 1
doit être additionné sinon que les répétitions pour chaque trouvé 'a'
.
Une approche traditionnelle utilisant des while
boucles - 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.