【算法刷题日记之本手篇】跳台阶扩展问题与快到碗里来

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【跳台阶扩展问题】和【快到碗里来】，展示语言java。

小贴士：本专栏所有题目来自牛客->面试刷题必用工具

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年9月13日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬推荐在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

---

注意事项：本专栏所有题目都来自牛客网，如果有小伙伴还没有注册牛客，可以点击下方链接进行注册，注册完就能立即刷题了。不仅是刷题，上面还有很多有关就业的面经，面试题库，以及名企的模拟面试，我非常推荐它，博主自己用的也很多，也刷了不少题了！下图可以作证：

注册地址：牛客网

有关任何问题都可以与博主交流，你可以在评论区留言，也可以私信我，更可以加上博主的vx与博主一对一交流（文章最下方有）。

---

⭐️跳台阶扩展问题⭐️

🔐题目详情

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

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

示例1

输入

3
1

输出

4
1

示例2

输入

1
1

输出

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⁰*f(1)+2¹*f(1)+…+2^n-3*f(1)+2^n-2*f(1)
=1+(2⁰+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⁰, f(2) = 2¹, f(3) = 2²…, f(n-1) = 2^n-2, f(n) = 2^n-1

🔑源代码

使用推导出的递推式：$f(n)=2\ast 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);
    }
}
1
2
3
4
5
6
7
8

不使用递归：

public class Solution {
    public int jumpFloorII(int target) {
        if (target < 0) return -1;
        int f = 1;
        while (--target > 0) {
            f = 2 * f;
        }
        return f;
    }
}
1
2
3
4
5
6
7
8
9
10

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

public class Solution {
    public int jumpFloorII(int target) {
        return 1 << (target - 1);
    }
}
1
2
3
4
5

🌱总结

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

⭐️快到碗里来⭐️

🔐题目详情

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

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

输入描述:

输入有多组数据。

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

圆周率使用3.14。
1
2
3
4
5

输出描述:

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

示例1

输入

6 1
7 1
9876543210 1234567890
1
2
3

输出

Yes
No
No
1
2
3

链接：快到碗里来

💡解题思路

基本思路： 使用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");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

🌱总结

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

---

到文章最后，再来安利一下吧，博主也是经常使用，并且也经常在牛客上刷题，题库也非常丰富：牛客网，刷题，面试，内推都有。也欢迎与博主交流有关刷题，技术方面，以及与博主聊聊天，交个朋友也好啊，毕竟有朋自远方来！

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！