ARTS #026

ARTS 026

This is article 26

Algorihm algorithm question

646. Longest pair chain

Difficulty: Medium

Give n number pairs. In every pair of numbers, the first number is always smaller than the second number.

Now, we define a following relationship. If and only if b < c, the number pair (c, d) can follow (a, b). We use this form to construct a chain of number pairs.

Given a set of pairs, find the length of the longest chain of pairs that can be formed. You don’t need to use all the pairs, you can choose some of them in any order to construct.

Example:

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]

Note:

1. The number of given number pairs is in the range [1, 1000].

Solution

Language: C

#define maxn 1005
struct Pair{
    int begin;
    int end;
} pair[maxn];

int cmp(const void* a, const void* b){
    struct Pair* x = (struct Pair*)a;
    struct Pair* y = (struct Pair*)b;
    if(x->end == y->end) return x->begin - y->begin;
    return x->end - y->end;
}

void matrixToStruct(int** pairs, int row){
    for(int i = 0;i < row;i++){
        pair[i].begin = pairs[i][0];
        pair[i].end = pairs[i][1];
    }
}

int findLongestChain(int** pairs, int pairsRowSize, int pairsColSize) {
    int row = pairsRowSize;
    int col = pairsColSize;
    
    matrixToStruct(pairs, row);
    qsort(pair, row, sizeof(struct Pair), cmp);
    
    int cnt = 1;
    for(int i = 1, k= 0;i < row;i++){
        if(pair[i].begin > pair[k].end){
            cnt++;
            k = i;
        }
    }
    return cnt;
}

198. Robbery

Difficulty: Easy

You are a professional thief planning to steal houses along the street. There is a certain amount of cash hidden in each room. The only restriction factor that affects your theft is that the adjacent houses are equipped with interconnected anti-theft systems. If two adjacent houses are broken into by thieves on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal without triggering the alarm device.

Example 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。```

**Example 2:**

输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

#### Solution

Language: **C**

//方法一 递归法 int rob(int* nums, int numsSize) { if (numsSize <=0) { return 0; }

if (numsSize==1) {
    return nums[0];
}
int r1= rob(nums,numsSize-2) +  nums[numsSize - 1];
int r2= rob(nums,numsSize-1) ;
if (r1 > r2) {
    return r1;
}
return r2;

}

//方法二 备忘录递归法 int re[10000] = {-1};

int rob1(int* nums, int numsSize) {

if (numsSize <=0) {
    return 0;
}

if (numsSize==1) {
    return nums[0];
}

if (re[numsSize] >-1) {
    return re[numsSize];
}

int r1= rob1(nums,numsSize-2) +  nums[numsSize - 1];
int r2= rob1(nums,numsSize-1) ;
if (r1 > r2) {
    re[numsSize] = r1;
    return r1;
}

re[numsSize] = r2;
return r2;

}

int rob(int* nums, int numsSize){ for (int i=0; i<10000; i++) { re[i] = -1; } return rob1(nums, numsSize); }

```c
//方法三 动态规划
int rob(int* nums, int numsSize){
    if (numsSize <=0) {
        return 0;
    }

    if (numsSize==1) {
        return nums[0];
    }
    
    int r0 = nums[0];
    int r1 = nums[1];
    int sum = r0 > r1 ? r0 : r1;
   
    
    for (int i = 2; i < numsSize; i++) {
        r1 = r0 + nums[i];
        r0 = sum;
        sum = r0 > r1 ? r0 : r1;
    }
    
    
    return sum;
}

Review

The article here talks about the job search process of an American, and finally got an annual salary of 300,000 US dollars. The salary level of the American emperor is indeed high. https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/

Tips

After our project actually grows, as the business iterates, there will be many useless classes, that is, classes that are not referenced by any class. These classes will cause the installation package to become larger, so it is necessary to clean it up. There is a script https://github.com/dblock/fui，很实用， on github It’s also very simple to use: Installation: gem install fui

Retrieve unused classes in the current directory:

fui find

There are also direct deletion and other functions, you can check it out for details.

Pay attention when using it. Classes that are not referenced by other classes may also be useful. For example, if the load method is implemented, everyone knows that the load method is a method that is automatically called when the APP starts. If there is some business logic written in it, if it is deleted, it will cause problems. I have ignored such errors. Therefore, it is best to be familiar with business logic when deleting classes.

Share

How to intercept crashes in iOS applications, prevent crashes, and reduce crash rates. The current idea is to be familiar with the bottom layer of the iOS system, that is, the operating system. Being familiar with the operating system requires in-depth study of C language and C++ to improve your own pattern. This question essentially comes back to familiarizing yourself with the basics. Only when you are familiar with the basic principles, you can fundamentally find solutions to problems when you encounter them.