Probando los algoritmos necesarios para las entrevistas de desarrollo

Una de las habilidades del desarrollo de pruebas es dominar algunos lenguajes de desarrollo y, para inspeccionar los lenguajes de desarrollo, la forma más fácil en la industria es inspeccionar varios algoritmos. Aquí hay un breve resumen (me gusta jugar Python recientemente, así que tomo Python como ejemplo y otros lenguajes como analogías).

Clasificación de burbujas

El algoritmo de clasificación de burbujas funciona de la siguiente manera: (De atrás hacia adelante)

Compara elementos adyacentes. Si el primero es más grande que el segundo, cámbialos.

Haz lo mismo para cada par de elementos adyacentes, desde el primero hasta el último par. En este punto, el último elemento debería ser el número más grande.

Repita los pasos anteriores para todos los elementos excepto el último elemento.

Continúe repitiendo los pasos anteriores para cada vez menos elementos cada vez hasta que no haya pares de números para comparar.

Ejemplo: lista de clasificación de burbujas [2, 8, 4, 7, 5, 9, 0]

Recursivo

Los procesos recursivos generalmente se componen de funciones o Implementación del subproceso. Método recursivo: llame a su propio algoritmo directa o indirectamente dentro de una función o subprocedimiento.

Ejemplo: Calcule el producto de 10 dígitos del 1 al 10. El algoritmo intuitivo es 1 2 3 4 5 6 7 8 9. La idea recursiva es recorrer n*n-1 hasta n=1 .

Algoritmo de recorrido de árbol binario

A partir de la definición recursiva de un árbol binario, un árbol binario no vacío consta de tres partes básicas: el nodo raíz y los subárboles izquierdo y derecho. Por lo tanto, en cualquier nodo dado, se pueden realizar tres operaciones en un orden determinado:

(1) Acceder al nodo en sí (n),

(2) Atravesar el subárbol izquierdo del nodo (L),

(3) Atraviesa el subárbol derecho (r) del nodo.

Hay seis órdenes de ejecución para las tres operaciones anteriores:

NLR, LNR, LRN, NRL, RNL, RLN.

Puedes utilizar la representación de nodo de un árbol binario

Recorrido de prefacio: nodo raíz ->; subárbol izquierdo ->; Recorrido en orden: subárbol izquierdo Árbol->Nodo raíz->Subárbol derecho

Recorrido posterior al pedido: Subárbol izquierdo->Subárbol derecho->Nodo raíz

Ejemplo: Encuentre la profundidad y el ancho del árbol binario

La recursión se usa para encontrar la profundidad; use una cola para encontrar el ancho y luego encuentre el ancho de cada capa.

Salida de cadena inversa

Idea 1: método de índice

Idea 2: buscar en la lista de grupos.

Si hay alguno, seguiremos agregándolos.