BastterCode semana 15 - 278. First Bad Version

Tecnologia
FlyCavok  
em 22/05/23 18:13

Comentários

Último comentário 1º comentário do autor Só moderadores Só quem eu sigo Ordenar por gostei
oxe  
em 22/05/2023 20:06
Se a busca for feita individualmente, pode demorar até 2^31-1 testes. O truque aqui é a cada loop reduzir o espaço de análise pela metade, o que torna a complexidade logarítmica. Nesse caso, no máximo serão necessários log2(2^31) = 31*log2(2) = 31 loops. Uma redução dramática.

Para isso, você começa analisando o meio do espaço de análise. Se lá a versão for ruim, então a versão ruim começou antes e você não precisa mais analisar a metade final. Se lá a versão for boa, então a versão ruim começou depois e você não precisa mais analisar a metade inicial. Ou seja, o espaço de análise caiu pela metade.

Depois é só continuar analisando o meio do espaço de análise restante, até que o espaço seja de apenas uma unidade, caso em que você achou a resposta do problema.
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int low = 1, high = n;
        while (high != low) {
            int mid = low/2 + high/2;
            
            if (isBadVersion(mid)) high = mid;
            else low = mid + 1;
        }
        return high;
    }
};?
; 3; ; 0;
0 '; 0';
BastterCode semana 15 - 278. First Bad Version - #1 de 7
FlyCavok  
em 06/06/2023 15:20
Isso aí @oxe. O problema dá para ser resolvido por busca binária!

class Solution {
public:
    int firstBadVersion(int n) {
        long l = 1, r = n;
        int bad = 0;
        
        while (l <= r) {
            int mid = (r + l)/2;
            if (isBadVersion(mid)) {
                bad = mid;
                r = mid - 1;
            } else {
                l = mid+1;
            }
            
        }
        
        return bad;
    }
};

; 1; ; 0;
0 '; 0';
BastterCode semana 15 - 278. First Bad Version - #2 de 7
Giovanni  
em 08/06/2023 23:19
antes de pensar em fazer uma busca binária eu fiz uma função na unha que estourou o tempo de execução do site

C
int firstBadVersion(int n) {
    unsigned int fail = 1;
    unsigned int mid = 0;

    while (fail < n) {
        mid = (fail + n) / 2;

        if (isBadVersion(mid)) n = mid;
        else fail = mid + 1;
    }

    return fail;
}
; 0; ; 0;
0 '; 0';
BastterCode semana 15 - 278. First Bad Version - #3 de 7
FlyCavok  
em 09/06/2023 00:31
@Giovanni

Aproveitando que você tá aí, quando clicamos no banner no site principal, dá no desafio da semana 10 ainda! Daí acho que muita gente que não se liga acha que tá parado desde então.

Url montando em BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - Tecnologia - Bastter.com

esse ID aí tá errado.

@Gustavo ?

Estamos na 16
; 0; ; 0;
0 '; 0';
BastterCode semana 15 - 278. First Bad Version - #4 de 7
gustavo  
em 09/06/2023 08:03
; 0; ; 0;
0 '; 0';
BastterCode semana 15 - 278. First Bad Version - #5 de 7
FlyCavok  
em 09/06/2023 09:33
@gustavo sim, esses mesmos. O link na barra lateral ?
; 0; ; 0;
0 '; 0';
BastterCode semana 15 - 278. First Bad Version - #6 de 7
gustavo  
em 09/06/2023 10:37
@FlyCavok tirei o link do banner q tava dando confusão, deixei só nos botões (tópico e challenge)
; 0; ; 0;
0 '; 0';
BastterCode semana 15 - 278. First Bad Version - #7 de 7

4 usuários comentaram este tópico.
Clique para ir para o primeiro comentário do usuário.

Ações Pesquisa Videos Livros Análise de Carteira Desconto FAQs Orientação Esportiva Ofertas e Serviços Bastter System Boletim IR Podcasts Revista Tecnologia - Ajuda Eu Assinar Ações Pesquisa Videos Livros Análise de Carteira Desconto FAQs Ofertas e Serviços Orientação Esportiva Boletim BS Podcasts IR Tecnologia Ajuda eu Revista Assinar Assinar

BastterZap