C++: Como preparar a entrevista em codificação

1. Bem-vindo a este curso!: Olá pessoal e bem-vindos à programação C mais explosão. A entrevista de codificação. Meu nome é Alex e tempo de um desenvolvedor de software experiente que vem trabalhando com C plus há cerca de quatro anos. Agora, a estrutura desta classe vai ser dividida em elementos-chave que são discutidos documento objetivo chamado entrevistas para desenvolvedores de software. Em primeiro lugar, vamos falar sobre as complexidades de um algoritmo, tanto tempo quanto espaço. Então vamos pular em matrizes. Então vamos olhar para cordas. Então, novamente, perguntas de entrevista baseadas em cordas é o tópico em que vamos nos concentrar. Em seguida, também, vamos olhar para alguns algoritmos de classificação muito importantes como classificação de bolha, quicksort e assim por diante. Nós também olharemos para as árvores. Eles são traversos, e algumas outras perguntas de entrevista que você pode receber no DOM. E também, vamos dar uma olhada em pilhas e filas. A classe é criada para qualquer parte que quer uma vez para aprender algoritmos na linguagem de programação de C plus, ou alguém que quer se empregar no campo da engenharia de software. E uma vez que você aprende perguntas que podem ser dadas em entrevistas para que eles possam basear suas entrevistas. Não há pré-requisitos reais para este curso. Então sua vontade de aprender e uma conexão com a Internet. Na medida em que o projeto da classe vai, será uma pergunta que pode ser recebida em um cenário de entrevista que você pode olhar. Pense na cabeça, pode ser tempo você mesmo por 30 minutos e tente chegar ao melhor extrato que você obtém. Chamou isso de interessante. Estou ansioso para vê-lo na próxima lição. Vamos começar. 2. Notação de Big o: Bem-vindo à Seção dois, grande notação O. Na palestra um, vamos falar sobre grande O, grande Omega na complexidade do tempo. Vamos começar. A grande notação O é uma notação matemática que descreve o comportamento limitante de uma função quando o argumento tende para um determinado valor ou infinito. Na ciência da computação, a grande notação O é usada para classificar algoritmos de acordo com a forma como eles executam os requisitos de tempo ou espaço crescem. À medida que o tamanho da entrada cresce. Não entender isso completamente pode realmente prejudicá-lo no desenvolvimento de um algoritmo. Você não só pode ser cobrado duramente por não entender o Big O, mas também lutará para julgar quando seu algoritmo está ficando mais rápido ou mais lento. Ao analisar algoritmos para eficiência, usamos grande O. Por exemplo, o tempo, o número de etapas necessárias para concluir um problema de tamanho n pode ser encontrado para ser n vezes n para o poder de dois mais oito vezes n mais um. À medida que n cresce, o n ao poder de dois termos passará a dominar isso. Todos os outros termos podem ser negligenciados. Por exemplo, quando n é 500, o termo cinco vezes n ao poder de dois é cento, dez centenas vezes maior do que as duas vezes n. Ignorar a letra teria um efeito insignificante sobre o valor da expressão para a maioria dos propósitos. Além disso, o coeficiente se tornou irrelevante se o compararmos com qualquer outra ordem de expressão. Então, a grande notação O captura o que resta. Escrevemos o de n para o poder de dois. Agora, vamos ver alguns exemplos das complexidades do tempo que certos algoritmos de ciência da computação. Um é chamado de constante. Por exemplo, um algoritmo que determina se um número é par ou ímpar teria complexidade desse tempo. O do log n é chamado de logarítmico. Por exemplo, pesquisando um elemento com pesquisa binária em uma matriz classificada. Vou apresentar esses tipos de pesquisa e como ela funciona em uma seção posterior de n é chamada linear. Essa é a complexidade do tempo de iterar por meio de uma matriz para uma variedade de propósitos. Por exemplo, para encontrar um elemento e assim por diante. O de n ao poder de dois é chamado de quadrático. Esse é o caso quando você tem duas forças aninhadas em uma matriz. Isso pode ser útil quando você deseja classificar uma matriz. Finalmente, o n fatorial é chamado fatorial. E nos deparamos com essa complexidade de tempo ao tentar, soluções de força bruta estão calculando permutações irrestritas. Em geral, codificando entrevistas, você insere a complexidade do tempo para, embora possível, para que seu algoritmo leve menos tempo para ser executado e seja mais eficiente e otimizado. No entanto, você pode começar a partir de uma solução que não é tão boa se essa for a primeira ideia de que você consegue resolvê-la e depois trabalhar seu caminho para uma abordagem mais otimizada. Acadêmicos usam Peek, oh, theta grande e grande ômega para descrever tempos de execução. Na academia, o grande Omega é o conceito equivalente, mas para menor ligação, impressão, os valores em uma matriz são grandes ômega de um. Afinal, você sabe que não será mais rápido do que esse tempo de execução. Big Theta dá um limite apertado no tempo de execução. Podemos dizer que a ligação da função de cima e de baixo é representada pela notação teta. O comportamento assintótico exato é feito pela notação d Theta. Neste curso, usaremos apenas a notação Big-O para nossos algoritmos da maneira que a indústria tende a usá-la sempre tentando oferecer a descrição mais rigorosa do tempo de execução. 3. Visão de matriz e vetor: Olá e seja bem-vindo aos arrays da seção três. Nesta seção, falaremos sobre uma estrutura de dados básica chamada apagar que surge muito nas perguntas da entrevista sobre codificação. E é muito importante que você tenha uma boa compreensão disso na programação. Quando pensamos em uma matriz, pensamos em uma estrutura de dados que se assemelha uma coleção de itens, locais de memória armazenados. A ideia é armazenar vários itens do mesmo tipo juntos. Isso facilita o cálculo da posição de cada elemento simplesmente adicionando um deslocamento a um valor base. Exemplo, o local da memória do primeiro elemento da matriz, geralmente denotado pelo nome da matriz. O valor base é o índice 0 e a diferença entre os dois índices é o deslocamento. Para simplificar, podemos pensar em uma frota de matrizes lá em cima onde em cada etapa é colocado o valor, digamos que um de seus amigos. Aqui, você pode identificar a localização de qualquer um de seus amigos simplesmente sabendo a conta do passo em que estão. Lembre-se, a localização do próximo índice depende do tipo de dados que usamos. E diz, por padrão, matrizes regulares de escopo local. Por exemplo, aqueles declarados dentro de uma função não são deixados sem inicialização. Isso significa que nenhum de seus elementos é enviado para nenhum valor específico. Seu conteúdo é indeterminado quando a teoria do ponto é declarada. Mas os elementos em uma matriz podem ser inicializados explicitamente para valores específicos quando são declarados colocando esses abraços de valores iniciais. Por exemplo, você pode ver aqui a primeira linha em nossa imagem. O número de valores entre louvores não deve ser maior do que o número de elementos na matriz. Por exemplo, em nossa imagem na primeira linha, foi declarado tendo cinco elementos especificados pelo número próximo dos colchetes. E o elogio está contido exatamente cinco valores. Um para cada elemento. Declare com menos. Os elementos restantes são definidos para seus valores padrão, que para tipos fundamentais significa que eles são preenchidos com zeros. O valor dos elementos em uma matriz pode ser acessado exatamente como a falha de uma variável regular. O mesmo tipo. A sintaxe é nome e , em seguida, entre colchetes, o índice. Observe que o terceiro Fu elementar especificou F-O-O. Em seguida, entre parênteses, o número dois. Como o primeiro é F0 de 0, o segundo é F0 F1. E, portanto, o terceiro é f o de dois. Pelo mesmo motivo, seu último elemento, é F0, F4. Portanto, se escrevermos algo como F0 05, estaríamos acessando o sexto elemento do F-O-O e, portanto, realmente excedendo o tamanho da matriz. Em C plus, plus. É sintaticamente correto exceder o intervalo de valores de índices para uma matriz. Isso pode criar problemas, já que o X está em elementos de franja externa não causam erros na compensação, mas podem causar erros no tempo de execução. Neste ponto, é importante ser capaz de distinguir claramente entre os dois usos que os colchetes têm relacionados ao apagar. Eles executam duas tarefas diferentes. Uma é especificar o tamanho das matrizes quando elas são declaradas. A segunda é especificar índices para elementos de matriz concreta quando eles são acessados. Não confunda esses dois possíveis usos de colchetes com matrizes. Em algum momento, talvez precisemos passar uma matriz para uma função como parâmetro, C plus plus. Não é possível passar toda a memória do bloco representada por uma matriz para uma função diretamente como um argumento. Mas o que você pode fazer é que você possa passar suas entradas. Na prática, isso tem quase o mesmo efeito e é uma operação muito mais rápida e eficiente desse ponto de vista base. Para aceitar um parâmetro de matriz para uma função. Os parâmetros podem ser declarados como tipo, mas com colchetes vazios estão atendendo ao tamanho real da matriz. Por exemplo, para um procedimento. E, em seguida, na lista de parâmetros, int arg. Em seguida, alguns colchetes vazios. Esta função aceita um parâmetro do tipo array de int chamado ARG. Para colar essa função, uma matriz declarada como int, meus elementos de matriz, seria suficiente escrever um código como esse procedimento da minha matriz. Portanto, isso seria uma visão geral do tipo de matriz em C plus plus. Claro que você pode fazer muitas outras operações com cada um dos elementos. Você pode trocá-los e assim por diante. Em seguida, nas próximas palestras, vamos dar uma olhada em uma variedade de algoritmos que muitas vezes surgem em perguntas de entrevista de codificação. E analisaremos a complexidade deles, diferentes abordagens e, basicamente, como resolvê-las para que possamos estar melhor preparados para suas futuras entrevistas. 4. Deletar em uma matriz: Olá pessoal e bem-vindos à palestra três, excluindo em uma matriz. Nesta palestra, vamos falar sobre como excluir um item de uma matriz. Essa pergunta tem duas variações. De uma matriz onde sabemos qual o valor do número que queremos excluir da matriz. E a variação em que sabemos qual é a posição do item na matriz que queremos excluir. Aqui temos a variação que o valor do item é inserido e não deposição, mas o outro é muito semelhante a este. Vamos executar o código e depois da dívida e algumas explicações sobre ele. Podemos pensar sobre a complexidade desse programa como faríamos em uma situação de entrevista. Vamos começar pela média. Como uma boa prática, é sempre bom separar suas funções da função principal e, em seguida, chamar sua função que você escreveu para uma pergunta específica da função principal. Em uma pergunta de entrevista e um cenário de entrevista, eles podem até lhe dar a função sem o corpo. Então, é apenas um cabeçalho. E então você escreve a função que deve fazer como isso iniciou o SQL para. Em nossa situação, à medida que entramos na função principal, declaramos nossa matriz int da qual vamos remover, inicializamos com alguns valores integrais codificados. Então temos cada lado dividindo o tamanho da teoria pelo tamanho de uma integral. Então escrevemos x é seis. Queríamos remover seis desse array. Agora, chamaremos a função delete element, que retorna o novo tamanho da matriz após a remoção, e também obviamente remove o item da matriz. Esta função de elemento de exclusão, como você pode ver, tem três argumentos. O primeiro argumento é nossa matriz da qual queremos remover o item. O próximo item. O item significa o tamanho da matriz. E o último item é o número que queremos excluir da matriz, no nosso caso seis. E como você pode ver, esses são os argumentos que passamos quando chamamos a função. O que essa função faz é declarar uma variável i usada para iterar através da matriz. E então, em um loop for-loop, iteramos toda a matriz, tomando cada elemento. E se o elemento for igual a x D elemento que queremos remover da nossa matriz. Então nós quebramos. X é encontrado na matriz e eu é o índice em que x foi encontrado. Vamos diminuir o tamanho da matriz porque ela será um tamanho menor do que era antes, porque obviamente vamos excluir um elemento dele. E então vamos apenas mover todos os elementos um espaço à frente. Lesley, vai retornar o tamanho da matriz. Aqui está o novo comprimento da matriz. Então vamos ver Monte Carlo e depois iterar através dele e mostrá-lo. Então, se executarmos isso, veremos que a nova matriz da torre deve ser 1158910. Você pode ver que é o array. Então, agora vamos pensar sobre a complexidade do espaço dos diamantes. A complexidade do espaço é obviamente linear porque não declaramos outras variáveis. Se o fizermos, eles são considerados constantes. Esse espaço é linear e, em seguida, a complexidade do tempo, bem, iteramos através da matriz uma vez aqui. E, obviamente, uma vez aqui. A complexidade do tempo também é linear. Podemos fazer isso em uma complexidade melhor do que esta? Bem, não, porque nosso elemento pode ser o primeiro, então ainda seria linear porque precisamos iterar através de toda a matriz. Nesta etapa. Tratava-se de excluir um item da matriz. E vocês podem fazer a variação em que você exclui um item de uma matriz onde você sabe que a posição é muito semelhante a esta. Mas você pode tentar isso em casa. E deixe-me saber como foi. 5. Pesquisa linear em uma matriz: Olá pessoal e bem-vindos de volta à palestra quatro. Nesta palestra, vamos falar sobre pesquisa em uma série de números inteiros, mais precisamente pesquisa linear. O cenário é que temos uma matriz de inteiros que tem números que não são classificados. Então, qualquer tipo de números que sejam inteiros. E o problema com o gás S para encontrar um número dessa matriz e retornar seu índice. Agora, obviamente escreveríamos uma função separada da função principal que chamamos, chamaríamos da função principal e a usaria para encontrar nosso elemento. Como você pode ver no meu código aqui, declaramos que uma taxa, é codificada, valores 2341040. Em seguida, o valor x que está lá. Então vamos, como de costume, usar o tamanho da função auxiliar para calcular o tamanho da nossa matriz. Então vamos dar nosso int, que salva o valor da função de pesquisa. Esta função retorna um int e leva três parâmetros. Nossa matriz, o tamanho da nossa matriz e o número que queríamos encontrar. Em seguida, vamos iterar através dele com a ajuda dessa variável auxiliar chamada. Enquanto o percorremos, encontramos nosso elemento necessário e, em seguida, retornaremos seu índice. No final, vamos retornar menos um, o que significa que não o encontramos. Retorne i, como você já provavelmente sabe, mas vou lembrá-lo disso. Diga-lhe se você não sabe, a instrução return quando você se senta em sua função, interrompe essa função e basicamente vai para onde a função é chamada e retorna esse valor. Então, o que é depois de um retorno que foi aquecido? A função não será executada. Esse retorno menos uma instrução só será calor se esse retorno nunca for executado. Portanto, se nosso valor nunca foi encontrado na matriz, o resultado com o índice do valor da matriz que queremos encontrar. Se o resultado for menos um, claro, vai dizer que o elemento não está presente. E se for dizer que está presente no resultado do índice que é retornado da nossa função. Agora, como você pode ver, se você executar este programa, veremos que esse elemento está presente no índice três. Você sabe, a contagem em uma matriz é baseada em zero, o que significa que o primeiro índice é 0. É por isso que este será um a n. O número de pesquisas para Dan é o índice três. Agora vamos falar sobre complexidade. A complexidade do espaço é o tamanho do nosso início, que é linear em relação à entrada. Então a complexidade do tempo, bem, a complexidade do tempo é dada pela nossa função porque aqui nós iteramos através do nosso array uma vez. Isso significa complexidade temporal linear. Agora, podemos fazer isso melhor do que linear? Bem, não, porque na pior das hipóteses, o elemento que queremos encontrar essa posição e isso significa que temos que iterar através de toda a matriz para finalmente encontrá-la na última posição. E isso levaria tempo linear. Nesse problema, a complexidade do espaço e do tempo dificilmente é linear. Vamos passar para a próxima palestra, onde mostrarei uma maneira mais eficiente de fazer isso. Mas sob uma condição, e essa é a matriz sendo classificada cada vez mais ou diminuindo. 6. Pesquisa de binário em uma matriz: Olá pessoal e bem-vindos à palestra cinco, pesquisa binária em uma matriz. Este é basicamente o primeiro algoritmo mais sério que vamos abordar neste curso. E este é mais frequentemente dado em entrevistas. E talvez não essas variações básicas, mas outras variações que podem ter outras restrições ou não lhe pediram incessantemente para implementar isso. Mas outro tipo de problema em que você precisa usar esse tipo de algoritmo. O problema é que, dada uma matriz classificada de n elementos, você deve escrever a função para começar a fornecer um elemento x nesta matriz. Uma abordagem simples, como vimos na última palestra, seria fazer pesquisa linear em sua matriz. A complexidade do tempo seria linear, como vimos nesse espaço a complexidade seria linear. Mas outra abordagem para executar a mesma tarefa usando pesquisa binária e dado o fato que nossa matriz já está classificada. Então, o que a pesquisa binária basicamente faz, em vez disso, ela pesquisa uma matriz classificada dividindo repetidamente o intervalo de pesquisa. Inale, comece com um intervalo cobrindo toda a matriz. Se o valor da chave de pesquisa for menor que o item no meio do intervalo. o intervalo para a parte inferior, ajude, estreite-o para a mão superior. Verifique repetidamente até que o valor seja encontrado ou o intervalo exatamente. A ideia de pesquisa binária é usar as informações de que a matriz está classificada. Reduzida a complexidade do tempo, logarítmica. Agora, se olharmos para essa imagem, podemos ver um exemplo. Temos essa matriz que tem 2581216233856172091. Vamos levar m no meio seria baixo e seria 0 e h seria nove. Os três índices com os quais estamos trabalhando, precisamos procurar por 23. Bem, vamos verificar, e 16 é menor que 23. Então, vamos nos mover para a direita. Vamos tomar l, m, a média aritmética de n e h. E podemos ver que 23 é menor, 36. Vou procurar na metade esquerda. E agora seriam seis, porque será m menos um. M seriam cinco. Aqui nós pesquisamos 23 sem sequer olhar para itens como 5812 ou mesmo 72. Agora vamos ver o código e ver como ele funciona. A função principal é muito parecida com a última função principal que usamos na pesquisa linear em uma matriz de números inteiros. A única diferença é a função que ela usa e retorna os índices em que nosso número foi encontrado. Essa função de pesquisa binária, como você pode ver, usa quatro argumentos. O primeiro é a nossa matriz de números inteiros. O segundo, o terceiro é o R. Ou no caso de esta imagem ser h. Porque aqui está certo, havia alta. Eles significam basicamente a mesma coisa. E então x é o número que fomos pesquisar. Vamos fazer chamadas recursivas. Começando dizendo, não estão tão certos é maior ou igual a L. Vamos declarar encontro no GRE e dar-lhe basicamente a média de R e L. Se vocês estão se perguntando, por que esse L plus R não é dividido por dois? E está escrito assim. Bem, isso em primeiro lugar tem menos l e depois adiciona. Isso ajuda a evitar casos de transbordamento. O número é grande o suficiente para exceder a memória e, para o seu programa, basicamente, falhará. Se a matriz de carne fosse igual a x, o número que não estávamos procurando, então devemos retornar o índice porque o encontramos. Se for maior do que o elemento que estamos procurando, só poderemos procurar no sub-array esquerdo. Então, vamos chamar recursivamente a pesquisa binária de ARR Again L. E então em vez da área que vou chamar meados menos um, vamos olhar apenas no sub-array esquerdo. No outro caso, vamos olhar no subarray certo dando a chamada recursiva em vez de l No segundo argumento, meados mais um. Por fim, se nenhum outro retorno foi atingido ao retornar das chamadas recursivas. Agora vai retornar menos um. Como você pode ver, se executarmos este programa, o número dez foi encontrado novamente no índice três. Como já disse antes, a complexidade do espaço é linear porque declaramos a matriz, então a complexidade do tempo é logarítmica. Graças a esse bom algoritmo. Se a matriz não for classificada, você não poderá encontrar um elemento em uma complexidade de tempo melhor do que linear. Isso só é possível aqui porque sabemos que a matriz está classificada e temos dessa forma, maneira mais rápida de examiná-la. Trata-se de pesquisa binária. Você pode tentar implementá-lo sozinho sem olhar para esse algoritmo. Esta é uma questão importante de entrevista e um algoritmo importante que você realmente deve conhecer muito bem. 7. Cordas: Olá pessoal e bem-vindos de volta à seção quatro. Nesta seção, estamos falando de cordas. Strings são objetos em C plus, além das três sequências atuais de caracteres. A classe String padrão fornece suporte para esses objetos com uma interface semelhante à de um contêiner padrão de bytes. Mas acho que recursos projetados especificamente para operar com cadeias de caracteres de byte único. Aqui podemos falar sobre funções de membro como swap, que troca o conteúdo de duas strings, anexar, que anexa uma string a uma determinada string e retorna um ponteiro para a string resultante. Inserir, apagar, encontrar alguns SDR e muitos outros. Vou anexar uma foto aqui com descrições para cada uma delas para que você possa lê-los e entender o que cada uma delas faz. Também podemos falar sobre operadores sobrecarregados, como uma flexão de duas ruas. Eles ficam com a concatenação de sinal de mais igual, desta vez com o sinal de mais. O operador de igualdade, implementando através de sinais de igualdade e assim por diante. Este vidro também tem uma variedade de construtores. O vazio que cria uma string vazia. Aquele que toma como argumento, a string entre colchetes. Você pode escrever sua string e ela inicializará esse objeto de bebida com o fluxo que você ali mesmo. Aquele que pega um inteiro e um caractere e instancia a string com esse caractere que será repetido pelo número de vezes dado. Para usar strings, você deve incluir um arquivo de cabeçalho adicional, código ilustrador que será incluído. E, em seguida, ponto de corda h entre parênteses triangulares. Além disso, você viu que pode incluir iostream que vem da entrada, fluxo de saída e geralmente precisa escrever e ler a entrada do teclado. Observe que essa classe lida com bytes independentemente da codificação, é usada para lidar com sequências multiplicadas ou caracteres de comprimento variável, como UTF oito. Os membros dessa classe, como comprimento ou tamanho, bem como seus iteradores, ainda operarão em termos de bytes, não caracteres codificados reais. Nas próximas palestras, vamos dar uma olhada em algumas perguntas de codificação de entrevistas que podem surgir que usam strings. Vamos começar a trabalhar. 8. Concatenação e encontrar o comprimento de uma corda de concatenação e encontrar o comprimento de uma corda: Olá pessoal. Nesta palestra, vamos falar sobre a nação de contato e encontrar o comprimento da rua. Vamos começar falando sobre concatenação. O operador plus pode ser usado entre duas cordas. Eu os adiciono e faço uma nova string? Isso é chamado de concatenação. Vamos tratá-lo em C plus. Além disso, na verdade, é um objeto, como já falamos. Na última palestra. objeto legal contém funções que podem executar determinadas operações em cadeias de caracteres. Por exemplo, você também pode concatenar strings com a função append. Você pode fazer isso da maneira que preferir. Falando em um nível mais concreto. Você pode ver no seu código algo como string S é igual a um mais b, onde a é outra string e B também é uma string. E concatene-os fazendo esse gêmeo de a e B no final. E basicamente fará com que um seja três, contém ambos primeiro dia e depois B. Agora, para obter o comprimento de uma string, você pode usar a função length tem profundo. Você pode ver alguns programas C plus plus que usam a função size para obter o comprimento da string. Este é apenas um alias que está em branco. Cabe completamente a você se você quiser usar o tamanho ou o tamanho. Agora, é claro, se você quisesse implementar esse problema sem usar essa função pré-construída, será bem simples. Você terá que iterar cada caractere da matriz com um loop for e seguida, ter uma integral instanciada com 0 incrementada para cada caractere. Dessa forma, você pode obter o comprimento sem essas funções pré-construídas. Você pode acessar os caracteres em uma string, como faria em uma matriz de carros, referindo-se ao seu número de índice dentro de colchetes. Para alterar o valor de um caractere específico. String, consulte o número do índice e use aspas simples, porque esse é um caractere. 9. Como alterar a caixa de string: Olá lá. Nesta palestra, vamos falar sobre como podemos mudar o fluxo de casos. O problema aqui é que precisamos converter todas as letras maiúsculas para minúsculas e vice-versa. Indústria. A nova abordagem aqui seria iterar a string e usar o ISA por função de pré-compilação para determinar se cada caractere está no aplicativo real ou não. Se for maiúscula, vamos convertê-lo minúsculas usando a função pré-construída inferior de CO2. E se não for maiúscula, converte-o em maiúsculas usando duas funções pré-construídas superiores. Agora, também podemos fazer isso sem essas funções pré-construídas adicionando ou subtraindo o valor 32. Porque essa é a diferença de números entre um valor maiúsculo e minúsculo. Por exemplo, a letra maiúscula tem um valor ascii de 65 e minúsculas tem um valor ascii de 97, que é 65 mais 32. Você também pode usar esse pequeno inferno para fazer esse problema. Se o entrevistador especificar que você não tem permissão para usar nenhuma função de string pré-criada. Agora, se olharmos para o código, temos essa função principal onde declaramos um fluxo STR, também especifica o escopo std porque não usamos o namespace std. Assim, você pode escrever o namespace usando std ou dizer std. E esses dois pontos duplos antes de Amy, membro STD que você escreve. Na próxima linha, inicializamos a string STR com essa string aqui. E então chamamos a função de transformação neste STR com o uso de três iteradores desde o início da string SDR até o final da história ou string, então não vamos respirar March chamou The Change Case para cada caractere dele. Esta é apenas uma maneira de iterar através dele. Na linha 16, as funções Change Case pega um caractere e retorna um caractere, como você pode ver em seu cabeçalho. E é apenas uma função if que verifica se o caractere está em maiúsculas, então ele retorna as letras minúsculas. E se não for significa que é minúscula. Nesse caso, vamos retornar a célula de caracteres maiúsculas depois de transformarmos toda a string com essa função, será praticamente a cada primeiro Casey. Em seguida, vamos gravá-lo no prompt de comando de saída. E como você pode ver, se executarmos esse código, obteremos a string exata que inicializamos o caso invertido. Eu já disse que você pode usar o hack 32 para fazer esse problema sem nenhuma função embutida. 10. Contando palavras/vogais: Oi pessoal e bem-vindos de volta à palestra quatro. Nesta palestra, vamos falar sobre como você pode chegar em direção às vogais em uma corda. Basicamente, uma string maior que tem espaços entre palavras. Algo como amostras ou Pablo pode ser se for um prêmio. O que o problema parece é que a função que você deve escrever recebe um argumento que é uma string, e então você precisa retornar o número de vogais. Para jantar de palavras. Este é o problema que vamos falar hoje nesta palestra. Como você pode ver, eu já codifiquei para você, mas vamos correr, como costumamos fazer. Elogiar, discutir o que tudo basicamente faz é que geralmente partimos da função principal. Aqui nós declaramos uma string que chamei SDR e Nike feet ABC space. E agora temos duas funções para contar o número de valores que ela tem. primeira função recebe o terceiro caractere, retorna brilhante. O que ele faz. Obrigado a esse personagem. Cabedal. Por exemplo, seria uma minúscula. Ele o devolve para maiúsculas. Podemos verificar contra os dentes superiores impecáveis e não os minúsculos também, porque então teríamos cinco condições aqui com o operador OR entre eles. O que fazemos é voltar lá, o personagem. Personagem. O personagem é um personagem como este, E, I, O, U. Algum desses assentos é verdade? Em seguida, retornamos a essa função. Como você pode ver, ele é chamado de outra função é chamado de vogais de contagem. Este recebe um TR baseado em parâmetros de string. Inicializa e integra, conte. O valor 0. Em seguida, iteramos através da string, através de cada um de seus caracteres. Então, se a vogal do personagem morto, então aumentamos a conta. No final, nós o devolvemos. Este é um método muito simples para retornar o número de vogais string. Agora vamos falar sobre a complexidade desse algoritmo. Bem, em primeiro lugar, esse espaço é linear porque não declaramos mais do que esse tratamento em si. Então a complexidade do tempo é linear para, porque iteramos cada um dos caracteres da string, tanto tempo quanto espaço e lugar. Estes são lineares grandes O de n. Agora, passando para o próximo problema, vai contar as palavras. Isso fará isso escrevendo uma função que recebe do parâmetro que é um fluxo e, em seguida, retorna um inteiro. Clara Decker, agora que inicializamos com 0 e um personagem que chamamos pré-forma morte anterior inicializa com espaço. Agora comemos o caminho através do fluxo que recebemos como parâmetro. Se o espaço de caracteres atual na lição anterior, incrementamos. Agora, o que isso significa? Bem, isso significa que encontramos o começo de uma nova palavra porque o personagem, agora não é o espaço no espaço anterior, costumava ser uma nova palavra, uma. Por fim, vamos atualizar anteriormente com x de i. Quando olharmos na próxima iteração. Atual, anterior, daí o urso anterior real. Orientação decente. Vamos devolver o número agora. Obrigado, você não pode ver. Se chamarmos essa função, ela retornará duas. Porque nossa string ABC space D0 seria considerado como tendo qualquer abc. E então essas não são palavras reais. Mas se você estiver digitando uma frase que não fizemos sentido, valeria a pena. Agora falando sobre a complexidade desse algoritmo, acho que está bem claro que esse espaço é em relação à entrada, porque não declaramos nada além do fluxo em si. Temos complexidade espacial linear, complexidade do tempo. Seria linear também porque comemos o retardado uma vez através do fluxo para verificar a condição e o valor anterior. Bem aqui. Discutimos dois algoritmos básicos que surgem. Algumas perguntas. Problemas iniciais. Eles são muito básicos, mas é muito importante começar com os mais básicos para entender as complexidades e como fazê-las de forma otimizada. Porque você pode então construir sobre a base, profundidade. Você precisa resolver e entender algoritmos e problemas mais complexos no futuro. O próximo capítulo sobre o qual vamos falar tem que reverter uma string, que é uma pergunta de entrevista mais comum. 11. Reversa de uma cadeia de caracteres: Olá pessoal, bem-vindos de volta. Nesta palestra, vamos falar sobre como reverter uma determinada sequência. Como você vai fazer isso? problema diz, é que dado esse gene da entrada, do teclado ou de um arquivo, você apenas dá a ele o valor que eu codifico a tarefa matric Jeff tapeçaria, e o problema é revertê-lo. Então, por exemplo, se tivermos uma string, se sua função com idealmente tendemos a transmitir se refere à dívida seria revertida ordem. Não vamos discutir como implementamos essa função e qual sua complexidade cada célula, primeiro lugar, declaramos uma string. Diz Bem-vindo aos quadrados. Então, apenas chamamos essa função. Essa função não retorna nada. É uma função de tipo de retorno vazio. Inicializamos o comprimento do fluxo e, em seguida, iteramos para a integridade do fluxo. O que fazemos é trocar entre eles, os personagens correspondentes. Por exemplo, quando eu vejo ou vamos trocar esses T-R-I-E saboroso r i n menos u, o menos um, menos um. Como contando matrizes decentes com base em zero, falaremos para trocar o primeiro elemento, que é 0, elemento que é menos um, um baseado em zero. Por exemplo, a string. Vamos tomar intenção G menos um. Vai levar a única indexação, em seguida, n menos dois, que é então trocá-los e depois trocá-los. Pontos. Aquecemos o meio da rua, paramos. Essa é basicamente a melhor maneira fazer essa operação. E isso, você pode ver se eu aquecer, nós vamos receber esses genes em sentido inverso. Agora, vamos falar sobre a complexidade espacial desse algoritmo. Em primeiro lugar, essa complexidade espacial é um respeito linear porque não recebemos a complexidade do tempo. N dividido por dois, porque metade da matriz pára de corresponder caracteres entre eles. Como sabemos, apenas o n e seu poder. A notação Big O da complexidade do tempo seria, assim como a complexidade do espaço seria linear para esse algoritmo. Na próxima palestra, vamos ver como conseguir verificar se uma palavra ou uma string é um palíndromo. Benadryl, o que significa que esse sonho que você tem primeiro é o mesmo. Vamos seguir em frente e falar sobre como podemos fazer isso. A complexidade desse algoritmo seria. 12. Verificação do palindrome: Olá pessoal e bem-vindos de volta à palestra do curso. Vamos ver como podemos verificar se funcionou? Significa que uma string é um palíndromo significa que é o mesmo. É o mesmo se o lemos da esquerda para a direita. Por exemplo, um BBA seria um Benadryl porque provavelmente seria a forma ABB. Isso ainda seria um BBA. Este também seria um pouco de drama, mas esses não seriam porque o lemos da esquerda para a direita além da meia-vida, o começo. Repita da direita para a esquerda. Temos dois LC WE. Agora que entendemos qual é o problema, você faria uma entrevista. O primeiro passo é entender qual é o problema uma vez de você. Podemos pensar em como resolvê-lo. Mas como acabamos de falar sobre como reverter uma string, esse é um problema muito semelhante nestes muito facilmente feitos se tivermos o algoritmo reverso, porque só precisaríamos verificar se nosso fluxo seria igual ao inverso disso. Com p igual, provavelmente seria verdade. Mas agora vamos adotar outra abordagem para esse problema. Resolva a função como uma string de parâmetros. E então não vamos retornar nenhum grau porque você vai apenas imprimir na saída esse gene que recebe como parâmetro. O parâmetro começará pelos valores iniciais 0 e depois envelhecerá com o tamanho do nosso fluxo. Então, enquanto índice, índice, índice, este caso XDR não é igual ao STR. Então, o personagem mágico desde o início, não a cena que vamos imprimir. A string não é aparente. Desenhe-me o retorno para a função h e del caminhos cruzados. O que significa que a idade não está invertida, significa que todo o fluxo, podemos desenhar isso. Você pode ver se eu arrasto, ele verifica cada um desses truques. Então, um BPA, um BB, CC, BB ou não. Complexidade. Complexidade facilmente se refere hoje em, mas porque temos essa constante napa diferente do fluxo de entrada, seria o caso, é dois divididos por dois porque todos nós precisamos ter esse gene. Atingimos metade de h seria o loop while com TI. Complexidade é linear instagram diz respeito ao preciso, estes seriam obviamente topo o impediu para fazê-lo. Porque você ainda precisa verificar a base da teoria para garantir que todos os personagens sejam iguais para que você possa confirmar que seus alunos sobre na última palestra desta seção, a próxima palestra. Vamos verificar se duas strings são anagramas, o que significa postar os mesmos caracteres. Há mais. Veja como podemos fazer para ser o algoritmo mais ideal. 13. Verifique se 2 corda, anagramas: Bem-vindo de volta. Nesta última palestra aqui falando sobre como você pode verificar a força dada? Palavras? Eles podem ser frases. O que significa que eles são compostos de personagens. O que quero dizer com amostra? Temos duas palavras, como cachorro. Cão seria anagramas porque um T1, 01. Isso seria mais um acordo porque a contagem dentro destes executa com f um g, e este temos dois anagramas de G. O problema nos pede para escrever a função para verificar se duas strings são ou não anagramas. Então, como você pode ver, a função principal começamos inicializando cada uma dessas cadeias de caracteres. Estamos chamando uma função que toma como parâmetros dois fluxos serão verdadeiros. Se esse G for eu integro a função cosseno, declaramos dois inteiros que vinculam. Primeiro vamos verificar se as cordas têm o mesmo comprimento. Isso significa que eles não podem ter os mesmos personagens. Como obviamente duas quantidades de caracteres não podem ser iguais antes do TPI do alto-falante sair, eles vão classificar strings. As estrelas, classificá-las com base em valores ascii, classificam-nas em ordem alfabética. Então, seremos três genes ao mesmo tempo. Usamos aqui então um, mas poderíamos ter usado porque basicamente o mesmo. Não estaríamos nessa função, nesta linha porque ela poderia hype já retornava falso booleano. Nós iteramos através de cada um desses genes e verificamos seu caráter, digamos igual, não igual, retornamos falso. Em vez disso, chegamos ao fim deles, personagens de conversa são iguais e podemos retornar verdadeiros. Colocamos essa função que retorna cada estado de um a dez. Podemos esses fluxos, gramas serão traçados. Caso contrário, podemos dizer que eles não são. Por exemplo, se vermos essas duas strings, a amostra correta, você pode ver que elas são n. Se mudarmos o segundo fluxo, o que ele faria é basicamente com essa condição, ser falso ou podemos até fazê-los do mesmo tamanho, letras diferentes e as duas, ainda são pacientes negros que você pode ver aqui porque eles iriam classificá-los em ordem alfabética e ver que um é p, um é G. Melhor esta tendência de declaração se aqui, três vezes falsa. Agora vamos falar sobre a complexidade do programa. solução salina diz respeito à complexidade espacial. Podemos considerar o primeiro streaming. complexidade do espaço seria grande O de n mais m. Obrigado pessoal por ficarem comigo. Nesta seção. Vamos continuar com a próxima seção. Tópico muito importante em relação às questões de codificação da entrevista. Classificação. Se falamos sobre o berçário ou como você pode ver, pode ser muito útil quando trabalhamos com cordas. Então, vamos encobrir a seção de complexidades deles agora. 14. Função de classificação de STL: Olá pessoal e bem-vindos de volta à palestra dois. Na segunda palestra, estamos falando sobre a função de classificação disponível na biblioteca padrão de C plus plus. Você pode usar como uma alternativa fácil quando o entrevistador não está realmente tentando testar sua capacidade classificar um array ou alguma estrutura de dados, mas é necessário para fazer o resto do seu problema. Você pode tentar usar esses tipos de função. E é um cenário em que você precisa de seus itens classificados, mas você não precisa realmente implementar todo o algoritmo sozinho. classificação é um dos dados mais básicos fornecidos pela função. Significa obviamente organizar os dados de uma forma específica, que pode estar aumentando ou diminuindo ou qualquer outra função de comparação que você possa usar, dependendo da estrutura de dados que você tem. Em ambientes mais complexos. Suponha que você tenha estruturas do tipo cat. Você quer encomendá-los pelo número de bigodes que eles têm. Você precisará implementar essa função de comparação específica. Você pode realmente passar o terceiro argumento para essa função. Veremos isso mais tarde. Ele irá classificá-los basicamente por bigodes numéricos. Existe uma função incorporada. Como já disse, o C plus plus STL vem da biblioteca padrão. Nome dessa função. Os interesses de usos internos estão em mais detalhes sobre cada implementação porque o entrevistador pode até mesmo SQ, como essas funções implementadas se ele perceber que você a usa. Bem, ele usa um híbrido de classificação rápida, tipo heap e tipo de inserção. Dependendo de alguns fatores. Por padrão, ele usa quicksort. E se a classificação rápida estiver fazendo particionamento injusto mais de n log n tempo? Ele muda para a classificação de heap. O tamanho da matriz se torna muito pequeno. Ele muda novamente para a classificação de inserção. Agora, se dermos uma olhada neste código aqui, podemos ver essa função aqui em ação. Você pode ver na função principal que analisamos unária que inicializamos a matriz codificada. Em seguida, obtivemos tamanho usando o tamanho dos operadores. Em seguida, usamos essa função aqui que leva dois iteradores. Então nós lhe demos ARR, que é o ponteiro do primeiro elemento da matriz. Em seguida, ARR mais n, que é o fim da matriz. Então ele o classifica. Para vê-lo em ação. Também o imprimimos na tela após classificação e, como você pode ver aqui , classificamos cada vez mais. Agora, como eu disse, seus parentes passaram dessa função de classificação, terceiro parâmetro de comparação que ordenaria os elementos de uma maneira diferente. Mostre isso a você. Vou manter essa função de classificação, parâmetro, função de comparação que classifica os elementos de forma decrescente. Isso se chama maior batida. Isso alterou nosso decrescente. Podemos, é claro, implementar sua própria função aqui que você pode escrever a si mesmo acima da função principal que usa dois parâmetros e retorna um booleano sobre se qualquer condição você quer reordenar é verdade. Este ano seria uma maneira muito interessante e fácil ignorar a classificação em uma entrevista. Como eu disse, se o entrevistador é essa dívida, curioso para ver se você pode realmente classificar o array sozinho ou S2 para um algoritmo de classificação específico. Além disso, dada a complexidade do tempo por sua implementação, é n vezes log de n. E essa é, na verdade, a melhor complexidade pela qual você pode solicitar um array. Agora, nas próximas palestras, vamos dar uma olhada em alguns algoritmos de classificação que são realmente implementados. A maneira como eles funcionam. Além disso, veremos suas complexidades. Veja algumas maneiras de classificar uma matriz ou outra estrutura de dados que você possa ter. 15. Bubblesort: Olá pessoal e bem-vindos de volta à palestra três. Nesta palestra, falaremos sobre o algoritmo mais básico que classifica uma matriz que você pode implementar por si mesmos com muita facilidade. É chamado de tipo de bolha. Ele não tem a melhor complexidade de tempo e espaço. Mas chegaremos a isso em um segundo. Primeiro de tudo, tenho que dizer sobre esse algoritmo, além do fato de que é o algoritmo de classificação mais simples existe, como ele funciona é trocando repetidamente os elementos adjacentes se eles estiverem errados ordem. Então, agora vamos ver este exemplo para que possamos visualizar melhor do que olhando para o código. Como é a forma como o algoritmo é realmente célula branca? Vamos levar o array 5142 para o que ele faz. Basicamente pagou os dois primeiros elementos. E vê que cinco é maior que um, então os troca. Então é preciso 545 também é maior que quatro, então ele os troca novamente. Em seguida, 525 é maior que dois, então eles os trocam. E no final temos 58. Estes são a posição correta, portanto, não faz nenhuma troca. Em seguida, ele passa novamente. Tomando elementos dois por dois, como já disse, elementos adjacentes, parafrasee-os se estiverem na ordem errada e, se estiverem, os trocam, se não, não acontece. Um em cada quatro está na ordem correta, então não vai trocar para ele ou não na ordem correta porque quatro é maior que dois, então vamos trocá-los. 45 estão na ordem correta e, em seguida, 58 estão na ordem correta. Mais uma vez. Você pode ver, neste momento, nossa matriz já está classificada, mas nosso algoritmo ainda não sabe se ele está completamente classificado, porque não poderia ter neste momento. Então, precisa de outra esperança é que ele não troque obviamente nenhum elemento porque eles já estão ou terceiro enviando. Mas, como você pode ver na terceira base, leva novamente os elementos Dubai, e não faz nenhuma troca. Agora, vamos dar uma olhada no código desse algoritmo. Como você pode ver na função principal, estamos declarando que geralmente é uma matriz codificada com alguns valores nela. Em seguida, declaramos um integral, e desta vez para comer o tamanho de nossa matriz que declaramos, fazendo uso novamente no tamanho do operador. E então estamos chamando a função de classificação de bolhas. Como você pode ver, é preciso dois parâmetros, nossa matriz, e agora está se movendo para cima na pilha. Você pode ver que ele entra na função de classificação de bolhas. Ele retorna um vazio porque apenas classifica a matriz e não retorna nada. Para o primeiro elemento pega a matriz nisso, eu disse, o segundo elemento é o tamanho dele. Agora vamos declarar dois elementos, eu e j. Theta. Só estou acostumado a iterar através da matriz. É assim. Consulta. Cada elemento da matriz, iremos novamente de 0 a n menos I menos um. Você pode ignorar porque ele é baseado em zero. Ele basicamente vai do primeiro elemento da teoria para o item n menos. E então ele verifica se ARR de j é maior que ARR de g mais um. O que significa que temos um elemento maior que está antes de um elemento menor. E não podemos ter esse SP1 nossa matriz em ordem crescente. Troque os endereços dos elementos localizados em, antes dos referidos índices. Exibição fazendo a mudança grávida. E quando voltamos para imprimir a teoria, você pode ver que quando executamos o programa imprime a matriz classificada cada vez mais com o fato de que o segundo loop no itera para n menos I. Há uma razão por trás disso. Porque os elementos da matriz depois de n menos eu já classifiquei. Porque se pensarmos nisso, primeiro, ele vai de 0 a n menos um. Então, o fim da teoria no segundo loop vai de 0 a n menos I menos um, que também é n menos um. Então ele vai até o fim. Ele mantém a chance de o último elemento estar na última posição. Em seguida, itere de 0 para o último elemento. E então o elemento da cadeia irá iterar nos dois n menos um menos I, que será um, isso é n menos dois. Portanto, excluindo o último elemento. Basicamente, ele pesquisará o segundo maior elemento da matriz e assim por diante. É assim que o algoritmo funciona. Continuamente trinta anos, onde o maior elemento para colocá-lo no final da teoria. No final, entendo que o final ainda não está classificado. A primeira iteração, procurará o maior e maior elemento. A segunda iteração para a segunda maior, e assim por diante, atinge o primeiro elemento na matriz já está classificada. Se falássemos sobre a complexidade de tempo e espaço desse algoritmo, a complexidade do espaço é linear em relação à entrada porque acabamos de declarar essa matriz aqui, e então declaramos duas variáveis, iterando três, mas que são consideradas constantes. Portanto, a complexidade do espaço é grande O de m e é linear. Agora, chegar à complexidade do tempo desse algoritmo é grande O de n para o poder de dois. Portanto, é uma complexidade de tempo quadrática à medida que o algoritmo itera para cada elemento da matriz. Outra iteração para basicamente não para todos os raios, mas você tem a ideia. Ele tende assintoticamente a uma complexidade quadrática. Agora, novamente, temos uma função de troca da qual eu nem falei. O que isso faz. Como você pode ver, ele não retorna nada necessário para integrar ponteiros e troca entre eles. Esse é um algoritmo de classificação muito rápido e simples que você pode usar em uma corrida que você queria classificar o inglês cada vez mais. Mas saiba que sua complexidade de tempo é quadrática e não o melhor tipo de complexidade de tempo que você pode ter ao classificar uma matriz, o que o BASF já disse n log n. Então, se nós propor implementar esse algoritmo agora que não é desta vez complexidade, como você pode ver na próxima palestra, existem melhores algoritmos de classificação por aí que você pode aprender e realmente implementar durante sua entrevista ao ser perguntado sobre isso. Mas é uma base. E este é um algoritmo bastante básico. É bom primeiro fazer contato com um algoritmo de classificação mais fácil para iniciá-lo. 16. : Pessoal, bem-vindos de volta à palestra quatro. Nesta palestra, falaremos sobre Quicksort. Quicksort é outro algoritmo de classificação que funciona em matrizes. E é um algoritmo mais eficiente, então, propor a classificação Do ponto de vista da complexidade do tempo e da complexidade do espaço. Agora, ao contrário de março, quicksort é um algoritmo de divisão e conquista. O que ele faz, é apenas um elemento grande e particiona a matriz dada em torno do pivô. Muitas versões diferentes do quicksort, esse grande pivô de maneiras diferentes seria sempre escolher o primeiro elemento é. Outra maneira seria sempre escolher o último elemento, esse pivô, como faremos em nossa implementação. Você verá isso em um segundo. Então você pode escolher um elemento aleatório é ponto. A melhor maneira seria escolher o SPM mediano dele. O quicksort de processamento de chaves é a partição. O destino da partição. Dada uma matriz e um elemento x do pivô da matriz. O que essa função de partição faz é que ela coloca x e sua posição correta em uma matriz, o que significa que todos os elementos menores que ficariam à esquerda. E todos os elementos maiores então estarão nele, certo? Neste processo deve levar apenas a complexidade do tempo linear. Nós olhamos para o código e tentamos entendê-lo. Veremos que, na função principal, declaramos uma matriz, pois sempre fazemos esses valores codificados. Em seguida, tomamos seu comprimento usando o tamanho do operador. E então chamamos uma função chamada quicksort que usa três parâmetros. O primeiro parâmetro é o array. O segundo parâmetro, pontos cor-de-rosa acima vinculado ao que você deseja classificar, no nosso caso, o primeiro índice de elemento, sendo 0. O último elemento, esse terceiro parâmetro, o limite superior que você queria classificar em nosso caso, o último índice de elemento e que é n menos um. Também declaramos algumas funções de transporte de oxigênio. Uma delas teoria de impressão. O segundo é trocar dois elementos usando ponteiros. Agora, se formos para a função QuickSort que é chamada a partir da função principal, veremos, em primeiro lugar, verificaremos se o baixo é menor do que isso é feito porque depois iremos chame recursivamente essa função nos subarrays esquerdo e direito do pivô. Portanto, sempre precisamos manter isso em cheque se o limite inferior é menor que o vínculo mais alto. Em seguida, vamos dar o valor da perdição da nossa matriz. E os limites inferior e superior são o índice de particionamento. Ou seja, onde está nosso pivô na posição correta na matriz que seria classificada. Neste depoimento que acabamos de falar. A posição onde todos os elementos à sua esquerda e menores que ele, e todos os elementos nele são maiores que ele. Não importa qual é a ordem deles porque a matriz foi classificada ou não. Isso não importa. Esse elemento está na posição da faixa onde essa condição acontece. E então chamaremos recursivamente essa função de nossa matriz, a posição de limite baixo e pivô menos um. E então nosso índice de pivô de matriz mais um e, em seguida, limite superior, o que significa que chamaremos recursivamente quicksort para o sub-array esquerdo e o subarray direito do pivô que está corretamente posicionado neste ponto. Vamos ver o que essa função de partição faz. Ele também usa três parâmetros como a função QuickSort faz. Declaramos um pivô. Integral leva o último elemento porque, como eu disse, implementaremos a variação do QuickSort onde o pivô é tomado como o último elemento da matriz. Então vamos declarar eu, que seria o menos um, menos um, porque o primeiro elemento da nossa matriz seria 00 menos um é menos um. Vamos ver em um pouco por que tomamos menos um e não 0. E então usaremos outra integral para iterar toda a matriz. Iterando por toda a matriz. Dizemos que se ARR de g, ou seja, o elemento atual da iteração, é menor que o pivô. Primeiro vamos incrementar I, então vamos trocar ARR de I de j. Então vamos mover esses corantes, iteração linear através da matriz. E 28, estamos encontrando um item menor que o nosso pivô. Nesse caso, o último elemento do sub-array que estamos nele, vamos colocá-lo no início da matriz. No começo, bem, primeiro índice que ainda não está ocupado. Ele coloca todos os elementos menores que o nosso pivô na frente da matriz. Então, por último, vamos trocar ARR de I mais um com o nosso pivô. Porque esse é o lugar certo na matriz. É aí que seria errado se a matriz fosse classificada, simplesmente retornaremos esse índice, que seria o índice correto. Agora, você pode ver que entendemos como a função de partição funciona. E também entendemos que depois do frio, também chamamos recursivamente essa função de partição no submotivo esquerdo e direito para girar. Dessa forma, classificando a matriz. Agora, como você pode ver, temos uma matriz de elementos, em seguida, 789, Um e cinco. Quando o executamos. A função PrintArray deve imprimir nossa matriz. Isso, você pode ver esses dados de classificação. Agora vamos falar um pouco sobre esses algoritmos. Os respeitos de estabilidade não estão em vigor. Propriedade. Primeiro de tudo, o Quicksort é estável? A implementação padrão não é estável. No entanto, qualquer algoritmo de classificação pode ser estável considerando índices como parâmetro de comparação. Em segundo lugar, especialista, a ampla definição de algoritmo no local. Quicksort se qualifica como um algoritmo de classificação de funcionários. C2c é espaço extra apenas para armazenar chamadas de função recursivas, mas não para manipular a entrada. Podemos dizer que ele tem complexidade espacial linear. Vamos falar sobre a complexidade do tempo para realmente ver o quão eficiente esse algoritmo é. Bem, mesmo que seja melhor do que o tipo de bolha, o que, no melhor tempo, a complexidade seria linear. Mas na média e nos piores casos seria quadrático, seria grande O de n para o poder de dois. Padrão de classificação rápida na complexidade do tempo médio, vários n log n. A complexidade da máscara ainda é n log n, mas a pior complexidade ainda é quadrática. N ao poder de dois. Em entrevistas, o nome realmente pergunta algo sobre semanas. Se não for a implementação completa. Você pode perguntar se você sabe qual é a complexidade do tempo, se você sabe como a função de partição funciona e qual é a complexidade do tempo. que, a propósito, é linear. Como já vimos. Nós apenas iteramos através da matriz. E ele pode até SQ as chamadas recursivas na função de classificação rápida onde é um algoritmo de classificação muito bom em uma entrevista. E é uma ferramenta muito útil que você pode usar para classificar os elementos de uma matriz que você tem. Quando você não tem a função de classificação STL, tipo de bolha, tipo de bolha. Se você quiser algo mais eficiente, esse algoritmo seria uma combinação perfeita. 17. Árvores: Olá pessoal e bem-vindos de volta à seção seis deste curso. Nesta seção, falaremos sobre a nova estrutura de dados chamada três. E, ao contrário de matrizes, listas vinculadas, pilhas e filas, que são estruturas de dados lineares, as árvores são estruturas de dados hierárquicas. O nó superior é chamado de raiz da árvore. Os elementos que estão diretamente sob um elemento são chamados de filhos. elemento D diretamente acima de algo é chamado de pai. Por exemplo, um é filho de f e f é pai de uma dívida nesta árvore que desenhamos na tela, certo? Finalmente, elementos sem filhos são chamados de folhas. Agora vamos falar sobre por que usaríamos árvores? Bem, uma razão seria porque você foi armazenar informações que naturalmente herança de farmácia. Pense em como seus arquivos são organizados no seu livro para PC ou Mac, o que quer que você tenha, o início da pasta raiz e, em seguida, você passa por eles em uma ordem de artigo. Sistema rápido no computador. Eles provavelmente implementaram usando árvores. Além disso, as árvores fornecem eixo moderado e pesquisa. Essa é a lista vinculada à cortina, mas mais lenta que as matrizes. A árvore também fornece inserção e exclusão moderadas. Mais rápido que os arrays, mas listas vinculadas mais lentas, mais finas e não ordenadas. Lista também provável. E, ao contrário das matrizes, as árvores não têm um limite superior no número de nós. Os nós são vinculados usando ponteiros. Portanto, há uma vantagem quando olhamos para esta página que uma árvore e você pode armazenar. As principais aplicações das árvores incluem manipular dados de hierarquia TO, facilitando a pesquisa das informações . Veremos que ele atravessa, em uma das próximas palestras. Manipule dados de listas classificadas. Eles podem ser usados como um fluxo de trabalho para compor imagens digitais, para efeitos visuais, algoritmos de roteador. E também a tomada de decisão em vários estágios do agricultor, por exemplo, xadrez empresarial. Do ponto de vista da implementação, a árvore é representada por um ponteiro para o nó mais alto da árvore. A árvore está vazia, então o valor desse nó superior chamado raiz é conhecido. Um nó de árvore contém as seguintes partes. Primeiro de tudo, ele contém dados, depois contém ponteiros para seus filhos. Podemos representar três nós usando estruturas. Por exemplo, estou preso aqui. Você pode ver exatamente o que estou falando. Mas passaremos para a implementação em C plus, além disso pouco mais tarde. Agora vamos falar um pouco mais sobre quais tipos de árvores existem na programação. Como eu disse, três em ciência da computação é como no mundo real. A única diferença é que na ciência da computação é visualizar isso de cabeça para baixo com raiz no topo e prevenir doenças originadas da raiz para as folhas da árvore. estrutura de dados em árvore é uma estrutura de dados não linear. Uma árvore pode ser representada usando vários tipos de dados primitivos ou definidos pelo usuário. Como vimos com o descarregador agora. Implementado três, também podemos fazer uso de matrizes, listas vinculadas, óculos ou em outros tipos de estruturas de dados. É uma coleção de nós que estão relacionados entre si para mostrar que os nós de relação estão conectados com bordas. Mas na prática, mais como ponteiros pesados um para o outro. Os tipos de árvores em estruturas de dados. Em primeiro lugar, existe a árvore geral, que não há restrição para ela, imposta a ela, no ar manteve a árvore. Em geral, cada nó pode ter um número infinito de filhos. Esses três são o superconjunto de todos os outros tipos de árvores. Agora, vamos passar para árvores binárias que são muito mais úteis em março, mais sobre perguntas de entrevista só porque elas têm uma estrutura mais simples e elegante e são mais fáceis de formar perguntas com base em. As árvores binárias são o tipo de árvore em que cada pai pode ter no máximo dois filhos. As crianças são referidas como o gráfico f ou uma criança certa. Ntc é uma das árvores mais usadas em certas restrições e propriedades são impostas às árvores binárias. Isso resulta em uma série de outras pesquisas binárias amplamente usadas na árvore G AVL. Então por diante. Vamos falar sobre esses tipos de árvores agora. Portanto, a árvore de pesquisa binária é uma extensão da árvore binária qual acabamos de falar, mas tem outras restrições de edição. Por exemplo, o valor dos filhos esquerdos de um nó deve ser menor ou igual ao valor de seu pai. E o valor do canal certo é sempre maior ou igual ao valor de seu pai. Esta propriedade das árvores de busca binária faz com que seja adequada para a operação de busca. Intenso. Como cada nó, podemos decidir com precisão se o valor estará na saída para seus direitos. Portanto, é chamado Search Tree. tipo de árvore mais complexo é a árvore AVL. Que estes são árvore de pesquisa binária de equilíbrio automático. O nome AVL é dado no nome de seus estoques. filho adulto se sentiu tímido. Então esta é a primeira árvore dinamicamente equilibrada que já foi implementada na árvore APR. Cada nó recebe um fator de balanceamento com base no qual é calculado se a árvore está balanceada ou não. Se você tem árvore, a altura dos filhos do nó difere em, no máximo, uma. O fator de equilíbrio válido se as artérias forem 10 n menos um. Quando o novo nó é 80 para a árvore AVL, entrada fica desequilibrada e, em seguida, rotação é feita para garantir que a árvore permaneça equilibrada. As operações comuns, como a intuição de inserção de pesquisa, levam apenas um grande tempo logarítmico nessas árvores AVL e são amplamente usadas para operações de pesquisa. Também existem algumas árvores que são chamadas de árvores NRV. O número máximo de filhos eles podem ter aqui é limitado a essa variável n. Árvore binária é uma árvore, como você denota na estrutura de dados de árvore mais dois filhos binária de hoje, você encontra que o mais comum usado na apresentação de n. Mas árvores NRA cheias, cujos filhos de um nó é 0 ou completo enter retiro é a árvore na qual todos os padrões estão no mesmo nível. Para algumas propriedades de árvores binárias. Mais algumas propriedades matemáticas. Podemos dizer que o número máximo de nós no nível l de uma árvore binária é dois para o poder de l. Então, novamente, a partir de sua construção, o número máximo de nós na árvore binária de altura h mais dois ao poder de h menos um. Na árvore binária com n nós, altura mínima possível ou número mínimo de logaritmo Cs da base dois de n mais um. Vamos fazer uma árvore binária com LDFs tem pelo menos dois l mais uma variáveis. Também na árvore binária onde cada nó tem dois filhos, o número de nós de folha é sempre um a mais do que nós com dois filhos. Esta é uma visão geral ampla sobre a estrutura de dados em árvore. Eles são muito úteis em perguntas de entrevista. É o tópico mais complexo para discutir aqui. Muitas pessoas que conheço , incluindo eu mesmo no melhor, não eram tão curtas em árvores. Mas neste curso, analisaremos alguns exercícios com eles, traversals e assim por diante para fazer você se sentir mais pronto para sua entrevista de codificação. Especialmente nessas estruturas de dados. Então dois problemas fazem pessoas, pessoas que foram entrevistadas no passado. Então, vamos passar para a próxima palestra agora. 18. Traversals: DFS, BFS: Olá pessoal. Nesta segunda palestra, falaremos sobre traversais de árvores, mais especificamente, traversals de árvores binárias. Como você já viu. Ao contrário das estruturas de dados lineares que são matrizes, listas vinculadas, filas , pilhas, etc., que têm apenas uma maneira lógica de atravessá-las. As árvores podem ser atravessadas de maneiras diferentes. seguir estão os geralmente usados para atravessar as árvores. Vamos falar sobre profundidade primeiro traversal, esta palestra, que está em ordem, o que significa primeiro vamos para a esquerda, anotamos, depois a raiz e depois para o nó direito. Pré-venda, que é primeiro visitamos a raiz, depois a criança esquerda e a criança direita. Digamos que tenhamos pós-ordem, o que significa que primeiro vamos para a esquerda, depois vamos para a direita e, por último, vamos para a raiz. Há também ESA, travessia de primeira largura ou passagem de ordem de nível, que basicamente leva, imprime a nota na ordem de seus níveis, de suas camadas. O algoritmo de travessia em ordem seria atravessar a subárvore esquerda primeiro e, em seguida, chamar em ordem para a subárvore esquerda. Em seguida, visite o tendão da raiz, atravesse a subárvore direita e, em seguida, ligue para a subárvore direita. Na primeira ordem, novamente foi a primeira vez que visitamos a criança esquerda e a criança direita. Usos de em ordem. No caso de árvores de busca binária. Em ordem, a travessia fornece nós em ordem não decrescente. Para obter nós de uma árvore de pesquisa binária quarto de variação não crescente da passagem em ordem. travessia em ordem pode ser facilmente usada. A passagem de pré-venda é bastante semelhante à em ordem, exceto a maneira como fazemos as coisas. Então, primeiro visitávamos a extremidade da raiz em direção à subárvore esquerda e chamamos a pré-ordem dos lábios. Leslie, vamos atravessar a subárvore certa. Pré-venda. A travessia de pós-ordem seria primeiro atravessar a subárvore esquerda, chamar a pós-ordem da subárvore esquerda, depois reverter a subárvore direita e chamar a pós-ordem dela. E assim, visitaríamos a raiz. Você vê que alguma passagem de pré-venda seria criar uma cópia da árvore. Ele também é usado para obter expressão de prefixo em uma árvore de expressões. passagem pós-ordem seria usada para excluir uma árvore, também seria usada para obter a expressão postfix de um tratamento de expressão. Se agora olhássemos o código que faria essa primeira travessia em profundidade. primeira coisa, a função principal, declararemos a raiz, anotaremos isso usando uma estrutura chamada nó, e nós a declaramos para cima. Temos um host integrado os dados e , em seguida, dois ponteiros para a nota de tipo que é filho esquerdo e direito. E também um construtor que pega dados de teste integrais e inicializa os filhos desses nós para saber. Então, diríamos que vazou ou não definitivamente, mas apenas para anotar, sem crianças. Primeiro, declaramos uma raiz e depois damos à esquerda. E você sabe, se duas notas de taxa de bits de três, são apenas falhas, o que significa que não há duas falhas. E então à esquerda, à esquerda, temos um nó com o valor flúor, embora eles tenham tentado ser um notado o valor de cinco. Aqui é assim que nossa árvore ficaria. E então chamamos de pré-venda , em ordem e pós-ordem dessas funções leva um argumento, que é o nó raiz, por exemplo, com a pós-ordem. Observe que não sei, obviamente, chamaremos recursivamente as crianças esquerdas, depois para as crianças certas e, em seguida, imprimiremos os dados. Então, o que isso faria é que ele chamará recursivamente à esquerda até chegar à folha. Então ele retornará da recursão e o levará direito. Então, finalmente, algum valor raiz. Em seguida, você também tem a pré-venda em ordem já definida. Apenas a diferença, apenas uma diferença na sucessão dessas instruções existe. Em ordem. Novamente, verifique se o nó não é nulo porque se isso significa que você já terminou a árvore ou não há filhos lá. Em seguida, chamamos recursivamente a função para o nó esquerdo. Em seguida, imprimiremos e, em seguida, pediremos recursivamente o direito. A pré-venda. Obviamente. Nós verificamos novamente, precisamos conhecer esses nano. Primeiro, imprimimos e, em seguida, chamamos recursivamente à esquerda. E então, por falar sobre a complexidade desses algoritmos, bem, venha ao palco. todos os problemas são, na verdade, o volt agradável do lado do servidor porque basicamente iterar. Nota. E o espaço auxiliar, se você não considerar o tamanho de um estado para chamadas de função, então é constante, nós vamos um. Caso contrário, seria linear grande O de n. Agora vamos falar sobre a passagem de árvore binária de alteração de nível, que é a primeira travessia da largura. Portanto, existem métodos diferentes. Falaremos sobre o método que usa uma função para imprimir um determinado nível. Novamente, em grande parte tentado fazer aqui é imprimir o número de nós na ordem de nível da esquerda para a direita nos níveis. Por exemplo, para a última árvore que vimos, a passagem da ordem de nível para ela seria 12345. O algoritmo aqui seria implementar duas funções. Uma é imprimir todos os nós em um determinado nível, então damos a eles uma maçã. A outra função é imprimir a passagem da ordem do nível da árvore. ordem de nível faz com que a impressão mantenha os níveis para imprimir notas em todos os níveis um a um a partir da raiz, nós faríamos é a primeira ordem de nível de impressão de três. Vá de uma altura da árvore e imprima esse nível. Itere todos os níveis e chame o nível de impressão dado. Permita que você pegue dois argumentos, a árvore e esse nível, e imprima. A função de impressão, imprimir determinado nível. Verificamos se a árvore é conhecida, então ela retornaria. Se o nível fosse um, então traria para o mundo. E chamaria recursivamente o nível da árvore direita e esquerda com o nível menos um. Como você pode ver aqui, fizemos a função para criar uma nova função de nó que retornaria a altura da árvore. As duas funções sobre as quais falamos. Como eu disse, a função de ordem de nível de impressão leva o argumento, a raiz. Em seguida, calcularemos com o método de altura a altura da árvore. Iterar em toda a altura e lidar com o nível de raiz I, que é o número do nível em que estamos atualmente. E o nível rosa dado é uma função que toma o nível e a nota verifica se a raiz é nula. Se for, ele retornará. Se o nível for um, ele imprimirá o nó raiz. Porque se estivermos no primeiro nível, significa que estamos nas raízes, simplesmente imprimiríamos chamando recursivamente qualquer coisa. Mas se estivermos em um nível mais baixo, não sou o nível raiz, mas downloads, chamaremos recursivamente essa função para a esquerda e para a direita. Observe com o nível menos um. Daí o segundo parâmetro. Então eu acho que isso é bem simples. Novamente, você pode ver para a árvore que mostramos na tela, a passagem da ordem de nível é 12345 é que já descobrimos. Mais uma vez aqui. complexidade desse algoritmo é linear. Aqui diz respeito à complexidade do tempo grande O de n, medida que iteramos através de todos os nós uma vez recursivamente, DC é praticamente a maneira como você pode atravessar a árvore de pesquisa binária. E eles são muito úteis para saber porque eles lhe darão mais morbidade em uma árvore. E eles vão se certificar de suas vendas ao lidar com três perguntas em uma entrevista de codificação. Então, agora vamos passar para o próximo vetor. 19. Confira se a propriedade de soma de crianças: Olá pessoal e bem-vindos de volta a este curso. Nesta palestra, falaremos sobre os três problemas que às vezes podem aparecer em uma pergunta de entrevista. Isso é para verificar para crianças alguma propriedade na árvore binária. O que isso significa é que, dada uma árvore binária, você deve escrever uma função que retorne true se a árvore satisfizer a propriedade que, para cada nó, valor de dados deve ser igual à soma do theta usará à esquerda e crianças certas. Considere o valor dos dados é 0. Por enquanto, crianças. Por exemplo. Se tivéssemos uma árvore que tivesse a raiz, então as crianças esquerdas seriam oito e as crianças certas seriam duas. Isso seria uma árvore válida. E assim por diante abaixo, se essa criança precisar ter dois filhos, então a mão esquerda tente pelo menos que seus dados em alguns sejam iguais a oito, e assim por diante para toda a árvore. O algoritmo que somos, vamos nos aproximar aqui é atravessar a árvore binária dada. E para cada nó, devemos verificar recursivamente se o nó, em seguida, ambas as crianças disseram ser por das crianças alguma propriedade. Se assim for, então true else retorna false. Isso é bem simples. Não vamos entrar no código e ver como podemos fazer isso em um nível técnico mais específico. Tudo bem, aqui já declaramos algumas coisas que nos ajudariam com a implementação da árvore. Então, declaramos uma estrutura que é nó. E então declaramos que uma árvore inteira é alguma propriedade da raiz dois. Em seguida, imprimiremos que a condição está satisfeita, caso contrário falsa. Então, basicamente, vamos implementar uma função chamada East algumas propriedades. Ele pega o parâmetro o nó raiz e retorna um inteiro, que pode muito bem ter sido um booleano, é a mesma coisa porque se você retornar 0 ou um, então pulando para esta função, declaramos duas variáveis auxiliares que nos ajudarão a lembrar os valores direito e esquerdo dos filhos do nó que estamos no presente com a iteração. Então, se o nó que somos honestos ou seus filhos ou não, então retornaremos um. Porque isso significa que chegamos ao fim e está tudo bem, porque tudo saiu para ser verdade até esse ponto. Caso contrário, você também verá que a maioria desses algoritmos começa com o caso base desses algoritmos de árvore. Primeiro, nosso recursivo e segundo, comece com o caso base, ou seja, o caso final. Bem, temos vários cenários aqui. Se o nó esquerdo não for nulo, então os dados nele, então o número que ele contém será dado à integral beta esquerda que declaramos aqui. Então, novamente, para o nó certo, faremos a mesma coisa. E então verificaremos se os dados do nó, então o número que o nó que estamos agora com a iteração é igual à soma dos filhos esquerdo e direito. E também chamado recursivamente a mesma função para o nó esquerdo e o nó direito. Verificaremos recursivamente a mesma coisa para ambos os filhos do nó. Então vamos devolver um, o que significa que é verdade. E nossos três 0s, com esta condição que estamos verificando, senão retornaremos 0. Então, o que isso faz é chamar recursivamente usando a pilha de custos. E quando ele retornará da pilha de chamadas, ele atingirá esta. Se todas as propriedades do ECM retornarem true, como você pode ver aqui com as instruções end, todas elas precisam ser verdadeiras para que essa instrução if faça check-out e retorne uma. É assim que verificaremos essa condição em toda a árvore com uma função recursiva. Agora, falando sobre a complexidade desse algoritmo, como você verá em quase todos os algoritmos de árvore. Linear do ponto de vista temporal e constante deste ponto de vista base maneiras que declaramos apenas duas integrais. Mas, do ponto de vista, itere por toda a árvore. Então isso é linear grande O de n. Obrigado por seguirem ao final comigo neste tutorial e eu os verei no próximo. 20. Suma de todos os nós: Olá pessoal e bem-vindos de volta a este curso. Nesta palestra, falaremos sobre outro problema de árvore. Vamos dar-lhes às vezes no cálculo da soma de todos os nós em uma árvore binária. Acho que o título é bastante autoexplicativo. O que você precisaria fazer quando dado esse problema é fornecer um algoritmo para encontrar a soma de todos os elementos na árvore binária. Basicamente, você precisa resumir todas as integrais que são mantidas por todos os nós em uma árvore binária que é dada a você. Como de costume, abordaremos esse algoritmo com recursão como costumamos fazer em três problemas. Vejamos o código para ver como faríamos esse problema. Nós declaramos um struct. Note que o mantém indutor é a chave e também a esquerda e direita do nó que são mantidas. Dando-lhes um ponteiro para a estrutura do nó. Nós desenhamos uma árvore aqui. E então nós declaramos por algum integral e atribuímos a ela nossa chamada de função que deveria retornar a integral. Essa integral sendo a soma de todos os nós na árvore dada, parâmetro T somente que esta função toma é o nó raiz da nossa árvore. Ponteiro para o nó. Obviamente. É como se a raiz fosse nula, então devemos retornar 0. Como de costume em três algoritmos e métodos de recursão, começamos com o caso base, ou seja, o que acontece quando a parte inferior chama esse calor? Quando a raiz é não, chegamos ao fim. Portanto, não há mais nota porque chamamos recursivamente essa função até ficarmos sem nós. Se esse não for o caso. Portanto, se não chegarmos a uma rota, devemos retornar a chave raiz, ou seja, o valor que a raiz está mantendo dentro do porque você pode ver a estrutura, a chave é a integrada que o nó mantém. Também adicionamos o curso recursivo dessa função para o filho esquerdo e direito da raiz, ou seja, a nota de que estamos nela. A chamada atual, é claro, recursiva do prato será chamada para as crianças esquerdas. E, novamente, a execução foi iniciada sem retorno. 0 IS retorna seu valor e , novamente, ligue recursivamente para cada um deles. Acho que você entendeu como isso acontece. Agora estamos falando sobre a complexidade dessa linha pegada. Bem, a complexidade do tempo é linear à medida que iteramos em toda a árvore é bastante intuitiva que precisamos iterar através de cada nó para que possamos descobrir qual valor ela nos mantém fiel a nós mesmos. E então a complexidade do espaço é constante, pois não declaramos nenhum elemento além dos padrões de Carsten vendidos, mas é grande O de um. Obrigado pessoal, e nos veremos na próxima palestra. 21. Verifique se todos os nós de folhas são no mesmo nível: Olá pessoal e bem-vindos de volta a este curso. Nesta palestra, falaremos sobre mais três problemas que podem ser dados em um ambiente de entrevista. Isso é para verificar se todas as folhas estão no mesmo nível em uma árvore. Neste problema, pedimos que você faça é dada uma árvore binária, você só precisa verificar se todos os nós de folhas, ou seja, os nós que não têm filhos. Então, aqueles que estão no nível inferior, no mesmo nível ou não, basicamente imaginam que a raiz esteja no nível um, crianças imediatas no nível dois, e assim por diante. Até você encontrar o nível da folha, ele tem de costume, abordaremos esse algoritmo usando recursão. Agora, a ideia é primeiro encontrar nível da folha mais à esquerda e armazená-la em uma variável. E usaremos essa variável. Em seguida, compare o nível de todas as outras folhas com o nível da dívida. Se for o mesmo, retornaremos ao fim caso contrário falso. Nós atravessamos a árvore binária dada de uma forma de pré-venda. O nível que temos em mente, seremos melhores para todas as chamadas como argumento. O valor desse argumento é inicializado com 0 em outra função para indicar que, primeiro lugar, se ele ainda não foi visto, o valor está no plano. Primeiro, encontrar uma folha ou nível de folhas subsequentes em pré-venda é comparado com esse argumento de nível. Agora vamos dar uma olhada no código. Declaramos a estrutura do nó e o construtor para ela. E na função principal, construiu três para nós. E então temos uma função chamada check que toma a raiz da nossa árvore. E o que ele faz é que ele inicializa o nível na folha com 0 e retorna o código para esta verificação, uma função que toma como parâmetros a raiz da nossa árvore, depois o nível e o nível da folha que são ambos inicializados com 0. Como você pode ver nesta função de verificação até. O caso base é quando temos uma raiz, isso é agora. E então devemos retornar verdadeiros. Então os filhos do nó que somos agora são nulos. Isso significa que chegamos a um nó de folha. E então verificamos se é a primeira vez que chegamos ao nó da folha. Como fazemos isso é verificando se o nível da folha é 0, como você pode ver aqui, ele passou por referência, então o valor dele permanece. Aquele quando chamamos o nível da folha é 0. Isso significa que é a primeira vez que encontramos uma folha, atribuímos a esse nível de folha, o nível em que estamos agora. Além disso, se não inserirmos esta instrução if, retornaremos o nível igual ao nível da folha. O que isso significa é que estamos bem na folha. O que é agora o Primeiro, se estivermos certos de que devemos retornar se o nível é igual ao nível da folha. O nível da folha é o nível real da primeira folha em que chegamos. Todas as nossas folhas precisam estar no mesmo nível. É por isso que temos em mente essa variável aqui. Em seguida, saindo desta instrução if, ou seja, se não for uma folha em que estamos, agora, retornamos chamadas recursivas dessa função para o nó esquerdo e direito. Porque estamos agora no nó que não é uma folha e Xist, o que significa que estamos em um nó pai. Precisamos chamar recursivamente essa função para ambas as crianças e incrementa o nível. Além disso, embora tenha em mente o nível da folha, é o nível mais baixo da primeira folha que já encontramos. Como já disse, vou enfatizar isso. Mais uma vez. Lembramos dessa dívida em nível foliar, o nível da primeira folha que encontramos. E esta é a referência que vamos verificar. Além disso, as próximas folhas de inode que encontraremos para a complexidade deste algoritmo. Novamente, a complexidade do espaço é constante. Isso não usamos nenhum espaço adicional maior de um. E então a complexidade do tempo é linear. À medida que atravessamos a árvore inteira para encontrar em primeiro lugar, o nível da primeira folha e em seguida, verificamos todas as outras folhas para ter o mesmo nível na primeira folha que encontramos. Obrigado por assistirem a este tutorial e verei vocês na próxima seção. 22. O problema de coletes equilibrados: Olá pessoal e bem-vindos de volta a este curso. Nesta palestra, falaremos sobre o problema que muitas vezes é dado em uma pergunta de entrevista. Isso é para verificar se há colchetes balanceados em uma expressão usando uma pilha. Bem, isso é feito usando uma pilha, mas o entrevistador pode realmente não lidar. Você faz esse problema usando isso tirado hoje à noite, descobri isso por si mesmo. O problema lhe dá uma string. Essa é uma expressão, e você precisa escrever um programa para examinar se os pares e as ordens dos colchetes, corretos nessa expressão, os parênteses podem estar atualmente normais ou ao quadrado. Por exemplo, vou colocar na tela agora duas entradas diferentes. Então você pode ver que o primeiro está equilibrado e o segundo não é. Você não pode fechar o colchete antes de fechar o normal porque não há a ordem natural. Qual seria o algoritmo para nos declarar deck que contém caracteres e depois atravessar a expressão que você recebe essa string, basicamente iterar através dela. Em dendrite dois cenários. Primeiro, se o caractere atual que você está iterando naquele momento for o colchete inicial, Inicie o colchete normal, iniciando colchete encaracolado ou o suporte quadrado inicial, então você pode empurrá-lo para este deck. O segundo cenário é se o colchete atual em que você está atualmente com iteração for um colchete de fechamento. uma vez, fechando os suportes normais, fechando o suporte quadrado, fechando o suporte encaracolado. Em seguida, saia deste baralho. Agora você está bombeando o elemento superior e verá qual é o último suporte aberto. E se o caractere pop, então o último colchete aberto é o colchete inicial correspondente, então está tudo bem. Os suportes não estão balanceados. Então, após a travessia completa, se houver algum suporte inicial deixando este deck, então ele não é balanceado porque em nossa string existem colchetes abertos que eu não estive perto do final do expressão. Vejamos os códigos rapidamente. Temos uma função principal e a leitura exercemos uma expressão que vai como começar a cinta encaracolada, iniciar a cinta encaracolada, iniciar a cinta normal, acabar com a cinta normal e a cinta encaracolada. Então, está tudo bem. Em seguida, iniciando o suporte quadrado, terminando o suporte quadrado. Essa deve ser uma expressão equilibrada porque não há colchetes deixados e abertos ou fechados na ordem errada. Agora temos uma função chamada, declaramos a função chamada nossos colchetes balanceada que vamos ver que tem um parâmetro, essa string. Declaramos uma pilha, pois já explicamos por que isso contém o tipo de data char. Em seguida, declaramos um gráfico auxiliar chamado X. Para int i de 0 ao comprimento da expressão. Nós iteramos basicamente com esse loop através de cada caractere da expressão que é dada. Pegamos cada caractere um por um e verificamos que tipo de colchete esses. Primeiro, precisamos ver se esse colchete está atualmente ao quadrado, é normal e está começando no tipo um. Se for, podemos empurrá-lo em nossa pilha e, em seguida, continuamos, pois não precisamos avançar com o resto da execução do loop. Caso contrário, se não for o suporte inicial, podemos verificar se a pilha está vazia. E se a pilha estiver vazia, devemos retornar false. Porque isso significa que é um suporte de fechamento. É que não pode ser suporte inicial porque se tivesse sido, a execução não estaria aqui, agora. É um suporte de fechamento e a pilha está vazia. O que isso significa? Isso significa que chegamos a um suporte de fechamento que não tem suporte inicial correspondente antes dele. Portanto, não é uma expressão válida de parênteses. Se esse não for o caso, temos uma instrução switch baseada no personagem que estamos agora em nossa expressão. Então, temos casos diferentes. O caso quando nosso personagem é um colchete normal de fechamento, nós vamos. Em nosso caractere auxiliar x, o topo da pilha. E então vamos estourar o topo da pilha, pois não precisamos mais dela. E então vamos verificar o valor que estava nele. Se o valor que foi visto, era um colchete encaracolado inicial ou um suporte quadrado inicial. Em seguida, devemos retornar false quando chegamos a um colchete normal final e listar um que estava aberto, então o colchete correspondente não era do mesmo tipo que os EDs. E então devemos quebrar. Nos outros casos, se for um colchete encaracolado que está terminando e, em seguida, o suporte de correspondência inicial está OK. Os outros dois tipos, não está tudo bem, então devemos retornar false. Então, novamente, se for um colchete quadrado final e seu parêntese correspondente for normal ou encaracolado. Novamente, não é uma expressão válida, então devemos retornar false e depois quebrar. O mesmo procedimento também se aplica, onde colocamos em nosso personagem auxiliar o topo da pilha, e depois o colocamos. Quando terminarmos a iteração, nossa pilha deve estar vazia. Portanto, não deve haver nenhum parêntese aberto, porque isso significa que eles não têm nenhum parêntese final correspondente. Se a pilha estiver esvaziada significa que todos os mercados corresponderam. E a expressão é válida. Se a string não estiver vazia no final da execução, isso significa que existem alguns elementos nela. E como você já viu, nós apenas empurramos os tipos iniciais de suportes. E isso significa que nele são deixados colchetes iniciais que não têm colchetes finais correspondentes. E isso significa que não é uma expressão válida. Portanto, essa função é chamada em uma instrução if. Então, se esta função aqui, o que significa que esta função está retornando verdadeira, podemos retornar que a expressão que nos é dada é uma expressão equilibrada. Caso contrário, não é equilibrado. Então, como você pode ver, amostra de conhecimento, se executarmos o código, você pode ver que ele diz equilibrado, então é uma expressão equilibrada. Agora vamos falar sobre a complexidade desse algoritmo. A complexidade desse algoritmo do ponto de vista temporal, este linear à medida que iteramos através de nossa expressão uma vez. Então isso é grande O de n. Agora, a complexidade do espaço também é linear, pois declaramos uma pilha que pode conter tanto quanto toda a string. Na pior das hipóteses, em que a string contém entre colchetes iniciais. Você pode fazer isso de uma maneira mais eficiente, na qual nem se lembra desse deck. E em vez desse baralho, você pode se lembrar de alguns números. Por exemplo, algumas variáveis que você incrementa quando você encontra um colchete inicial e diminuem quando você encontra um colchete final. Essa é uma solução mais avançada. Você pode tentar em casa ou procurar por ele. Mas a solução básica para esses problemas, este e este que você realmente deve entender e conhecer de cor. Mas obrigado por continuar com este tutorial até o fim. Vejo você na próxima vez.