C #: повторяющаяся строка

Aug 20 2020

Из испытания HackerRank «Повторяющаяся строка»:

У Лайлы есть строка \$s\$, строчных английских букв, которые она повторяла бесконечно много раз.

Учитывая целое число, \$n\$, найдите и выведите количество букв а в первом \$n\$ буквы бесконечной строки Лайлы.

Например, если строка \$s=abcac\$и \$n=10\$, рассматриваемая подстрока - \$abcacabcac\$, первый \$10\$символы ее бесконечной строки. Есть \$4\$ вхождения в подстроку.

Тестовый пример 1:

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

Тестовый пример 2:

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

Мое решение:

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

Результатом должно быть 7 и 1000000000000. Это решение прошло все тестовые примеры на HackerRank. Он основан на других решениях, особенно на одном, за который я проголосовал.

Ответы

4 MartinVerjans Aug 20 2020 at 21:46
  1. Вам нужно проверить вводимые данные?

Если да, вам следует проверить все случаи:

  • ввод может быть нулевым
  • ввод может быть пустой строкой
  • n может быть отрицательным или 0
  1. Имена переменных

Имена переменных важны, они помогают лучше понять код. Необязательно делать их как можно меньше. Особенно, когда у вас есть IDE, такая как VisualStudio, которая поможет вам выбрать подходящую с InteliSense.

  • numAs -> aCount
  • rem -> остаток
  • повторения -> повторения
  • sRem -> restderString
  1. Быстро потерпеть неудачу

Обычно лучше оставить метод «как можно скорее». Итак, вы хотите выполнить проверку ввода перед выполнением какой-либо работы и выйти из метода, если он не прошел проверку. Таким же образом, если ваш остаток равен 0, вы можете сразу вернуть результат.

  1. Целочисленное деление

Чтобы рассчитать повторение, вы вычтите остаток из n. Если вы проверяете целочисленное деление в C # , вам не нужно:

long repetitions = n / input.length;
  1. Используйте Linq

В соответствии с решением tinstaafl вы можете использовать Linq для сохранения переменной и строки:

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

Итак, в итоге вы получаете:

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

Я не вижу много улучшений. Однако я заметил пару вещей:

Условный ярлык:

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

должно быть первым делом в вашем коде сразу после input

Аналогично:

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

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

Эта строка не нужна, если не rem> 0, поэтому включите ее в условный блок. Еще лучше, используйте расширение LINQ Takeи сделайте все одним оператором:

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

Те же моменты, что и другие ответы, однако есть более простое решение для этого: вы можете просто заменить Aпустой строкой и сравнить длину обеих строк, что даст вам количество A.

Вот пример:

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

Я не могу ничего добавить к тому, что уже было написано, кроме того, что касается производительности, вы часто обнаружите, что Linq ( long numAs = input.Count(c => c.Equals('a'));) работает довольно медленно по сравнению с более традиционным forили whileциклическим. Но если вы настаиваете на Linq, вы можете пойти ва-банк, например:

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

Здесь используется перегрузка, Select()которая предоставляет индекс вместе с каждым элементом для сопоставления с кортежем значений, из которого можно фильтровать 'a'и, наконец, суммировать повторения: если индекс меньше размера напоминания, тогда repetitions + 1должен быть в противном случае суммированы только повторения для каждого найденного 'a'.


Традиционный подход с использованием while-loops - по сути, с использованием того же подхода, что и выше, может выглядеть так:

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

При таком подходе строка s( data) анализируется только один раз.