点击这里给我发消息【本站不支持IE浏览器】请使用浏览器极速模式浏览本站--效果更佳~!要辅助游戏社区 让游戏简单一点-www.ucxia.com

网站首页 / 精品软件 / 正文

剑指offer面试题牛客_递归和循环_变态跳台阶(java版)

2019-07-06 休闲人生 精品软件 113 ℃ 0 评论

welcome to my blog

剑指offer面试题牛客_递归和循环_变态跳台阶(java版):

题目描述

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

思路

  • 见注释

使用f(n) = f(n-1)+f(n-2)+…+f(1)+f(0) 递归版 不推荐

public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)    这个递归式太长了, 能用是能用, 但是不妨化简一下
        */
        //execute
        if(target == 0) return 1;
        int res=0;
        for(int i=1; i<=target; i++)
            res = res + JumpFloorII(target - i);
        return res;
    }
}

使用f(n) = f(n-1)+f(n-2)+…+f(1)+f(0) 循环版 不推荐, 但要注意使用的是循环嵌套

public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)    这个递归式太长了, 能用是能用, 但是不妨化简一下
        */
        //input check
        if(target < 1) return 0;
        //execute
        int[] arr = new int[target+1];
        arr[0] = 1;
        for(int i=1; i<=target; i++)
            for(int j=i-1; j>=0; j--)
                arr[i] += arr[j];
        return arr[target];
    }
}

使用f(n) = 2f(n-1) 递归版

public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)
            2)f(n-1) = f(n-2)+...+ f(2) + f(1) + f(0)
            综合1)和2),得到f(n) = 2f(n-1), 这样的递归式就简洁了许多!
        */
        //input check
        if(target<1) return 0;
        //execute
        if(target==1) return 1;
        return 2*JumpFloorII(target-1);
    }
}

使用f(n) = 2f(n-1) 循环版(推荐)

public class Solution {
    public int JumpFloorII(int target) {
        //input check
        if(target<1) return 0;
        //execute
        if(target == 1) return 1;
        int[] arr = new int[target+1];
        arr[1] = 1;
        for(int i=2; i<=target; i++)
            arr[i] = 2*arr[i-1];
        return arr[target];
    }
}

使用f(n) = 2^(n-1); 不要弄错对谁移位! (最优解)

public class Solution {
    public int JumpFloorII(int target) {
        /*
        思路:
            1)f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + f(0)
            2)f(n-1) = f(n-2)+...+ f(2) + f(1) + f(0)
            综合1)和2),得到f(n) = 2f(n-1), 这样的递归式就简洁了许多!
            进一步地, f(n) = 2f(n-1)= 2*2f(n-2)=2*2*2f(n-3)= 2^(n-1)*f(1)= 2^(n-1)  学好数学很关键!
        */
        //input check
        if(target<1) return 0;
        //execute
        return 1 << (target-1); //注意是谁移位!!!!! 是1, 不是2!!!!
    }
}

Tags:

猜你喜欢

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

请填写验证码
«   2020年2月   »
12
3456789
10111213141516
17181920212223
242526272829
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接
  • 订阅本站的 RSS 2.0 新闻聚合

网站公告★客服QQ游戏侠客服×

看片片提示:最新电影资源【少年的你】提供了。
看片片提示:XXX级电影资源【姐妹狂艳】已开放。
看片片提示:最新枪版电影资源【银河补习班】已开放。
辅助更新:皮皮搞笑【决斗英雄】自瞄加速已开放合作--【神仙工具】里有信息
看片片提示:最新枪版电影资源【蜘蛛侠:英雄远征】已开放。
恭喜张先生:预购QQ:52013 + 52014(我爱你一生,我爱你一世) 押金50000元
恭喜王先生:定购QQ:33***(靓号已激活)。 订购金500元已完成
看片片提示:赵哥需要的片片(日本妈妈2)已上架。 请注意观看
恭喜李先生:定购QQ:66***(靓号已激活)。 订购金1100元已完成
恭喜刘先生:定购QQ:520***(靓号已激活)。 订购金3300元已完成
恭喜张女士:定购QQ:888**0 + 888**1(靓号已激活)。 订购金4600元已完成
恭喜孙先生:盗号QQ:77***(盗号已交付)。 订购金5300元已完成
看片片提示:酒哥需要的片片(日本肉肉)已上架。 请注意观看
恭喜马女士,预购QQ:13520 + 13521(一生我爱你情侣号) 押金60000元
恭喜金女士:定购QQ:99***(靓号已激活)。 订购金1300元已完成
看片片提示:胖子需要的片片(金瓶梅)已上架。 请注意观看
看片片提示:三军需要的片片(老师好)已上架。 请注意观看
恭喜樊先生:定购QQ:1988****(生日号已激活)。 订购金200元已完成
恭喜王女士:定购QQ:7878** + 7878**(情侣号已激活)。 订购金3300元已完成
恭喜冯先生:盗号QQ:386****(盗号已交付)。 订购金300元已完成
恭喜刘女士:盗号QQ:999**(盗号已交付)。 订购金6300元已完成
★①:QQ靓号视频仅支持火狐浏览器~★②:承接QQ盗号,先盗号后付款 QQ81801116~★①:需要看片片的留言给我第二天就有了~★②:神仙工具就是游戏辅助(非外挂)各种内部或免费的都 有