ARTES #024

##ARTES 024 este es el articulo 24

Pregunta sobre el algoritmo del algoritmo

Estuve leyendo sobre programación dinámica recientemente y me sentí un poco familiarizado. Sentí que estaba comenzando, así que busqué una pregunta de programación dinámica.

746. Costo mínimo para subir escaleras

Dificultad: Fácil

En una escalera, el escalón i-ésimo tiene asignado un coste no negativo cost[i] (0 indexado).

Una vez que pague el costo, podrá subir uno o dos escalones. Necesita encontrar el costo mínimo para llegar a la parte superior del piso, y puede comenzar desde el paso con índice 0 o desde el paso con índice 1.

Ejemplo 1:

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

Ejemplo 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 tendrá una longitud en el rango [2, 1000].
2. Cada cost[i] será un número entero en el rango [0, 999].

Solución

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 pregunta no es muy comprensible porque utiliza escaleras para representarla. Lo volveré a describir aquí usando peajes. Desde el túnel A hasta el punto B, debes pasar. Hay N escalones de puentes colgantes. Puedes cruzar un paso como máximo a la vez. Debes prestar atención a los peajes después de cada paso.

Método 1: recursividad

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

El método anterior caduca.

Método 2: recursión de notas

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

El método recursivo de notas puede pasar, el tiempo es de 4 ms.

Método tres: programación 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; 
}

El tiempo de programación dinámica también es de 4ms.

Pregunta 2:

70. Subir escaleras

Dificultad: Fácil

Estás subiendo una escalera. Se necesitan n pasos para llegar a la cima.

Cada vez puedes subir 1 o 2 escalones. ¿De cuántas maneras distintas puedes subir a la cima?

Nota: Dado n será un número entero positivo.

Ejemplo 1:

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

Ejemplo 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

Solución

La clave de esta pregunta es entender: subirEscaleras(n)= subirEscaleras(n-1) + subirEscaleras(n-2);

Idioma: C

Solución 1: recursividad, tiempo de espera de LeetCode

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

Opción 2: recursión de notas

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

Opción 3: programación 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 tres:

509. Número de Fibonacci

Dificultad: Fácil

Los números de Fibonacci, comúnmente conocidos como F(n), forman una secuencia, llamada secuencia de Fibonacci, de manera que cada número es la suma de los dos anteriores, comenzando por 0 y 1. Es decir,

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

Dado N, calcule F(N).

Ejemplo 1:

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

Ejemplo 2:

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

Ejemplo 3:

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

Nota:

0 ≤ N ≤ 30.

Solución

Idioma: C

programación 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;
}

Revisión

Este artículo habla principalmente sobre los conjuntos de herramientas y bibliotecas de clases más utilizados para el desarrollo de iOS.

CONSEJOS

Cómo monitorear el estado de Runloop de un hilo. El runloop tiene los siguientes estados. ¿Cómo lo monitoreamos, como ejecutar un evento antes de entrar en estado de espera?

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

He aquí cómo: Configurar la supervisión del ciclo de ejecución

// 添加一个监听者
-(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){
   //
}

Compartir

¿Cómo mejorar la capacidad expresiva? Entiendo muchas verdades y cosas, pero cuando las expreso, siempre siento que son deficiencias y no lo suficientemente claras. ¿Es porque no entiendo el problema lo suficientemente profundo o soy pobre para expresarme? ¿Cómo mejorarlo?

Por ejemplo, todo el mundo sabe que las tres visiones de la gente son la visión del mundo, la visión de la vida y los valores. ¿Pero puedes expresar claramente lo que significan estos tres puntos de vista? La siguiente es la expresión de 左耳朵耗子 de las tres vistas. ¿Es muy claro y fácil de entender?

世界观 representa cómo ves el mundo. ¿Es de izquierda o de derecha, radical o conservadora, ideal o actual? De verdad, ¿es optimista o pesimista?.. 人生观 representa el tipo de persona que quieres ser. ¿Es convertirse en una persona rica o ser un experimentador de la vida? Ser profesor, ser un experto en la industria, ser una persona reflexiva o ser… 价值观 Se trata de lo que crees que es más importante para ti. ¿Es fama o fortuna, proceso o resultado, dedicación o Ya sea el país o uno mismo, la familia o la carrera…