semantics - sentences - ¿Qué significa "en el lugar"?

syntax definition

Question

Invierta las palabras en una cadena (las palabras están separadas por uno o más espacios). Ahora hazlo en el lugar.

¿Qué significa in situ?

Answer 1

Debe cambiar el contenido de la cadena original a la inversa sin utilizar una variable de almacenamiento temporal para mantener la cadena.

Answer 2

En el lugar significa que debe actualizar la cadena original en lugar de crear una nueva.

Dependiendo del lenguaje / framework que estés usando, esto podría ser imposible. (Por ejemplo, las cadenas son inmutables en .NET y Java, por lo que sería imposible realizar una actualización in situ de una cadena sin tener que recurrir a algunos ataques maliciosos).

Answer 3

Los algoritmos en el lugar solo pueden usar O(1) espacio adicional, esencialmente. La inversión de matrices (esencialmente a lo que se reduce la pregunta de la entrevista) es un ejemplo clásico. Lo siguiente está tomado de Wikipedia:

Supongamos que queremos revertir una matriz de n elementos. Una forma simple de hacer esto es:

function reverse(a[0..n])
    allocate b[0..n]
    for i from 0 to n
       b[n - i] = a[i]
    return b

Desafortunadamente, esto requiere O(n) espacio adicional para crear la matriz b , y la asignación es a menudo una operación lenta. Si ya no necesitamos a , podemos sobrescribirla con su propia inversión utilizando este algoritmo in situ:

function reverse-in-place(a[0..n])
    for i from 0 to floor(n/2)
       swap(a[i], a[n-i])

A veces hacer algo in situ es MUY DIFÍCIL. Un ejemplo clásico es la transposición general de matriz no cuadrada.

Ver también

• Algoritmo en el lugar
• Transposición de matriz en el lugar