ARTES #024

ARTES 024

Este é o artigo 24

Pergunta sobre algoritmo de algoritmo

Eu estava lendo sobre programação dinâmica recentemente e me senti um pouco familiarizado. Eu senti que estava começando, então procurei uma questão de programação dinâmica.

746. Custo mínimo para subir escadas

Dificuldade: Fácil

Em uma escada, o degrau i tem algum custo não negativo cost[i] atribuído (0 indexado).

Depois de pagar o custo, você pode subir um ou dois degraus. Você precisa encontrar o custo mínimo para chegar ao topo do andar e pode começar na etapa com índice 0 ou na etapa com índice 1.

Exemplo 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Exemplo 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Nota:

1. cost terá um comprimento no intervalo [2, 1000].
2. Cada cost[i] será um número inteiro no intervalo [0, 999].

Solução

Idioma: C

int minCostClimbingStairs(int* cost, int costSize) {
    if (costSize < 2) {
        return 0;
    }
    
    int dd_0 = 0;
    int dd_1  = 0;
    int result = 0;
​
    for (int i = 2;i<=costSize;i++) {
        int tem1 =  dd_0  + cost[i-2];
        int tem2 = dd_1 + cost[i-1];
        if (tem1 > tem2) {
            result = tem2;
        }
        else{
            result = tem1;
        }
        dd_0 = dd_1;
        dd_1 = result;
    }
    return result; 
}
}

Esta questão não é muito compreensível porque utiliza escadas para representá-la. Vou redescrevê-lo aqui usando pedágios. Do túnel A ao ponto B, você precisa passar. Existem N degraus de pontes suspensas. Você pode cruzar no máximo um passo de cada vez. Você precisa prestar atenção aos pedágios após cada etapa.

Método 1: Recursão

int minCostClimbingStairs(int* cost, int costSize) {

    if (costSize<=0) {
        return  0;
    }
    
    int sum;
     int sum1 = minCostClimbingStairs(cost,costSize -1) + cost[costSize -1];
    int sum2 = minCostClimbingStairs(cost,costSize -2) + cost[costSize -2];
    
    if (sum1>sum2) {
        sum = sum2;
    }
    else{
        sum = sum1;
    }

    
    
    return sum;
}

O método acima expira.

Método 2: recursão de memorando

int dd[1001] = {-1};

int minCostClimbingStairs1(int* cost, int costSize) {
    if (costSize<=0) {
        return  0;
    }
    if (dd[costSize] >=0) {
        return dd[costSize];
    }
    
    int sum;
    int sum1 = minCostClimbingStairs1(cost,costSize -1) + cost[costSize -1];
    int sum2 = minCostClimbingStairs1(cost,costSize -2) + cost[costSize -2];
    
    if (sum1>sum2) {
        sum = sum2;
    }
    else{
        sum = sum1;
    }
    
    dd[costSize] = sum;
    
    return sum;
}

int minCostClimbingStairs(int* cost, int costSize) {
    for (int i = 0; i < 1001; i++) {
        dd[i] = -1;
    }
    
   int sum = minCostClimbingStairs1(cost,costSize);
    
    return sum;
}

O método memo recursivo pode passar, o tempo é de 4ms

Método três: programação dinâmica

int minCostClimbingStairs(int* cost, int costSize) {
    if (costSize < 2) {
        return 0;
    }
    
    int dd_0 = 0;
    int dd_1  = 0;
    int result = 0;

    for (int i = 2;i<=costSize;i++) {
        int tem1 =  dd_0  + cost[i-2];
        int tem2 = dd_1 + cost[i-1];
        if (tem1 > tem2) {
            result = tem2;
        }
        else{
            result = tem1;
        }
        dd_0 = dd_1;
        dd_1 = result;
    }
    return result; 
}

O tempo de programação dinâmica também é de 4ms

Pergunta 2:

70. Subindo escadas

Dificuldade: Fácil

Você está subindo uma escada. São necessários n passos para chegar ao topo.

Cada vez você pode subir 1 ou 2 degraus. De quantas maneiras distintas você pode chegar ao topo?

Observação: Dado n será um número inteiro positivo.

Exemplo 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1\. 1 step + 1 step
2\. 2 steps

Exemplo 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1\. 1 step + 1 step + 1 step
2\. 1 step + 2 steps
3\. 2 steps + 1 step

Solução

A chave para esta questão é entender: subidaEscada(n)= subidaEscada(n-1) + subidaEscada(n-2);

Idioma: C

Solução 1: recursão, tempo limite LeetCode

int climbStairs(int n) {
    if (n<3) {
        return n;
    }
    
    return climbStairs(n-1) + climbStairs(n-2);
}

Opção 2: recursão de memorando

int dd[1001];
int climbStairs1(int n) {
    if (n < 3) {
        return n;
    }
    
    if (dd[n] > 0) {
        return dd[n];
    }
    
    int c = climbStairs1(n-1) + climbStairs1(n-2);
    dd[n] = c;
    return c;
}


int climbStairs(int n) {
    for (int i = 0; i < 1001; i++) {
                dd[i] = -1;
        }
    
    return climbStairs1(n);
}

Opção 3: programação dinâmica

int climbStairs(int n) {
    if (n < 3) {
        return n;
    }
    int c1 = 1;
    int c2 = 2;
    int result = 0;
    
    for (int i=3; i<=n; i++) {
        result = c1 + c2;
        c1= c2;
        c2 = result;
    }
    
    return result;
}

Algoritmo três:

509. Número Fibonacci

Dificuldade: Fácil

Os números de Fibonacci, comumente chamados de F(n), formam uma sequência, chamada sequência de Fibonacci, de modo que cada número é a soma dos dois anteriores, começando em 0 e 1. Isto é,

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

Dado N, calcule F(N).

Exemplo 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Exemplo 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Exemplo 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Nota:

0 ≤ N ≤ 30.

Solução

Idioma: C

programação dinâmica

int fib(int N) {
    if (N<2) {
        return N;
    }
    
    int f0 = 0;
    int f1 = 1;
    int fn = 0;
    
    for (int i=2; i<=N; i++) {
        fn = f0 + f1;
        f0= f1;
        f1 = fn;
    }
    
    return fn;
}

Revisão

Este artigo fala principalmente sobre os conjuntos de ferramentas e bibliotecas de classes comumente usados para desenvolvimento em iOS.

DICAS

Como monitorar o status Runloop de um thread. O runloop possui os seguintes estados. Como podemos monitorá-lo, como executar um evento antes de entrar no estado de espera.

   kCFRunLoopEntry = (1UL << 0),
     kCFRunLoopBeforeTimers = (1UL << 1),
     kCFRunLoopBeforeSources = (1UL << 2),
     kCFRunLoopBeforeWaiting = (1UL << 5),
     kCFRunLoopAfterWaiting = (1UL << 6),
     kCFRunLoopExit = (1UL << 7),
     kCFRunLoopAllActivities = 0x0FFFFFFFU

Veja como: Configurar o monitoramento runloop

// 添加一个监听者
-(void)addRunloopObserver{
    //获取当前runloop
    CFRunLoopRef  currentRunloop =  CFRunLoopGetCurrent();
    //runloop观察者上下文， 为下面创建观察者准备，只有创建上下文才能在回调了拿到self对象，才能进行我们的监听操作. 这是一个结构体。
    /**
     typedef struct {
     CFIndex	version;
     void *	info;
     const void *(*retain)(const void *info);
     void	(*release)(const void *info);
     CFStringRef	(*copyDescription)(const void *info);
     } CFRunLoopObserverContext;
     **/
    CFRunLoopObserverContext  context = {
        0,
        (__bridge void *)(self),
        &CFRetain,
        &CFRelease,
        NULL
    };
  
    static CFRunLoopObserverRef  obserberRef;
    obserberRef =CFRunLoopObserverCreate(NULL, kCFRunLoopBeforeWaiting, YES, 0,&callback, &context);
    //给当前runloop添加观察者
    CFRunLoopAddObserver(currentRunloop, obserberRef, kCFRunLoopDefaultMode);
    //释放观察者
    CFRelease(obserberRef);
}

//观察回调
static void callback(CFRunLoopObserverRef observer, CFRunLoopActivity activity, void *info){
   //
}

Compartilhar

Como melhorar a capacidade expressiva? Entendo muitas verdades e coisas, mas quando as expresso, sempre sinto que são deficiências e não são suficientemente claras. É porque não entendo o problema com profundidade suficiente ou sou pobre em me expressar? Como melhorar isso?

Por exemplo, todos sabemos que as três visões das pessoas são a visão do mundo, a visão da vida e os valores. Mas você consegue expressar claramente o que essas três visões significam? A seguir está a expressão das três visualizações de 左耳朵耗子. É muito claro e fácil de entender?

世界观 representa como você vê o mundo. É de esquerda ou de direita, radical ou conservador, ideal ou atual? Realmente, é otimista ou pessimista?.. 人生观 representa o tipo de pessoa que você deseja ser. É tornar-se uma pessoa rica ou ser um experimentador de vida? Ser professor, ser um especialista do setor, ser uma pessoa atenciosa ou ser… 价值观 É sobre o que você acha que é mais importante para você. É fama ou fortuna, processo ou resultado, dedicação ou Seja o país ou você mesmo, a família ou a carreira…