⭐️跳台阶扩展问题⭐️

🔐题目详情

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

数据范围：1≤n≤20
进阶：空间复杂度 O(1) ， 时间复杂度O(1)

示例1

输入

3

输出

4

示例2

输入

1

输出

1

链接：跳台阶扩展问题

💡解题思路

基本思路： 数学
解题思路：
每次跳的台阶级数不受限，但是换汤不换药，思考的方法是一样的。
1.当n=1或n=2时，青蛙跳台阶跳法次数和没修改条件时是一样的，n=1有一种跳法，n=2有两种跳法。
2.当n>2时，同理我们将青蛙跳n级台阶时的跳法记成函数f(n)。但是青蛙在第一次的选择不仅仅是跳1级和跳2级，它还可以选择跳3,4,5,…,n级。所以青蛙跳一次后还会剩n-1，n-2，n-3，…，2, 1, 0级台阶。
此时，f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(2)+f(1)+1
同理，f(n-1)=f(n-2)+f(n-3)+f(n-4)+…+f(2)+f(1)+1
合并上面两个式子得，f(n)=2*f(n-1)
3.根据2的推论得出一个等比数列，由此我们还可以进一步推导：
🍁推导1：f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(2)+f(1)+1
=1+f(1)+f(2)+…+f(n-2)+f(n-1)
=1+2^0^*f(1)+2^1^*f(1)+…+2^n-3^*f(1)+2^n-2^*f(1)
=1+(2^0^+2^1^+2^2^+…+2^n-3^+2^n-2^)
=1+(2^n-1^-1)
=2^n-1^
f(1) = 1，f(2) = 2，f(n)为公比的2的等比数列（n>2）
🍁推导2：f(1) = 2^0^, f(2) = 2^1^, f(3) = 2^2^…, f(n-1) = 2^n-2^, f(n) = 2^n-1^

🔑源代码

使用推导出的递推式： $f(n)=2*f(n-1)， 其中f(1)=1.$

使用递归：

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

不使用递归：

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

直接使用最终结论：跳上 $n$级台阶的方案数有 $2^{n-1}$种。

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

🌱总结

本题为数学推理题，斐波拉契数列的变式题，最难的部分是递推公式的推导。

⭐️快到碗里来⭐️

🔐题目详情

小喵们很喜欢把自己装进容器里的（例如碗），但是要是碗的周长比喵的身长还短，它们就进不去了。

现在告诉你它们的身长，和碗的半径，请判断一下能否到碗里去。

输入描述:

输入有多组数据。

每组数据包含两个整数n (1≤n≤2^128) 和r (1≤r≤2^128)，分别代表喵的身长和碗的半径。

圆周率使用3.14。

输出描述:

对应每一组数据，如果喵能装进碗里就输出“Yes”；否则输出“No”。

示例1

输入

6 1
7 1
9876543210 1234567890

输出

Yes
No
No

链接：快到碗里来

💡解题思路

基本思路： 使用BigDecimal类或大数乘法模拟

解题思路：
使用BigDecimal类，由于输入的数据非常大超过了int long等数据类型的范围，我们可以使用BigDecimal类来做，Scanner类中有一个nextBigDecimal方法可以读取BigDecimal对象，然后再构造一个值为2*3.14的BigDecimal对象（建议使用字符串构造，精度更高），使用BigDecimal对象中的multiply方法进行乘法运算，最终根据得到的碗周长结果与猫身长大小输出Yes或者No。

另外一个更加底层的思路，使用大数乘法模拟乘法的计算，基本思路就是将输入数据以字符串的形式进行输入，存入数组中，然后将数组的元素对应相乘，再取模保留，取除数进位，最后按照顺序输出即可，解题代码后续更新，占个坑。

🔑源代码

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            BigDecimal n = sc.nextBigDecimal();
            BigDecimal r = sc.nextBigDecimal();
            BigDecimal c = new BigDecimal("6.28").multiply(r);
            System.out.println(n.compareTo(c) <= 0 ? "Yes" : "No");
        }
    }
}

🌱总结

本题为大数计算题，在java中可以使用BigDecimal类来进行数据的计算，也可以使用大数乘法进行计算（面试官更想得到的答案）。