ARTS #024

ARTS 024

This is article 24

Algorihm algorithm question

I was reading about dynamic programming recently, and I felt a little bit familiar. I felt like I was getting started, so I looked for a dynamic programming question.

746. Min Cost Climbing Stairs

Difficulty: Easy

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

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

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

Note:

1. cost will have a length in the range [2, 1000].
2. Every cost[i] will be an integer in the range [0, 999].

Solution

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

This question is not very understandable because it uses stairs to represent it. I will re-describe it here using tolls. From tunnel A to point B, you need to pass through. There are N steps of suspension bridges. You can cross one step at most at a time. You need to pay attention to the tolls after each step.

Method 1: Recursion

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

The above method times out.

Method 2: Memo recursion

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

The memo recursive method can pass, the time is 4ms

Method three: dynamic programming

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

The time of dynamic programming is also 4ms

Question 2:

70. Climbing Stairs

Difficulty: Easy

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

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

Example 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

Solution

The key to this question is to understand: climbStairs(n)= climbStairs(n-1) + climbStairs(n-2);

Language: C

Solution 1: Recursion, LeetCode timeout

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

Option 2: Memo Recursion

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

Option 3: Dynamic programming

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

Algorithm three:

509. Fibonacci Number

Difficulty: Easy

The Fibonacci numbers, commonly referred to as F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

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

Given N, calculate F(N).

Example 1:

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

Example 2:

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

Example 3:

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

Note:

0 ≤ N ≤ 30.

Solution

Language: C

dynamic programming

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

Review

This article mainly talks about the commonly used tool sets and class libraries for iOS development.

TIPS

How to monitor the Runloop status of a thread. The runloop has the following states. How do we monitor it, such as executing an event before entering the waiting state.

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

Here’s how: Set up runloop monitoring

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

Share

How to improve one’s expressive ability? I understand many truths and things, but when I express them, I always feel that they are shortcomings and not clear enough. Is it because I don’t understand the problem deeply enough or am I poor at expressing myself? How to improve it?

For example, everyone knows that people’s three views are world outlook, outlook on life and values. But can you clearly express what these three views mean? The following is 左耳朵耗子’s expression of the three views. Is it very clear and easy to understand?

世界观 represents how you see the world. Is it left or right, radical or conservative, ideal or current? Really, is it optimistic or pessimistic?.. 人生观 represents the kind of person you want to be. Is it to become a rich person or to be an experiencer of life? To be a teacher, to be an industry expert, to be a thoughtful person, or to be… 价值观 It’s about what you think is more important to you. Is it fame or fortune, process or result, dedication or Whether it is the country or oneself, family or career…