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

共以下 11 个回答

• 九号球 普通 2023年12月3日 下午8:35

  “`java
  //for循环
  class Solution {
  public int fib(int n) {
  if (n <= 1) { return n; } int n1 = 0; int n2 = 1; int mod = 1000000007; for (int i = 2; i <= n; i++) { int tmp = n2; n2 = (n1 + n2)%mod; n1 = tmp; } return n2; } }

  0 赞同 0 条回复

  登录以回复
• 张开怀 普通 2023年7月24日 下午8:15

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

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

  0 赞同 0 条回复

  登录以回复
• yxy 普通 2023年7月24日 下午3:05

  时间O(n)

  const int m = 1e9+7;
  class Solution {
  public:
      int fib(int n) {
          if(n==0) return 0;
          if(n==1) return 1;
          int a=0,b=1,c=0;
          for(int i=2;i<=n;i++)
          {
              c=(a+b)%m;
              a=(b)%m;
              b=(c)%m;
          }
          return c;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 小吕 普通 2023年7月24日 下午2:34

  c++实现
  int fib(int n) {
  int MOD = 1000000007;
  if(n<2)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 条回复

  登录以回复
• mpweixin用户 永久会员 2023年7月24日 上午11:45

  class Solution {
  //时间O(n) 空间 O(n)
      public int fib(int n) {
          if(n < 2){
              return n;
          }
          long[] dp = new long[n + 1];
          dp[0] = 0;
          dp[1] = 1;
          for(int i = 2;i <= n;i++){
              dp[i] = (dp[i - 1] + dp[i - 2])%1000000007;
          }
          return (int)dp[n];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Vow the vow。 普通 2023年7月24日 上午11:08

  时间复杂度O(n)

  public int fib(int n) {
          int[] dp = new int[n+3];
          int mod = 1000000007;
          dp[0] = 0;
          dp[1] = 1;
          for(int i = 0; i <= n; i++){
              dp[i+2] = (dp[i+1] + dp[i])%mod;
          }
          return dp[n];
      }
  

  0 赞同 0 条回复

  登录以回复
• 哈哈哈哈开开心心 普通 2023年7月24日 上午1:48

  class Solution:
      def fib(self, n: int) -> int:
          if n == 0:
              return 0
  
          a, b = 0, 1
          for _ in range(2, n + 1):
              tmp = b
              b += a
              a = tmp
  
          return b % 1000000007
  

  可优化

  0 赞同 0 条回复

  登录以回复
• 花老爷 普通 2023年7月23日 下午5:22

  动态规划
  时间：O(n)
  空间：O(1)

  class Solution {
      private static final int MOD = 1000000007;
  
      public int fib(int n) {
          int first = 0, second = 1;
          for (int i = 2; i <= n; i++) {
              int temp = (first + second) % MOD;
              first = second;
              second = temp;
          }
          return n > 0 ? second : first;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 怀瑾 永久会员 2023年7月23日 下午3:56

  C++实现

  “`C++
  public int fib(int n) {
  if(n <= 1) return n; int a = 0, b = 1; int c = 2; for(int i = 2; i <= n; i++) { c = (a + b) % 1000000007; a = b; b = c; } return c; } ```

  0 赞同 0 条回复

  登录以回复
• Yodl. 普通 2023年7月23日 下午3:47

  //动态规划
  class Solution {
  public:
      int fib(int n) {
          if(n==0)
          {
              return 0;
          }
          if(n==1)
          {
              return 1;
          }
          int dp[n+1];
          dp[0]=0;
          dp[1]=1;
          for(int i=2;i<=n;i++)
          {
              dp[i]=(dp[i-1]+dp[i-2])%1000000007;//dp[i]=dp[i-1]+dp[i-2];
          }
          return dp[n];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Ming 普通 2023年7月23日 下午3:33

   public int fib(int n) {
          if(n <= 1) return n;
          int a = 0, b = 1;
          int c = 2;
          for(int i = 2; i <= n; i++) {
              c = (a + b) % 1000000007;
              a = b;
              b = c;
          }
          return c;
      }
  

  防止溢出，赋值c前先取余

  0 赞同 0 条回复

  登录以回复