C#: stringa ripetuta

Aug 20 2020

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

4 MartinVerjans Aug 20 2020 at 21:46
  1. 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
  1. 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
  1. 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.

  1. 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;
  1. 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'));
2 tinstaafl Aug 20 2020 at 05:06

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 Takee fai tutto in un'unica istruzione:

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

Stessi punti delle altre risposte, tuttavia esiste una soluzione più semplice a questo, puoi semplicemente sostituire Acon 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;
}
1 Noname Aug 22 2020 at 01:50

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 foro whileloop. 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 + 1dovrebbe 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.