2021.01.04 斐波那契数列
今日题目：斐波那契数列，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
- 思路：很明显采用递归调用，递归结束的条件是n=0或n=1；其他情况则继续递归。
- 缺陷：代码是很简单，但是若递归次数过多即n过大的话，就会出现栈溢出的情况。
- 自己的菜鸡代码：
其他人的代码（采用非递归的方式）：class Solution {public int fib(int n) {if(n == 0) return 0;else if(n == 1) return 1;else return fib(n-1) + fib(n-2);}}
递归（下）与非递归（上）方式的比较：递归中有许多计算是重复的，因此时间开销较大，非递归的方式的运行时间明显较短class Solution {public int fib(int n) {if(n==0) return 0;if(n==1) return 1;int p0=0,p1=1,res=0;for(int i=2;i<=n;i++){res=p0+p1;p0=p1;p1=res;}return res;}}
递归调用树如图：
2021.01.05 斐波那契数列（有点差别）
今日题目：斐波那契数列（有点差别）
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
提示：0 <= n <= 100
- 思路：
- 法一：采用迭代的方式计算
- 法二：看评论区看到了动态规划解决这个问题的方法。（等俺复习了再来补充8 唉）
- 自己的菜鸡代码：
class Solution {public int fib(int n) {// 采用非递归的方式进行，可以省不少时间if(n == 0) return 0;if(n == 1) return 1;int f0 = 0, f1 = 1,temp = 0;for(int i = 2; i <= n; i++){temp = (f1 + f0) % 1000000007;f0 = f1;f1 = temp;}return (int)f1;}}
运行结果：
2021.01.20 求1+2+···+n
今日题目：求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
限制：1 <= n <= 10000
- 思路：
- 法一：感觉这里可以用递归解决。（违规使用 if ）
- 法二：确实是使用递归，但是没有用到 if 。在没有 if 的情况下要如何终止递归呢？可以利用逻辑符的短路效应。例如： && 只要左边为false，就不会继续判断右边； || 只要右边为true就不会继续判断右边。所以可以利用逻辑符来终止递归。
- 时间复杂度 O(n) ： 计算 n + (n-1) + … + 2 + 1 需要开启 n 个递归函数。
- 空间复杂度 O(n) ： 递归深度达到 n ，系统使用 O(n) 大小的额外空间。
- 自己的菜鸡代码：
```java
// 法一：违规作废
class Solution {
public int sumNums(int n) {
} }if(n == 1) return 1;return n + sumNums(n - 1);
// 法二 class Solution { public int sumNums(int n) { boolean x = n > 1 && (n += sumNums(n - 1)) > 0; return n; } }
- 运行结果：法一：本来想着可以用递归，结果违规使用了if。<br />法二：利用逻辑符的短路效应。<br /><a name="a6t7x"></a>### 2021.02.01 数值的整数次方（好气）今日题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。<br /><br />**说明:**- -100.0 < _x_ < 100.0- _n_ 是 32 位有符号整数，其数值范围是 [−2, 2− 1] 。- 思路：快速幂：- 自己的菜鸡代码：```javadouble result = 1.0;for (int i = n; i != 0; i /= 2) {if ((i&1) == 1) {result *= x;}x *= x;}if (n < 0) {result = 1 / result;}return result;
- 运行结果：
若有收获，就点个赞吧
0 人点赞
