C#: cadena repetida

Aug 20 2020

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

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

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

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 Takey haga todo en una declaración:

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

Los mismos puntos que otras respuestas, sin embargo, hay una solución más simple para esto, simplemente puede reemplazar Acon 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;
}
1 Noname Aug 22 2020 at 01:50

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:forwhile

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 + 1deberí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.