此系列文章的目的就是让非科班的前端同学迅速对计算机科班同学的必修课达到速成的效果，因为前端一般情况下对很多知识点的面试要求并不高，只需要具备基础理论素养一般就够用了，所以速成是完全可行的。

导航：
系列文章分为四部分，欢迎大家点赞，收藏，我们一起进步！

  • 计算机组成原理
  • 操作系统
  • 计算机网络
  • 数据结构和算法

这篇文章跟面试是强相关的，我采取基础理论（比如每一种数据结构的特点，增删改查的时间复杂度） + leetcode面试算法题的形式呈现给大家。闲话不说，开干！

1、预备知识

算法的时间复杂度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

举个例子：

  1. function A(n) {
  2.     for(let i = 0; i < n; i++) {
  3.         console.log(i)
  4.     }
  5. }

如上，其中（ 假如调用A(2000) ）

  • let i = 0总共执行了1次
  • i < n 执行了2001次
  • i++执行了2000次
  • console.log(i)执行了2000次

当调用A（2000），算法的频度如下

  1. T(2000) = 1 + 2001 + 2*2000;

因此可以推理出，问题规模n和时间开销T的关系,大概为

  1. T(n) = 3n + 1

在计算机领域，n只能趋近于无穷大，所以，就暂且只考虑这个无穷大的方向。所以T(n) = n(只考虑阶数高的部分)

也就是说例如时间复杂为T(n)=3n+2n此时的时间复杂度可以写成T(n)=n

下图为常见的时间复杂度和规模n的关系如下：
👍计算机基础理论速成系列 --- 数据结构和算法 - 图1

这里最需要记忆的就是前三种时间复杂度常用的比较低的情况logn、 n、 nlogn

算法的空间复杂度

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模，S(n)表示空间复杂度。
我们先上一个案例，如下图
👍计算机基础理论速成系列 --- 数据结构和算法 - 图2

如上，空间复杂度说白了（忽略程序代码占的内存空间），无论问题规模n怎么变，所占的空间都是常量，所以空间复杂度为 S(n) = O(1)
空间复杂度跟时间复杂度是一样的，只考虑n无穷大的时候，空间的复杂度。

3、线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表分为：顺序表（暂时理解为js的数组） 和 链表。我们首先介绍顺序表。

顺序表

顺序表的图形化表示如下，即“把所有数据用一根线儿串起来，再存储到物理空间中”
👍计算机基础理论速成系列 --- 数据结构和算法 - 图3 首先，大家看起来有点像数组，但是JS数组分两种（以V8引擎为例），一种是”快数组”，使用的是线性表（另一种是“慢数组”, 用的哈希。表结构，我们后面会讲）
需要注意的是，线性表有一些特点：

  • 表中元素具有逻辑上的顺序性，也就是元素之间是有排序的。
  • 表中元素数据类型都相同，也就是说每个元素占的内存空间是一样的。

所以我们讲的JS里的慢数组，要存储一样的类型，比如[1，2，3]都存数字类型。

接下来我们讲什么时候要用到数组（以下的数组我们指的是js里的”慢数组”，也就是存同样类型的元素）

我们先说结论：数组最大的优势在于查和改数据，是能达到O（1）的时间复杂度，你可以理解为最好的时间复杂度了，但是增加数据和删除数据就很不理想了，我们接下来仔细分析一下其中的原理。

在了解顺序表增删改查的时间复杂度之前，我们需要知道顺序表支持随机访问（随机访问是说你可以随意访问该数据结构中的任意一个节点），因为知道第一个元素的物理地址，可以推算剩下元素的物理地址。

举个例子，比如输数组 let a = [1, 2, 3]，因为a其实保存的是内存的一段地址，比如是内存编号21的地址，那么21指的就是a[0]的地址，也就是数组a的起始地址，又因为1，2，3这三个数字在内存的存储空间都是一样的，JavaScript 内部，所有数字都是以64位浮点数形式储存，即使整数也是如此。所以我们如果查询数组里2这个数字的内存地址，我们可以a(也就是内存编号21的变量) + 64位，同理，3这个数字在内存的地址是 a + 2*64位

👍计算机基础理论速成系列 --- 数据结构和算法 - 图4

顺序表插入时间复杂度分析

我们先假设有一个数组[‘a’, ‘c’, ‘g’, ‘w’, ‘f’]，然后我们准备给它元素末尾加一个元素’z’
插入操作的时间复杂度分析如下：
👍计算机基础理论速成系列 --- 数据结构和算法 - 图5
注意看图中文字，是解释为什么这次插入是O（1）复杂度。
上图是最好的情况，尾部插入的时间复杂度是常数级的：O(1)
平均的情况, 插入到任意位置的时间复杂度，首先每个位置可能被插入的机会是1/n+1，那么会循环从1到n（如下图），求极限的话，时间复杂度为：O(n/2) => O(n)

👍计算机基础理论速成系列 --- 数据结构和算法 - 图6
最坏情况插入到队首，时间复杂度是O(n)

顺序表删除时间复杂度分析

删除和插入原理是一样的，所以我们就直接把结论写出来：

  • 最好的情况是删除最后一个元素，时间复杂度是O(1)
  • 插入任意位置，时间复杂度是O(n)
  • 最坏情况删除到队首，时间复杂度是O(n)

顺序表按下标查和按下标改，我们之前推理过了，是O（1）

顺序表按值查找复杂度分析（意思是按数组里的值查找，不是按下标查找）

按值查找和插入原理是一样的，所以我们就直接把结论写出来：

  • 最好的情况是查找第一个元素，时间复杂度是O(1)
  • 查找任意位置，时间复杂度是O(n)
  • 最坏情况查找到最后一个元素（从第一个元素开始对比是否是要找的元素，一直循环到最后一个元素），时间复杂度是O(n)

为什么呢，你想想，你去查找值，是不是要挨个遍历，遍历你也不知道到底在第几个元素，可能是第n个，所以平均查找的复杂度是O（n）

leetcode面试题 —- 数组训练

腾讯面试题：验证回文字符串

leetcode地址：https://leetcode-cn.com/problems/valid-palindrome/

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

  1. 输入: "A man, a plan, a canal: Panama"
  2. 输出: true

示例 2:

  1. 输入: "race a car"
  2. 输出: false

这里我提供一个解决方法，大家可以去上面我给出的算法题的地址，去看看各种社区的答案。这道题很经典，比如我用的首尾双指针的做法，帮助你理解数组数据结构的特点。思路如下：

  • 先都转成大写（不然会出现 a A 判定为不相同）
  • 设置头尾双指针，开启循环
    • 如果指向的元素是不是有效的（不是字母和数字），则跳过
    • 如果指向的元素有效，但不相同，则不是回文，返回false
    • 否则有效，且相同，收缩指针，继续循环
  • 直至指针相遇，循环结束，始终没有返回false，返回true。
  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var isPalindrome = function(s) {
  6.     s = s.replace(/[^\w]/g, '').toLowerCase();
  7.     let leftPointer = 0;
  8.     let rightPointer = s.length - 1;
  9.     while(rightPointer > leftPointer){
  10.         if(s[leftPointer++] === s[rightPointer--]){
  11.             continue;
  12.         }else{
  13.             return false;
  14.         }
  15.     }
  16.     return true;
  17. };

我们再来一道题帮助大家理解一下二维数组（二维数组可以简单理解为这样[ [1,2], [3,4] ]，数组里面还有一层数组）

字节跳动面试题：杨辉三角

leetcode地址：https://leetcode-cn.com/problems/pascals-triangle/

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

👍计算机基础理论速成系列 --- 数据结构和算法 - 图7

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

  1. 输入: 5
  2. 输出:
  3. [
  4.      [1],
  5.     [1,1],
  6.    [1,2,1],
  7.   [1,3,3,1],
  8.  [1,4,6,4,1]
  9. ]

这道题就是找规律，题中已经指出，”在杨辉三角中，每个数是它左上方和右上方的数的和。这里我提供一种解题思路。

  1. /**
  2.  * @param {number} numRows
  3.  * @return {number[][]}
  4.  */
  5. var generate = function (numRows) {
  6.   if (numRows === 0) { return [] }
  7.   // 创建二维数组
  8.   const result = Array.from(new Array(numRows), () => [])
  10.   for (let i = 0; i < numRows; i++) {
  11.     // 初始化第一个元素和最后一个元素的值
  12.     result[i][0] = 1; result[i][i] = 1;
  13.     for (let j = 1; j < i; j++) {
  14.       // 这里是杨辉三角的规律
  15.       result[i][j] = result[i - 1][j - 1] + result[i - 1][j]
  16.     }
  17.   }
  18.   return result
  19. };

接下来，我们看一下跟顺序表有关的两个数据结构：栈和队列（在JS常常用数组去模拟这两种数据结构）

栈

我们用一组图片来展示栈的特点：
👍计算机基础理论速成系列 --- 数据结构和算法 - 图8
往栈中添加数据的时候，新数据被放在最上面。
👍计算机基础理论速成系列 --- 数据结构和算法 - 图9
然后，我们往栈中添加了数据 Green。往栈中添加数据的操作叫作入栈。
👍计算机基础理论速成系列 --- 数据结构和算法 - 图10
接下来，数据 Red 入栈。
👍计算机基础理论速成系列 --- 数据结构和算法 - 图11
从栈中取出数据时，是从最上面，也就是最新的数据开始取出的，即 Red。从栈中取出数据的操作叫作出栈。
👍计算机基础理论速成系列 --- 数据结构和算法 - 图12
如果再进行一次出栈操作，取出的就是 Green 了。

像栈这种最后添加的数据最先被取出，即后进先出的结构，我们称为 Last In First Out，简称 LIFO。

顺序表和单链表的图例如下，我们现有一个印象，后面详细讲解
👍计算机基础理论速成系列 --- 数据结构和算法 - 图13

3.2 顺序表

3.6 单链表

单链表的每一个元素由数据和下一个节点的指针组成
👍计算机基础理论速成系列 --- 数据结构和算法 - 图14

  • data域—存放结点值的数据域
  • next域—存放结点的直接后继的地址（位置）的指针域（链域）