【杂题】剑指 Offer 10- II. 青蛙跳台阶问题

共以下 5 个回答

• kfaebot 普通 2024年5月10日 下午9:35

  class Solution {
  public:
      int trainWays(int num) {
          int MOD=1000000007;
          //包含0
          if(num==0){
              return 1;
          }
          if(num>0&&num<=2){
              return num;
          }
          int f1=1;
          int f2=2;
          for(int i=3;i<=num;i++){
              int sum=(f1+f2)%MOD;
              f1=f2;
              f2=sum;
          }
          return f2;
  
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 王位詮釋 普通 2024年4月14日 下午7:48

  class Solution {
      public int trainWays(int num) {
          final int MOD = 1000000007;
          if(num==0){
              return 1;
          }
          if(num<=2){
              return num;
          }
          int first = 1;
          int second = 2;
          for(int i=3;i<=num;i++){
              int temp = first+second;
              first = second;
              second = temp%MOD;
          }
          return second;
      }
  }
  思路：小青蛙一次可以跳一阶，也可以跳两阶，所以如果要知道跳num阶有多少中情况，只需要之后num-1或者num-2有多少阶就好了。
  时间复杂度：O(n)
  空间复杂度：O(1)
  

  0 赞同 0 条回复

  登录以回复
• 白雪公主倒拔垂杨柳 永久会员 2024年4月10日 下午4:24

  class Solution {
      public int trainWays(int num) {
          if(num<=1) return 1;
          if(num==2) return 2;
          int a=1;
          int b=2;
          int c=0;
          for(int i=3;i<=num;i++){
              c=(a+b)%1000000007;
              a=b;
              b=c;
          }
  
          return c;
      }
  }
  

  //时间复杂度On
  //空间复杂度O1

  0 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月6日 下午10:09

  class Solution {
  public int trainWays(int num) {
  if(num 0) return 1;
  if(num 1) return 1;
  int num1 = 1;
  int num2 = 1;
  int sum = 0;
  for(int i = 0; i <= num – 2; i++){
  sum = (num1 + num2) % 1000000007;
  num1 = num2;
  num2 = sum;
  }
  return sum;
  }
  }
  //时间复杂度On
  //空间复杂度O1

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月5日 下午7:50

  时间：O(n)
  空间：O(1)

  “`c++
  class Solution {
  public:
  constexpr static int mod = 1000000007;
  int trainWays(int num) {
  if (num <= 1) return 1; int s0 = 1, s1 = 1, s2; for (int i=2; i<=num; i++) { s2 = (s0 + s1) % mod; s0 = s1; s1 = s2; } return s2; } }; ```

  0 赞同 0 条回复

  登录以回复