《剑指offer》71--跳台阶扩展问题[C++][C][Java][Kotlin][Rust]

跳台阶扩展问题_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tags=&title=&difficulty=0&judgeStatus=0&rp=1

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么

f(n-1) = f(n-2) + f(n-3) + ... + f(0)

同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去... ，那么

f(n) = f(n-1) + f(n-2) + ... + f(0)

综上可得f(n) - f(n-1) = f(n-1)

即f(n) = 2*f(n-1)

所以 f(n) 是一个等比数列

1、递归 

class Solution {
public:
    int jumpFloorII(int target) {
        if (target <= 0)  return -1;
        else if (target == 1)  return 1;
        else  return 2 * jumpFloorII(target - 1);
    }
};

2、位移 

class Solution {
public:
    int jumpFloorII(int target) {
        if (target <= 0)  return -1;
        return 1<<(target-1);
    }
};

3、指数

class Solution {
public:
    int jumpFloorII(int number) {
        if (target <= 0)  return -1;
        return (int)pow(2, number-1);
    }
};

int jumpFloorII(int number ) {
    if (number <= 0) {return -1;}
    return 1 << (number - 1);
}

public class Solution {
    public int jumpFloorII(int target) {
        if (target <= 0) {return -1;}
        return 1 << (target - 1);
    }
}

【Kotin解法】

object Solution {
    fun jumpFloorII(number: Int): Int  {
        if (number <= 0) {return -1}
        return 1 shl (number - 1)
    }
}

【Rust解法】

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    pub fn jumpFloorII(&self, number: i32) -> i32 {
        if (number <= 0) {return -1}
        1 << (number - 1)
    }
}