BastterCode semana 7 - Longest Common Prefix
comentada em 01/03/2023 20:16

Ver mais

Dart

@Giovanni,

Acho que esta semana é a 7, no título saiu 6.

Bacana a ideia do github. Por mim aprovado.

@Oxe,

Se quiser desafios matemáticos, lembrei deste post sobre o projeto Euler:
Desafios matemática + programação - Tecnologia - Bastter.com
Código da semana abaixo:

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        
        // finds the length of the shortest word in strs
        var shortestLen: Int = 200 // 200 is maximum, given by problem
        strs.forEach{
            if (it.length < shortestLen) shortestLen = it.length
        }

        var output: String = "" // output string, starts empty

        // 1st loop, for every char
        for (charPosition in 0 until shortestLen){
            var auxChar: Char = strs[0][charPosition] // char for comparison, taken from 1st word
         
        // 2nd loop, for every word in strs
            for (word in strs){
                if (word[charPosition] != auxChar) return output
            }
            output += auxChar // if true adds char to the output
        }
        return output
    }
}

@Rod100

Cara, muito legal! Pura felicidade isso daí. Valeu pela dica!

@Giovanni

Duas perguntas. Primeiro, o que é github?

E segundo, eu vejo a galera postando código usando a ferramenta daqui do site, mas lá não tem a opção de C++ como linguagem. Dá algum problema usar a ferramenta mesmo assim?

@Giovanni

Valeu!

Segue minha solução com comentários bem explicadinhos. 

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) //input é um vetor de palavras
{
        int count = 0, size = strs.size(), word_index = count/size;

//se interpretarmos o vetor de palavras como uma matriz, as palavras seriam as linhas da
//matriz. Como os índices começam no 0, então strs[0][0] seria a 1° letra da 1° palavra, 
//strs[0][2] seria a 3° letra da 1° palavra e strs[2][0] seria a 1° letra da 3° palavra. 

//O algoritmo vai percorrer as letras das palavras pela ordem das letras, ou seja, olha
//a primeira letra em todas as palavras, depois a segunda letra, etc. Ele faz isso até
//achar uma inconsistência. 

//A inconsistência pode ser: 1- letras distintas na mesma posição; ou 2- ausência de 
//letra na palavra seguinte (ou seja, ela é mais curta). Nos dois casos, já chegamos ao 
//tamanho máximo das letras em comum entre palavras. A primeira inconsistência é testada
//diretamente no statement do while e a segunda é testada por um if dentro de cada laço. 

//Para percorrer as letras pela sua ordem, mudando as palavras, basta que o 1° índice da
//matriz varie de forma que ele retorne a 0 quando chegar à última palavra e só aí o 2°
//índice aumente. As operações aritméticas de modulo (%) e divisão (/) permitem isso se
//feitas entre um contador sempre crescente e o número de palavras na matriz. 

//Enquanto o contador for inferior a um múltiplo do n° de palavras, o modulo aumenta, e, 
//quando chega ao múltiplo, o módulo retorna a 0. Já a divisão é truncada, ou seja, 
//descarta o resto. Isso significa que a divisão só aumenta quando o contador chega a um 
//múltiplo do n° de palavras. 

//Pelo mesmo motivo, a divisão vai indicar a última posição em comum a todas as palavras.
//A resposta será a string formada por qualquer uma das palavras desde a posição inicial
//até essa posição, exceto se a posição for zero, pois aí não haverá letra em comum e o
//retorno será da string vazia "".

//o contador precisa aumentar antes da divisão para permitir testar o tamanho da próxima
//palavra antes de iniciar outro laço do while (evitando erro por referenciar um elemento
//que não existe na palavra seguinte).
   
        while (strs[count % size][word_index] == strs[0][word_index])
        {      
            count++;        
            word_index = count/size;
            
            if (word_index >= strs[count % size].size())
            {
                break;
            }
        }
        
        if (word_index == 0)
        {
            return "";
        }
        
        return strs[0].substr(0,word_index);
    }
};?

Aqui sem as explicações e com os resultados lá do teste. Depois vou ver se tem como melhorar esses números daí ou se tem algum jeito mais criativo de resolver o problema. 


Ver mais

Legal. A vantagem de usar python é que dá para fazer muita coisa em pouca linha :D

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        common_prefix = ''
        try: 
            for i in range(201):
                current_letter = strs[0][i]
                for string in strs:
                    if string[i] != current_letter:
                        return common_prefix
                common_prefix += current_letter
        except IndexError:
            return common_prefix

Ver mais

começando no python..

mandei submit mais de uma vez, e o resultado do runtime e memory cada hora dá diferente

@FlyCavok : quem pergunta é neófito em algoritmos, e sem nunca ter lido script de Dart: é impressão minha, ou usou recursão na sua solução (i.e., chamou a função dentro dela mesma)?

@PMHM Isso. Usei uma técnica chamada Divide and Conquer

O objetivo é encontrar o começo idêntico entre n strings, certo?
Então eu divido as n strings em n/2

E divido novamente,
e novamente

até que sobram 2 strings  (divide)
Agora vem o conquer:

comparo uma com a outra e pego o prefixo comum.
Ao retornar dessa função, eu tenho para 2 pares o prefixo comum, agora eu vou pegar o prefixo comum dentre os prefixos comuns.

E assim vai resolvendo.

Performance:

Como tá dividindo por 2 a cada iteração, então a operação de divide é O(lg (n))   (log n na base 2)
Como a operação de conquer é um looping for em cima da string, é n para o pior caso.
Então seria algo como O(n lg(n)), o que é melhor do que O(n²) da solução "normal" de usar um looping dentro de outro looping.

Eu fiz assim pra praticar Divide and Conquer, que é algo que to tentando aprender. Entender eu entendo, mas não é algo que estou acostumado. O objetivo é me acostumar com essa técnica. 

@FlyCavok

Essa é a técnica do binary search, né? Li sobre ela esses dias, bem legal ver na prática

postado por @oxe em 22/02/2023 22:50

FlyCavok

Essa é a técnica do binary search, né? Li sobre ela esses dias, bem legal ver na prática

Isso.

É a mesma técnica que usam o MergeSort e o QuickSort. 

Por exemplo:   quero ordenar [2 3 1 5 4]

MergeSort:

1) divide no meio até não poder mais dividir
divide:  [2 3 1]     [  5 4]
divide:  [2 3]  [1]     [ 5 ]  [ 4 ]
divide:  [2] [3]  [1]   [ 5 ]  [ 4 ]

2) faz merge ordenado
merge:  [ 2 3 ] [ 1 5 ] [ 4 ]
merge:  [ 1 2 3 5 ] [ 4 ]
merge:  [ 1 2 3 4 5 ]

QuickSort:

Escolhe um pivot qualquer. ex: o último - tudo que for menor que ele vai pra esquerda, tudo que for maior, pra direita e divide o vetor nesses 2 vetores.

 [ 2 3 1 5 4]:  
pivot: 4, divide/sort: [2 3 1] 4 [5]
pivot: 1,  divide/sort: 1 [ 2 3] 4 5
pivot: 2, divide/sort: 1 2 3 4 5

@PMHM   Não sei se você percebeu, mas você tá lendo Dart sem nunca ter visto a linguagem. Olha aí a prova de que sabendo uma sabe a maioria, se não todas hahahah

Quando eu falo que linguagem de programação são todas iguais não é exagero

char * longestCommonPrefix(char ** strs, int strsSize){

    int i,j;
    int prefixSize = 0;
    int firstWordSize = strlen(strs[0]);
    char * prefix = malloc(sizeof(char)*(firstWordSize+1)); //+1 pra colocar o caractere de fim de string

    for(i=0;i<firstWordSize;i++)
        for(j=1;j<strsSize;j++)
            if(strs[j][i]!=strs[0][i]){
                prefixSize = i;
                i = firstWordSize +1;
                j = strsSize +1;
            }

    if(i==firstWordSize) //se chegou aqui eh pq a primeira palavra inteira eh prefixo valido
        prefixSize=firstWordSize;

    for(i=0;i<prefixSize;i++){ //copiando prefixo
        prefix[i]=strs[0][i];
    }

    prefix[prefixSize]=0; //colocando fim de string

    return prefix;
}?

@maxete

malloc é pra separar memória, né?

No C os arrays funcionam como ponteiros? 

postado por @oxe em 23/02/2023 10:17

maxete

malloc é pra separar memória, né?

No C os arrays funcionam como ponteiros? 

isso, malloc é de memory allocation. é para a gestão dinamica da memória.
Como o retorno é um char *, o formato que precisamos fazer é via malloc. Se eu criasse estaticamente o array, o tamanho tem que ser fixo (tipo 200 : char prefix[200]) e ao entregar o endereço surge o principal problema: ao criar o array no escopo local da função, depois de finalizada a função o setor de memoria utilizado é liberado para uso de qquer função, ou seja, não há aagarantia de integridade do ponteiro entregue.

Desta forma, você tem que separar (alocar) a memória deste array, que só vai liberar para uso quando você usar o "free".

Em C, os array são sempre trechos de memória contígua (o que não acontece com vectors do C++, por exemplo). quando vc usa o nome da variável do array sem o operador de acesso ao elemento "[i]", vc recebe o ponteiro do primeiro elemento.

prefix ---------------> ponteiro para o endereço da memória que começa o array

prefix+4*sizeof(char) -------------> ponteiro para o 5o elemento (endereço da memória + 4 elementos char pra frente)

prefix == &prefix[0] -----------------> mesma coisa
prefix+4*sizeof(char) == &prefix[4]   -------------------> mesma coisa

*prefix == prefix[0] ---------------> mesma coisa, conteúdo do endereço do ponteiro inicial do array

Em Python pra variar um pouco

@maxete

Muito legal, obrigado pela explicação.

No caso, o memory leak ocorre quando a pessoa esquece de liberar a memória da variável local, né? Tipo, a memória fica presa em uma variável que não existe mais.

Depois vou estudar melhor esse assunto pra ver se consigo implementar

@oxe
exatamente isso. Pra isso que existe o comando `free`

@oxe, isso, C (e C++) não tem garbage collector. todo malloc tem que ter um free explicito. No caso destes exercicios do leetcode faz a mao do TOC coçar. pq a gente tem que "confiar" no free alheio, a gente nao ve no codigo o free explicito, e isso cheira a mem leak...

OBS: algumas outras funcoes fazem malloc escondido, tipo o strdup, e precisam de free tb.

Ver mais

Valeu pelas explicações, @FlyCavok ! Ficou bem didático de entender

postado por @maxete em 23/02/2023 10:40

isso, malloc é de memory allocation. é para a gestão dinamica da memória.
Como o retorno é um char *, o formato que precisamos fazer é via malloc. Se eu criasse estaticamente o array, o tamanho tem que ser fixo (tipo 200 : char prefix[200]) e ao entregar o endereço surge o principal problema: ao criar o array no escopo local da função, depois de finalizada a função o setor de memoria utilizado é liberado para uso de qquer função, ou seja, não há aaaagarantia de integridade do ponteiro entregue.

Desta forma, você tem que separar (alocar) a memória deste array, que só vai liberar para uso quando você usar o "free".

Em C, os array são sempre trechos de memória contígua (o que não acontece com vectors do C++, por exemplo). quando vc usa o nome da variável do array sem o operador de acesso ao elemento "[i]", vc recebe o ponteiro do primeiro elemento.

prefix ---------------> ponteiro para o endereço da memória que começa o array

prefix+4*sizeof(char) -------------> ponteiro para o 5o elemento (endereço da memória + 4 elementos char pra frente)

prefix == &prefix[0] -----------------> mesma coisa
prefix+4*sizeof(char) == &prefix[4]   -------------------> mesma coisa

*prefix == prefix[0] ---------------> mesma coisa, conteúdo do endereço do ponteiro inicial do array

Isso.

Existem basicamente 2 tipos de alocação: estática e dinâmica. Na estática, o espaço de memória é contínuo pq ela é feita na hora da compilação. Assim, quando o programa é iniciado, aquele espaço já é alocado. Por isso precisa por o tamanho sempre. 

Na dinâmica, a memória é alocada durante a execução. O compilador não tem como saber quanto alocar, então nada é pre alocado.

A alocação funciona na base de pedir x bytes ao sistema operacional. Veja que o malloc é em bytes. Se vc quer alocar 4 inteiros, tem que fazer sizeof(int)*4, se fizer malloc(4) vai dar ruim. Char é 1 byte, então tudo bem.

O sistema operacional devolve o que vc pediu ou da um erro de alocação. No caso do C, não lembro o que faz se retorna null ou se crasheia o programa.

Se você pedir um tamanho pequeno, a chance de receber contínuo é grande, mas se não for, o SO acaba mandando uma memória fragmentada mesmo. Não há aagarantias.

O retorno é sempre o endereço pro primeiro "byte" da memória. Daí como é um endereço de memória, ele tem que ser armazenado em um ponteiro.

Se você armazenar em um ponteiro char, ao incrementar o ponteiro ele vai andar 1 byte. Se você armazenar em um ponteiro int, ele vai andar 4 bytes.

Se não chamar o free pode dar memory leak. Digo pode pq depende. Se não tá em um local que supostamente vc fica chamando, não vai dar problema. Vai gastar memória à toa, mas quando o programa terminar, libera.

Agora se tiver em uma função, vc alocou, saiu da função. Vai chamar ela de novo e de novo... À medida que o programa roda ele vai consumindo cada vez mais, sem nunca liberar. Até consumir tudo que tiver disponível e aí ser crasheado pelo SO. 

É um dos bugs mais comuns em C. Pau a pau com buffer overflows 

Kotlin

Acho essa aqui bacaninha
LeetCode - The World's Leading Online Programming Learning Platform

Já me perguntaram em entrevista.