ARTS 026
这是第26篇
Algorihm 算法题
646. 最长数对链
难度: 中等
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 :
输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]
注意：
- 给出数对的个数在 [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. 打家劫舍
难度: 简单
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。```
**示例 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);
}
//方法三 动态规划
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
这边文章讲了一位美国人求职的过程，最终拿到了30万美元的年薪，美帝的工资水平确实高啊。 https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/
Tips
我们的工程实际长了之后，随着业务的迭代，会有很多无用的类，也就是不被引用任何类引用的类，这些类会导致安装包变大，所以有必要清理一下，github上有一个脚本https://github.com/dblock/fui，很实用， 使用也很简单： 安装： gem install fui
在当前目录下检索未使用类:
fui find
还有直接删除和其他功能，具体可以去看看。
使用的时候注意一下，没有被别的类引用的类，也可能是有用的，比如实现了load方法，大家都知道load方法是，APP启动的时候自动调用的方法，如果有些业务逻辑写作里面，删除的话就会引起问题，我就算过这样的错误。所以删除类的时候最好还是要熟悉业务逻辑。
Share
iOS 应用程序怎么截获crash，防止崩溃，降低crash率，目前想到的思路是熟悉iOS系统的底层，也就是操作系统，熟悉操作系统需要深入学习C 语言和C++，提高自己的格局。 这个问题本质上又回到了熟悉基础知识的问题。只有对基础原理知识比较熟悉的时候，遇到问题的时候才能从根本上找到问题的解决办法。
