C#: cadena repetida
Del desafío "Cadena repetida" de HackerRank:
Lilah tiene una cadena, \$s\$, de minúsculas inglesas que repetía infinitas veces.
Dado un número entero, \$n\$, busque e imprima el número de letras a en la primera \$n\$letras de la cadena infinita de Lilah.
Por ejemplo, si la cadena \$s=abcac\$y \$n=10\$, la subcadena que consideramos es \$abcacabcac\$, el primero \$10\$caracteres de su cadena infinita. hay \$4\$apariciones de a en la subcadena.
Caso de prueba 1:
string input = "aba";
long n = 10;
Caso de prueba 2:
string input = "a";
long n = 1000000000000;
Mi solución:
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'));
}
Los resultados deberían ser 7 y 1000000000000. Esta solución pasó todos los casos de prueba en HackerRank. Se basa en otras soluciones, especialmente en una que voté.
Respuestas
- ¿Necesitas validar las entradas?
Si es así, debe probar todos los casos:
- la entrada podría ser nula
- la entrada podría ser una cadena vacía
- n puede ser negativo o 0
- Nombres de variables
Los nombres de las variables son importantes, ayudan a comprender mejor el código. No tienes que hacerlos lo más pequeños posible. Especialmente cuando tienes un IDE como VisualStudio que te ayudará a seleccionar el adecuado con InteliSense.
- numAs -> aCuenta
- rem -> resto
- repeticiones -> repeticiones
- sRem -> cadena restante
- Fallar rapido
Por lo general, es mejor dejar un método "lo antes posible". Por lo tanto, desea realizar la validación de entrada antes de realizar cualquier trabajo y salir del método si no se valida. De la misma manera, si su resto es 0, puede devolver su resultado de inmediato.
- División entera
Para calcular tu repetición, restas el resto de n. Si marca la división de enteros en C# , no tiene que hacerlo:
long repetitions = n / input.length;
- Usar Linq
Según la solución tinstaafl , puede usar Linq para guardar una variable y una línea:
count += remainderString.Take((int)remainder).Count(c => c.Equals('a'));
Entonces, en total, obtienes:
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'));
No veo mucho que mejorar. Sin embargo, me di cuenta de un par de cosas:
El atajo condicional:
if (input.Length == 0)
{
return 0;
}
debe ser lo primero en su código justo despuésinput
Del mismo modo con:
string sRem = input.Substring(0, (int)rem);
if (rem != 0)
{
count += sRem.Count(c => c.Equals('a'));
}
No necesita esa cadena a menos que rem
> 0, así que inclúyala en el bloque condicional. Mejor aún, use la extensión LINQ Take
y haga todo en una declaración:
if (rem != 0)
{
count += sRem.Take((int)rem).Count(c => c.Equals('a'));
}
Los mismos puntos que otras respuestas, sin embargo, hay una solución más simple para esto, simplemente puede reemplazar A
con una cadena vacía y comparar la longitud de ambas cadenas, lo que le daría la cantidad de A.
Aquí hay un ejemplo :
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;
}
No puedo agregar mucho a lo que ya se ha escrito, aparte de lo que se refiere al rendimiento, a menudo encontrará que Linq ( ) es bastante lento en comparación con un bucle o long numAs = input.Count(c => c.Equals('a'));
más tradicional . Pero si insistes en Linq, podrías ir con todo como:for
while
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);
}
Aquí se usa la sobrecarga de Select()
que proporciona el índice junto con cada elemento para mapear a una tupla de valor, desde la cual es posible filtrar 'a'
y finalmente resume las repeticiones: si el índice es menor que el tamaño del recordatorio, entonces repetitions + 1
debería ser En caso contrario se suman sólo las repeticiones de cada uno de los encontrados 'a'
.
Un enfoque tradicional usando while
-loops - esencialmente usando el mismo enfoque que el anterior podría verse así:
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 este enfoque, la cadena s
( data
) solo se analiza una vez.