绪论

第一章：概述

一、计算思维

什么是计算思维？2006 年，美国卡内基梅隆大学的 Jeannette M. Wing 教授首次提出了计算思维的概念。

谷歌公司为教育者开发了一套计算思维的课程：

1. 分解

   将一个复杂的问题拆解成一个一个简单的问题，然后逐一击破。

2. 模式识别

   一些问题具备相同的属性或者说相似之处，这些相似之处被称之为模式。

   模式识别指的就是在一组数据中找出特征或规则，用于对数据进行分类，以作为决策判断的依据。

3. 抽象

   计算机科学中，“抽象”指提取问题的关键部分，忽略无关紧要的细节部分。

4. 算法

   本质就是解决问题的方法和步骤。

二、数据结构

数据结构 (Data Structrue) ，用于在计算机中存储和组织数据的方式。

数据结构不仅仅是定义了数据元素之间的关系，还定义了能够操作这些数据的方法。

数据结构分类

1. 物理结构：数据在计算机内存中真实的存储方式。
2. 逻辑结构：描述数据元素之间的逻辑关系。

逻辑结构

1. 线性结构：排成一个线性的序列
   • 数组
   • 链表：由一个一个节点组成，每个节点会指向下一个节点
   • 栈：只有一个出口，因此先进后出，后进先出
   • 队列：有两个口，一个是入口，一个是出口。先进先出，后进后出
2. 非线性结构
   • 树：由一个一个节点组成的一个层次结构。例如 DOM 树就是一个典型的树结构。
   • 图：由顶点和边组成的网络结构。
   • 集合（Set）：存储一组不重复的元素。就是数学里面的集合，经常涉及的操作：并集、交集、差集。
   • 字典：也被称之为映射（Map），存储一组一组的键值对，通过键可以快速的找到值。

物理结构

表示的是内存中真实的存储数据的方式。只有 2 种：

• 数组：顺序存储
• 链表：链式存储

也就是说，其他的逻辑结构都是依靠这两种结构来存储的。

三、算法

1. 基本概念

1）是什么

本质就是解决问题的方法和步骤。

2）要求

一个算法必须要符合以下 5 个条件：

1. 输入：一个算法有 0 个或者多个输入，并且这些输入要有明确的描述或者含义。
2. 输出：至少会有一个输出结果。
3. 明确性 / 确定性：算法设计中的每一个步骤必须是简洁明确的。
4. 有限性 / 有穷性：你设计的算法在有限的步骤后会结束。
5. 有效性 / 可行性：算法的步骤清楚而且是可行，所谓可行，指的是只要时间允许，我甚至可以使用笔和纸来求出答案。

3）描述

如何来做一个算法的表达，将我的算法设计传达给别人。

1. 自然语言描述：所谓自然语言，就是指中文、英文这种语言来描述算法。缺点：描述算法的时候比较冗余，而且通过自然语言描述算法的时候，对方容易产生理解上的偏差。
2. 流程图
3. 伪代码

2. 算法的复杂度

1）大 $O$ 表示法

大 O 表示法中，经常会省略底数

举个例子，假设算法的复杂度为 O(log₂ⁿ) ，我们会直接表示为 O(logn)，直接省略了底数 2。

原因：因为大 O 表示法关心的是算法的增长速率，而底数是多少不会影响增长的速率，底数的变化仅仅是一个常数因子的变化。

假设有 log₂ⁿ 和 log₁₀ⁿ，这两者之间的关系可以用一个公式：log₁₀ⁿ = log₂ⁿ / log₂¹⁰，进一步进行换算：log₂ⁿ = log₁₀ⁿ * log₂¹⁰，这里的 log₂¹⁰ 就是一个常数因子，在大 O 表示法中常数因子会被忽略，不会去关心常数。这也是为什么在大 O 表示法中会省略底数的原因。

2）时间复杂度

3）空间复杂度

3. 常见算法思维

常见算法思维：

1. 分治法（包含了递归）
2. 迭代法
3. 枚举法
4. 回溯法
5. 贪心法
6. 动态规划

1）分治法

英语里面叫做 divide and Conquer。

核心思想

将一个复杂的问题分解成多个简单的子问题，递归地求解这些子问题，如果子问题还是比较复杂，那么就继续进行拆分。最后再将所有子问题的解合并成最终解。

核心步骤

1. 分解：将原来的问题分解为多个小问题。
2. 求解：递归的解决所有的子问题。
3. 合并：将所有子问题的解合并成原来问题的解。

举例：归并排序

归并排序就是典型的使用的是分治的思想：

整个归并排序会经历：

1. 分解：将待排序的数组不断的分成两个部分，直到不能再分解
2. 求解：递归的将两个部分的数组进行归并排序
3. 合并：将两个排序后的数组将其合并为一个排序好的数组

分治法的优缺点

• 优点：简化问题。通过分解一个大问题，将其全部转换为较为简单的子问题，从而易于求解。
• 缺点：空间换时间。往往需要一些额外的空间。空间复杂度一般在 O(n) 左右。分治法往往需要额外的存储空间来存储分解后的子问题。

2）迭代法

英语叫做 Iteration。

核心思想

重复执行一系列步骤，直到满足某个条件或达到预定目标。每次迭代都在一定程度上修改问题的状态，最终通过不断的更新和计算得到问题的解。

核心步骤

1. 初始化：先设置一个初始值，准备进入迭代。

2. 条件判断：在每次迭代开始之前，需要检查当前状态是否满足结束条件，如果满足结束条件，那么就停止迭代。

3. 更新：需要不停的去更新状态，从而进入下一次迭代。

4. 重复：一直执行迭代。

其实，循环就是典型的迭代的思想。

举例：计算递增序列的和

1 + 2 + 3 + 4 + .... + 99 + 100

let sum = 0;

for(let i = 1; i <= 100; i++){
  sum += i;
}

上面的解法，背后采用的就是迭代的思想。

3）枚举法

英语叫做 Enumeration。

核心思想

列出所有可能的选项，并逐一检查每一个选项，判断是否符合问题的约束条件。

核心步骤

1. 穷举所有可能的解
2. 检查每个解：看每一个解是否符合要求
3. 选择合适的解

举例：力扣第 1 题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

示例 1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

示例 2

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3

输入：nums = [3,3], target = 6
输出：[0,1]

这道题大家能够想到的就是枚举的方式，从第一个数开始，和后面的数进行组合，看是否符合要求。

function twoSum(nums, target) {
  // 遍历数组从第一个到倒数第二个
  for (let i = 0; i < nums.length - 1; i++) {
    // 遍历数组从第二个到最后一个
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

const nums2 = [3, 2, 4];
const target2 = 6;
console.log(twoSum(nums2, target2));

虽然上面的算法也用到了迭代的操作，但是我们迭代是为了枚举出所有的和，迭代仅仅是实现手段，算法背后的核心思想仍然是枚举。

第二章：递归

一、是什么

递归属于函数式编程。递归是典型的分治的思想。

什么是递归？一种特殊形式的调用形式，指的是函数自己调用自己的形式。

书写递归函数的步骤

1. 明确函数的目标。假设你目前写的这个递归函数已经能实现该功能了。
2. 化简问题（大问题变小问题）。也就是变为与目前编写的递归函数有关的表达式。
3. 找到终止条件。也就是最小问题的解。

递归函数的诀窍

1. 委托的思想：一个递归函数，告诉你是什么功能，你就不要想内部怎么实现的，反正委托给它，它就能给你正确的结果。
2. 设计出口：什么时候是递归的终点，一旦没有设计出口，就会变成死递归。

二、递归例子

求 n 的阶乘

function f(n){
  // 出口非常重要，不会再继续往下调用了。
  if(n === 1){
    return 1;
  }
  return n * f(n-1);
}

斐波那契数列

function f(n){
  // 设计出口
  if(n === 1){
    return 0;
  } else if(n === 2){
    return 1;
  } else {
    return f(n-1) + f(n-2);
  }
}

实现一个 sum 函数，该函数接收 2 个参数，返回从第一个参数加到第二个参数的和。

function sum(m, n){
  if(m === n){
    return m;
  }
  return n + sum(m, n - 1);
}

三、循环与递归互转

循环元素	对应递归的元素	在你 pipe 代码里的体现
初始状态	初次调用的参数	传入索引 0 和初始的 val
循环条件（如 i < length）	终止条件(反转)	if (index >= args.length) return
循环体内部逻辑	递归体内部逻辑	func(val) 执行单个函数操作
步进器（如 i++）	下一次递归的参数调整	run(index + 1, newVal)

附加

一、自学资源

• 代码随想录
• 通过动画可视化数据结构和算法 - VisuAlgo