in

Elimine caracteres consecutivos y agregue ceros al final con una restricción

Dada una matriz de caracteres, necesito eliminar todos los caracteres que se repitieron 3 o más veces (consecutivamente) y agregar ‘0’ al final de la matriz para cada carácter eliminado,

Las restricciones: O(n) tiempo O(1) memoria No se puede sobrescribir una celda en la matriz más de una vez

Ejemplos: «aacccbbddde» –> «aabbe000000»

Logré encontrar la siguiente solución sin la restricción de memoria/sobrescritura O(1) (solo puedo hacer una a la vez)

¿Algunas ideas?

2 respuestas
2

Tener un índice de escritura. Luego revise la matriz, identifique y mida cada racha de caracteres iguales. Se escriben rayas más cortas que 3. Al final, escriba ceros en los índices restantes.

Mientras esperaba su publicación actualizada que incluye su solución, publiqué la mía:

Solución

Una subcadena es eliminable si todos sus caracteres se eliminarán según sus requisitos. Esta subcadena puede tener varios grupos de caracteres repetidos. Por ejemplo, si la cadena es «accccbbbdddagggde», entonces «cccc» y «bbb» son eliminables. Una subcadena eliminable es máximo si no es adyacente a ninguna subcadena eliminable. Los ejemplos anteriores no son subcadenas eliminables máximas, pero «ccccbbbddd» y «ggg» son máximas. Un imborrable subcadena es una subcadena que permanecerá en la cadena. UN máxima imborrable substring sigue la misma idea que maximal deletable.

Su problema es esencialmente eliminar todas las subcadenas eliminables máximas en una cadena y luego agregar la cadena resultante con tantos 0 como los caracteres eliminados. A continuación se muestra una solución:

  1. Dejar $cur = -1$ ser el índice de inicio en la matriz que se puede sobrescribir. Inicialmente, no hay ningún índice para sobrescribir. Dejar $contar$ sea ​​el número de caracteres que se eliminarán.

  2. Escanee la matriz hasta que encuentre la subcadena eliminable máxima más a la izquierda $d$. Dejar $d_{inicio}$ y $d_{fin}$ ser el índice inicial y final de esta cadena, y $ d_ {largo} = | d | $ ser $d$longitud de .

  3. Continúe el escaneo para encontrar la subcadena imborrable máxima adyacente $u$. Dejar $u_{inicio}$ y $u_{fin}$ sean sus índices inicial y final y $u_{largo} = |u|$ ser $u$longitud de .

  4. Si ambos $d$ y $u$ existe, haga lo siguiente:

    • Si $cur$ sigue siendo -1, conjunto $cur = d_{inicio}$.
    • Colocar $cuenta = cuenta + d_{len}$.
    • Copiar subcadena $u$ en la posición $cur$ todo el camino hasta $cur + u_{largo} – 1$. Esto esencialmente mueve la subcadena $u$ a la izquierda, sobrescribiendo $d$total o parcialmente, según se trate $|tu| \ge |d|$.
    • Moverse $cur$ pasó la subcadena copiada, eso es let $cur = cur + u_{len}$.
    • Vuelva al paso 2, pero el escaneo comenzará en $u_{fin} + 1$.
  5. Si alguno $u$ o $d$ no existe, escribe tantos 0 $contar$ a la matriz que comienza en la posición $cur$y hemos terminado.

Análisis

  • Esta solución solo utiliza $O(1)$ variables adicionales, por lo que utiliza $O(1)$ espacio extra.
  • Sobrescribe un índice de la matriz una vez. Ya sea en el paso 4, al mover una cadena imborrable hacia la izquierda o al escribir 0 en el paso 5.
  • Esta solución se ejecuta en $O(n)$ tiempo. Obsérvese que un índice se visita como máximo dos veces, una cuando se considera en la búsqueda de subcadena borrable/no borrable y la otra cuando se sobrescribe. Encontrar un borrable e imborrable lleva tiempo $O(|d|)$ y $ O (| tu |) $ resp., mientras se mueve un imborrable toma $O(|d|)$ tiempo. En el peor de los casos, todas las subcadenas de la cadena se clasificarán como eliminables o no eliminables. Dado que los índices se escriben como máximo una vez, el tiempo total para encontrar y mover todas esas subcadenas es $O(n)$.

¿Te ayudó la respuesta?

Subscribirse
Notificar por
guest
0 Comentarios
Inline Feedbacks
Ver todas las Respuestas

¿Las plantas se originan a partir de una sola célula?

¿Por qué la fuerza ácida entre el H2S y el HCl puede explicarse sobre la base de la electronegatividad, pero el H2S y el H2O no?