ARTS 024
这是第24篇
Algorihm 算法题
最近在看动态规划，感觉有点感觉了，感觉入门了，就找了个动态规划的题。
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:
costwill have a length in the range[2, 1000].- 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;
}
}
这个题目用楼梯表示让人不是很理解，我这里用买路钱重新描述一下，从A地道B地需要经过，一共有N步吊桥，一次最多可以跨过一步，走过每一步需要留心买路钱。
方法一：递归
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;
}
上面的方法超时。
方法二： 备忘录递归
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;
}
备忘录递归递归法可以通过，时间是4ms
方法三：动态规划
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;
}
动态规划的时间也是4ms
题目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
这道题的关键是想明白：climbStairs(n)= climbStairs(n-1) + climbStairs(n-2);
Language: C
方案1：递归 ，LeetCode超时
int climbStairs(int n) {
if (n<3) {
return n;
}
return climbStairs(n-1) + climbStairs(n-2);
}
方案2：备忘录递归
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);
}
方案3：动态规划
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;
}
算法三：
509. Fibonacci Number
Difficulty: Easy
The Fibonacci numbers, commonly denoted 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
动态规划
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
这篇文章主要讲了iOS开发常用的工具集和类库.
TIPS
如何监听一个线程的Runloop状态。 runloop有下面几种状态，我们如何监听呢，比如在进入等待状态之前执行某个事件.
kCFRunLoopEntry = (1UL << 0),
kCFRunLoopBeforeTimers = (1UL << 1),
kCFRunLoopBeforeSources = (1UL << 2),
kCFRunLoopBeforeWaiting = (1UL << 5),
kCFRunLoopAfterWaiting = (1UL << 6),
kCFRunLoopExit = (1UL << 7),
kCFRunLoopAllActivities = 0x0FFFFFFFU
方法如下： 设置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){
//
}
Share
如何提高一个人的表达能力？很多道理和事情自己懂，但是表达出来的时候，总觉得缺点东西，不够精辟明了，是自己把问题看的不够深入还是表达能力差？怎么提高呢？
比如人的三观大家都知道是世界观、人生观和价值观。但是你能清楚的表达清楚这三观分别表达的意思吗？下面是左耳朵耗子对于三观的表述，是不是很清晰易懂!
世界观代表你是怎么看这个世界的。是左还是右,是激进还是保守,是理想还是现 实,是乐观还是悲观…….
人生观代表你要想成为什么样的人。是成为有钱人,还是成为人生的体验者,是成 为老师,还是成为行业专家,是成为有思想的人,还是成为…..
价值观则是你觉得什么对你来说更重要。是名是利,是过程还是结果,是付出还是 索取,是国家还是自己,是家庭还是职业……
-
Previous
My Development Toolset 2019 for iOS. -
Next
How I negotiated a $300,000 job offer in Silicon Valley
