1

分享

70. Climbing Stairs(C++)

70. Climbing Stairs、Leetcode、費波那契數
筆記
費波那契數
  • 前面兩數相加等於下一個數字
  

1  2  3  5  8  13  21  ...... // 5+8=13、8+13=21

70. Climbing Stairs

題目:你在爬樓梯。 需要n步才能到達頂部。 每次您可以爬 1 步或 2 步。 你可以通過多少種不同的方式登上頂峰?
回傳:多少種不同的方式(int)。
例如1:
Input: n = 2
  • 1+1
  • 2
  

Output: 2

例如2:
Input:n = 3
  • 1+1+1
  • 1+2
  • 2+1
  

Output: 3

Code(費波那契數)

  

#include <iostream>

#include <algorithm>

using namespace std;

int climbStairs(int n) {

    int cal1=0;

    int cal2=1;

    int i=0;

    while(i<n){

        if(cal1<cal2){

            cal1+=cal2;

        }

        else{

            cal2+=cal1;

        }

        i++;

    }

    return max(cal1,cal2);

}


int main(){

    cout<<climbStairs(5)<<endl;

}

筆記 leetcode c語言

費波那契數

Output

  

8

Code(排列組合)

  • 使用階乘計算,排列組合(1和2排隊,同個物種,不重複)
Input:n = 5
1、1、1、1、1排隊 = 1種
1、1、1、2排隊 = 4!/(3!1!) = 4種
1、2、2排隊 = 3!/(1!2!) = 3種
失敗:數字超過long long最大值,所以只能算到n=33
  

#include <iostream>

using namespace std;

long long factorial(int cal){

    long long factor=1;

    for(int i=1; i<=cal; i++){

        factor*=i;

    }

    return factor;

}

int climbStairs(int n) {

    int cal1=n;

    int cal2=0;

    int ans=0;

    while(cal1>=0){

        ans+=factorial(cal1+cal2)/(factorial(cal1)*factorial(cal2));

        cal1-=2;

        cal2++;

    }

    return ans;

}

int main(){

    cout<<climbStairs(5)<<endl;

}

筆記 leetcode c語言

排列組合

Output

  

8

參考資料

[1]. Climbing Stairs - LeetCode
[2]. 斐波那契數 - 維基百科,自由的百科全書 (wikipedia.org)
[3]. [LeetCode] 70. Climbing Stairs 爬楼梯问题 - Grandyang - 博客园 (cnblogs.com)
#筆記  #leetcode  #c語言 
分類:學習

【關鍵字】:新手教學、Leetcode ; 【分類】:學習、理財。(目前C++新手教學第二章內容已完結)。建議或意見可私訊:https://reurl.cc/ze7L9k。文章有錯誤的地方還請留言指正,謝謝各位

評論
上一篇
  • 69. Sqrt(x) (C++)
  • 下一篇
  • 83. Remove Duplicates from Sorted List(C++)
  • 更多文章
    載入中... 沒有更多了