SENI #024

SENI 024

Ini adalah pasal 24

Pertanyaan algoritma algoritma

Saya membaca tentang pemrograman dinamis baru-baru ini, dan saya merasa sedikit familiar. Saya merasa seperti baru memulai, jadi saya mencari pertanyaan pemrograman dinamis.

746. Biaya Minimal Menaiki Tangga

Kesulitan: Mudah

Di tangga, langkah ke-i memiliki beberapa biaya non-negatif yang ditetapkan cost[i] (0 diindeks).

Setelah Anda membayar biayanya, Anda dapat menaiki satu atau dua anak tangga. Anda perlu mencari biaya minimum untuk mencapai puncak, dan Anda bisa memulai dari langkah dengan indeks 0, atau langkah dengan indeks 1.

Contoh 1:

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

Contoh 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].

Catatan:

1. cost akan memiliki panjang di kisaran [2, 1000].
2. Setiap cost[i] akan menjadi bilangan bulat dalam rentang [0, 999].

Solusi

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

Pertanyaan ini kurang dimengerti karena menggunakan tangga untuk mewakilinya. Saya akan uraikan kembali disini dengan menggunakan tol. Dari terowongan A ke titik B, Anda harus melewatinya. Ada N anak tangga jembatan gantung. Anda dapat melewati paling banyak satu langkah dalam satu waktu. Anda perlu memperhatikan jumlah korban setelah setiap langkah.

Metode 1: Rekursi

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

Metode di atas kehabisan waktu.

Metode 2: Rekursi memo

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

Metode memo rekursif bisa lewat, waktunya 4ms

Metode ketiga: pemrograman dinamis

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

Waktu pemrograman dinamis juga 4ms

Pertanyaan 2:

70. Memanjat Tangga

Kesulitan: Mudah

Anda sedang menaiki tangga. Dibutuhkan n langkah untuk mencapai puncak.

Setiap kali Anda dapat menaiki 1 atau 2 anak tangga. Dalam berapa cara berbeda Anda dapat mendaki ke puncak?

Catatan: Diberikan n akan menjadi bilangan bulat positif.

Contoh 1:

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

Contoh 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

Solusi

Kunci dari pertanyaan ini adalah memahami: pendakianStairs(n)= pendakianStairs(n-1) + pendakianStairs(n-2);

Bahasa: C

Solusi 1: Rekursi, batas waktu LeetCode

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

Opsi 2: Rekursi Memo

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

Opsi 3: Pemrograman dinamis

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

Algoritma tiga:

509. Angka Fibonacci

Kesulitan: Mudah

Bilangan Fibonacci, biasa disebut F(n), membentuk barisan yang disebut Deret Fibonacci, sehingga setiap angka merupakan penjumlahan dari dua angka sebelumnya, dimulai dari 0 dan 1. Artinya,

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

Diberikan N, hitung F(N).

Contoh 1:

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

Contoh 2:

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

Contoh 3:

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

Catatan:

0 ≤ N ≤ 30.

Solusi

Bahasa: C

pemrograman dinamis

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

Ulasan

Artikel ini terutama membahas tentang kumpulan alat dan pustaka kelas yang umum digunakan untuk pengembangan iOS.

TIPS

Cara memonitor status Runloop dari sebuah thread. Runloop memiliki status berikut. Bagaimana cara kita memantaunya, seperti mengeksekusi suatu event sebelum memasuki status menunggu.

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

Begini caranya: Siapkan pemantauan 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){
   //
}

Bagikan

Bagaimana cara meningkatkan kemampuan ekspresif seseorang? Saya memahami banyak kebenaran dan hal, tetapi ketika saya mengungkapkannya, saya selalu merasa bahwa itu adalah kekurangan dan tidak cukup jelas. Apakah karena saya kurang memahami masalahnya atau karena saya kurang bisa mengekspresikan diri? Bagaimana cara memperbaikinya?

Misalnya, semua orang tahu bahwa tiga pandangan manusia adalah pandangan dunia, pandangan hidup, dan nilai-nilai. Namun bisakah Anda mengungkapkan dengan jelas apa maksud dari ketiga pandangan tersebut? Berikut ekspresi 左耳朵耗子 terhadap ketiga tampilan tersebut. Apakah sangat jelas dan mudah dimengerti?

世界观 mewakili cara Anda melihat dunia. Apakah kiri atau kanan, radikal atau konservatif, ideal atau terkini? Beneran optimis atau pesimis?.. 人生观 mewakili orang seperti apa yang Anda inginkan. Apakah menjadi orang kaya atau menjadi orang yang mengalami kehidupan? Menjadi guru, menjadi pakar industri, menjadi orang yang bijaksana, atau… 价值观 Ini tentang apa yang menurut Anda lebih penting bagi Anda. Apakah itu ketenaran atau kekayaan, proses atau hasil, dedikasi atau Baik itu negara atau diri sendiri, keluarga atau karier…