C#: stringa ripetuta
Dalla sfida HackerRank "Stringa ripetuta":
Lilah ha una stringa, \$s\$, di lettere inglesi minuscole che ripeteva infinite volte.
Dato un numero intero, \$n\$, trova e stampa il numero della lettera a nel primo \$n\$lettere della stringa infinita di Lilah.
Ad esempio, se la stringa \$s=abcac\$e \$n=10\$, la sottostringa che consideriamo è \$abcacabcac\$, il primo \$10\$caratteri della sua stringa infinita. Ci sono \$4\$occorrenze di a nella sottostringa.
Caso di prova 1:
string input = "aba";
long n = 10;
Caso di prova 2:
string input = "a";
long n = 1000000000000;
La mia soluzione:
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'));
}
I risultati dovrebbero essere 7 e 1000000000000. Questa soluzione ha superato tutti i casi di test su HackerRank. Si basa su altre soluzioni, in particolare una che ho votato a favore.
Risposte
- Hai bisogno di convalidare gli input?
In tal caso, dovresti testare tutti i casi:
- l'input potrebbe essere nullo
- input potrebbe essere una stringa vuota
- n potrebbe essere negativo o 0
- Nomi variabili
I nomi delle variabili sono importanti, aiutano a capire meglio il codice. Non devi renderli il più piccoli possibile. Soprattutto quando hai un IDE come VisualStudio che ti aiuterà a selezionare quello giusto con InteliSense.
- numAs -> aCount
- rem -> resto
- ripetizioni -> ripetizioni
- sRem -> resterString
- Fallire velocemente
Di solito è meglio lasciare un metodo "il prima possibile". Quindi si desidera eseguire la convalida dell'input prima di eseguire qualsiasi lavoro e uscire dal metodo se non viene convalidato. Allo stesso modo, se il tuo resto è 0, puoi restituire subito il risultato.
- Divisione intera
Per calcolare la tua ripetizione, sottrai il resto da n. Se controlli la divisione intera in C# , non devi:
long repetitions = n / input.length;
- Usa Linq
Come per la soluzione tinstaafl , puoi usare Linq per salvare una variabile e una riga:
count += remainderString.Take((int)remainder).Count(c => c.Equals('a'));
Quindi, tutto sommato, ottieni:
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'));
Non vedo molto da migliorare. Tuttavia, ho notato un paio di cose:
La scorciatoia condizionale:
if (input.Length == 0)
{
return 0;
}
dovrebbe essere la prima cosa nel tuo codice subito dopoinput
Allo stesso modo con:
string sRem = input.Substring(0, (int)rem);
if (rem != 0)
{
count += sRem.Count(c => c.Equals('a'));
}
Non hai bisogno di quella stringa a meno che non sia rem
> 0, quindi includila nel blocco condizionale. Ancora meglio, usa l'estensione LINQ Take
e fai tutto in un'unica istruzione:
if (rem != 0)
{
count += sRem.Take((int)rem).Count(c => c.Equals('a'));
}
Stessi punti delle altre risposte, tuttavia esiste una soluzione più semplice a questo, puoi semplicemente sostituire A
con una stringa vuota e confrontare la lunghezza di entrambe le stringhe, che ti darebbe il numero di A.
Ecco un esempio:
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;
}
Non posso aggiungere molto a ciò che è già stato scritto, a parte quando si tratta di prestazioni, spesso troverai Linq ( long numAs = input.Count(c => c.Equals('a'));
) piuttosto lento rispetto a un più tradizionale for
o while
loop. Ma se insisti su Linq, potresti andare all in come:
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);
}
Qui viene utilizzato l'overload di Select()
che fornisce l'indice insieme a ciascun elemento da mappare a una tupla di valori, da cui è possibile filtrare 'a'
e infine riassumere le ripetizioni: se l'indice è minore della dimensione del promemoria, allora repetitions + 1
dovrebbe essere sommato altrimenti solo le ripetizioni per ogni trovato 'a'
.
Un approccio tradizionale che utilizza while
-loop - essenzialmente utilizzando lo stesso approccio di cui sopra potrebbe essere simile a:
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;
}
Con questo approccio la stringa s
( data
) viene analizzata solo una volta.