C #: повторяющаяся строка
Из испытания 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. Он основан на других решениях, особенно на одном, за который я проголосовал.
Ответы
- Вам нужно проверить вводимые данные?
Если да, вам следует проверить все случаи:
- ввод может быть нулевым
- ввод может быть пустой строкой
- n может быть отрицательным или 0
- Имена переменных
Имена переменных важны, они помогают лучше понять код. Необязательно делать их как можно меньше. Особенно, когда у вас есть IDE, такая как VisualStudio, которая поможет вам выбрать подходящую с InteliSense.
- numAs -> aCount
- rem -> остаток
- повторения -> повторения
- sRem -> restderString
- Быстро потерпеть неудачу
Обычно лучше оставить метод «как можно скорее». Итак, вы хотите выполнить проверку ввода перед выполнением какой-либо работы и выйти из метода, если он не прошел проверку. Таким же образом, если ваш остаток равен 0, вы можете сразу вернуть результат.
- Целочисленное деление
Чтобы рассчитать повторение, вы вычтите остаток из n. Если вы проверяете целочисленное деление в C # , вам не нужно:
long repetitions = n / input.length;
- Используйте 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'));
Я не вижу много улучшений. Однако я заметил пару вещей:
Условный ярлык:
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'));
}
Те же моменты, что и другие ответы, однако есть более простое решение для этого: вы можете просто заменить 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;
}
Я не могу ничего добавить к тому, что уже было написано, кроме того, что касается производительности, вы часто обнаружите, что 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
) анализируется только один раз.