秦怀杂货店

General Store

  • 首页
  • 文章归档
  • 标签
  • 分类
  • 关于页面

  • 搜索
随便聊聊 数据结构 小游戏 数据库 Docker Springboot 系统设计 雪花算法 分布式 海量ip 最长回文子串 算法 面试题 线程池 多线程 线程 java学习 布隆过滤器 github 架构设计 docsify Git JVM LeetCode 杂货思考 设计模式 Lambda native isAssignableFrom 反射 剑指Offer mybatis SPI JDBC 编程工具 Java基础 集合

剑指Offer【9】--跳台阶变态版

发表于 2020-11-03 | 分类于 剑指Offer | 0 | 阅读次数 237

[toc]

题目描述

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

思路和解法

首先青蛙一次可以跳1,2,3到n级。假设函数是f(n),则:

  • 青蛙跳到第一级是f(1)=1,只有一种跳法。
  • 青蛙跳到第二级,可以是直接跳到第二级,也可以是从第一级直接跳。所以f(2)=f(1)+1
  • 青蛙跳到第三级,可以从第0级跳,也可以从第1级跳,也可以从第2级跳。所以f(3) =f(1)+f(2)+1;
  • 依次类推,青蛙跳到第n级,可以是从0,1,2,3..(n-1)级跳,所以f(n)=f(1)+f(2)+f(3)...+f(n-1)+1;

因此我们需要双层for循环即可完成。

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

完成之后我们可以顺便推一下公式:
$$
f(n)= f(1)+f(2)+...+f(n-2)+f(n-1)+1;\newline
f(n-1)=f(1)+f(2)+...+f(n-2)+1;\newline
f(n)-f(n-1)=f(n-1);\newline
f(n)=2*f(n-1);\newline
$$

所以最后我们可以推倒出:
$$
f(n) = 2^

$$

show you the code:

public class Solution {
    public int JumpFloorII(int target) {
        return (int) Math.pow(2, target - 1);
    }
}
  • 本文作者: 秦怀杂货店
  • 本文链接: http://aphysia.cn/archives/jianzhioffer9
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 随便聊聊 # 数据结构 # 小游戏 # 数据库 # Docker # Springboot # 系统设计 # 雪花算法 # 分布式 # 海量ip # 最长回文子串 # 算法 # 面试题 # 线程池 # 多线程 # 线程 # java学习 # 布隆过滤器 # github # 架构设计 # docsify # Git # JVM # LeetCode # 杂货思考 # 设计模式 # Lambda # native # isAssignableFrom # 反射 # 剑指Offer # mybatis # SPI # JDBC # 编程工具 # Java基础 # 集合
剑指Offer【8】--用两个栈实现队列
剑指Offer【10】--矩形覆盖
  • 文章目录
  • 站点概览
秦怀杂货店

秦怀杂货店

纵然缓慢,驰而不息。

145 日志
19 分类
37 标签
Github E-mail
Creative Commons
0%
© 2022 秦怀杂货店
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4