Lexi's Leetcode solutions

[leetcode] Climb Stairs | 小孩上楼梯

Posted on: October 8, 2013

这个经典题居然submit了4遍才过,给33.8%的通过率拖后腿了。原因是忘记d[i]表示什么了就开始瞎写。就算做过的经典题,当场再想一想又有什么不好的?

d[i]表示到第i级台阶有几种走法。d[0]必须是1,这个是用i=1试出来的。最后返回d[n]不是d[n – 1]!

public int climbStairs(int n) {
  if (n == 0)
    return 0;
  int[] d = new int[n + 1];
  d[0] = 1;
  for (int i = 1; i <= n; i++) {
    d[i] += d[i - 1];
    if (i >= 2)
      d[i] += d[i - 2];
  }
  return d[n];
}

只用三个变量,不用array的做法(既然只看d[i – 1], d[i -2]往前看两个,那keep三个变量就够了。

public int climbStairs(int n) {
  if (n == 0)
    return 0;
  int prevPrev = 0;
  int prev = 1;
  for (int i = 1; i <= n; i++) {
    int curr = 0;
    curr += prev;
    if (i >= 2)
      curr += prevPrev;
    prevPrev = prev;
    prev = curr;
  }
  return prev;
}
Advertisements
Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: