【leetcode刷題】30.青蛙跳台階——Java版

前言

哈喽，大家好，我是一條。

糊塗算法，難得糊塗

發現很多劍指offer的題目都是leetcode熱題改的，是以我們既可以複習，還可以刷一波面試題，nice😉

Question

劍指 Offer 10- II. 青蛙跳台階問題

難度：簡單

一隻青蛙一次可以跳上1級台階，也可以跳上2級台階。求該青蛙跳上一個 n 級的台階總共有多少種跳法。

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請傳回 1。

示例 1：

輸入：n = 2

輸出：2

示例 2：

輸入：n = 7

輸出：21

示例 3：

輸入：n = 0

輸出：1

提示：

0 <= n <= 100

Solution

和爬樓梯，斐波那契數列一樣

定義初始值

狀态轉換

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第30/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

大家可以先自己找一下擷取方式，尋寶遊戲現在開始。

如果實在找不到可以評論區留言或私信我領取，不過一定要先關注哦！不然無法發私信！