《算法零基础100讲》

该栏目是CSDN@英雄哪里出来大佬的万人千题计划第一阶段，其目标是让想要学会算法的人抱团成长，能通过这个项目稳步成长，扎扎实实掌握算法，最终用算法改变世界！

大佬将算法学习的路线总结如下，并分别根据五步路线总结写出了相应的教学内容，关于目前的第一阶段算法入门的详细的介绍可以看博文《万人千题：第一阶段，算法零基础抱团打卡》学习路线指引

100讲的学习大纲如下：

本学习笔记是根据该项目进行的每讲总结，目标是总结归纳复盘，扩展并实实在在掌握学习内容。

每一讲的笔记内容大致分为四个部分：What(记住)、Where(扩展)、How(运用)、Draw：

1. What(记住)的内容是基础概念和预备知识汇总；
2. Where(扩展)的内容是通过更多资料探索知识点，进行扩展和理解；
3. How(运用)是根据讲后习题进行的练习和模板总结；
4. Draw是试图用图示的方式将所学内容进行可视化，方便记忆和内化。

2.数列

What(记住)

数列是一列两个以上按顺序排列的数，所组成的序列，记为 ⟨$a_k$⟩ 、 {$a_k$} 或 ($a_k$)：
$${⟨a_k⟩}_{k=1}^n=⟨a_1,a_2,a_3,\cdots ,a_n⟩{⟨a_k⟩}_{k=1}^n=⟨a_1,a_2,a_3,\cdots ,a_n⟩$$

几个重要的数列：

• 等差数列：数列中，从第二项起，每一项与前一项的差相等。
• 等比数列：从第2项起，每一项与前一项的比都是一个常数。
• 斐波那契数列：首两项均是1，从第3项起，每一项均为前两项的和。
  以数学符号表示，即$a_1=a_2=1，且对于n\ge 3n\ge 3，a_n=a_{n-1}+a_{n-2}$。
• 素数数列：数列中的数据均为素数，目前找不到规律：2 ,3 ,5 ,7 ,11 ,13 ,17…………

数列通项公式的几种求解方式：

• 数学归纳法
• 逐差全加
• 逐商全乘
• 从和式求通项
• 换元法
• 不动点法

数组(计算机角度的数列)的作用：

• 记录一组特殊的值，可以使用
• 通过一定的规律计算得出想要的结果
• 分析数列的特征

Where(扩展)

1. 数列可以看作定义域为正整数集上的特殊函数.运用函数思想去研究数列，就是要借助于函数的单调性、图象和最值等知识解决相关问题，它不仅使问题简化，而且还可以加深对知识间的关系的理解.
2. 运用方程思想，分析数列的规律，获得递推公式，可以通过方程解决数列问题.
3. 不同的数据适用不同的场景，分类讨论思想根据问题的实际需要按一定标准将所研究的对象分成若干种不同的情况，可以使问题清晰.
4. 数学概念都是从现实问题求解的思想方法中进行高度的抽象、提炼出来的。存在性和唯一性是数学概念中最基本、最核心的性质。
5. 引入的每一个数学概念，首先初步学习概念、并利用概念解决简单结构的问题，形成初步的结论。之后，为研究、解决更一般或更复杂的对象，可引入相应的性质，进行求解。
   

How(运用)

509. 斐波那契数

1137. 第 N 个泰波那契数

int tribonacci(int n){int T[4] = {0, 1, 1, 2};enum {first = 0, second, curr, next};if (n < 4) {return T[n];}for (int i = 3; i <= n; ++i) {T[next] = T[first] + T[second] + T[curr];T[first] = T[second];T[second] = T[curr];T[curr] = T[next];}return T[curr];
}

剑指 Offer 64. 求1+2+…+n

int sumNums(int n){int A = n;int B = n + 1;int ans = 0;//当b为偶数，a*b=2a * b/2;当n为奇数，a*b=(b-1)/2 * 2a+a(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;return ans >> 1;}

896. 单调数列

bool isMonotonic(int* nums, int numsSize){if (numsSize == 1)   {return true;}int preDiff = nums[1] - nums[0] ? ((nums[1] - nums[0])/fabs(nums[1] - nums[0])) : nums[1] - nums[0];int newDiff = 0;for (int i = 1; i < numsSize; ++i) {printf("%d ", preDiff);if (nums[i] - nums[i-1]) {printf("%d ", nums[i] - nums[i-1]);newDiff = (nums[i] - nums[i-1])/fabs(nums[i] - nums[i-1]);}if (preDiff && newDiff != preDiff) {printf("%d ", newDiff);return false;}if (preDiff == 0) {preDiff = newDiff;}}return true;
}

1. 有已知递归公式，只需要计算特定值，可以只记录需要的数据，减少使用的空间；
2. A 和 B 两数相乘的时候可以利用加法和位运算来模拟：将 B 二进制展开，如果 B 的二进制表示下第 ii 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i)A∗(1<<i) ，即 A<<iA<<i。

参考资料

此处列出除文中链接之外的参考资料

1. 数列-维基百科
2. 数列中的几种数学思想
3. 数学性质的结构与应用思想——从数列极限的性质谈起
4. 学会这几招，可以秒杀所有数字推理！
5. 数列――找规律
6. 数列
7. 集合入门
8. Leetcode官方题解-剑指 Offer 64. 求1+2+…+n