Transcripciones
1. Introducción: Mi nombre es Sarnoff, y soy ingeniero de software de pila completa e instructor de ingeniería. Ya le he dicho a Ingeniería de software en un boot camp de codificación, y algo que noté repetidamente fue que se están graduando Estudiantes, aunque extremadamente brillantes y capaces de construir sitios web poderosos, dinámicos, no
estaban listos para el tipos de preguntas que vieron en sus entrevistas. Después de ver a estos estudiantes luchar con preguntas típicas de entrevista, decidí crear y recolectar preguntas que los estudiantes pudieran ver en sus entrevistas. Y yo los repartí. Fue práctica extra para que los estudiantes lo intentaran. repetidas ocasiones me dijeron cuánto los problemas les ayudaban a ver los agujeros en sus conocimientos y los cayeron con las habilidades que necesitaban. Este curso es la culminación de esas preguntas. Casi todos estos problemas son variaciones en preguntas que yo mismo me han hecho, o que otras que conozco se han hecho en entrevistas. Bueno, no
verás estas preguntas exactas en tus entrevistas. Las estrategias que aprendes al resolverlos nuestro público son aplicables en casi todos los problemas que te darán. Aquí está la estructura general del curso típicamente empezará por crear un
algoritmo de fuerza bruta que solucione bien el problema, luego refinarlo hasta que podamos optimizar la complejidad del tiempo o del espacio o ambos. Al final del curso, habrás dominado varias estrategias algorítmicas que podrás aplicar de punta una amplia gama de problemas. Aprenderemos formas de analizar críticamente los algoritmos que ideamos y de encontrarlos, voltearlos para reducir la cantidad de tiempo que tardan. Esto es exactamente lo que busca un entrevistador. Hay un par de requisitos para este curso. Um, primero, debes tener un conocimiento básico de trabajo de JavaScript y la capacidad de escribir
código significativo con él. También debes estar familiarizado con los conceptos Básicos ES 2015, como funciones cero y las palabras clave Let y Const. Deberías tener alguna idea de lo que significan los términos, la complejidad del
tiempo y el espacio. Está bien si no sabes exactamente cuáles son, ya que caminaremos por encontrarlos a detalle para cada solución. El editor de códigos que uso en mis videos es Ripple. Uh, puedes llegar ahí yendo a rebelde punto i t slash lenguajes slash javascript, y la razón por la que uso esto es porque es simple y funcional, y vamos a enfocarte en tu código, pero eres por supuesto, libre de usar cualquier editor de código que te guste. El proyecto para este curso es recoger cualquiera de los problemas cubiertos en la clase. Aquí hay un total de cinco listados y comparte tu propia solución. Existen 1000 formas de resolver cualquiera de estos problemas y la clase se beneficiará al ver tu versión. Bienvenido al curso. Me emociona enseñarte lo que sé y ayudarte a as en tus entrevistas. Cuando estés listo, te
veré en el primer problema.
2. Personajes únicos: bienvenido a su primer problema es único. El objetivo aquí es escribir una función que tome en una cadena y determinar si cada carácter de esa cadena aparece sólo una vez. Esencialmente, estamos tratando de ver si cada personaje de la cuerda es único en esa fuerza. Queríamos sensibles a mayúsculas y minúsculas, lo que significa que tanto las versiones minúsculas como mayúsculas de una letra en la misma cadena se consideran únicas. Aquí te dejamos algunos ejemplos. Obtenemos una cadena normal A, B, C, D E f, y todo es único, por lo que queremos que la función regrese. Cierto. Este siguiente ejemplo solo muestra que queremos que nuestra función sea capaz de aceptar una cadena con cualquier tipo de carácter, no sólo letras. Otra vez. Todos son únicos. Entonces nos hacemos realidad. Este tercer ejemplo muestra de nuevo que una A minúscula en una A mayúscula en la misma cadena
seguiría queriendo que volviera nuestra función. True para esa entrada, el 4to 1 muestra un duplicado de minúsculas ocho y su función devolvería falso. Vamos a seguir adelante y empezar a escribir esta función de inmediato. Entonces para asegurarnos de que cada personaje de nuestra cadena sea único, vamos a necesitar procesar cada carácter de la cadena, que sepamos que vamos a necesitar bucle. Adelante y empecemos por ahí. ¿ Qué queremos hacer en este bucle? Bueno, una estrategia que podemos emplear es la siguiente. Nuestro bucle aquí va a pasar por una cuerda de izquierda a derecha. Entonces tomando esto como ejemplo, vamos a empezar por una. Lo que podemos hacer es que podemos tener otro bucle yendo de derecha a izquierda buscando a ese mismo personaje. Entonces mientras nuestro bucle externo está en un, podemos tener un bucle interno que va de derecha a izquierda. También buscando un si lo encuentra y no está en la misma posición
en la que está el bucle exterior , sabemos que tenemos un duplicado y podemos devolver de inmediato falso. Si no hay duplicado, esto correrá todo el camino hasta que llegue a la A por aquí, y sabemos que es único en la calle. Podemos repetir esto yendo de izquierda a derecha ya que nuestro segundo bucle va del dedo del pie derecho izquierdo. Para cada caso individual, esto podría parecer complicado, pero hay un pequeño método que nos hace muy simples. Vamos a escribirlo y discutirlo justo después del último índice apagado. Esto hará exactamente lo que yo estaba describiendo. Pasará por la cuerda del dedo del pie derecho izquierdo, buscando el personaje que proporcionamos en este caso, sea cual sea el personaje en el que esté actualmente. Entonces de nuevo, le
damos un en este caso para la primera ronda, y va a ir de derecha a izquierda buscando un Entonces lo que estamos haciendo es asegurarnos que el último índice de A sea el mismo que el índice actual que estaban en. Esto mostrará que el que el carácter no está duplicado en la cadena. Si, sin embargo, el último índice de A no es el mismo que el primer índice de a, entonces podemos devolver inmediatamente falso Um, esa es realmente toda la lógica que necesitamos al final de la función, podemos devolver cierto, sólo
llega aquí después de que se procesa cada personaje aquí y se aseguró de que no haya duplicados, trabajo
disfuncional. Adelante y código corredor aquí, y esperamos ver verdadero, verdadero,
verdadero, verdadero, verdadero, falso y eso es exactamente lo que vemos aparecer por lo que nuestra función funciona correctamente. Vamos a pasar por la complejidad del tiempo de esta función para que podamos ver que tenemos un bucle for y que de inmediato trae nuestra complejidad del tiempo a O de n porque cada personaje se está procesando aquí mismo. En realidad tenemos otro bucle en forma de último índice de Bueno, no
es un bucle que escribimos. Se trata de un bucle que está pasando por la cadena de derecha a izquierda. Entonces esto es en realidad otra o de fin. Dado que esto está anidado dentro del bucle externo, necesitamos multiplicar estas complejidades de tiempo para dar una complejidad de tiempo final de O de
n veces n oh de n cuadrado. ¿ Cuál es la complejidad del espacio? Bueno, pensémoslo. No importa cuánto tiempo sea la cadena, ya sean tres caracteres o 30 o 300 solo estamos usando una variable en toda nuestra función. Y es decir, yo sólo estaba almacenando un personaje a la vez. No importa cuán grande sea la entrada, nuestra función ocupa la misma pequeña cantidad de espacio. Entonces decimos que utiliza espacio constante, o O de uno. Eso es todo para esta versión. La solución. Podemos mejorar un poco la complejidad del tiempo. Sí, podemos. Adelante y probemos eso. Hay algo que podemos hacerlo antes de pasar por nuestra cuerda para hacerlo un poco más simple , podemos ordenar nuestra cuerda. Entonces sigamos adelante y probemos eso. Entonces lo que he hecho hasta ahora aquí es que estoy tomando la cuerda y dividiéndola en una matriz. Eso es lo que hace este método dot split con una cadena vacía aquí mismo. Por lo que en este punto, los autos simplemente serían iguales a una matriz de caracteres individuales en la misma línea que
lo consortamos . Ahora todos los personajes se ordenarán de izquierda a derecha. Entonces si nos dieran algo como D B A C, parecería que tendría una matriz. Ahora sería una matriz de A,
B, B, C y D. Simple es que ¿qué podemos hacer ahora que nuestros personajes están ordenados? Bueno, hay una pieza de lógica diferente que podemos aplicar para que esto sea mucho más fácil. Vamos a necesitar de nuevo el estándar for loop. En realidad, iba a empezar en una para ésta, y vamos a explicar por qué en un segundo así ahora. Pero el no sé cuáles son los personajes ordenados individualmente. Si hay duplicados, se van a colocar uno al lado del otro otra vez. Asumiendo que conseguimos D B A. C A. Esto ahora se convertirá en un B C D. Los dos duplicados aparecen justo al lado del otro. Entonces lo que queremos hacer es para esta cadena, o mejor dicho, esta matriz de caracteres. Queremos empezar por el segundo personaje, y lo que queremos hacer es compararlo con el personaje que tiene ante sí. Si son iguales, es un duplicado, y de inmediato podemos devolver falso. Vamos a codificar eso. Eso es todo. Esta función funciona perfectamente también. Vamos a ejecutarlo sólo para asegurarnos de nuevo, estamos esperando Verdadero, verdadero, verdadero, falso. Y eso es exactamente lo que obtenemos. Vamos a limpiar un poco esto. Y de nuevo, hablemos de complejidades del tiempo y del espacio. Entonces en este caso, estamos empezando con una tienda a aquí mismo. Ahora, diferentes algoritmos de clasificación tienen diferentes complejidades temporales, pero en general, si estamos hablando de una espada, podemos asumir la complejidad del tiempo de O de los tiempos finales. Registro de n Este aquí es un bucle estándar. Simplemente va a ser Oh, de N porque estas cosas pasan secuencialmente y no tenemos un bucle dentro de un bucle. Simplemente podemos añadir estos. Entonces vamos a empezar con O de M Times. Un registro de fin más o de N, que se convierte en oh de N más n veces a lo largo de End y N es un término de orden menor que este aquí. Simpliquemos esto aún más para mostrar exactamente lo que eso significa cuando hablamos de tiempo, las complejidades se debilitan. Simplemente elimina los términos de orden inferior para que podamos deshacernos de este plus y nuestra complejidad de
tiempo final termina siendo exactamente esto. Ah, de tiempos finales largos de ellos y que su complejidad de tiempo para esta solución. ¿ Qué pasa con el espacio? Anteriormente era más de uno, pero ahora nos llevamos a cada personaje y lo estamos almacenando a toda prisa. Eso es lo que pasa aquí. Entonces estamos almacenando cada personaje, lo que significa que ocupamos la misma cantidad de espacio que el tamaño de la entrada. Entonces va a ser, oh de, y hablaremos de dos soluciones más en el próximo video. Nos vemos allí
3. Procesamiento de cuerda rápido: bienvenido de nuevo a su único. Ahora hemos pasado por dos soluciones, y hemos logrado mejorar la complejidad del tiempo desde O de y al cuadrado Thio de End Times. Bitácora de Fin. Esto lo logramos ordenando la cadena que obtenemos como entrada. En realidad podemos hacer que nuestra complejidad del tiempo sea aún mejor. Y eso requerirá de una estrategia diferente. Adelante y borremos todo esto y empecemos de nuevo. Por lo que la última vez habíamos ordenado la cuerda. Quieres hacer algo diferente Esta vez, vamos a crear un objeto para almacenar personajes A medida que nos encontramos con ellos de nuevo. Vamos a necesitar un bucle pasando por nuestra cuerda y no le gusta algo. 04 bucle. Entonces lo que queremos hacer es comprobar si nuestro objeto ya contiene una copia del
trabajo de carácter actualmente procesando. Eso es todo. Esto es en realidad todo el problema es sólo eso. Corre de nuevo y asegúrate de que funciona bien. Y no está funcionando bien. ¿ Qué está pasando? Uh, devuelto False aquí abajo. Esto tiene que ser cierto. Ahí vamos. Mis disculpas. Entonces recorremos lo que está pasando aquí una vez más mientras pasamos por cada personaje, por ejemplo, Tomemos esta cuerda aquí mismo. ABC A e f. Vamos a procesar cada ítem individualmente. Por lo que la primera vez que pasemos por
este bucle, este auto va a ser un Vamos a comprobar si nuestro objeto ya lo contiene. Y si lo hace, queremos devolver las caídas. Nuestro objeto está vacío al principio. Por lo que pasa este cheque y pasamos a aquí. Vamos a almacenar un en nuestro objeto. Simplemente vamos a establecer su valor igual a verdadero. Por lo que nuestro objeto contendrá cada carácter que ya hemos procesado hasta ahora. medida que pasemos por la cuerda, vamos a sumar en a y luego B y luego ver cuando lleguemos a la siguiente a nos iban de nuevo a comprobar si los autos tienen el personaje A Y si eso águilas cierto, ya que lo hace, porque ya hemos lo hemos visto y ya lo hemos insertado en nuestro objeto. Sabemos que es un duplicado y podemos devolver de inmediato falso. Si pasamos por todo este bucle, sabemos que no hay duplicados y la cadena y podemos devolver true. Eso es todo. Hablemos de la complejidad del tiempo en esta versión de esta función. Sólo tenemos un bucle. Estamos pasando por cada personaje y a medida que pasamos por cada personaje, las cosas que hacemos aquí son tiempo constante. No hay más bucles ni nada de esa naturaleza. Entonces tenemos un solo bucle dándonos una complejidad Tom de o de N. ¿Qué pasa con el espacio? Bueno, cada personaje llegar a través está siendo almacenado en nuestro objeto. Por lo que el espacio también va a ser un amor N porque es proporcional al tamaño de la entrada. Hay una manera de que podamos cambiar un poco esto. En lugar de un objeto, vamos a utilizar un constructo E S 2015 llamado conjunto, ahora un conjunto un similar a un objeto. Excepto que es más apropiado para esta tarea exacta, una repentina como una estructura de datos destinada a contener elementos únicos. De hecho, sigamos adelante y veamos el set Indian Page four como podemos ver, un conjunto, es un objeto que te permite almacenar valores únicos de cualquier tipo, uh, en un conjunto. Por lo que un valor en un ajuste solo puede ocurrir una vez, y es único en la colección de sets. Por lo que esta es una estructura de datos hecha específicamente. Esencialmente, para este problema, sólo
necesitamos cambiar un par de cosas. Por ejemplo, En lugar de esto, necesitamos usar un método incorporado y lo mismo aquí en lugar de establecer. En lugar de poner nuestro elemento en true, simplemente lo
vamos a agregar al set. No necesitamos eso. Y eso no lo necesitamos. Y otra vez para asegurarse de que esto funcione. Efectivamente nos da lo que queremos. Verdadero, verdadero, verdadero, falso. Nuevamente, Esto es muy similar a un off al método que teníamos antes con un objeto. La única diferencia es que intercambiamos o estructura de datos. Y en realidad hay una muy buena razón por la que hicimos esto. Nos permitirá escribir nuestra solución de una manera nueva y aún más sencilla. Y eso lo discutiremos en el próximo video. Ver, ahí
4. Personajes únicos : simplicidad definitiva: bienvenido de nuevo a su único. Ya cubrimos tres formas diferentes de resolver este problema. Para el último método, mostramos cómo hacerlo tanto con un objeto como con un conjunto. Ahora quizá te estés preguntando por qué te mostré este set. Hace lo mismo que un objeto, y en realidad no ofrece nada nuevo. Es sólo otra cosa para que aprendamos y nos acostumamos. Bueno, quiero mostrarles el verdadero poder detrás de un set, y quiero mostrarles una manera en la que puede hacer que nuestra solución sea mucho, mucho más simple. Entonces, antes de hacer algo, sumerjamos en algunas de las propiedades de un conjunto. Vamos a crear uno nuevo aquí y vamos a tirar unos cuantos ítems así que le daremos una matriz con los números del uno al cinco, y vamos a salir de esto. Entonces como puedes ver, cuando nos demos set una matriz, tomará cada elemento individual en la matriz. Un agregado al conjunto. Ahora, ¿qué fue un intuitivo, al
menos para mí, fue lo que pasa cuando le damos una cuerda en su lugar? Esperanzas así vamos a seguir adelante y deshacernos de esto y en su lugar darle la cuerda A B C D e Como se puede ver, lo que pasó es que cada personaje individual en la cadena se insertó en el conjunto. Uno por uno, la cuerda esencialmente se separó. Para nosotros, esto es muy importante. Hay una cosa más que quiero señalar y esa es la propiedad de tamaño. Por lo que una cadena tiene una propiedad length, que le indica el número de caracteres en la cadena. Un conjunto tiene una propiedad size la cual solo te indica el número de elementos en el conjunto. Entonces, como era de esperar, son cinco porque tenemos cinco artículos diferentes en el set. Yo quiero mostrarles una cosa más, que es lo que pasa si agregamos duplicados. Déjame seguir adelante y agregar ABC de nuevo y lo ejecutamos y vemos que la salida aquí es exactamente la misma porque set de nuevo solo puede contener elementos únicos. Y los personajes A, B y C ya están ahí dentro. Por lo que ignora por completo estos tres. Y el conjunto contiene cinco artículos como podemos ver aquí mismo. Adelante y volvamos a nuestro problema. Voy a borrar todo esto y voy a escribir una línea de código y hablaremos de ello justo después. Esa es en realidad toda la solución. Y déjame ejecutar esto sólo para demostrar que funciona. Y lo hace. Adelante y pruébalo por tu cuenta si lo deseas. Funcionará cada vez. Discutamos por qué esto es como se muestra antes por aquí. Si somos duplicados en el set, serán completamente ignorados. Eso es lo que está pasando aquí. Insertamos una cadena en el conjunto, y cada carácter individual se está insertando en el conjunto estaban comprobando entonces para ver si el tamaño del conjunto es el mismo que la longitud de la cadena original. Si no hubiera duplicados que el tamaño del conjunto, debería ser exactamente el mismo que la longitud de la cadena. No obstante, si hubiera duplicados en el liquidar, ser un poco más pequeño. Al devolver esta comparación directamente, hemos resuelto todo el problema si su única esta igualdad de lo verdadero y lo funcional devuelven verdadero. Si hay caracteres duplicados, esta igualdad no se mantendrá y la función devolverá falso de nuevo. Repasemos la complejidad del tiempo y del espacio para esta función. Estamos tomando una cuerda y la estamos agregando al set carácter por carácter. Esa es una operación lineal. Entonces es O del espacio final otra vez estaban agregando cada carácter individual al conjunto, por lo que va a ser proporcional al tamaño de la cadena. Entonces una vez más, oh, de n terminemos rápidamente hablando de todo lo que hemos cubierto hasta ahora. La primera solución que se nos ocurrió fue la solución de fuerza bruta que tenía un juramento y complejidad de tiempo
cuadrada su
simple, directa. Y es la primera solución que se le ocurre a la mayoría de la gente. Si puedes identificar la complejidad del tiempo y luego trabajar para hacerlo mejor, enfrentarás esta pregunta en entrevista. La segunda solución consistió en ordenar la cadena. En primer lugar, era mejor en términos de tiempo, complejidad, pero tuvimos que aumentar la complejidad del espacio para esa solución. El tercero y cuarto soluciones son ideales. Tenemos la menor complejidad temporal, y la reducimos hasta O de fin, lo cual es una mejora muy significativa. El 4to 1 aquí es inteligente, pero el 3er 1 hubiera sido más que suficiente. En entrevista, ambos
lograron la mejor complejidad temporal posible. La idea principal es quitarle esto es que aplicando diversas técnicas a un problema, Consignia mejorar eficientemente la complejidad del tiempo o del espacio. Ordenar nuestros datos lo bajó,
bajó nuestra complejidad del tiempo y luego, usando una estructura de datos apropiada, ya sea un objeto o conjunto lo mejoró de nuevo. Veremos esto apareciendo una y otra vez en los problemas futuros. Intenta usar un conjunto de matriz de objetos. Apila nuestro cue o cualquier otra estructura de datos y mira si eso abre alguna nueva vía para tu solución. Te veré en el siguiente problema en el siguiente video.
5. Arrays anidados: bienvenido a nuestro segundo problema aplanar matriz. En este problema son la entrada va a ser una matriz de matrices anidadas,
a veces matrices profundamente anidadas. Y nuestro objetivo es escribir una función que tome cada elemento individual en la matriz y se extraiga a una nueva matriz plana. Aquí tienes un ejemplo. Recibimos una matriz que tiene varios o elevar dentro de ella, además de otros artículos. El objetivo es sacar esos elementos de sus matrices profundamente anidadas en una sola matriz plana mientras se preserva el orden. Las entradas pueden ser números, o pueden ser cadenas, o podrían ser objetos que realmente pueden ser cualquier cosa. Nuestro objetivo es llevarlos lo que sean y ponerlo en una nueva matriz plana mientras preserva el orden. Este problema tiene algunos usos prácticos en una carrera de desarrolladores. He tenido que lidiar con fuentes de datos anidadas muchas veces, y resolver este problema te dará alguna visión sobre cómo resolver problemas similares que surgen en el futuro. A diferencia del último problema donde mostré soluciones y luego las discutí, creo que será más instructivo en este caso caminar por la solución. Entonces sigamos adelante y empecemos. Te animo a pausar el video y probarlo tú mismo primero. Adelante. Por lo que necesitamos crear una nueva matriz. En primer lugar, sigamos adelante y hagamos eso. ¿ De acuerdo? Vamos a necesitar pasar por cada elemento en nuestra memoria y procesarlos uno por uno. Entonces vamos a necesitar un bucle. ¿ De acuerdo? Simplemente voy a almacenar el elemento actual en una nueva variable. ¿ Y qué queremos hacer aquí? Bueno, vamos a querer hacer algo. Si este elemento de aquí es una matriz y vamos a querer hacer otra cosa si no tiene prisa, Si no es una matriz, entonces podemos empujarlo inmediatamente a nuestra nueva matriz. Pero si lo es, necesitamos pasar por cada individuo, cabeza de la escuela y empezar a recubrirlo. Entonces primero, lo que queremos hacer es comprobar si este ítem es una matriz. Entonces, si este elemento no es una matriz, sabemos que no está anidado más, y podemos seguir adelante y empujarlo directamente a nuestra nueva matriz. No obstante, si se trata de una matriz, lo que queremos hacer es tomar cada elemento individual dentro de la batería y empujar esos uno por uno
en una nueva matriz. Entonces en realidad vamos a necesitar otro bucle aquí, y al final, queremos devolver nuestra nueva matriz. De acuerdo, entonces esta función aquí mismo funcionará si tenemos una matriz anidada un nivel profundo, por ejemplo, digamos que esta es nuestra entrada. Nuestro funcional funciona correctamente para esta matriz, y lo convertirá en una matriz que no está anidada. Eso se ve así. Tan solo para asegurarse de que funcione. Adelante y probémoslo. Y sí funciona. Vamos a pasar por por qué funciona esto. Entonces somos internos for loop, y este ítem, la primera vez, va a ser el número uno. No es una matriz tan ruina para empujar directamente a una nueva matriz, que ahora tendrá solo una dentro de ella. La próxima vez que este artículo va a ser, también, y vamos a hacer lo mismo y otra vez lo mismo para tres. Eventualmente llegamos a esta matriz, que tiene cinco foráneos dentro de ella, y vamos a entrar en esta parte de la declaración if vamos a pasar por cada ítem aquí y empujar cada ítem, que es extranjero cinco individualmente en. Por lo que sólo va a seguir adelante y añadirlos a nuevos arreglos otra vez con seis. Vamos a entrar aquí y empujarlo directamente. Y por eso esta función funciona como lo hace ahora. ¿ Qué pasa si tenemos más necesarios? Por ejemplo, Si tenemos algo como, Disculpe, algo así, no
va a funcionar porque sólo vamos a un nivel profundo. En lugar de entrar en esto y empujar siete, va a empujar toda esta matriz a nuestra nueva matriz. Entonces, ¿cómo arreglamos esto? Bueno, la clave está en realidad en esto aquí mismo, así que no sabemos cuántos niveles de profundidad vamos a necesitar ir. Por ejemplo, los siete podrían ser otra matriz profunda. Incluso podría ir más allá, y simplemente podría seguir adelante. Ese es el problema que estamos tratando de resolver. Entonces realmente no sabemos cuántas veces, y vamos a necesitar irnos porque no sabemos cuán profundamente anidados pueden estar estos artículos. Eran actor iba a necesitar convertir esto en una función recursiva, y así es como hacemos eso Eso es todo. Esto funcionará. Vamos a seguir adelante y probarlo sólo para asegurarnos. Y funciona exactamente como esperamos. ¿ Qué hicimos aquí? Bueno, estamos diciendo que si nos encontramos con una matriz anidada, sólo
vamos a llamar de nuevo a toda la función aplanada en eso necesario. Pensemos en eso. A ver. Llegamos a este elemento, que es una matriz anidada. Parece tres niveles de profundidad. Cuando eso suceda, sólo lo
pasaremos. Aplanar una vez más, por lo aplanado la próxima vez alrededor de baja recibir una matriz, anidado dos niveles de profundidad. De nuevo, lo
vamos a pasar. Va a recibir éste, y de nuevo va a pasar y recibir éste. Eventualmente, llegará solo a los siete, y tomará eso y lo empujará a una nueva matriz. Esto funcionará sin importar cuán profundamente anidados estén. Array es
6. Discusión de Arrays: Bienvenido de nuevo a aplanar. Rickerson es un concepto difícil, por lo que te animo a tomar algunas entradas diferentes y caminar por la función varias veces por tu cuenta. Asegúrate de que te has convencido de que la solución funciona de la forma en que crees que funciona . Hablemos de la complejidad temporal de esta función. Tenemos un bucle de cuatro aquí, y tenemos una llamada recursiva e incluso otro bucle de cuatro aquí abajo. En la superficie, parece que la complejidad del tiempo va a ser bastante loca en esta, pero en realidad es bastante simple. Ignoremos la función por ahora, y solo pensemos en lo que le está haciendo a una entrada. Otra vez. Tomemos este. medida que pasamos por la función, cada elemento es empujado uno por uno en nuestra nueva matriz. Entonces nuestro bucle irá aquí y procesará uno y lo pondrá de otra manera, poco proceso a y poner en nuestra nueva matriz, y hará lo mismo con tres. Una vez que llegue a esta matriz, se sumergirá dentro de ella y procesará cuatro y luego cinco y luego seis. Y luego cuando llegue por aquí, simplemente
se sumergirá en el fondo, procesará los siete y luego irá todo el camino de vuelta hacia fuera. Como se puede ver, cada elemento se procesa sólo una vez. Tenemos todos estos bucles e incluso tenemos una llamada recursiva. Pero al final, cada artículo aquí se procesa. Once Eso nos da un tiempo lineal, complejidad o oh, de fin. ¿ Y qué pasa con el espacio? Bueno, cada elemento individual se almacena en su nueva matriz, por lo que es proporcional al tamaño de la entrada nuevamente, Lineal. Eso es realmente todo a este problema. Lo que puedes quitarle es que Rikers in es una poderosa herramienta. cualquier momento puedes ver que vas a estar repitiendo algo en este caso sumergiéndote en una matriz y no sabes cuántas veces podrías necesitar hacerlo, probablemente
vas a necesitar rickerson. Gracias. Y te veré en el siguiente video.
7. Eliminar personajes duplicados: bienvenido al problema número tres. Quitar los dupes. El objetivo aquí es escribir una función que tomará en una cuerda. La función debe devolver una nueva cadena con los mismos caracteres que la cadena original, pero con caracteres duplicados eliminados. Entonces si a nuestra función se le da una cadena con caracteres únicos, queremos devolver esa cadena exacta. Si hay algún duplicado, queremos despojarlos manteniendo el orden de los personajes. Eso es lo que hacen estos dos ejemplos aire aquí. Adelante y empecemos a escribir de nuevo esta función. Te recomiendo que lo pausas y asegúrate de ti mismo y luego vuelvas a este video. Necesitamos iniciar esta función creando una matriz para almacenar los caracteres únicos en nuestra cadena. Adelante y hagamos eso. Vamos a necesitar un bucle para procesar cada uno de los personajes individuales. Entonces vamos a la derecha que dentro de este bucle primero queremos comprobar para ver si el carácter actual se estaba procesando ya existe en nuestra matriz. Si ya está en nuestro array, significa que lo hemos visto antes y no queremos reinsertarlo, así que solo queremos continuar. Si, sin embargo, es la primera vez que lo
vemos, queremos empujarlo a nuestra matriz. Nuestra matriz única de autos ahora solo contiene personajes únicos. Lo que queremos hacer es convertir esto en una cadena y devolver esa cadena, y esa es la solución. Vamos a ejecutarlo y asegurarnos de que funcione. Y lo hace. En efecto, vemos un B. C D apareciendo tres veces exactamente lo que queremos. Vamos a pasar por las complejidades del tiempo y el espacio para el tiempo que no tenemos exterior para bucle aquí. Eso de inmediato nos lleva a O de N Lord lineal porque estamos procesando cada personaje dentro de este for loop que usamos incluye esto en sí es un bucle porque está pasando por esta matriz de autos
únicos y buscando este auto. Y para hacerlo, tiene
que pasar individualmente por todo lo que hay en la matriz. Por lo que tiene que recorrer la matriz de izquierda a derecha, y eso se detendrá cuando otro encuentre el elemento o llegue al final. Pero en efecto es un bucle, y como tenemos un bucle en un bucle, vamos a tener oh de fin de los tiempos. Ya que estás multiplicando sus complejidades del tiempo, lo que nos lleva dedo del pie de n Square y esa es nuestra complejidad del tiempo. ¿ Qué pasa con el espacio? Bueno, tenemos que tomar la cuerda e insertar cada carácter único en nuestra matriz. Entonces tenemos que almacenar esencialmente toda la cadena otra vez, casi toda la cadena, al
menos. Entonces eso va a ser Oh, de N porque la cantidad de datos que usamos va a ser proporcional al tamaño de la entrada . Hay una manera de que podamos hacer que este tiempo la complejidad sea un poco mejor después de todo mucho mejor . Vamos a pasar por eso. Entonces estoy agregando un objeto a nuestra matriz aquí mismo. Siempre que empujamos a un personaje a nuestra matriz, también
queremos agregarlo a nuestro objeto. En lugar de comprobar la matriz para ver si contiene nuestro carácter, ahora
queremos comprobar el objeto. Entonces vamos a reemplazar en esto. Esto ya no es una O de una operación. Se trata de una comprobación de tiempo constante. Si un objeto contiene un elemento es una operación de tiempo constante. Sucede bastante instantáneamente, a diferencia de una matriz que tiene que buscarse de principio a fin. que ya no tenemos un bucle dentro de un bucle, solo
tenemos un solo bucle trayendo nuestro dedo de la complejidad del tiempo un total de descuento. Ah, de y hay una manera de que podamos hacer esto un poco más simple. No hará mucho por un tiempo o espacio complejidades, pero hará que el problema sea mucho más elegante y mucho más fácil de entender. Y vamos a pasar por eso en el siguiente video. Nos vemos ahí.
8. Eliminar manos: simplicidad definitiva: bienvenida de nuevo para quitar los dupes. Lo que hemos hecho hasta ahora se resuelve este problema para luego reducir la complejidad del tiempo. Empezamos por encima y al cuadrado, y al agregar en un objeto, logramos reducirlo a O de fin. Hay otra forma de resolver este problema, que no cambia tus complejidades de tiempo o espacio. Eso hace que todo el problema sea mucho más fácil de pensar. Yo sólo voy a escribir la solución y luego podremos discutirla después. Asegurémonos de que funcione y lo haga. Obtenemos lo que esperamos. Esta es la solución, y vamos a explicar qué está pasando. Estamos usando un set una vez más. Entonces cuando insertamos una cadena en un conjunto, cada carácter individual se inserta en un conjunto sólo valores únicos aire almacenado. Por lo que cualquier duplicado va a ser ignorado y desechado una vez creado el conjunto. Utilizamos este método llamado un punto de rayos a partir de ahora lo que hace el raid fuera es que toma en una epidural, un adorable, y JavaScript es una estructura de datos que mantiene nuestro seguimiento del orden en el que se insertado y un conjunto hace exactamente eso. Un conjunto hará un seguimiento de los personajes en el orden en que fueron insertados, que es exactamente lo que necesitamos, porque hace que podemos decir que si set es un honorable y funcionará con este método arrayado desde el cual literalmente se lo convirtió en una matriz. Por lo que esta afirmación aquí mismo es igual a una matriz que contiene los caracteres únicos y la fuerza con su orden preservado. Todo lo que estamos haciendo después de eso es usar join para convertirlos en una cuerda. La complejidad del tiempo aquí es exactamente la misma. Tomamos cada personaje e insertamos en el conjunto uno por uno. Entonces ese es el bucle. Dándonos oh, de fin. Unirlo a una matriz es nuestro arrepentimiento. Transformarlo en una matriz también es viejo entonces y después, uniéndolo como oh, de n una vez más. Entonces tenemos tres n y cuando dejamos caer la constante, nos quedamos en O de n por complejidad espacial. Ponemos a cada personaje en un conjunto y luego en una matriz. Entonces tenemos oh de dos n, que de nuevo se convierte en O de n. ojalá el te muestre lo poderoso que es un conjunto y cuánto masterización estructuras de datos pueden ayudarte con estos problemas. Cuanto más sepas, más podrás aplicar estas cosas y problemas futuros. Giramos lo que se trataba de una función de 15 líneas. Si las dos líneas, es mucho más fácil de leer, entender y correcto, te
veré en el siguiente video.
9. Frecuencia máxima: bienvenidos al siguiente problema. Frecuencia más alta. El objetivo aquí es escribir una función que tome en una matriz de cadenas y retorno. El string que ocurre más comúnmente implícito en este problema es que la teoría que recibes podría tener algunas cadenas duplicadas, algunas ahí dentro varias veces, y queremos la que aparece con mayor frecuencia. Si hay múltiples cadenas con la misma alta frecuencia, queremos devolver la que aparece primero. Estos son algunos ejemplos en el 1er 1 C es la única cadena que aparece más de una vez, así que eso es lo que queremos devolver en la siguiente. ABC aparece tres veces y D E F dos veces, Así que queremos ver a ABC saliendo en la siguiente. Ambos son presidente sólo una vez. Tanto lo siento. Y como ABC es el primero, queremos que ese salga de nuevo y en el último ojos GH y son más veces que cualquiera de los demás. Entonces eso es lo que queremos volver. Adelante y empecemos con la solución, así que vamos a necesitar procesar cada cadena que está en nuestro array para poder realizar un seguimiento de las frecuencias. Entonces vamos a necesitar empezar con un bucle como de costumbre a medida que lleguemos a cada cadena o de alguna manera vamos a
necesitar hacer un seguimiento de cuántas veces lo hemos visto. Vamos a seguir adelante y usar un objeto para hacer un seguimiento de estas cuerdas y en el bucle. A medida que procesamos cada cadena, podemos seguir adelante y actualizar nuestro objeto. Entonces pensemos en la primera cuerda. Adelante y centrémonos en este ejemplo por ahora, en I igual a cero, el primer ítem va a ser ABC. Vamos a seguir adelante y crear una variable para eso. Por lo que esta cadena va a ser A B, C y R Objeto está vacío. Vamos a querer agregarla a las frecuencias. Objeto. De acuerdo, hasta ahora, tan bien. Sigamos adelante y veamos qué pasa si volvemos a pasar a la siguiente cuerda. ABC vamos a estar aquí, y esta cuerda va a ser ABC una vez más. Pero ahora esta línea de código no está haciendo lo que queremos. Es restablecer el valor a uno que no hace nada por nosotros. Vamos a necesitar alguna forma de comprobar si es la primera vez que nuestro objeto ve esta cadena. Si lo es, necesitamos darle el valor de uno. De lo contrario necesitamos de alguna manera tomar el valor y aumentarlo en uno. Entonces comencemos comprobando si es la primera vez que vemos esta cadena. Y si lo es, entonces aún no estará presente en el objeto. Entonces si aún no existe en el objeto, entonces comprobarlo debería darnos indefinido. Y si es indefinido, necesitamos darle un valor de uno. ¿ Quién es la primera vez que vemos la cuerda? Si, sin embargo, ya existe, lo que
significa que ya ha cementado tu valor 123 o lo que necesitemos para aumentar eso en uno . Esto parece que tiene sentido para mí. Vamos a seguir adelante y alargar nuestra matriz de frecuencias. Disculpa objeto solo para asegurarnos de que estamos haciendo esto correctamente. Y voy a seguir adelante y deshacerme de estos tres por ahora y solo trabajar con este ejemplo veamos
lo que esperamos. A. B C's aquí dos veces D E f. tres veces y G h I cuatro veces encendido. Nuestro objeto refleja eso correctamente. ¿ Qué tenemos que hacer ahora? Bueno, alguna manera
necesitamos averiguar cuál de estos valores es el más alto. Necesitamos saber que cuatro es el valor más alto aquí y que la cadena correspondiente a eso es G H I. Podríamos hacer algo de procesamiento aquí abajo. Podríamos tomar cada valor individual en el objeto y luego encontrar el número más alto haciendo
un seguimiento . Pero ya tenemos un bucle for. Sólo podemos hacer eso mediante, uh actualizando una variable a lo largo del bucle. Vamos a seguir adelante y crear una variable para almacenar la más alta conjetura gratuita que hemos encontrado
hasta ahora . Y lo inicializaremos a cero. Y también es variable creativa para la cadena más frecuente, y la inicializaremos al primer elemento de nuestras cadenas son un en nuestro bucle. Sigamos adelante y actualicemos esto cada vez que pasemos por nuestro bucle. Por lo que sólo van a necesitar actualización Si tenemos una nueva frecuencia máxima. Vamos a comprobar si damos este cheque aquí mismo comprueba si nuestra nueva frecuencia lo que significa que el valor acabamos de actualizar es mayor que la frecuencia Max anterior que teníamos. Si lo es, queremos actualizar ese número de frecuencia También queremos actualizar la cadena más frecuente
porque eso significa que se cambia una vez a medida que pasamos por este bucle, estas dos variables se actualizan repetidamente ya que necesitan Teoh. Al final, la variable de cuerdas
más frecuentes aquí contendrá la calle más frecuente. Entonces podemos simplemente seguir adelante y devolver eso. Añadamos estos de nuevo y asegurémonos de que todo funcione como esperamos, Así que si lo es, esperamos ver ABC,
ABC y G H I. Y eso es lo que obtenemos. Parece estar funcionando correctamente. Sigamos adelante y hablemos de la complejidad del tiempo de esta solución. Tenemos un bucle aquí de inmediato. Tráenos 20 de fin dentro del bucle. Todo lo que hacemos es realizar algunas comprobaciones y actualizar un par de variables si es necesario. Esos no son bucles en sí mismos, así que no van a cambiar nuestra complejidad del tiempo. Entonces nuestra complejidad del tiempo final va a ser o de cualquiera Y ¿qué pasa con el espacio? Bueno, estamos almacenando cada cadena que encontramos en nuestro objeto de frecuencias. Si nuestra matriz de cadenas contiene sólo cadenas únicas, entonces este objeto de frecuencias va a contener todas ellas. Por lo que esencialmente va a ser proporcional al tamaño de nuestras cuerdas son un significado. También va a ser oh, de fin. ¿ Qué podemos quitarle a este problema? Bueno, este problema esencialmente nos obliga a almacenar datos de actualización a medida que pasamos por nuestro bucle. Esta es una buena técnica a tener en cuenta. Los problemas a menudo no requerirán esto, y se puede llegar a una solución sin hacer un seguimiento. De hecho, incluso aquí no teníamos que hacer esto. Podríamos simplemente comentar eso fuera y comentar esto, y podríamos realizar algún significado de post procesamiento aquí abajo. Podríamos agregar un poco más de código para luego averiguar qué valor es el más alto y luego a
qué cadena corresponde. Pero en cambio hacemos un seguimiento de todo a medida que pasamos por nuestro bucle, por lo que no necesitamos hacer nada después. En general, trate de ver. Si el almacenamiento de datos y alguna forma creativa puede facilitar un algoritmo, podría ser capaz de reducir la complejidad del tiempo. Pero si no, al
menos puede hacer que el código sea más sencillo. Ya veremos en el siguiente video
10. Rotación de cuerda: bienvenidos al siguiente problema. Rotación de cuerdas. El objetivo aquí es escribir una función que tome en dos cuerdas y determine si sus rotaciones unas de otras. Ahora, ¿cuál es la rotación? Estos son ejemplos de rotaciones, por lo que tenemos la cuerda 1234 Para rotarla, podemos sacar un personaje del principio y colocarlo al final. Eso nos da 2341 Podemos hacerlo de nuevo y tomar los dos y moverlo hasta el final, y obtenemos 3412 y haciendo eso una vez más. Mover un tres al final consigue su 4123 Eso es una rotación aquí. Algunos ejemplos más. Adelante y empecemos a escribir esta función, así que la primera forma en que podemos averiguar si ciertamente no son rotaciones es si las cuerdas tienen longitudes diferentes para dos cuerdas tres rotaciones de otra de otra. Tienen que ser exactamente de la misma longitud. Entonces sigamos adelante y comprobemos eso. De acuerdo, ¿ terminaste con eso? No. Una forma de resolver este problema sería tomar nuestra primera cuerda y crear cada rotación
posible de la misma a medida que lo hacemos. Verificaremos si esas rotaciones equivalen a la segunda cuerda. Si lo hacen, podemos volver verdadero. Y si superamos todas las rotaciones y no hay coincidencias de las que podamos devolver false, sigamos adelante y escribamos un bucle para hacerlo por nosotros, y para hacerlo, vamos a usar el método string dot en rodajas. Este es un método que extraerá texto de una cadena. El modo de usarlo es darle a los parámetros el índice de inicio y fin que nos gustaría recortar y rebanará entre esos dos índices. Entonces, por ejemplo, rebanar esto en Índices uno y ocho significa que el Índice uno está aquí y el próximo ocho está justo aquí y vamos a conseguir todo entre esos dos. Significando esto este es el método que usará. Veamos qué en esto imprime y sigamos adelante y deshacernos de tres de estos y enfocarnos en éste. De acuerdo, Entonces a medida que me muevo de izquierda a derecha, obtenemos rebanadas un poco más grandes y más grandes. Ahora intentemos con otros índices. Intentemos rebanar. Lo hicimos desde el principio hasta el índice, y ahora intentemos en el índice hasta la longitud de las cadenas. Y lo que vemos aquí es una división perfectamente limpia. Lo que tenemos que hacer para realmente rotar esta cuerda, su lugar, esto al principio. Y entonces obtendríamos rotación con una R al final. Seguimos haciendo eso y poniendo esta cadena antes que ésta, y hemos generado cada rotación posible. Déjame mostrarte lo que eso significa. Simplemente necesitamos cambiar el orden de estos dos y obtenemos cada rotación una por una de letras. Quítalo del principio y colocado al final. Esto es exactamente lo que tenemos que hacer ahora es chequear. La rotación de F es igual a la segunda cadena. Si lo es, podemos salir del bucle y devolver verdadero. Y si llegamos al final y ninguno de ellos coincide, regresamos falso. Adelante,
deshaznos de estos y veamos si eso funciona. Entonces esperamos tregua y dos falsos es, y eso es lo que obtenemos. Nos vemos bien. Hablemos de la complejidad temporal de esta función. Entonces ya tenemos un bucle aquí, llevándonos a Ole de Ed esta vez n no es el tamaño de la teoría a o el número de argumentos . En realidad va a representar la longitud de estas cuerdas porque eso es más o menos lo
único que cambia. De hecho, eso es lo único que cambia que podemos medir. Entonces tenemos un no de bucle final aquí. Inspeccionemos esta línea este renglón un poco de cerca. Por lo que la rebanada, según los muelles para Indian, es en realidad un bucle porque cada personaje tiene que estar contaminado uno por uno. Entonces lo creas o no, rebanada es una operación O de n. Y lo que tenemos aquí es un bucle dentro de un bucle que nos lleva a, aunque de n cuadrado y espacio. Estamos almacenando una rotación y esta variable, por lo que la cantidad de caracteres en la cadena que sostiene esta variable va a ser igual a la longitud de la cadena. Entonces, en otras palabras, la cantidad de espacio que esta variable usa hacia arriba va a ser equivalente a la cantidad de espacio que usa esta cadena. Entonces eso va a ser lineal. Eso es todo por la solución. Pero hay uno más que hace que esto sea mucho más sencillo para nosotros. Voy a seguir adelante y escribir el código y lo discutiremos inmediatamente después y vamos a ejecutarlo y estamos bien para ir ahora Pensemos por un minuto por qué esto está funcionando. Tomemos estos dos y coloquemos la rotación junto a sí mismo. Entonces, en otras palabras, estamos realizando esta acción aquí mismo. Str wana plus str one Y estamos revisando para ver si esta cadena así que el 1er 1 duplicado tiene el 2do 1 en algún lugar de ella. Por lo que estamos buscando la existencia de esto en algún lugar dentro de esto y podemos encontrarlo. Está justo ahí. Pruébalo por ti mismo. Pero cada rotación que se pueda llegar a estar presente en esta cuerda. Eso es más o menos una ley aquí. En cuanto a cómo funcionan estas rotaciones, pones una cadena junto a sí misma y contiene cada rotación de la cadena inicial. El tiempo de complejidad de esta solución es oh, de n. todo lo que estamos haciendo es agregar una cadena a sí misma, que es lineal y luego verificando para ver si incluye el 2do 1 que también es Lanier. Entonces eso se convirtió en oh, apagado y el espacio también es de n porque estamos sumando estos dos y la longitud va a ser proporcional exactamente. Doblar a la longitud de éste aquí mismo. Eso es todo por este problema al ver el siguiente.
Arnav Aggarwal, Full-Stack Engineer & Instructor
