2023 10:37

Tecnologia

FlyCavok 181º
em 22/05/23 18:13

comentada em 09/06/2023 10:37

Mais um desafio para a semana!
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Link para o desafio: First Bad Version - LeetCode

ver comentários do moderador

@Giovanni

@Gustavo

tópicos e FAQs relacionados

Comentários

Último comentário 1º comentário do autor Só moderadores Só os meus Só quem eu sigo Ordenar por gostei

oxe 1º

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;
    }
};?

Ajuda aí pow!

BastterCode semana 15 - 278. First Bad Version - #1 de 7

FlyCavok 181º
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;
    }
};

Ajuda aí pow!

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

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;
}

Ajuda aí pow!

BastterCode semana 15 - 278. First Bad Version - #3 de 7

FlyCavok 181º
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