引言
2022年初，开始养成了一个习惯，刷一些LeetCode题目，一直是自学。近期，CSDN官方正好发起了一个 14天阅读挑战赛，《趣学算法》的作者带着大家一起来学习，趁这个机会，一方面深入学习一下，另外一方面，想要对2022年前面9个月刷题的经验，进行一下总结。
还是小编的老方法，开始阅读一本书之前，大家先要脑子里进行一下头脑风暴，你想要从这本书中学到什么？或者说，更加明确一点，想要解决哪些问题？带着一些目的或者问题去阅读一本技术类的书籍，相信可以学到更多。
说一点阅读后的直接感受，这本书和之前看过的很多算法类的书籍不太一样，之前阅读过的基本，都是侧向与先将算法的基本理论说明白，然后举一些经典简单例子，说明验证。而这本书，在讲完一些理论之后，往往不是用经典的例子，而是用一些常见的复杂问题，把复杂问题拆解为简单问题，一方面达到了把相关理论知识实践深化的目的，另外一方面，对于一些复杂问题简单化，常常会给我带来一个感受原来这个问题还能这样解决呀~~~~。
书籍分为三部分：
- 第一部分：算法入门介绍
- 第二部分：经典算法
- 第三部分：实用算法
1. 第一章知识点
1.1 算法复杂性的衡量
如何衡量一个算法的好坏？我们常常用的是时间复杂度和空间复杂度。
时间复杂度： 算法运行需要的时间，一般讲算法的执行次数，作为时间复杂度的度量标准。
我们场景的时间复杂度有常数阶、多项式阶、指数阶、对数阶，他们之间的关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)
我们在设计算法时候，要注意算法复杂度增量的问题，尽量避免爆炸级增量
空间复杂度： 算法运行占用的空间大小，一般讲算法的辅助空间，作为空间复杂度的度量标准。
这个其实很好理解，就不多说了，一个算法执行所占的空间实际上有输入输出占用的空间、辅助变量占用的空间、算法本身占用的空间，和时间复杂度量化一样，一般我们仅考虑辅助空间占用情况，来作为空间复杂度的度量标准。
1.2 斐波那契数列的进化
现实的算法问题：
- 兔子序列问题：假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？
- 花瓣、叶子序列问题：观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花
的花瓣，可以发现它们的花瓣数目为斐波那契数：3，5，8，13，21，…，难道这些植物懂得斐波那契数列吗？应该并非如此，它们只是按照自然的规律才进化成这样的。这似乎是植物排列种子的“优化方式”，它能使所有种子具有相近的大小却又疏密得当，不至于在圆心处挤太多的种子而在圆周处却又很稀疏。
这里我们以兔子问题，来一步一步优化解决斐波那契数列问题。
这个数列有十分明显的特点，从第3个月开始，当月的兔子数=上月兔子数+当月新生
兔子数，而当月新生的兔子正好是上上月的兔子数。因此，前面相邻两项之和，构
成了后一项，即：
当月的兔子数=上月兔子数+上上月的兔子数
斐波那契数列如下：
1，1，2，3，5，8，13，21，34，…
递归式表达式：
1.2.1 第一种解法（递归）
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str_0 = scan.nextLine().trim();
int n = Integer.parseInt(str_0);
System.out.println(fib1(n));
scan.close();
}
/**
* 递归解法
*
* @Title: fib1
* @Description:
* @author: itbird
* @date 2022年10月19日 上午10:08:57
* @param n
* @return int 时间复杂度: O(指数级) 空间复杂度: O(N)
*/
public static int fib1(int n) {
if (n < 1) {
return -1;
}
if (n == 1 || n == 2) {
return 1;
} else {
return fib1(n - 1) + fib1(n - 2);
}
}
}
所以我们需要改进。
1.2.2 第二种解法（优化时间复杂度，以空间换时间）
既然递归解法，时间复杂度太高，那么我们想办法，通过空间换时间
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str_0 = scan.nextLine().trim();
int n = Integer.parseInt(str_0);
// System.out.println(fib1(n));
System.out.println(fib2(n));
scan.close();
}
/**
* 既然递归解法，时间复杂度太高，那么我们想办法，通过空间换时间
*
* @Title: fib2
* @Description:
* @author: itbird
* @date 2022年10月19日 上午10:20:59
* @param n
* @return int 时间复杂度: O(N) 空间复杂度: O(N)
*/
public static int fib2(int n) {
if (n <= 2) {
return 1;
}
int[] nums = new int[n];
nums[0] = 1;
nums[1] = 1;
for (int i = 2; i < nums.length; i++) {
nums[i] = nums[i - 1] + nums[i - 2];
}
return nums[n - 1];
}
}大家发现，这个算法的确可以解决时间复杂度的问题，而且输入50以上的n时，都可以很快得出结论，但是当输入的数字很大时，运行过程中，可能出现了内存溢出的问题。
仔细想想，这个算法中存在的缺点是，实际上我们仅仅需要nums[i] 、 nums[i - 1] 、 nums[i - 2]三个值，过程中的值，不需要保存，那么下一步优化，就优化这个方向。
1.2.3 第三种解法（优化时间&空间）
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str_0 = scan.nextLine().trim();
int n = Integer.parseInt(str_0);
// System.out.println(fib1(n));
// System.out.println(fib2(n));
System.out.println(fib3(n));
scan.close();
}
/**
* 解决算法2中，空间利用率低的问题
*
* @Title: fib3
* @Description:
* @author: itbird
* @date 2022年10月19日 上午10:21:39
* @param n
* @return int 时间复杂度: O(N) 空间复杂度: O(1)
*/
public static int fib3(int n) {
if (n <= 2) {
return 1;
}
int nums1 = 1;
int nums2 = 1;
int nums3 = 0;
for (int i = 2; i < n; i++) {
nums3 = nums1 + nums2;
nums2 = nums1;
nums1 = nums3;
}
return nums3;
}
}
