C#: Wiederholte Zeichenfolge

Question

Aus der HackerRank „Repeated String“-Challenge:

Lilah hat eine Zeichenfolge, \$s\$, aus englischen Kleinbuchstaben, die sie unendlich oft wiederholte.

Bei einer Ganzzahl \$n\$, suchen und drucken Sie die Anzahl der Buchstaben a im ersten \$n\$Buchstaben von Lilahs unendlicher Schnur.

Wenn beispielsweise die Zeichenfolge \$s=abcac\$und \$n=10\$, die Teilzeichenfolge, die wir betrachten, ist \$abcacabcac\$, das erste \$10\$Zeichen ihrer unendlichen Schnur. Es gibt \$4\$Vorkommen von a in der Teilzeichenfolge.

Testfall 1:

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

Testfall 2:

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

Meine Lösung:

        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'));
        }

Die Ergebnisse sollten 7 und 1000000000000 lauten. Diese Lösung hat alle Testfälle auf HackerRank bestanden. Es basiert auf anderen Lösungen, insbesondere einer, die ich positiv bewertet habe.

Answer 1

1. Müssen Sie Eingaben validieren?

Wenn ja, sollten Sie alle Fälle testen:

• Eingabe könnte null sein
• input könnte ein leerer String sein
• n kann negativ oder 0 sein

1. Variablennamen

Variablennamen sind wichtig, sie helfen, den Code besser zu verstehen. Sie müssen sie nicht so klein wie möglich machen. Vor allem, wenn Sie eine IDE wie VisualStudio haben, die Ihnen bei der Auswahl der richtigen mit InteliSense hilft.

• numAs -> aCount
• rem -> Rest
• Wiederholungen -> Wiederholungen
• sRem -> restString

1. Schnell scheitern

Es ist normalerweise besser, eine Methode "so schnell wie möglich" zu verlassen. Sie möchten also eine Eingabevalidierung durchführen, bevor Sie irgendwelche Arbeiten ausführen, und die Methode beenden, wenn sie nicht validiert wird. Auf die gleiche Weise können Sie Ihr Ergebnis sofort zurückgeben, wenn Ihr Rest 0 ist.

1. Ganzzahlige Division

Um Ihre Wiederholung zu berechnen, subtrahieren Sie den Rest von n. Wenn Sie die Integer-Division in C# überprüfen , müssen Sie Folgendes nicht tun:

long repetitions = n / input.length;

1. Verwenden Sie Linq

Gemäß der tinstaafl-Lösung können Sie Linq verwenden, um eine Variable und eine Zeile zu speichern:

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

Alles in allem erhalten Sie also:

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'));

Answer 2

Ich sehe nicht viel zu verbessern. Allerdings sind mir ein paar Dinge aufgefallen:

Die Verknüpfungsbedingung:

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

sollte gleich danach das allererste in Ihrem Code seininput

Ähnlich mit:

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

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

Sie benötigen diese Zeichenfolge nur, wenn rem> 0, also fügen Sie sie in den Bedingungsblock ein. Noch besser, verwenden Sie die LINQ-Erweiterung Takeund erledigen Sie alles in einer Anweisung:

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

Answer 3

Dieselben Punkte wie bei anderen Antworten, es gibt jedoch eine einfachere Lösung dafür. Sie können sie einfach durch eine Aleere Zeichenfolge ersetzen und die Länge beider Zeichenfolgen vergleichen, wodurch Sie die Anzahl der A erhalten.

Hier ist ein Beispiel :

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;
}

Answer 4

Ich kann dem, was bereits geschrieben wurde, nicht viel hinzufügen, außer wenn es um die Leistung geht, werden Sie Linq ( long numAs = input.Count(c => c.Equals('a'));) im Vergleich zu einer traditionelleren foror while-Schleife oft als ziemlich langsam empfinden. Aber wenn Sie auf Linq bestehen, könnten Sie all-in gehen wie:

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);
}

Hier wird die Überladung von verwendet Select(), die den Index zusammen mit jedem Element bereitstellt, um auf ein Wertetupel abzubilden, aus dem gefiltert 'a'und schließlich die Wiederholungen summiert werden können: Wenn der Index kleiner ist als die Größe der Erinnerung, dann repetitions + 1sollte sie sein summiert sonst nur die Wiederholungen für jeden gefundenen 'a'.

---

Ein traditioneller Ansatz mit while-Schleifen - im Wesentlichen der gleiche Ansatz wie oben - könnte wie folgt aussehen:

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;
}

Bei diesem Ansatz wird der String s( data) nur einmal geparst.