C++: preparación de una entrevista

1. ¡Bienvenido a este curso!: Hola chicos y bienvenidos a programación C plus blast. El entrevista de codificación. Mi nombre es Alex y tiempo de un experimentado desarrollador de software que lleva trabajando con C plus plus desde hace unos cuatro años. Ahora, la estructura de esta clase se va a dividir en elementos clave que se discuten documento de objetivo llamado entrevistas para desarrolladores de software. En primer lugar, vamos a hablar de las complejidades de un algoritmo, tanto el tiempo como el espacio. Entonces saltaremos a matrices. Entonces veremos las cuerdas. Entonces de nuevo, las preguntas de entrevista basadas en cuerdas es el tema en el que vamos a concentrarnos. Entonces también, veremos algunos algoritmos de clasificación muy importantes como la clasificación de burbujas, quicksort y así sucesivamente. También veremos los árboles. Son traversales, y algunas otras preguntas de entrevista que puedes recibir en DOM. Y además, echaremos un vistazo a las pilas y las colas. Se crea la clase para cualquier partido que ya sea una vez para aprender algoritmos en el lenguaje de programación de C plus plus, o alguien que quiera emplearse en el campo de la ingeniería de software. Y una vez que aprendas preguntas que se pueden dar en entrevistas para que puedan basar sus entrevistas. No hay prerrequisitos reales para este curso. Entonces tu disposición para aprender y una conexión a Internet. respecta al proyecto de clase, será una pregunta que se puede recibir en un escenario de entrevista que se puede ver. Piensa en la cabeza, puede ser tiempo tú mismo durante 30 minutos e intenta llegar al mejor extracto que obtienes. Por lo que llamó eso suena interesante. Espero verlos en la siguiente lección. Empecemos. 2. Notación de grandes O: Bienvenido a la Sección dos, gran notación O. En la conferencia uno, vamos a hablar de grande O, gran Omega en la complejidad del tiempo. Empecemos. La gran notación O es una notación matemática que describe el comportamiento limitante de una función cuando el argumento tiende hacia un valor particular o infinito. En la informática, la notación grande O se usa para clasificar algoritmos de acuerdo a cómo crecen los requisitos de tiempo o espacio. A medida que crece el tamaño de entrada. No entenderlo a fondo puede realmente lastimarte en el desarrollo de un algoritmo. No sólo podría ser acusado duramente por no entender realmente a Big O, sino que también luchará para juzgar cuando su algoritmo se está volviendo más rápido o más lento. Al analizar algoritmos para la eficiencia, usamos big O. Por ejemplo, el tiempo, el número de pasos que toma para completar un problema de tamaño n podría encontrarse para ser n veces n al poder de dos más ocho veces n más uno. A medida que n crece grande, el n al poder de dos término vendrá a dominar eso. Todos los demás términos pueden ser descuidados. Por ejemplo, cuando n es 500, el término cinco veces n al poder de dos es cien, diez veces más grande que las dos veces n. Ignorar la letra tendría un efecto insignificante sobre el el valor de expresión para la mayoría de los propósitos. Además, el coeficiente se volvió irrelevante si lo comparamos con cualquier otro orden de expresión. Entonces la gran notación O captura lo que queda. Escribimos o de n al poder de dos. Ahora, veamos algunos ejemplos de las complejidades del tiempo que ciertos algoritmos de informática. uno se le llama constante. Por ejemplo, un algoritmo que determina si un número es par o impar tendría esta complejidad temporal. O de log n se llama logarítmico. Por ejemplo, buscar un elemento con búsqueda binaria en una matriz ordenada. Voy a presentar este tipo de búsqueda y cómo funciona en una sección posterior de n se llama lineal. Esta es la complejidad temporal de iterar a través de una matriz para una variedad de propósitos. Por ejemplo, para encontrar un elemento y así sucesivamente. O de n al poder de dos se llama cuadrático. Este es el caso cuando tienes dos fuerzas anidadas en una matriz. Esto puede ser útil cuando se desea ordenar una matriz. Por último, o n factorial se llama factorial. Y nos encontramos con esta complejidad temporal al intentar, las soluciones de fuerza bruta están calculando permutaciones sin restricciones. En general, codificando entrevistas, ingresas complejidad del tiempo a, aunque como puedas, para que tu algoritmo tome menos tiempo en ejecutarse y ser más eficiente y optimizar. No obstante, puedes partir de una solución que no es tan grande si esa es la primera idea que llegas a resolverlo y luego trabajar tu camino hacia un enfoque más optimizado. Los académicos usan Peek, oh, big theta y omega grande para describir los tiempos de ejecución. En la academia, el gran Omega es el concepto equivalente, pero para el vínculo más bajo, la impresión, los valores en una matriz es gran omega de uno. Después de todo, sabes que no será más rápido que este tiempo de ejecución. Big Theta da un apretado encuadernado en tiempo de ejecución. Podemos decir que la vinculación de la función desde arriba y abajo está representada por notación theta. El comportamiento asintótico exacto se realiza mediante la notación d Theta. En este curso, usaremos solo la notación Big-O para nuestros algoritmos en la forma que la industria tiende a usarla siempre tratando de ofrecer la descripción más ajustada del tiempo de ejecución. 3. Descripción general de la matriz y la vectorial: Hola ahí y bienvenidos a la sección tres matrices. En esta sección hablaremos una estructura básica de datos llamada borrado que surge mucho en preguntas de entrevista sobre codificación. Y es muy importante para ti tener una buena comprensión de ella en la programación. Cuando pensamos en una matriz, pensamos en una estructura de datos que se asemeja a una colección de elementos, ubicaciones de memoria almacenadas. La idea es almacenar varios artículos del mismo tipo juntos. Esto facilita el cálculo de la posición de cada elemento simplemente agregando un desplazamiento a un valor base. Ejemplo, la ubicación de memoria del primer elemento de la matriz, generalmente denotada por el nombre de la matriz. El valor base es índice 0, y la diferencia entre los dos índices es el desplazamiento. Por simplicidad, podemos pensar en una flota de arreglos arriba donde en cada paso se coloca el valor, digamos uno de tus amigos. Aquí, puedes identificar la ubicación de cualquiera de tus amigos simplemente conociendo la cuenta del paso en el que están. Recuerde, la ubicación del siguiente índice depende del tipo de datos que utilicemos. Y dice, por defecto, matrices regulares de alcance local. Por ejemplo, los declarados dentro una función no se dejan sin inicializar. Esto significa que ninguno de sus elementos se envía a ningún valor particular. Sus contenidos están indeterminados en el punto se declara la teoría. Pero los elementos de una matriz se pueden inicializar explícitamente a valores específicos cuando se declara al adjuntar esos abrazos de valores iniciales. Por ejemplo, puedes ver aquí la primera línea de nuestra imagen. El número de valores entre alabanzas no será mayor que el número de elementos en la matriz. Por ejemplo, en nuestra imagen en la primera línea, se declaró teniendo cinco elementos especificados por el número en cierre los corchetes. Y la alabanza está contenida exactamente cinco valores. Uno para cada elemento. Declararlo con menos. Los elementos restantes se establecen en sus valores predeterminados, lo que para los tipos fundamentales significa que están llenos de ceros. El valor de los elementos en una matriz se puede acceder al igual que la falla de una variable regular. Del mismo tipo. La sintaxis es nombre y luego entre corchetes, el índice. Observe que el tercer elemental Fu especificó F-O-O. Entonces entre paréntesis el número dos. Dado que el primero es F0 de 0, el segundo es F0 F1. Y por lo tanto, el tercero es f o de dos. Por la misma razón, su último elemento, Es F0, F4. Por lo tanto, si escribiéramos algo como F0 05, estaríamos accediendo al sexto elemento de F-O-O, y por lo tanto en realidad superando el tamaño de la matriz. En C plus, plus. Es sintácticamente correcto exceder el rango de valores de índices para una matriz. Esto puede crear problemas ya que X está en elementos de flecos externos no causan errores en la compensación, pero pueden causar errores en tiempo de ejecución. Este punto, es importante poder distinguir claramente entre los dos usos que los corchetes tienen relacionados con el borrado. Realizan dos tareas diferentes. Una es especificar el tamaño de las matrices cuando se declaran. El segundo es especificar índices para elementos de matriz de hormigón cuando se accede a ellos. No confunda estos dos posibles usos de soportes con matrices. En algún momento podemos necesitar pasar una matriz a una función como parámetro, C plus plus. No es posible pasar toda la memoria de bloque representada por una matriz a una función directamente como argumento. Pero lo que puedes hacer es que puedas pasar en cambio sus entradas. En la práctica, esto tiene casi el mismo efecto y es mucho más rápido y eficiente operación desde este punto de vista base. Para aceptar un parámetro de matriz para una función. Los parámetros se pueden declarar como tipo, pero con corchetes vacíos están cumpliendo con el tamaño real de la matriz. Por ejemplo, para un procedimiento. Y luego en la lista de parámetros, int arg. Entonces algunos corchetes vacíos. Esta función acepta un parámetro de tipo array de int llamado ARG. Para pegar esta función, una matriz declarada como int, mis elementos de matriz, sería suficiente escribir un código como este procedimiento de mi matriz. Entonces esta sería una visión general del tipo de matriz en C plus plus. Por supuesto se pueden hacer muchas más operaciones con cada uno de los elementos. Puedes cambiarlos y así sucesivamente. A continuación, en las próximas conferencias, vamos a echar un vistazo a una variedad de algoritmos que muy a menudo surgen en la codificación de preguntas de entrevista. Y veremos su complejidad, diferentes enfoques, diferentes enfoques, y básicamente cómo resolverlos para que podamos estar mejor preparados para sus futuras entrevistas. 4. Borrar en una matriz: Hola chicos y bienvenidos a dar conferencias tres, eliminando en una matriz. En esta conferencia, vamos a hablar sobre cómo eliminar un elemento de una matriz. Esta pregunta tiene dos variaciones. De una matriz donde sabemos cuál es el valor del número que queremos eliminar de la matriz. Y la variación donde sabemos cuál es la posición del ítem en la matriz que queremos eliminar. Aquí mismo tenemos la variación donde se ingresa el valor del ítem y no deposición, pero la otra es muy similar a ésta. Vamos a ejecutar el código y después de la deuda y algunas explicaciones del mismo. Podemos pensar en la complejidad de este programa como lo haríamos en una situación de entrevista. Empecemos desde la media. Como buena práctica, siempre es bueno separar tus funciones de la función principal y luego llamar a tu función que escribiste para una pregunta específica de la función principal. En una pregunta de entrevista y un escenario de entrevista, incluso podrían darte la función sin el cuerpo. Entonces es sólo una cabecera. Y luego escribes la función que debería hacer cómo eso inició el SQL para. En nuestra situación, al entrar a la función principal, declaramos nuestra matriz int que vamos a eliminar, lo inicializamos con algunos valores integrales codificados. Entonces conseguimos cada lado dividiendo el tamaño de la teoría por el tamaño de una integral. Entonces escribimos x es seis. Queríamos eliminar seis de esta matriz. Ahora, llamaremos a la función de elemento delete, que devuelve el nuevo tamaño de la matriz después de la eliminación, y también obviamente elimina el elemento de la matriz. Esta función de elemento delete, como se puede ver, tiene tres argumentos. El primer argumento es nuestra matriz de la que queremos eliminar el elemento. El siguiente ítem. El elemento significa el tamaño de la matriz. Y el último ítem es el número que queremos eliminar de la matriz, en nuestro caso seis. Y como pueden ver, estos son los argumentos que pasamos cuando llamamos a la función. Lo que hace esta función es declara una variable i utilizada para iterar a través de la matriz. Y luego en un for-loop, iteramos a través de toda la matriz, tomando cada elemento. Y si el elemento es igual al elemento x D que queremos eliminar de nuestra matriz. Entonces rompemos. X se encuentra en la matriz y yo es el índice donde se encontró x. Vamos a disminuir el tamaño de la matriz porque va a ser un tamaño más pequeño de lo que era antes, porque obviamente vamos a eliminar un elemento de ella. Y luego vamos a simplemente mover todos los elementos un espacio por delante. Lesley, va a devolver el tamaño de la matriz. Aquí está la nueva longitud de la matriz. Entonces vamos a ver a Montecarlo y luego iterar a través de él y mostrarlo. Entonces si ejecutamos esto, vamos a ver la torre nueva matriz debería ser 1158910. Se puede ver que esa es la matriz. Así que ahora pensemos en la complejidad del espacio diamantado. La complejidad espacial es obviamente lineal porque no declaramos ninguna otra variable. Si lo hacemos, se consideran constantes. Este espacio es lineal y luego la complejidad del tiempo, bueno, iteramos a través de la matriz una vez aquí. Y obviamente una vez aquí. La complejidad del tiempo también es lineal. ¿ Podemos hacer esto en una mejor complejidad que ésta? Bueno, no, porque nuestro elemento puede ser el primero, entonces seguiría siendo lineal porque necesitamos iterar a través de toda la matriz. En este paso. Se trataba de eliminar un elemento de la matriz. Y ustedes pueden hacer la variación donde se elimina un elemento de una matriz donde saben que la posición es muy similar a ésta. Pero puedes probar eso en casa. Y avísame cómo fue. 5. Búsqueda lineal en una matriz: Hola chicos y bienvenidos de nuevo a la conferencia cuatro. En esta conferencia vamos a hablar de búsqueda en una matriz de enteros, más precisamente de búsqueda lineal. El escenario es que tenemos una matriz de enteros que tiene números que no están ordenados. Entonces cualquier tipo de números que sean enteros. Y el problema con el gas S para encontrar un número de esta matriz y devolver su índice. Ahora, obviamente escribiríamos una función separada de la función principal que llamamos, llamaría desde la función principal y usaría eso para encontrar nuestro elemento. Como se puede ver en mi código aquí mismo, declaramos que una tasa, está codificada, valores 2341040. Entonces el valor x que está ahí. Entonces vamos a, como de costumbre, utilizar el tamaño de función auxiliar para calcular el tamaño de nuestra matriz. Entonces vamos a dar nuestro int, que salan el valor de la función de búsqueda. Esta función devuelve un int y toma tres parámetros. Nuestra matriz, el tamaño de nuestra matriz, y el número que queríamos encontrar. Después va a iterar a través de ella con la ayuda de esta variable auxiliar llamada. Si bien pasamos por él, encontramos nuestro elemento necesario, entonces vamos a devolver su índice. Al final, vamos a devolver menos uno, lo que significa que no lo encontramos. Devolver i, como ya probablemente sepas, pero te recordaré esto. Te diré si no lo sabes, la declaración return cuando te sientas en tu función, detiene esa función y básicamente va a donde se llama a la función y devuelve ese valor. Entonces, ¿qué hay después de un regreso que se ha calentado? La función no se ejecutará. Este retorno menos una declaración solo será de calor si esta devolución nunca se ejecuta. Entonces si nuestro valor nunca fue encontrado en la matriz, el resultado con el índice del valor de la matriz que queremos encontrar. Si el resultado es menos uno, por supuesto, va a decir que el elemento no está presente. Y si va a decir que está presente en el resultado del índice que se devuelve de nuestra función. momento, como se puede ver, si ejecuta este programa, vamos a ver que ese elemento está presente en el índice tres. Ya sabes, el conteo en una matriz está basado en cero, lo que significa que el primer índice es 0. Por eso éste será uno a n El número de investigaciones para Dan es el índice tres. Ahora hablemos de complejidad. La complejidad espacial es del tamaño de nuestros primeros, lo cual es lineal en cuanto a la entrada. Entonces la complejidad del tiempo, bueno, la complejidad del tiempo está dada por nuestra función porque aquí mismo iteramos a través de nuestra matriz una vez. Eso significa complejidad temporal lineal. Ahora, ¿podemos hacer esto mejor que lineal? Bueno, no, porque en el peor de los casos, el elemento que queremos encontrar esta posición y eso significa que tenemos que iterar a través de toda la matriz para finalmente encontrarla en la última posición. Y eso tomaría tiempo lineal. En este problema, tanto la complejidad del espacio como del tiempo es apenas lineal. Pasemos a la siguiente conferencia, donde les mostraré una forma más eficiente de hacerlo. Pero bajo una condición, y esa es la matriz que se está ordenando cada vez más o disminuyendo. 6. Búsqueda binaria en una matriz: Hola chicos y bienvenidos a dar conferencias cinco, búsqueda binaria en una matriz. Este es básicamente el primer algoritmo más serio que vamos a abordar en este curso. Y éste se da más a menudo en entrevistas. Y tal vez no estas variación básica, sino otras variaciones que pueden tener otras limitaciones o no le pidieron la incesantemente implementar esto. Pero otro tipo de problema donde se necesita utilizar este tipo de algoritmo. El problema es que dada una matriz ordenada de n elementos, debes escribir la función para empezar a dar un elemento x en esta matriz. Un enfoque sencillo, como hemos visto en la última conferencia, sería hacer búsqueda lineal en tu matriz. La complejidad temporal sería lineal, como vimos en este espacio la complejidad sería lineal. Pero otro enfoque para realizar la misma tarea usando búsqueda binaria y dado el hecho que nuestra matriz ya está ordenada. Entonces, lo que básicamente hace la búsqueda binaria, en cambio, busca una matriz ordenada dividiendo repetidamente el intervalo de búsqueda. Inhale, comience con un intervalo que cubre toda la matriz. Si el valor de la clave de búsqueda es menor que el elemento en el medio del intervalo. Estrecho el intervalo a la parte inferior, ayuda, estrecharlo a la parte superior. Revisar repetidamente hasta que se encuentre el valor o el intervalo exactamente. La idea de la búsqueda binaria es utilizar la información que se ordena la matriz. Se redujo la complejidad del tiempo, logarítmica. Ahora bien, si miramos esta imagen, podemos ver un ejemplo. Tenemos esta matriz que tiene 2581216233856172091. Vamos a tomar m en el medio sería baja y sería 0 y h sería nueve. Los tres índices con los que estamos trabajando, necesitamos buscar 23. Bueno, vamos a revisar, y 16 es menor que 23. Por lo que vamos a pasar a la derecha. Vamos a tomar l, m, el promedio aritmético de n y h. Y podemos ver que 23 es menor, 36. Ir a buscar en la mitad izquierda. Y ahora mismo serían seis, porque será m menos uno. M sería cinco. Justo aquí buscamos 23 sin siquiera mirar artículos como 5812 o incluso 72. Ahora veamos el código y veamos cómo funciona. La función principal se asemeja muy a la última función principal que utilizamos en la búsqueda lineal en una matriz de enteros. La única diferencia es esa función que utiliza y devuelve los índices donde se encontró nuestro número. Esta función de búsqueda binaria, como se puede ver, toma cuatro argumentos. El primero es nuestra matriz de enteros. El segundo, el tercero es el R. O en el caso de que esta imagen sería h. porque aquí mismo tiene razón, había alto. Significan básicamente lo mismo. Y luego x es el número que fuimos a buscar. Vamos a hacer llamadas recursivas. Ir a empezar diciendo, no son tan correcto es más grande o igual a L. Vamos a declarar reunirse en el GRE y darle básicamente el promedio de R y L. Si se están preguntando, ¿por qué esta L más R no está dividida por dos? Y está escrito así. Bueno, esto en primer lugar lleva menos l y luego agrega. Esto ayuda a evitar casos de desbordamiento. El número es lo suficientemente grande como para superar la memoria y para tu programa básicamente se estrellará. Si matriz de carne era igual a x, el número que no buscábamos, entonces deberíamos devolver el índice porque lo encontramos. Si es más grande que el elemento que estamos buscando, entonces sólo podemos mirar en la submatriz izquierda. Entonces vamos a llamar recursivamente a la búsqueda binaria de ARR Again L. Y luego en lugar de área voy a llamar mid menos uno, sólo vamos a mirar en la submatriz izquierda. En el otro caso, vamos a mirar en el submarino derecho dando la llamada recursiva en lugar de l En el segundo argumento, mid plus one. Por último, si no se golpeó ningún otro retorno al regresar de las llamadas recursivas. Ahora va a devolver menos uno. Como se puede ver, si ejecutamos este programa, número diez fue encontrado nuevamente en el índice tres. Como he dicho antes, la complejidad espacial es lineal porque declaramos la matriz, entonces la complejidad del tiempo es logarítmica. Gracias a este bonito algoritmo. Sin embargo, si la matriz no está ordenada, no se puede encontrar un elemento en una mejor complejidad temporal que lineal. Esto solo se hace posible aquí porque sabemos que la matriz está ordenada y tenemos de esta manera, forma más rapida de mirar a través de ella. Se trata de búsqueda binaria. Puedes intentar implementarlo por tu cuenta sin mirar este algoritmo. Esta es una pregunta importante de entrevista y un algoritmo importante que realmente debes conocer muy bien. 7. Cuerdas: Hola chicos y bienvenidos de vuelta a la sección cuatro. En esta sección, estamos hablando de cuerdas. Las cadenas son objetos en C plus, más las tres secuencias presentes de caracteres. La clase String estándar proporciona soporte para dichos objetos con una interfaz similar a la de un contenedor estándar de bytes. Pero creo que características específicamente diseñadas para operar con cadenas de caracteres de un solo byte. Aquí podemos hablar de funciones miembro como swap, que intercambia el contenido de dos cadenas, append, que anexa una cadena a una cadena dada y devuelve un puntero a la cadena resultante. Insertar, borrar, encontrar algunos DEG y muchos otros. Adjuntaré aquí una imagen con descripciones para cada una de ellas para que puedas leerlas y entender lo que hace cada uno de ellos. También podemos hablar de operadores sobrecargados, como una flexión de dos calles. Se paran con el plus iguala firma concatenación, esta vez con el signo más. El operador de igualdad, implementando a través de señales de igualdad y así sucesivamente. Este vidrio también cuenta con una variedad de constructores. El vacío que crea una cadena vacía. El que toma como argumento, la cadena entre corchetes. Puedes escribir tu cadena y se inicializará ese objeto de bebida con la corriente que ahí mismo. El que toma un entero y un carácter y crea una instancia la cadena con ese carácter que será repetido por el número dado de veces. Para utilizar cadenas, debe incluir un archivo de encabezado adicional, código de ilustradores que se incluirá. Y luego cadena dot h entre paréntesis triangulares. Además, viste que podrías incluir iostream que proviene de entrada, flujo de salida, y por lo general necesitas escribir y leer la entrada del teclado. Tenga en cuenta que esta clase maneja bytes independientemente de la codificación, se utiliza para manejar secuencias multiplicadas o caracteres de longitud variable, como UTF ocho. Los miembros de esta clase, como longitud o tamaño, así como sus iteradores, seguirán operando en términos de bytes, no caracteres codificados reales. En las próximas conferencias, vamos a echar un vistazo más de cerca a algunas preguntas de codificación de entrevistas que podrían surgir que usan cadenas. Vamos a trabajar. 8. Concatenación y búsqueda de la longitud de una stringConcatenation y búsqueda de la longitud de una cuerda: Hola chicos. En esta conferencia vamos a hablar contacto nación y encontrar la longitud de la calle. Empecemos hablando de concatenación. El operador plus se puede utilizar entre dos cuerdas. ¿ Los agrego juntos y hago una nueva cadena? A esto se le llama concatenación. Vamos a tratarlo en C plus. Plus es en realidad un objeto, como ya hemos hablado. En la última conferencia. Bonito objeto contiene funciones que pueden realizar ciertas operaciones en cadenas. Por ejemplo, también puede concatenar cadenas con la función append. Puedes hacer esto de la forma que prefieras. Hablar en un nivel más concreto. Puedes ver en tu código algo así como cadena S es igual a un plus b, donde a es otra cadena y B también es una cadena. Y concatenarlos haciendo este gemelo de a y B al final. Y básicamente hará que uno sea tres, contiene ambos primer día y luego B. Ahora para obtener la longitud de una cadena, se puede utilizar la función length tiene profunda. Es posible que veas algunos programas C plus plus que usan la función size para obtener la longitud de la cadena. Esto es solo un alias que está en blanco. Depende completamente de ti si quieres usar longitud o talla. Ahora por supuesto, si quisieras implementar este problema sin usar estas funciones preconstruidas, será bastante simple. Tendrás que iterar a través de cada carácter de la matriz con un bucle for y luego tener una instancia integral con 0 incrementado para cada personaje. De esa manera se puede obtener la longitud sin estas funciones preconstruidas. Puede acceder a los caracteres en una cadena, como lo haría en una matriz de autos refiriéndose a su número de índice dentro de corchetes. Cambiar el valor de un personaje específico. String, refiérase al número de índice y use comillas simples, porque eso es un carácter. 9. Cambio de caso de cuerda: Hola ahí. En esta conferencia vamos a hablar de cómo podemos cambiar la corriente de casos. El problema aquí es que necesitamos convertir todas las letras mayúsculas a minúsculas y viceversa. Industria. El nuevo enfoque aquí sería iterar la cadena y usar la ISA por función de pre-compilación para determinar si cada carácter está en aplicación real o no. Si es mayúscula, lo convertiremos minúsculas usando la función preconstruida de CO2 inferior. Y si no es mayúscula, lo convierte en mayúsculas usando dos funciones preconstruidas superiores. Ahora, también podemos hacer esto sin estas funciones preconstruidas sumando o restando el valor 32. Porque esa es la diferencia en números entre un valor mayúsculas y minúsculas. Por ejemplo, la letra mayúscula tiene un valor ascii de 65, y minúsculas tiene un valor ascii de 97, que es 65 más 32. También puedes usar este pequeño carajo para hacer este problema. Si el entrevistador especifica que no se le permite utilizar ninguna función de cadena preconstruida. Ahora, si miramos el código, tenemos esta función principal donde declaramos una corriente STR, también especifica el alcance std porque no usamos usando namespace std. Por lo que puede escribir el uso de namespace std o decir std. Y estos dos puntos dobles ante Amy, miembro de STD que escribes. En la siguiente línea, inicializamos la cadena STR con esta cadena justo aquí. Y luego llamamos a la función transform en este STR con el uso de tres iteradores desde el inicio de la cadena SDR hasta el final de la historia o cadena, entonces no vamos a respirar Marzo llamó The Change Case para cada carácter de la misma. Esta es solo una forma de iterar a través de él. En la línea 16, las funciones The Change Case toma un carácter y devuelve un carácter, como se puede ver en su encabezado. Y es solo una función if que verifica si el carácter es mayúscula, entonces devuelve la minúscula. Y si no es significa que sea minúsculas. Ese caso vamos a devolver la celda de carácter mayúscula después de transformar toda la cadena con esta función, lo hará prácticamente cada primera Casey. Entonces vamos a escribirlo en el símbolo del sistema de salida. Y como se puede ver, si ejecutamos este código, obtenemos la cadena exacta que inicializamos el caso invertido. Ya he dicho que puedes usar el pequeño hack 32 para hacer este problema sin ninguna función incorporada. 10. Contar palabras/vowels: Hola chicos y bienvenidos de nuevo a la conferencia cuatro. En esta conferencia vamos a hablar de cómo se puede llegar hacia las vocales en una cuerda. Básicamente una cadena más grande que tiene espacios entre palabras. Algo así como muestras o Pablo puede ser si es un premio. Como suena el problema es que la función que se supone que debes escribir recibe un argumento que es una cadena, y luego necesitas devolver el número de vocales. Para la cena de palabras. Este es el problema del que vamos a hablar hoy en esta conferencia. Como pueden ver, ya lo codificé para ustedes, pero vamos a correr, como lo hacemos habitualmente. Encomiar, ir a discutir lo que básicamente hace todo es generalmente partimos de la función principal. Aquí declaramos una cuerda que llamé SDR y Nike pies espacio ABC. Y ahora tenemos dos funciones para contar el número de valores que tiene. Primera función recibe el tercer personaje, devuelve brillante. Lo que hace. Gracias a este personaje. Parte superior. Por ejemplo, sería una minúscula. Se lo devuelve a mayúsculas. Podemos verificar contra los dientes superiores impecables y no la minúscula también, porque entonces habríamos tenido aquí cinco condiciones con el operador OR entre ellos. Lo que hacemos es volver ahí, el personaje. Carácter. El carácter es un personaje como este, E, I, O, U. Alguno de estos asientos es cierto? Entonces volvemos a esta función. Como se puede ver, se llama desde otra función se llama contar vocales. Este recibe un parámetro de cadena basado TR. Inicializa e integra, cuente. El valor 0. Después iteramos a través de la cadena, a través de cada uno de sus caracteres. Entonces si el personaje muerto vocal, entonces subimos la cuenta. Al final, lo devolvemos. Este es un método muy simple para devolver el número de vocales de cuerda. Ahora hablemos de la complejidad de este algoritmo. Bueno, en primer lugar, este espacio es lineal porque no declaramos más que este tratamiento en sí mismo. Entonces la complejidad del tiempo es lineal a, porque iteramos a través de cada uno de los caracteres de la cadena, tanto tiempo como espacio y lugar. Estas son grandes O lineales de n. Ahora, pasando al siguiente problema, va a contar las palabras. Eso va a hacer esto escribiendo una función que recibe de parámetro que es una corriente y luego devuelve un entero. Clara Decker, ahora que inicializamos con 0 y un personaje que llamamos preforma muerte anterior se inicializa con el espacio. Ahora comemos el camino a través del arroyo que recibimos como parámetro. Si el espacio actual del personaje en la lección anterior, incrementamos. Ahora, ¿qué significa esto? Bueno, significa que encontramos el comienzo de una nueva palabra porque el personaje, ahora no es el espacio en el espacio anterior, solía ser una palabra nueva, una. Por último, vamos a actualizar anterior con x de i Cuando miremos en la siguiente iteración. Actual, anterior, de ahí el oso actual anterior. Orientación decente. Vamos a devolver el número ahora. Gracias, no se puede ver. Si llamamos a esta función, devuelve dos. Porque nuestra cadena ABC espacio D0 sería considerado tener algún abc. Y entonces estas no son palabras reales. Pero si estás escribiendo una frase que no teníamos sentido, valdría la pena. Ahora hablando de la complejidad de este algoritmo, creo que es bastante claro que este espacio está en lo que respecta a la entrada, porque no declaramos nada más que la corriente misma. Contamos con complejidad espacial lineal, complejidad del tiempo. Sería lineal también porque comemos el retardado una vez a través del arroyo para comprobar la condición y el valor anterior. Aquí mismo. Hablamos de dos algoritmos básicos que surgen. Unas cuantas preguntas. Problemas de inicio. Son muy básicos, pero es muy importante comenzar con las muy básicas en la comprensión las complejidades y cómo hacerlas de manera óptima. Porque entonces se puede construir sobre la base, profundidad. Hay que resolver y comprender algoritmos y problemas más complejos en el futuro. El siguiente capítulo del que vamos a hablar tiene que revertir una cadena, que es una pregunta de entrevista más comúnmente conocida. 11. Reversión de una cuerda: Hola chicos, bienvenidos de vuelta. Esta conferencia, vamos a hablar de cómo revertir una racha dada. ¿ Cómo vas a hacer esto? problema dice, es que dado este gen de entrada, desde el teclado o un archivo, solo le das el valor que codifico duro la tarea matric tapiz Jeff, y el problema es revertirlo. Entonces por ejemplo, si tenemos una cadena, si su función con idealmente tendemos a transmitir se refiere a la deuda sería orden inverso. No vamos a discutir cómo implementamos esta función y cuál es su complejidad cada celda, primer lugar, declaramos una cadena. Dice Bienvenido a las plazas. Entonces simplemente llamamos a esta función encendida. Esta función no devuelve nada. Es una función de tipo de retorno vacío. Inicializamos la longitud del arroyo, luego iteramos a la salud del arroyo. Lo que hacemos es intercambiar entre ellos, los personajes coincidentes. Por ejemplo, cuando veo o vamos a intercambiar estos T-R-I-E sabroso r i n menos u, o menos uno, menos uno. Porque contando matrices decentes basados en cero, vamos a hablar para intercambiar el primer elemento, que es 0, elemento que es menos uno, un basado en cero. Por ejemplo, la cadena. Vamos a tomar la intención G menos uno. Se va a tomar la indexación única luego n menos dos, que luego los cambia y luego los canjea. Puntos. Calientamos el medio de la calle, nos detenemos. Esta es básicamente la forma más óptima hacer esta operación. Y esto, se puede ver si caliento, vamos a recibir estos genes a la inversa. Ahora, hablemos de la complejidad espacial de este algoritmo. En primer lugar, esta complejidad espacial es saludos lineales porque no recibimos la complejidad del tiempo. N dividido por dos, porque la mitad de la matriz deja de hacer coincidir caracteres entre ellos. Como sabemos, sólo el n y su poder. Sería la notación Big O de la complejidad del tiempo, así como la complejidad espacial sea lineal a este algoritmo. En la siguiente conferencia, vamos a ver cómo logramos comprobar si una palabra o una cuerda es un palíndromo. Benadryl, lo que significa que este sueño que tienes primero es el mismo. Pasemos y hablemos de cómo podemos hacer eso. La complejidad de ese algoritmo sería. 12. Comprobar el palindrome: Hola chicos y bienvenidos de nuevo a la conferencia del curso. Vamos a ver cómo podemos comprobar si funcionó? Significar que una cuerda es un palíndromo significa que es lo mismo. Es lo mismo si lo leemos de izquierda a derecha. Por ejemplo, un BBA sería un Benadryl porque probablemente sería forma ABB. Eso seguiría siendo un BBA. Éste sería un poco de drama también, pero estos no lo serían porque lo leíamos de izquierda a derecha más allá la vida media, el principio. Repita de derecha a izquierda. Tenemos dos LC NOSOTROS. Ahora que hemos entendido cuál es el problema, harías una entrevista. El primer paso es entender cuál es el problema una vez de ti. Podemos pensar en cómo resolverlo. Pero como acabamos de hablar de cómo revertir una cadena, este es un problema muy similar en estos muy fácilmente hechos si tenemos el algoritmo inverso, porque solo necesitaríamos comprobar si nuestro stream sería igual al revés de la misma. Con p igual, probablemente sería cierto. Pero ahora vamos a tomar otro enfoque a este problema. Resuelve va a funcionar como una cadena de parámetros. Y entonces no vamos a devolver ningún grado porque vas a simplemente imprimir en la salida este gen que recibe como parámetro. El parámetro va a empezar por los valores iniciales 0 y luego envejecer con el tamaño de nuestra corriente. Entonces, mientras que índice, índice, índice, este caso XDR de no igual al STR. Entonces el personaje mágico desde el principio, no la escena que vamos a imprimir. La cuerda no es aparente. Dibuja el regreso a la función h y del cruce de caminos. Significando que la edad no está invertida, significa que toda la corriente, podemos dibujar esto. Se puede ver si arrastro, se echa un vistazo a cada uno de estos trucos. Entonces un BPA, un BB, CC, BB o no. Complejidad. La complejidad se refiere fácilmente hoy en, pero porque tenemos esta constante napa aparte de la corriente de entrada, sería el caso, es dos divididos por dos porque todos necesitamos tener este gen. Llegamos a la mitad de h sería el bucle while con TI. La complejidad es lineal instagram se refiere a lo preciso, estos serían obviamente topo lo detuvo lejos para hacerlo. Porque todavía tienes que revisar a través de la teoría para asegurarte de que todos los personajes sean iguales para que puedas confirmar que tus alumnos sobre en la última conferencia de esta sección, la siguiente conferencia. Vamos a comprobar si dos cadenas son anagramas, es decir, publicar los mismos caracteres. Ahí hay más. Vea cómo podemos hacer para ser el algoritmo más óptimo. 13. Comprueba si 2 cuerdas son anagramas: Bienvenido de nuevo. En esta última conferencia aquí hablando de cómo se puede comprobar dada fuerza? Palabras? Pueden ser oraciones. Lo que significa que están compuestos por personajes. ¿ Qué quiero decir con muestra? Tenemos dos palabras, como perro. Perro sería anagramas porque uno T1, 01. Esto sería un acuerdo más porque el conteo dentro de estos corren con f one g, y éste tenemos dos anagramas de G. El problema nos pide escribir la función para comprobar si dos cadenas son o no son anagramas. Para que como se puede ver, la función principal empezamos inicializando cada una de estas cadenas. Estamos llamando a una función que toma como parámetros dos flujos serán ciertas. Si este G es integro función coseno, declaramos dos enteros que enlazan. Primero vamos a revisar las cuerdas tienen la misma longitud. Significa que no pueden tener los mismos personajes. Porque obviamente dos cantidades de caracteres no pueden ser iguales antes que el altavoz TPI fuera, van a ordenar cadenas. Las estrellas, las ordenan en función de los valores ascii, las ordenan en orden alfabético. Entonces vamos a ser tres genes a la vez. ¿ Aquí usamos entonces uno, pero podríamos haber usado porque básicamente lo mismo. No estaríamos en esta función, esta línea porque podría bombo ya devuelto falso booleano. Iteramos a través de cada uno de estos genes y revisamos su carácter, decimos iguales, no iguales, devolvemos falso. Llegamos al final de ellos en cambio, personajes de charla son iguales y podemos volver verdaderos. Ponemos esta función que devuelve cada estado uno a diez. Podemos estos arroyos, se dibujarán gramos. De lo contrario podemos decir que no lo son. Por ejemplo, si vemos estas dos cadenas, la muestra correcta, puede ver que son n Si cambiamos la segunda corriente, lo que haría es básicamente con esta condición, ser un falso o incluso podemos hacerlos del mismo tamaño, letras diferentes y las dos, sigue siendo pacientes negros que se pueden ver aquí mismo porque los ordenarían en orden alfabético y verían que uno es p, uno es G. Mejor esto si tendencia de declaración aquí, tres veces falso. Ahora hablemos de la complejidad del programa. La solución salina se refiere a la complejidad espacial. Podemos considerar el primer streaming. La complejidad espacial sería grande O de n más m. gracias chicos por quedarse conmigo. En esta sección. Vamos a continuar con la siguiente sección. Tema muy importante respecto a las preguntas de codificación de entrevistas. Clasificación. Ya sea si hablamos de la guardería o como se puede ver, puede ser muy útil cuando trabajamos con cuerdas. Entonces vamos a encubrir su sección de complejidades ahora. 14. Función de la clase de STL: Hola chicos y bienvenidos de nuevo a la conferencia dos. En la segunda conferencia, estamos hablando de la función de clasificación que está disponible en la biblioteca estándar de C plus plus. Se puede utilizar como una alternativa fácil cuando el entrevistador en realidad no está tratando de probar su capacidad para ordenar una matriz o alguna estructura de datos, pero se requiere para hacer el resto de su problema. Puedes intentar usar estos ordenar una función. Y es un escenario en el que necesitas ordenar tus artículos, pero no necesitas implementar realmente todo el algoritmo por ti mismo. La clasificación es una de las funciones más básicas suministradas datos. Significa obviamente organizar los datos de una manera particular, que puede estar aumentando o disminuyendo o cualquier otra función de comparación que pueda usar dependiendo de la estructura de datos que tenga. En ambientes más complejos. Supongamos que tienes estructuras de tipo cat. Quieres pedirlos por el número de bigotes que tienen. Tendrá que implementar esta función de comparación específicamente. En realidad se puede pasar tercer argumento a esta función. Lo veremos más adelante. Los ordenará básicamente por bigotes de número. Hay una función incorporada. Como ya he dicho, el C plus plus STL viene de la biblioteca estándar. Nombre de esta función. Los intereses de usos internos están en más detalles sobre cada implementación porque el entrevistador podría incluso SQ, cómo se implementan estas funciones si ve que la usas. Bueno, se usa un híbrido de ordenación rápida, tipo de montón, y ordenación de inserción. Dependiendo de algunos factores. Por defecto utiliza quicksort. ¿ Qué pasa si la ordenación rápida está haciendo particiones injustas más de n log n tiempo? Se cambia a tipo de montón. El tamaño de la matriz se vuelve realmente pequeño. Vuelve a cambiar a ordenación de inserción. Ahora, si echamos un vistazo a este código aquí mismo, podemos ver esta función aquí mismo en acción. Se puede ver en la función principal que miramos unary que inicializamos matriz codificada en duro. Entonces obtuvimos tamaño usando el tamaño de los operadores. Entonces usamos esta función aquí mismo que toma dos iteradores. Entonces le dimos ARR, que es el puntero del primer elemento de la matriz. Entonces ARR plus n, que es el final de la matriz. Entonces lo ordena. Para verlo en acción. También lo imprimimos en la pantalla después clasificar y como puedes ver aquí mismo , lo ordenamos cada vez más. Ahora como ya he dicho, sus familiares más allá de esta función de ordenación, tercer parámetro de comparación que ordenaría los elementos de una manera diferente. Muéstrale esto. Mantendré esta función de ordenación, parámetro, función de comparación que ordena los elementos de manera decreciente. Eso se llama mayor latido. Se alteró nuestra decreciente. Podemos por supuesto, implementar su propia función aquí mismo que pueda escribirse por encima la función principal que toma dos parámetros y devuelve un booleano sobre si cualquier condición que quieres reordenar es cierto. Este año sería una forma muy interesante y fácil eludir la clasificación en una entrevista. Como he dicho, si el entrevistador es esa deuda, curioso por ver si en realidad puedes ordenar la matriz tú mismo o S2 para un algoritmo de clasificación específico. Además, dada la complejidad del tiempo por su implementación, es n veces log de n Y esa es en realidad la mejor complejidad por la cual se puede pedir una matriz. Ahora, en las próximas conferencias, vamos a echar un vistazo más de cerca a algunos algoritmos de clasificación que en realidad se implementan. La forma en que trabajan. Además, veremos sus complejidades. Vea algunas formas de ordenar una matriz u otra estructura de datos que pueda tener. 15. Bubblesort: Hola chicos y bienvenidos de nuevo a la conferencia tres. En esta conferencia, hablaremos del algoritmo más básico que ordena una matriz que pueden implementar por ustedes muy fácilmente. Se llama burbuja sort. No tiene la mejor complejidad del tiempo y el espacio. Pero llegaremos a eso en un segundo. En primer lugar, tengo que decir sobre este algoritmo, además del hecho de que es el algoritmo de clasificación más simple existe, cómo funciona es intercambiando repetidamente los elementos adyacentes si están en el mal orden. Así que ahora veamos este ejemplo para que podamos visualizar mejor que mirando el código. ¿ Cómo es la forma en que el algoritmo es realmente de célula blanca? Vamos a llevar la matriz 5142 a lo que hace. Básicamente pagó primero dos elementos. Y ve que cinco es más grande que uno, por lo que los intercambia. Entonces se necesita 545 también es más grande que cuatro, por lo que los cambia de nuevo. A continuación, 525 es mayor que dos, por lo que los intercambia. Y al final tenemos 58. Estas son correctamente posicionadas, por lo que no hace ningún swaps. Después pasa otra vez. Tomando elementos dos por dos, como ya he dicho, elementos adyacentes, parafrasearlos si están en el orden equivocado y si lo son, los intercambia, si no, no lo hace. Uno de cada cuatro están en el orden correcto, por lo que no va a intercambiar venir por él o no en el orden correcto porque cuatro es mayor que dos, por lo que los vamos a intercambiar. 45 están en el orden correcto y luego 58 están en el orden correcto. Nuevamente. Se puede ver en este punto nuestra matriz ya está ordenada, pero nuestro algoritmo no sabe si está completamente ordenado todavía, porque podría no haberlo hecho en este punto. Por lo que se necesita otra esperanza es que no va intercambiar obviamente ningún elemento porque ya son o terceros enviando. Pero como se puede ver en la tercera base, se necesita de nuevo los elementos Dubai, y no hace ningún swaps. Ahora, veamos el código para este algoritmo. Como se puede ver en la función principal, estamos declarando suele ser una matriz codificada con algunos valores en ella. A continuación declaramos una integral, y esta vez para comer el tamaño de nuestra matriz que declaramos, haciendo uso nuevamente al tamaño de operador. Y luego estamos llamando a la función de ordenación de burbujas. Eso como se puede ver, se necesitan dos parámetros, nuestra matriz, y ahora se está moviendo hacia arriba en la pila. Se puede ver que entra en la función de ordenación de burbujas. Devuelve un vacío porque simplemente ordena la matriz y no devuelve nada. Para el primer elemento toma la matriz en esto, he dicho, el segundo elemento es del tamaño de la misma. Ahora vamos a declarar dos elementos, yo y j. Theta. Solo estoy acostumbrado a iterar a través de la matriz. Va así. Consulta. Cada elemento de la matriz, volveremos a ir de 0 a n menos I menos uno. Se puede ignorar porque está basado en cero. Básicamente pasa del primer elemento de la teoría al elemento n menos. Y luego comprueba si ARR de j es mayor que ARR de g más uno. Lo que significa que tenemos un elemento más grande que está antes de un elemento más pequeño. Y no podemos tener este SP1 a nuestra matriz en orden ascendente. Intercambiar las direcciones de los elementos ubicados en, antes de dichos índices. Exhibición haciendo embarazada el cambio. Y cuando volvemos a imprimir la teoría, puede ver que cuando ejecutamos el programa imprime cada vez más la matriz ordenada con el hecho de que el segundo bucle en el itera a n menos I. Hay una razón detrás de eso. Debido a que los elementos de matriz después de n menos ya ordené. Porque si lo pensamos, primero, va va de 0 a n menos uno. Entonces el final de la teoría en el segundo bucle va de 0 a n menos I menos uno, que también es n menos uno. Por lo que va hasta el final. Se mantiene la oportunidad de que el último elemento esté en la última posición. A continuación, iterar de 0 al último elemento. Y entonces el elemento de cadena iterará en los dos n menos uno menos I, que será uno, eso es n menos dos. Por lo que excluye el último elemento. Básicamente buscará el segundo elemento más grande de la matriz y así sucesivamente. Así funciona el algoritmo. Se continuamente treinta, donde el elemento más grande para ponerlo al final de la teoría. Al final, entiendo que el final no está ya ordenado. La primera iteración, buscará el elemento más grande, más grande. La segunda iteración para la segunda más grande, y así sucesivamente, llega al primer elemento de la matriz ya está ordenada. Si tuviéramos que hablar de la complejidad del tiempo y el espacio de este algoritmo, la complejidad espacial es lineal en cuanto a la entrada porque acabamos de declarar esta matriz aquí mismo, y luego declaramos dos variables, iterando tres, pero que se consideran constantes. Entonces la complejidad espacial es grande O de m y es lineal. Ahora llegar a la complejidad temporal de este algoritmo es grande O de n al poder de dos. Entonces es una complejidad de tiempo cuadrática ya que el algoritmo itera para cada elemento de la matriz. Otra iteración a básicamente no realmente a todo el rayo, pero se obtiene la idea. Tiende asintóticamente a una complejidad cuadrática. Ahora de nuevo, tenemos una función de swap de la que ni siquiera hablé. Qué hace esto. Como se puede ver, no devuelve nada que se necesita para integrar punteros y se intercambia entre ellos. Ese es un algoritmo de clasificación muy rápido y simple que puedes usar en una carrera que querías ordenar el inglés cada vez más. Pero solo saber que su complejidad temporal es cuadrática y no el mejor tipo de complejidad de tiempo que se puede tener al clasificar una matriz, lo que BASF ya dijo n log n Así que si proponer implementar este algoritmo ahora que no es esta complejidad de tiempo, como se puede ver en la próxima conferencia, hay mejores algoritmos de clasificación por ahí que se podría aprender y en realidad implementar durante tu entrevista al ser preguntado al respecto. Pero es una fundación. Y este es un algoritmo bastante básico. Es bueno primero hacer contacto con un algoritmo de clasificación más fácil para empezar. 16. Quicksort: Chicos, bienvenidos de nuevo a la conferencia cuatro. En esta conferencia hablaremos de Quicksort. Quicksort es otro algoritmo de clasificación que funciona en matrices. Y es algoritmo más eficiente entonces proponer ordenación Desde el punto de vista de la complejidad del tiempo y la complejidad del espacio. Ahora, a diferencia de marzo hacia, quicksort es un algoritmo de división y conquista. Lo que hace, simplemente elemento grande y particiona la matriz dada alrededor del pivote. Muchas versiones diferentes de quicksort, ese gran pivote diferentes maneras sería elegir siempre el primer elemento es. Otra forma sería escoger siempre el último elemento, este pivote, como lo haremos en nuestra implementación. Verás eso en un segundo. Entonces puedes escoger un elemento aleatorio es periodo. La mejor manera sería escoger la mediana SPM ella. El procesamiento de claves quicksort es partición. El objetivo de la partición. Dada una matriz y un elemento x de matriz pivot. Lo que hace esta función de partición es que pone x y su posición correcta en una matriz, lo que significa que todos los elementos más pequeños entonces estaría a su izquierda. Y todos los elementos mayores entonces estará en él, ¿verdad? En este proceso sólo debe tomar complejidad lineal del tiempo. Miramos el código y tratamos de entenderlo. Vamos a ver que en la función principal declaramos una matriz como siempre hacemos estos valores codificados. Después tomamos su longitud usando el tamaño del operador. Y luego llamamos a una función llamada quicksort que toma tres parámetros. El primer parámetro es la matriz. El segundo parámetro, puntos rosados sobre enlazado a eso se quiere ordenar, en nuestro caso, primer índice de elemento, siendo ese 0. El último elemento, ese tercer parámetro, el encuadernado superior que querías ordenar en nuestro caso, el último índice de elemento, y eso es n menos uno. También declaramos un par de funciones de transporte de oxígeno. Uno de ellos teoría de la impresión. El segundo es intercambiar dos elementos usando punteros. Ahora, si vamos a la función QuickSort que se llama desde la función principal, vamos a ver, en primer lugar, verifica si baja es menor que esto se hace porque después lo haremos Llama recursivamente a esta función en las subbarras izquierda y derecha del pivote. Por lo que siempre tenemos que mantener eso en control que el encuadernado inferior es más bajo que el vínculo más alto. Entonces va a dar el valor de perdición de nuestra matriz. Y límites inferiores y superiores siendo el índice de particionamiento. decir, ¿dónde está nuestro pivote en la posición correcta en la matriz que se ordenaría. En esta declaración de la que acabamos de hablar. El puesto donde todos los elementos de su izquierda y más pequeños que él, y todos los elementos en ella son más grandes que él. No importa cuál sea su orden porque la matriz se ordenó o no. No importa. Ese elemento se encuentra en la posición de la pista donde ocurre esa condición. Y luego llamaremos recursivamente a esta función nuestra matriz, la posición de enlace bajo y pivote menos uno. Y luego nuestro índice de pivote de matriz más uno y luego un enlace más alto, lo que significa que recursivamente llamaremos quicksort para la submatriz izquierda y la subbarra derecha del pivote que es correctamente posicionado en este punto. Veamos qué hace esta función de partición. También toma tres parámetros como lo hace la función QuickSort. Declaramos un pivote. Integral toma el último elemento porque como he dicho, implementaremos la variación de QuickSort donde se toma el pivote como último elemento de la matriz. Entonces declararemos I, que sería o menos uno, menos uno, porque el primer elemento de nuestra matriz sería 00 menos uno es menos uno. Veremos en un poco por qué lo tomamos menos uno y no 0. Y luego usaremos otra integral para iterar a través de toda la matriz. Iterando a través de toda la matriz. Decimos si ARR de g, decir, el elemento actual de la iteración, es menor que el pivote. Primero incrementaremos I, luego intercambiaremos ARR de I de j Entonces nos moveremos en estos tintes, iteración lineal a través de la matriz. Y 28, estamos encontrando un artículo que es más pequeño que nuestro pivote. En este caso, el último elemento de la sub-matriz que estamos en ello, lo pondremos en el inicio de la matriz. Al principio, bueno, primer índice que aún no está ocupado. Pone todos los elementos que son más pequeños que nuestro pivote en el frente de la matriz. Entonces por último, intercambiaremos ARR de I más uno con nuestro pivote. Porque ese es su lugar correcto en la matriz. Ahí es donde estaría mal si se ordenara la matriz , simplemente devolveremos este índice, ese sería su índice correcto. Ahora, se puede ver que entendimos cómo funciona la función de partición. Y también entendimos que después del frío, también llamamos recursivamente a esta función de partición en la sub razón izquierda y derecha para pivote. De esta manera, clasificando la matriz. Ahora como se puede ver, tenemos una matriz de elementos luego 789, Uno, y cinco. Cuando lo ejecutamos. La función PrintArray debe imprimir nuestra matriz. Esto, se pueden ver estos datos de ordenación. Ahora hablemos un poco de estos algoritmos. Los respetos de estabilidad no están en su lugar. Inmueble. En primer lugar, ¿ Quicksort es estable? La implementación por defecto no es estable. No obstante, cualquier algoritmo de clasificación se puede hacer estable considerando los índices como parámetro de comparación. En segundo lugar, experto, la amplia definición de algoritmo in place. Quicksort califica como un algoritmo de clasificación de empleados. C2c es espacio extra solo para almacenar llamadas a funciones recursivas, pero no para manipular la entrada. Podemos decir que tiene complejidad espacial lineal. Hablemos de la complejidad del tiempo para ver realmente lo eficiente que es este algoritmo. Bueno, a pesar de que es mejor que el tipo de burbuja, que en el mejor tiempo la complejidad sería lineal. Pero en los casos promedio y peores sería cuadrático, sería grande O de n al poder de dos. Patrón Quicksort en la complejidad de tiempo promedio, varios n log n La complejidad de la máscara sigue siendo n log n, pero la peor complejidad sigue siendo cuadrática. N al poder de dos. En las entrevistas, el nombre realmente te pregunta algo sobre semanas. Si no la plena implementación. Puedes preguntarte si sabes cuál es su complejidad temporal, si sabes cómo funciona la función de partición y cuál es su complejidad temporal. Que por cierto es lineal. Como ya vimos. Solo iteramos a través de la matriz. Y podría incluso SQ las llamadas recursivas en función de ordenación rápida donde es un muy buen algoritmo de clasificación en una entrevista. Y es una herramienta muy útil que puedes usar para ordenar los elementos de una matriz que tienes. Cuando no tienes la función STL sort, bubble sort, bubble sort. Si quisieras algo más eficiente, entonces este algoritmo sería una combinación perfecta. 17. Árboles: Hola chicos y bienvenidos de vuelta a la sección seis de este curso. En esta sección hablaremos la nueva estructura de datos llamada threes. Y a diferencia de matrices, listas enlazadas, pilas y colas, que son estructuras de datos lineales, los árboles son estructuras de datos jerárquicas. El nodo superior se llama raíz del árbol. A los elementos que se encuentran directamente debajo un elemento se les llama sus hijos. D elemento directamente encima de algo se llama su padre. Por ejemplo, a es hijo de f y f es padre de una en esta deuda arbórea que dibujamos en la pantalla, ¿verdad? Por último, los elementos sin hijos absoluto se llaman hojas. Ahora hablemos de por qué usaríamos árboles? Bueno, una de las razones sería porque fuiste a almacenar información que naturalmente la herencia de farmacia. Piensa en cómo se organizan tus archivos en tu libro de PC o Mac, lo que sea que tengas, el inicio desde la carpeta raíz y luego los atraviesas en un orden de artículo. Sistema rápido en la computadora. Estos probablemente implementados usando árboles. Además, los árboles proporcionan eje moderado y búsqueda. Eso es lista vinculada cortina, pero más lenta que las matrices. Tree también está proporcionando una inserción y eliminación moderadas. Más rápido que las matrices pero las listas enlazadas más lentas, delgadas, desordenadas. También lista probable. Y a diferencia de las matrices, los árboles no tienen un límite superior en número de nodos. Los nodos se vinculan mediante punteros. Por lo que hay una ventaja cuando miramos esta página que un árbol y tú puedes almacenar. Las principales aplicaciones de los árboles incluyen la manipulación de los datos de jerarquía TO, haciendo que la información sea fácil de buscar. Veremos que atraviesa, en una de las próximas conferencias. Manipular los datos de listas ordenadas. Se pueden utilizar como flujo de trabajo para componer imágenes digitales, para efectos visuales, algoritmos de enrutador. Y también el agricultor toma de decisiones multietapa, por ejemplo, el ajedrez empresarial. Desde un punto de vista de implementación, el árbol está representado por un puntero al nodo más alto del árbol. El árbol está vacío, entonces se conoce el valor de este nodo superior llamado raíz. Un nodo de árbol contiene las siguientes partes. En primer lugar, contiene datos en, luego contiene punteros a sus hijos. Podemos representar tres nodos utilizando estructuras. Por ejemplo, estoy adjunta aquí mismo. Se puede ver exactamente de lo que estoy hablando. Pero pasaremos a la implementación en C plus, además de que poco más tarde. Ahora mismo hablemos un poco más sobre qué tipos de árboles hay en la programación. Como dije, tres en informática es como en el mundo real. La única diferencia es que en la informática es visualizar esta boca abajo con raíz en la parte superior y evitar enfermedades que originan desde la raíz hasta las hojas del árbol. La estructura de datos de árbol es una estructura de datos no lineal. Un árbol se puede representar utilizando varios tipos de datos primitivos o definidos por el usuario. Como vimos con descargador justo ahora. Implementado tres, también podemos hacer uso de matrices, listas enlazadas, vidrios, o en otros tipos de estructuras de datos. Se trata de una colección de nodos que están relacionados entre sí para mostrar que los nodos de relación están conectados con bordes. Pero en la práctica, más como punteros pesados el uno al otro. Los tipos de árboles en las estructuras de datos. En primer lugar, existe el árbol general, que no hay restricción para él, que se le impone, en el aire mantenido el árbol. En árbol general cada nodo puede tener un número infinito de hijos. Estos tres es el superconjunto de todos los demás tipos de árboles. Ahora, pasaremos a árboles binarios que son mucho más útiles en marzo, más sobre preguntas de entrevista solo porque tienen estructura más simple y elegante y son más fáciles de formar preguntas basadas en. El árbol binario es el tipo de árbol en que cada padre puede tener como máximo dos hijos. A los niños se les conoce como el gráfico f o un niño derecho. Ntc es uno de los árboles más utilizados en ciertas restricciones y propiedades se imponen a los árboles binarios. Se da como resultado un número de otro árbol de búsqueda binaria de gran uso G AVL. Y así sucesivamente. Vamos a hablar de este tipo de árboles en este momento. Entonces el árbol de búsqueda binaria es una extensión del árbol binario que acabamos de hablar, pero tiene algunas otras restricciones de edición. Por ejemplo, el valor de los hijos izquierdos de un nodo debe ser menor o igual que el valor de su padre. Y el valor del canal correcto siempre es mayor o igual al valor de su padre. Esta propiedad de los árboles de búsqueda binaria hacen que se sienta adecuado para la operación de búsqueda. Intenso. A medida que cada nodo podemos decidir con precisión si el valor estará en la salida a sus derechos. Por lo tanto, se llama Árbol de Búsqueda. El tipo de árbol más complejo es el árbol AVL. Que estos son árbol de búsqueda binaria de auto-equilibrio. El nombre AVL se da en el nombre de sus inventarios. Hijo adulto se sintió tímido. Entonces este es el primer árbol dinámicamente equilibrado que se implementó en el árbol APR. cada nodo se le asigna un factor de equilibrio basado en el cual se calcula si el árbol está equilibrado o no. Si tienes árbol, la altura de los hijos de nodo difiere como máximo en uno. El factor de equilibrio válido en si las arterias son 10 n menos uno. Cuando el nuevo nodo es 80 al árbol AVL, la entrada se desequilibra, luego se realiza la rotación para asegurarse que el árbol permanezca equilibrado. Las operaciones comunes como la intuición de inserción de búsqueda solo toma logarítmica grande de tiempo en estos árbol AVL y es ampliamente utilizado para operaciones de búsqueda. También existen algunos árboles que se llaman los árboles NRV. El número máximo de hijos que pueden tener aquí está limitado a esta variable n. árbol binario es un árbol, como se denota en binario estructura de datos de árbol más de dos hijos de hoy en día, se encuentra que el más común utilizado en la presentación de n. Pero árboles completos de la NRA, que los hijos de un nodo es o bien 0 o completa enter retiro es el árbol en el que todos los valores predeterminados están en el mismo nivel. Para algunas propiedades de árboles binarios. Algunas propiedades matemáticas más. Podemos decir que el número máximo de nodos en el nivel l de un árbol binario es de dos al poder de l Entonces de nuevo desde su construcción, el número máximo de nodos en el árbol binario de altura h más dos al poder de h menos uno. En el árbol binario con n nodos, altura mínima posible o número mínimo de Cs logaritmo de base dos de n más uno. Hagamos un árbol binario con LDFs tiene al menos dos l más una variables. También en el árbol binario donde cada nodo tiene dos hijos, el número de nodos hoja es siempre uno más que nodos con dos hijos. Se trata de una amplia visión general sobre la estructura de datos del árbol. Estas son muy útiles en preguntas de entrevista. Es el venir a tema más complejo para discutir aquí. Muchas personas que conozco incluirme en lo mejor no fue tan corto en los árboles. Pero en este curso veremos algunos ejercicios con ellos, travesaños y así sucesivamente para te sientas más listo para tu entrevista de codificación. Especialmente en estas estructura de datos. Entonces dos problemas lo hacen las personas, las personas que han sido entrevistadas en el pasado. Así que pasemos a la siguiente conferencia ahora. 18. Traversals: DFS, BFS: Hola chicos. En esta segunda conferencia, hablaremos sobre los travesaños de árboles, más concretamente, los traversos de árboles binarios. Como ya viste. A diferencia de las estructuras de datos lineales que son matrices, listas enlazadas, colas , pilas, etc, que solo tienen una forma lógica de atravesarlas. Los árboles se pueden atravesar de diferentes maneras. A continuación se presentan los generalmente utilizados para atravesar los árboles. Hablaremos de profundidad primero el recorrido, esta conferencia, que están en orden, decir primero vamos a la izquierda, anotamos, luego la raíz, y luego al nodo derecho. Pre-orden, que es primero visitamos la raíz, luego el niño izquierdo y el niño derecho. Digamos que tenemos postorden, lo que significa que primero vamos a la izquierda, luego vamos a la derecha, y luego por último vamos a la raíz. También hay ESA, travesura primera travesura o recorrido de orden de nivel, que básicamente toma, imprime la nota en orden de sus niveles, de sus capas. El algoritmo de recorrido en orden sería atravesar primero el subárbol izquierdo, luego llamar para el subárbol izquierdo. Después visita el tendón raíz, atraviesa el subárbol derecho, y luego llama en orden para el sub árbol derecho. En el orden uno, de nuevo fue primero visitamos al niño izquierdo y niño derecho. Usos de en-orden. En caso de árboles de búsqueda binaria. En orden el recorrido da nodos en orden no decreciente. Para obtener nodos de un árbol de búsqueda binario cuarto no creciente de variación del recorrido inorder. Desordenar el recorrido fácilmente se puede utilizar. El recorrido de preorden es bastante similar al en orden excepto la forma en que hacemos las cosas. Por lo que primero visitaríamos el extremo de la raíz hacia el sub árbol izquierdo y llamábamos preorden de los labios. Leslie, atravesaremos el subárbol derecho. Preordenar. El recorrido de postorden sería primero atravesar el subárbol izquierdo, llamar al postorden del subárbol izquierdo, luego invertir el sub árbol derecho y llamar al postorden del mismo. Y así, visitaríamos la raíz. Ves algún recorrido de preorden sería crear una copia del árbol. También se utiliza para obtener expresión de prefijo en un árbol de expresiones. recorrido post-orden se usaría para eliminar un árbol, también se usaría para obtener la expresión postfix de un tratamiento de expresión. Si ahora estuviéramos a mirar el código que haría estos travesías de profundidad primero. En primer lugar, la función principal, declararemos la raíz, anotaremos esto usando una struct que se llama nodo, y lo declaramos hacia arriba. Contamos con un host integrado los datos y luego dos punteros a la nota tipo que es hijos de izquierda y derecha. Y también un constructor que toma datos de prueba integrales, luego inicializa a los hijos de estos nodos para saber. Entonces diríamos filtrados o no definitivamente, pero solo para anotarlo, no hay hijos. Primero declaramos una raíz y luego le damos a la izquierda. Y ya sabes, si dos bitrate nota de tres, estos son solo fracasos, lo que significa que no hay dos fallas. Y luego a la izquierda, a la izquierda tenemos un nodo con el valor flúor aunque han tratado de ser una nota el valor de cinco. Esto de aquí es cómo se vería nuestro árbol. Y luego llamamos pre-orden, en orden y post-orden de estas funciones toma un argumento, ese es el nodo raíz, por ejemplo, con el post-orden. Aviso no sé, obviamente, llamaremos recursivamente a los niños de izquierda, luego por los niños correctos, y luego imprimiríamos los datos. Entonces lo que esto haría es recursivamente llamado izquierda hasta que llegue a la hoja. Entonces volverá de la recursividad y lo lleva a la derecha. Entonces finalmente algún valor raíz. Entonces también tienes en orden, pre-orden ya establecido. Apenas la diferencia, sólo existe una diferencia en sucesión de estas instrucciones. En orden. Nuevamente, comprueba si el nodo no es nulo porque si significa que ya estás terminado el árbol o no hay hijos ahí. Luego llamamos recursivamente a la función para el nodo izquierdo. Después vamos a imprimir y luego llamaremos recursivamente a la derecha. El pre-orden. Obviamente. Revisamos de nuevo, necesitamos conocer estos nano. Primero imprimimos, luego llamamos recursivamente a la izquierda. Y luego por hablar la complejidad de estos algoritmos, bueno, ven al escenario. Para todos los problemas son en realidad voltios agradables del lado del servidor porque básicamente iteran. Nota. Y el espacio auxiliar, si no se considera el tamaño de un estado para las llamadas de función, entonces es constante, vamos uno. De lo contrario sería lineal grande O de n Ahora vamos a hablar de nivel alter binario traversal de árbol, que es la amplitud primera travesura. Por lo que hay diferentes métodos. Hablaremos del método que utiliza una función para imprimir un nivel dado. Nuevamente, en gran parte tratado de hacer aquí es imprimir el número de nodos en el orden de nivel de izquierda a derecha en niveles. Por ejemplo, para el último árbol que vimos, el recorrido de orden de nivel para ello sería 12345. El algoritmo aquí sería implementar dos funciones. Una es imprimir todos los nodos a un nivel dado, así que les damos una manzana. La otra función es imprimir el recorrido de orden de nivel del árbol. Orden de nivel te hace que la impresión mantenga en niveles para imprimir notas en todos los niveles uno por uno a partir de la raíz, lo haríamos es primer orden de nivel de impresión de tres. Ve desde una altura del árbol e imprime ese nivel. Iterar a través de todos los niveles y llamar a impresión dado nivel. Deja que tomes dos argumentos, el árbol y ese nivel, e imprimirlo. La función de impresión, imprimir dado nivel. Comprobamos si el árbol es conocido, entonces volvería. Si el nivel sería uno, entonces traería al mundo. Y recursivamente llamaría se le dio nivel del árbol derecho e izquierdo con nivel menos uno. Como se puede ver aquí mismo, hicimos la función para crear una nueva función de nodo que devolvería la altura del árbol. Las dos funciones de las que hablamos. Como dije, la función de orden de nivel de impresión toma el argumento, la raíz. Después calcularemos con el método de altura la altura del árbol. Iterar a lo largo de la altura y afrontamiento dado nivel de raíz I, que es el número del nivel en el que estamos actualmente. Y el nivel rosado dado es una función que toma el nivel y nota comprueba si la raíz es nula. Si es así, entonces volverá. Si el nivel es uno, imprimirá el nodo raíz. Porque si estamos en el primer nivel, significa que estamos en las raíces, simplemente lo imprimiríamos recursivamente llamando a cualquier cosa. Pero si estamos en un nivel inferior, no soy el nivel raíz, sino descargas, recursivamente llamaremos a esta función para la izquierda y la derecha. Nota con el nivel menos uno. De ahí el segundo parámetro. Entonces creo que eso es bastante sencillo. Nuevamente, se puede ver por el árbol que mostramos en la pantalla, el recorrido de orden de nivel es 12345 es que ya nos dimos cuenta. Otra vez aquí. La complejidad para este algoritmo es lineal. Aquí se refiere a la complejidad del tiempo grande O de n, ya que iteramos a través de todos los nodos una vez recursivamente, DC es más o menos las formas en que puede atravesar el árbol de búsqueda binaria. Y son muy útiles para saber porque te darán más morbilidad en un árbol. Y se asegurarán de sus ventas al tratar con tres preguntas en una entrevista de codificación. Así que ahora pasemos al siguiente vector. 19. Verifica si hay una propiedad de la suma de los niños: Hola chicos y bienvenidos de nuevo a este curso. En esta conferencia, hablaremos sobre los tres problemas que a veces pueden aparecer en una pregunta de entrevista. Eso es para comprobar si hay niños alguna propiedad en árbol binario. Lo que eso significa es que dado un árbol binario, debes escribir una función que devuelva true si el árbol satisface la propiedad que por cada nodo, valor de datos debe ser igual a suma de theta usará en left y los niños de derecho. Considerar el valor de los datos es 0. Por ahora niños. Por ejemplo. Si tuviéramos un árbol que tuviera la raíz, entonces los niños de izquierda serían ocho y los niños correctos serían dos. Ese sería un árbol válido. Y así sucesivamente a continuación, si ese niño con necesidad de tener dos hijos, por lo que la mano izquierda intenta al menos que sus datos en algunos sean iguales a ocho, y así sucesivamente para todo el árbol. El algoritmo que somos, nos acercaremos aquí es atravesar el árbol binario dado. Y para cada nodo, debemos revisar recursivamente si el nodo entonces ambos niños dijeron es por parte los niños alguna propiedad. Si es así entonces true else devuelve false. Eso es bastante sencillo. No saltemos al código y veamos cómo podemos hacerlo en un nivel técnico más específico. Muy bien, aquí ya declaramos algunas cosas que nos ayudarían con la implementación del árbol. Entonces declaramos una estructura que es nodo. Y luego declaramos que un árbol entero es alguna propiedad de la raíz dos. Entonces imprimiremos que la condición esté satisfecha, de lo contrario falsa. Entonces básicamente vamos a implementar una función que se llama East algunas propiedades. Toma el parámetro el nodo raíz y devuelve un entero, que también podría haber sido un booleano, es lo mismo porque si devuelves 0 o uno, luego saltando a esta función, declaramos dos variables auxiliares que nos ayudarán a recordar los valores derecho e izquierdo de los hijos del nodo que estamos en el presente con la iteración. Entonces si el nodo que somos honestos o sus hijos o no, entonces le devolveremos uno. Porque eso significa que hemos llegado al final y está bien porque todo lo comprobó para ser verdad hasta ese punto. De lo contrario, también verá que la mayoría de estos algoritmos comienzan con el caso base de este algoritmos de árbol. En primer lugar, nuestro recursivo y segundo, comienza con el caso base, es decir, el caso final. Bueno, tenemos múltiples escenarios aquí. Si el nodo izquierdo no es nulo, entonces los datos en él, por lo que el número que tenga se le dará a la beta integral izquierda que aquí declaramos. Entonces otra vez por el nodo correcto, haremos lo mismo. Y luego comprobaremos si los datos del nodo, por lo que el número que el nodo que estamos ahora mismo con la iteración es igual a la suma de los hijos izquierdo y derecho. Y también recursivamente llamada a la misma función para el nodo izquierdo y el nodo derecho. Revisaremos recursivamente lo mismo para ambos hijos del nodo. Entonces vamos a devolver uno, lo que significa que es verdad. Y nuestros tres 0s, con esta condición que estamos comprobando, lo contrario volveremos 0. Entonces lo que esto hace es llamar recursivamente mediante el uso de la pila de costos. Y cuando regrese de la pila de llamadas, le pegará a ésta. Si todas las propiedades de ECM devolverán true, como se puede ver aquí mismo con las declaraciones finales, todas ellas necesitan ser verdaderas para que esta declaración if check out y devuelva una. Es así como comprobaremos esta condición en todo el árbol con una función recursiva. Ahora hablando de la complejidad de este algoritmo, como vas a ver en casi todos los algoritmos de árbol. Lineal desde el punto de vista del tiempo y constante desde este punto de vista base formas solo declaramos dos integrales. Pero desde el punto de vista, iterar a través de todo el árbol. Entonces eso es lineal grande O de n. gracias chicos por pegarse al final conmigo en este tutorial y los veré en el siguiente. 20. Sum de todos los nodos: Hola chicos y bienvenidos de nuevo a este curso. En esta conferencia, hablaremos de otro problema arbóreo. Vamos a darles a veces en el cálculo de la suma de todos los nodos en un árbol binario. Creo que el título es bastante autoexplicativo. Lo que necesitarías hacer cuando se le dé este problema es proporcionar un algoritmo para encontrar la suma de todos los elementos en el árbol binario. Básicamente, es necesario resumir todas las integrales que tienen todos los nodos en un árbol binario que se te da. Como es habitual, abordaremos este algoritmo con recursión como lo hacemos habitualmente en tres problemas. Veamos el código para ver cómo haríamos este problema. Declaramos una struct. Tenga en cuenta que le mantiene inductor es la clave y también el nodo izquierdo y derecho que se guardan. Al darles un puntero a la estructura del nodo. Dibujamos un árbol aquí mismo. Y luego declaramos por alguna integral y le asignamos nuestra llamada de función que se supone que devuelva la integral. Esa integral siendo la suma de todos los nodos en el árbol dado, T solamente parámetro que toma esta función es el nodo raíz de nuestro árbol. Puntero al nodo. Obviamente. Va como si root es nulo, entonces deberíamos devolver 0. Como es habitual en tres algoritmos y métodos de recursión, comenzamos con el caso base, es decir, ¿qué sucede cuando el fondo llama a estos calor? Cuando la raíz es no, llegamos al final. Entonces ya no hay nota porque recursivamente llamamos a esta función hasta que nos quedemos sin nodos. Si ese no es el caso. Entonces si no llegamos a una ruta, debemos devolver la clave raíz, lo que significa el valor que la raíz está manteniendo dentro del porque se puede ver la estructura, la clave es la integrada que guarda ese nodo. También agregamos el curso recursivo de esta función para el hijo izquierdo y derecho de la raíz, decir la nota que estamos en ella. El llamado actual, por supuesto, recursivo el platillo será llamado para los niños de izquierda. Y luego de nuevo, la ejecución se inició sin retorno. 0 IS devuelve su valor y luego otra vez recursivamente llamar para cada uno de ellos. Creo que entendiste cómo va esto. Ahora estamos hablando de la complejidad de esta fila agarrada. Bueno, la complejidad del tiempo es lineal ya que iteramos a través de todo el árbol es bastante intuitivo que necesitamos iterar a través de cada nodo para que podamos averiguar qué valor tiene fiel a nosotros mismos. Y entonces la complejidad espacial es constante ya que no declaramos ningún elemento que no sea los estándares de Carsten vendido sin embargo es grande O de uno. Gracias chicos, y nos veremos en la próxima conferencia. 21. Comprueba si todos los nodos de hojas están al mismo nivel: Hola chicos y bienvenidos de nuevo a este curso. En esta conferencia, hablaremos de otros tres problemas que podrían darse en un entorno de entrevista. Eso es para comprobar si todas las hojas están al mismo nivel en un árbol. En este problema, te pediremos que hagas se le da un árbol binario, solo tienes que comprobar si todas las hojas nodos, es decir, los nodos que no tienen hijos. Entonces los que están en el nivel inferior, al mismo nivel o no, básicamente imaginan que la raíz está en el nivel uno, los niños inmediatos estando en el nivel dos, y así sucesivamente. Hasta que encuentres el nivel de hoja, tiene habitual, nos acercaremos a este algoritmo usando recursión. Ahora, la idea es encontrar primero nivel de la hoja más a la izquierda y almacenarla en una variable. Y usaremos esa variable. Entonces compara el nivel de todas las demás hojas con el nivel de deuda. Si es lo mismo, volveremos a terminar de lo contrario falso. Recorreremos el árbol binario dado en forma de preorden. El nivel que tenemos en cuenta, seremos lo mejor para todas las llamadas como argumento. El valor de este argumento se inicializa con 0 en otra función para indicar que, primer lugar, si aún no se ve, el valor está en el plano. En primer lugar encontrar una hoja o nivel de hojas posteriores en pre-orden se compara con este argumento de nivel. Ahora echemos un vistazo al código. Declaramos la estructura del nodo y el constructor para ello. Y en la función principal, construimos tres para nosotros. Y luego tenemos una función que se llama check que toma la raíz de nuestro árbol. Y lo que hace es que inicializa nivel en hoja con 0 y devuelve el código a esta comprobación, una función que toma como parámetros la raíz de nuestro árbol, luego el nivel y el nivel hoja que ambos se inicializan con 0. Como se puede ver en esta comprobación hasta función. El caso base es cuando tenemos una raíz, eso es ahora. Y entonces deberíamos volver verdad. Entonces los hijos del nodo que estamos en este momento son los dos nulos. Significa que llegamos a un nodo foliar. Y luego verificamos si es la primera vez cuando llegamos al nodo foliar. Cómo hacemos eso es comprobando si el nivel de hoja es 0, como se puede ver aquí, ha pasado por referencia, lo que el valor del mismo permanece. El que cuando llamamos al nivel de la hoja es 0. Significa que es la primera vez cuando nos encontramos con una hoja, asignamos a este nivel foliar, el nivel en el que estamos ahora mismo. Además, si no ingresamos esta declaración if, entonces devolvemos nivel igual al nivel de hoja. Lo que esto significa es que estamos justo en la hoja. Lo que ahora es el Primero, si tenemos razón que debemos devolver si el nivel es igual al nivel de la hoja. El nivel de la hoja es el nivel real de la primera hoja a la que llegamos. Todas nuestras hojas necesitan estar al mismo nivel. Por eso tenemos en cuenta esta variable aquí mismo. Entonces saliendo de esta declaración if, lo que significa que si no es una hoja en la que estamos, ahora mismo, devolvemos llamadas recursivas de esta función para el nodo izquierdo y derecho. Porque estamos ahora mismo en el nodo que no es una hoja y Xist, lo que significa que estamos en un nodo padre. Necesitamos llamar recursivamente a esta función para ambos niños e incrementa el nivel. Además, si bien teniendo en cuenta el nivel de la hoja, es la parte inferior más nivel de la primera hoja que hemos encontrado. Como ya he dicho, voy a recalcar esto. Nuevamente. Recordamos esta deuda a nivel foliar, el nivel de la primera hoja que hemos encontrado. Y esta es la referencia que revisaremos. Además inode siguiente deja que nos encontraremos por la complejidad de este algoritmo. Nuevamente, la complejidad espacial es constante. Esto no usamos ningún espacio adicional más grande de uno. Y entonces la complejidad del tiempo es lineal. Al atravesar todo el árbol para encontrar en primer lugar, el nivel de la primera hoja y luego revisando todas las demás hojas para tener el mismo nivel en la primera hoja que nos encontramos. Gracias chicos por ver este tutorial y los veré en la siguiente sección. 22. El problema de los soportes equilibrados: Hola chicos y bienvenidos de nuevo a este curso. En esta conferencia, hablaremos sobre el problema que muy a menudo se da en una pregunta de entrevista. Es decir para comprobar si hay corchetes equilibrados en una expresión usando una pila. Bueno, eso se hace usando una pila, pero el entrevistador podría realmente no tratar. Se hace este problema usando esto tomado esta noche, dio cuenta de eso por ti mismo. El problema te da una cuerda. Esa es una expresión, y hay que escribir un programa para examinar si los pares y los órdenes de los corchetes, correctos en esa expresión, los paréntesis pueden ser actualmente normales o cuadrados. Por ejemplo, pondré en la pantalla ahora mismo dos entradas diferentes. Por lo que se puede ver que el primero está equilibrado y el segundo no lo es. No se puede cerrar el cuadrante antes de cerrar el normal porque no existe el orden natural. Cuál sería el algoritmo para declararnos deck que contiene caracteres y luego atravesar la expresión que se le da esta cadena, básicamente iterar a través de ella. En la dendrita dos escenarios. En primer lugar, si el personaje actual por el que estás iterando en ese momento está iniciando el corchete, Iniciar corchete normal, arrancar corchete rizado o arrancar el soporte cuadrado, entonces puedes empujarlo a esta baraja. El segundo escenario es si el corchete actual en el que estás actualmente en este momento con iteración es un corchete de cierre. Nuevamente, un cierre de corchetes normales, cierre de corchetes, cierre de soporte rizado. Entonces pop de esta baraja. En este momento estás bombeando el elemento superior y vas a ver cuál es el último soporte abierto. Y si el personaje pop, por lo que el último corchete abierto es el corchete inicial coincidente, entonces está bien. Los corchetes no están equilibrados. Entonces después del recorrido completo, si hay algún soporte de partida dejando esta baraja, entonces no está balanceada porque en nuestra cuerda existe corchetes abiertos que no he estado cerca del final de la expresión. Echemos un vistazo rápido a los códigos. Tenemos una función principal y leemos ejercen una expresión que va como iniciar corsé rizado, comenzando corsé rizado, comenzando corsé normal, terminando el corsé normal y el corsé rizado. Entonces eso está bien. Después iniciando el soporte cuadrado, terminando el soporte cuadrado. Esta debe ser una expresión equilibrada porque no hay corchetes que queden y se abran o cierren en el orden equivocado. Ahora tenemos una función llamada, declaramos la función que se llama nuestros corchetes balanceados que vamos a ver que tiene un parámetro, esa cadena. Declaramos una pila, como ya explicamos por qué eso contiene el tipo de datos char. Entonces declaramos un gráfico auxiliar llamado X. Para int i de 0 a la longitud de la expresión. Iteramos básicamente con este bucle a través de cada carácter de la expresión que se da. Tomamos a cada personaje uno por uno y verificamos qué tipo de corchete estos. En primer lugar, necesitamos ver si ese corchete está actualmente al cuadrado, son normales y está empezando en el tipo uno. Si lo es, entonces podemos empujarlo en nuestra pila y luego continuamos ya que no necesitamos seguir adelante con el resto de la ejecución del bucle. De lo contrario, si no está iniciando el soporte, podemos comprobar si la pila está vacía. Y si la pila está vacía, deberíamos devolver false. Porque significa que es un corchete de cierre. ¿ No puede ser soporte inicial porque si hubiera sido, la ejecución no estaría aquí mismo, ahora mismo. Es un soporte de cierre y la pila está vacía. ¿ Qué significa eso? Eso significa que hemos llegado a un corchete de cierre que no tiene un corchete inicial coincidente ante él. Entonces no es una expresión válida de paréntesis. Si ese no es el caso, tenemos una declaración switch basada en el carácter que estamos ahora mismo en nuestra expresión. Por lo que tenemos diferentes casos. El caso cuando nuestro personaje es un corchete normal de cierre, vamos a hacerlo. En nuestro carácter auxiliar x, la parte superior de la pila. Y luego vamos a hacer estallar la parte superior de la pila ya que ya no la necesitamos. Y luego vamos a verificar el valor que había en ella. Si el valor que se vio, era un corchete rizado inicial o un corchete cuadrado de partida. Entonces deberíamos devolver false ya que llegamos a un corchete normal final y enumerar uno que estaba abierto, por lo que es corchete coincidente no era del mismo tipo que los EDs. Y entonces debemos romper. En los otros casos, si se trata de un corchete rizado que está terminando, y entonces el corchete de partida inicial está bien. Los otros dos tipos, no está bien, por lo que debemos devolver false. otra parte, si se trata de un corchete cuadrado final y su paréntesis coincidente es normal o rizado. Nuevamente, no es una expresión válida, por lo que debemos devolver false y luego romper. También se aplica el mismo procedimiento, donde ponemos en nuestro personaje auxiliar la parte superior de la pila, y luego lo pop. Cuando terminemos con la iteración de que nuestra pila debe estar vacía. Por lo que no debe quedar paréntesis abierto, porque eso significa que no tienen paréntesis final que estén coincidentes. Si se vacía la pila significa que todos los mercados han igualado. Y la expresión es válida. Si la cadena no está vacía al final de la ejecución, eso significa que hay algunos elementos en ella. Y como ya viste, solo empujamos en ella iniciando tipos de soportes. Y eso significa que en ella se dejan paréntesis iniciales que no tienen corchetes finales coincidentes. Y eso significa que no es una expresión válida. Entonces esta función se llama en una declaración if. Entonces si esta función aquí mismo, lo que significa que esta función está volviendo verdadera, podemos devolver que la expresión que se nos da es una expresión equilibrada. De lo contrario no está equilibrado. Para que como se puede ver, muestra de conocimiento, si ejecutamos el código, se puede ver que dice equilibrado, por lo que es expresión equilibrada. Ahora hablemos de la complejidad de este algoritmo. La complejidad de este algoritmo desde un punto de vista del tiempo, este lineal a medida que iteramos a través de nuestra expresión una vez. Entonces eso es grande O de n Ahora la complejidad espacial también es lineal ya que declaramos una pila que puede contener tanto como toda la cadena. En el peor de los casos donde la cadena contiene en los corchetes iniciales. Puedes hacer esto de una manera más eficiente donde ni siquiera recuerdas esta baraja. Y en lugar de esta baraja, puedes recordar algunos números. Por ejemplo, algunas variables que incrementa cuando cumple con un corchete inicial y decremento cuando cumples con un corchete final. Esa es una solución más avanzada. Es posible que lo intentes en casa o buscarlo. Pero la solución básica para estos problemas, éste y éste realmente debes entender y conocer de memoria. Pero gracias por seguir con este tutorial hasta el final. Nos vemos la próxima vez.