ARTES #025

ARTES 025

Este é o artigo 25

Pergunta sobre algoritmo de algoritmo

264. Número Feio II

Dificuldade: Média

Escreva um programa para encontrar o número feio n.

Um número feio é um inteiro positivo contendo apenas fatores primos 2, 3, 5.

Exemplo:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。```

**Descrição: **

1. `1` é um número feio.
2. `n` **não exceda**1690.


#### Solução

Idioma: **C**

```c
int nthUglyNumber(int n) {
    if (n<7) {
        return n;
    }


    int rs[1691] = {0};

    for (int i = 1; i < 7; i++) {
        rs[i] = i;
    }


    int N2 = 0;
    int N2_flag = 0;

    int N3 = 0;
    int N3_flag = 0;

    int N5 = 0;
    int N5_flag = 0;
    int loop = 1;

    for (int i = 7; i <= n; i++) {
         loop = i;
        for (int j = 1; j < loop; j++) {
            if (N2_flag ==0 && (rs[j] * 2 > rs[i-1])) {
                N2 = rs[j] * 2;
                N2_flag =1;
            }

            if (N3_flag ==0 && (rs[j] * 3 > rs[i-1])) {
                N3 = rs[j] * 3;
                N3_flag =1;
            }

            if (N5_flag ==0 && (rs[j] * 5 > rs[i-1])) {
                N5 = rs[j] * 5;
                N5_flag =1;
            }
        }

        //取 N2 N3 N5  最小的一个
        int r = N2;
        if (r>N3) {
            r  = N3;
        }


        if (r>N5) {
            r=N5;
        }

        rs[i] = r;
        N2_flag = 0;
        N3_flag = 0;
        N5_flag = 0;

    }

    return rs[n];
}

53. Soma máxima de subsequência

Dificuldade: Fácil

Dado um array inteiro nums , encontre um subarray contínuo com a soma máxima (o subarray contém pelo menos um elemento) e retorne sua soma máxima.

Exemplo:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

Avançado:

Se você já implementou uma solução O(n), tente usar a solução mais elegante de dividir e conquistar.

Solução

Idioma: C

int maxSubArray(int* nums, int numsSize){
    if (numsSize < 1) {
        return 0;
    }
    
    int sum = nums[0];
    int max = sum;
    
    for (int  i = 1; i < numsSize; i++) {
        if (sum + nums[i] > nums[i]) {
            sum = sum + nums[i];
        }
        else{
            sum = nums[i];
        }
        
        if (sum > max) {
            max = sum;
        }
    }
    return max;
}

121. O melhor momento para comprar e vender ações

Dificuldade: Fácil

Dado um array, o _i_ésimo elemento é o preço de uma determinada ação no dia i.

Se você só tiver permissão para concluir no máximo uma transação (ou seja, comprar e vender uma ação), crie um algoritmo para calcular o lucro máximo que você pode obter.

Observe que você não pode vender uma ação antes de comprá-la.

Exemplo 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

Exemplo 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

Solução

Idioma: C

int maxProfit(int* prices, int pricesSize) {
    if (pricesSize < 2) {
        return 0;
    }
    
    int min = prices[0];
    int ret = 0;
    for (int i = 0; i<pricesSize; i++) {
        int tem = prices[i] - min;
        if (tem > ret ) {
            ret = tem;
        }
        
        if (min > prices[i]) {
            min = prices[i];
        }
    }
    return ret;
}

A ideia inicial deste problema é encontrar os valores máximo e mínimo, sendo que o valor máximo está atrás do valor mínimo. A maneira mais fácil de pensar é muitas vezes a menos eficiente.

A chave para esse problema é calcular o retorno a cada vez que o loop passa e atualizar o valor mínimo.

Revisão

O artigo aqui fala sobre o processo de procura de emprego de um americano, que finalmente conseguiu um salário anual de 300.000 dólares americanos. O nível salarial do imperador americano é realmente alto. https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/

Dicas

Use o seguinte método para medir o tempo de execução de uma determinada linha de código:

os_log_t log = os_log_create("com.example.your-app", "RefreshOperations");
os_signpost_id_t log_t = os_signpost_id_generate(log);


os_signpost_interval_begin(log, log_t, "Buscar ativo");

//O código que você deseja medir
 os_signpost_interval_end(log, log_t, "Buscar Ativo1");

Compartilhar