【杂题】剑指 Offer 10- I. 斐波那契数列

共以下 6 个回答

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

  class Solution {
  public:
      int fib(int n) {
          //取模
          int MOD=1000000007;
          if(n<2){
              return n;
          }
          int f0=0;
          int f1=1;
          for(int i=2;i<=n;i++){
              int sum=(f0+f1)%MOD;
              f0=f1;
              f1=sum;
          }
          return f1;
      }
  };
  

  0 赞同 0 条回复

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

  class Solution {
      public int fib(int n) {
          final int MOD = 1000000007;
          if(n<=1){
              return n;
          }
          int first = 0;
          int second = 1;
          for(int i=2;i<=n;i++){
              int temp = first+second;
              first = second;
              second = temp%MOD;
          }
          return second;
      }
  }
  时间复杂度：O(n)
  空间复杂度：O(1)
  需要注意题意里的取模部分，给我恶心坏了
  

  0 赞同 0 条回复

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

  class Solution {
      public int fib(int n) {
          // 特殊情况
          if( n <= 1){
              return n;
          }
  
          // int[] dp = new int[n+1];
  
          // dp[0]=0;
          // dp[1]=1;
          int a =0;
          int b=1;
          int c=0;
  
          // if(n==0) return b;
          // if(n==1) return 1;
  
          for(int i=2;i<=n;i++){
              c=(a+b)%1000000007;
              a=b;
              b=c;
          }
  
          return c;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Jimmy 普通 2024年4月6日 下午11:00

  时间复杂度O(n)，空间复杂度O(1)

  class Solution {
  private:
      int mod = 1000000007;
  public:
      int fib(int n) {
          if(n<=1)return n;
          int p=0,q=0,r=1;
          for(int i=2;i<=n;i++)
          {
              p = q;
              q = r;
              r = (p+q)%mod;
          }
          return r;
      }
  };
  

  0 赞同 0 条回复

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

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

  0 赞同 0 条回复

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

  时间复杂度：O(n)
  空间：O(1)

  “`c++
  class Solution {
  public:
  const int mod = 1000000007;
  int fib(int n) {
  if (n <= 1) return n; int f0 = 0, f1 = 1, f2; for (int i=2; i<=n; i++) { f2 = (f0 + f1) % mod; f0 = f1; f1 = f2; } return f2; } }; ```

  0 赞同 0 条回复

  登录以回复