Recientemente me encontré con esta pregunta de la entrevista de codificación y parece que no puedo encontrar una respuesta. Aquí está la pregunta.
Dada una matriz de enteros, escriba una función que devuelva los intercambios mínimos necesarios para organizar la matriz de modo que todos los elementos adyacentes tengan una diferencia absoluta menor o igual a K. Los intercambios pueden ser de dos elementos cualquiera de la matriz, no necesariamente adyacentes.
Por ejemplo,
public static void main(String[] argv) { int[] arr1 = new int[]{10, 40, 30, 20}; int K = 20; getMinimumSwap(arr1, K); // should return 1 }La razón por la que debería devolver 1 es porque al intercambiar 40 y 30, la matriz cumpliría la declaración dada de que todos los elementos adyacentes deben estar dentro de los 20 entre sí.
Intenté buscar respuestas en Google, y pensé que encontré alguna respuesta en otros sitios de ayuda de algoritmos, pero no pude obtener las respuestas a mis preguntas. El caso de prueba fallido tenía una matriz de 3, 7, 2, 8, 6, 4, 5, 1 y K = 3 que debería devolver 2 .
La única restricción que puedo recordar es que la longitud de la matriz de entrada es 1 <= n <= 8 .
Abordaría esto como un problema de búsqueda de gráficos.
Para abordar esto como un problema de búsqueda de gráficos, primero debemos definir los estados de nuestro sistema. En nuestro caso, los estados serán la secuencia de los números.
Después de definir los estados, cada problema de búsqueda de gráficos puede hacer el trabajo, pero dado que desea la menor cantidad de intercambios, usaremos BFS.
Lo siguiente se implementó en python por conveniencia, pero también se puede hacer en java.
Primero, escribiremos una función de ayuda que, dada una secuencia de números, devuelva todos los intercambios de 1 posibles de esa secuencia:
def get_swaps(sequence): swapps = collections.deque([]) ii = 0 jj = 1 done = False while not done: temp_seq = sequence.copy() temp = sequence[jj] temp_seq[jj] = sequence[ii] temp_seq[ii] = temp swapps.append(temp_seq) if jj < len(sequence)-1: jj += 1 elif ii < len(sequence)-2: ii += 1 jj = ii + 1 else: done = True return swappsTenga en cuenta que esto no está escrito de manera óptima, pero funciona.
Ahora podemos implementar un algoritmo BFS de la siguiente manera (lea más sobre BFS y DFS aquí )
def findSwap(sequence, k): state_queue = collections.deque([]) # Pending states which have not been explored yet visited = set() state = (sequence, 0) # Starting state, starting sequence and 0 swapps min_diff = max([abs(sequence[1:][ii] - sequence[:-1][ii]) for ii in range(len(sequence)-1)]) found = True while min_diff > k: curr_seq = state[0] curr_count = state[1] # Getting all swaps possible swaps = get_swaps(curr_seq) # Adding to the queue and to visited set all the unvisited states for next_state in swaps: None if tuple(next_state) in visited else state_queue.append((next_state, curr_count+1)), visited.add(tuple(next_state)) # popping next state from the queue try: state = state_queue.popleft() curr_seq = state[0] min_diff = max([abs(curr_seq[1:][ii] - curr_seq[:-1][ii]) for ii in range(len(curr_seq) - 1)]) except IndexError: found = False break if found: return state[1] else: return -1En cada estado nosotros:
Después de finalizar la verificación de todos los siguientes estados posibles, sacamos el siguiente estado de la cola y verificamos la diferencia máxima. Si la diferencia máxima es lías, entonces hemos terminado. Si la cola está vacía, buscamos en todo el espacio de estado y no encontramos una solución, y en este caso devolveremos -1 .
Tenga en cuenta que, además de los estados, llevamos el número de intercambios realizados desde el estado original a este estado en la tupla.
Al configurar su matriz de prueba, obtenemos:
a = [3,7,2,8,6,4,5,1] print(findSwap(a, 3)) # 2, as expected