变态跳台阶多种解法

变态跳台阶

http://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387

  • 普通人能想到的暴力解法:
    跳上第n个台阶,我们可以推算上一步是如何跳到这第n个台阶的:

    • 如果上一步跳 1 步到达第 n 个台阶,说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]

    • 如果上一步跳 2 步到达第 n 个台阶,说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]

    • 如果上一步跳 n 步到达第 n 个台阶,说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0]

那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + ... + f[0]
显然初始条件f[0] = f[1] = 1
所以我们就可以先求f[2],然后f[3]...f[n-1], 最后f[n]

public class Solution {
    public int JumpFloorII(int target) {
        if(target == 0 || target == 1)
            return 1;
        int[] f = new int[target+1];
        f[0] = f[1] = 1;
        for(int i = 2; i <= target; i++){
            for(int j = 0; j < i; j++){
                f[i] += f[j];
            }
        }
        return f[target];
    }
}

时间复杂度 O(N2)
空间复杂度 O(N)

  • 我们可以发现规律
    f(1) = f(0) = 1;
    f(2) = f(1) + f(0) = 2 * f(1);
    f(3) = f(2) + f(1) + f(0) = 2 * f(2);
    f(4) = 2* f(3)
    ...
    f(n) = 2 * f(n-1)
    因为初始f(1)为1,所以刚好可以利用位运算。
    public class Solution {
      public int JumpFloorII(int target) {
          return 1 << (target - 1);    //左移1位是乘2,左移几就是几次乘2
      }
    }

时间复杂度 O(1)
空间复杂度 O(1)


基于该思想还有别的方法能够降低复杂度

public class Solution {
    public int JumpFloorII(int target) {
        if(target == 0 || target == 1)
            return 1;
        int a = 1, b = 0;
        for(int i = 2; i <= target; i++){
            b = a << 1;
            a = b;
        }
        return b;
    }
}

时间复杂度 O(n)
空间复杂度 O(1)


只有1级和2级台阶的解法:
图片说明

可以使用递归:

public class Solution {
    public int JumpFloor(int target) {
        if(target == 1)
               return 1;
        if(target == 2)
               return 2;
        return JumpFloor(target-1) + JumpFloor(target-2);

    }
}

但是时间复杂度为 O(2的n次方)


因此在面试时还是推荐递推型:

public class Solution {
    public int JumpFloor(int target) {
        int a = 1, b = 1;
        for(int i = 1; i < target; i++){
            //a是n后返1个的台阶
            a = a + b;
            //b是n后返2个的台阶
            b = a - b;
        }
        return a;

    }
}
全部评论

相关推荐

10-28 15:45
门头沟学院 C++
西南山:海康威视之前不是大规模裁员吗
点赞 评论 收藏
分享
09-27 00:29
东北大学 Java
伟大的麻辣烫:查看图片
阿里巴巴稳定性 75人发布 投递阿里巴巴等公司10个岗位
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务