题目描述 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例： js 输入：[2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 解法一： 哈希表 [在线链接](https://codesandbox.io/s/hzfe-suan-fa-shu-zu-zhong-chong-fu-shu-zi-ha-xi-biao-forked-p8df3?file=/index.html) 从题目中分析，只需要找到任意一个重复的数字，那么可以利用哈希表，用数字的值作为 key 去存储，如果遇到已经存在的 key，则直接返回，这样就找到了重复的数字。 算法步骤 1. 声明哈希表用来保存遍历的值。 2. 开始遍历数组。 3. 获取当前值，判断值是否已经存在，若存在，则返回结果并结束循环；若不存在，则继续下一步。 4. 储存当前值进哈希表。 5. 处理数组下一位

题目描述 给定一棵二叉搜索树，请找出其中第 k 大的节点。 示例 1： js 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 示例 2： js 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 4 解题基本知识 二叉搜索树（Binary Search Tree）又名二叉查找树、二叉排序树。它是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 解法一： 递归 [在线链接](https://codesandbox.io/s/erchasousuoshudedi-k-dadejiedian-vfpbh?file=/index.html) 利用二叉搜索树

需求来源分析： 在需要存储树结构的情况下，一般由于使用的关系型数据库（如 MySQL），是以类似表格的扁平化方式存储数据。因此不会直接将树结构存储在数据库中，通常是通过邻接表、路径枚举、嵌套集或闭包表来存储。 其中，邻接表是最常用的方案之一，其存储模型如下： | id | pid | data | | -- | -- | -- | | 1 | 0 | a | | 2 | 1 | b | | 3 | 1 | c | 该模型代表了如下的树状结构： js { id: 1, pid: 0, data: 'a', children: [ {id: 2, pid: 1, data: 'b'}, {id: 3, pid: 1, data: 'c'}, ] } 大部分情况下，会交给应用程序来构造树结构。 典型题目 js const list = [ { pid: null, id: 1, data: "1" }, { pid: 1, id: 2, data: "2-1" }, { pid: 1, id: 3,

题目描述 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例： js 输入: 1 2 3 4 5 NULL 输出: 5 4 3 2 1 NULL 解法一：迭代（双指针） [在线链接](https://codesandbox.io/s/hzfe-suanfa-omcjw?file=/index.html) 本方法是对链表进行遍历，然后在访问各节点时修改 next 的指向，达到反转链表的目的。 1. 初始化 cur 和 pre 两个节点，分别指向 head 和 null。 2. 对链表进行循环，声明 temp 节点用来保存当前节点的下一个节点。 3. 修改当前节点 cur 的 next 指针指向为 pre 节点。 4. pre 节点修改为 cur 节点。 5. cur 节点修改为 t

题目描述 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。 示例 1: js 给定二叉树 [3, 9, 20, null, null, 15, 7] 3 / \ 9 20 / \ 15 7 返回 true。 示例 2: js 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false。 限制：0 <= 树的结点个数 <= 10000 基本知识点 二叉树的每个节点最多有两个子节点，平衡二叉树中任意一个节点的左右子树高度相差不能大于 1，满二叉树和完全二叉树都是平衡二叉树，普通二叉树有可能是平衡二叉树。 题解 解法一 思路 若想判断二叉树是不是平衡二叉树，只需要判断左右子树的高度差是不是不超过 1 即可。同时，要满足一个树是平衡二叉树，它的子树也必须

一、是什么 在计算机领域，树形数据结构是一类重要的非线性数据结构，可以表示数据之间一对多的关系。以树与二叉树最为常用，直观看来，树是以分支关系定义的层次结构 二叉树满足以下两个条件： 本身是有序树 树中包含的各个结点的不能超过 2，即只能是 0、1 或者 2 如下图，左侧的为二叉树，而右侧的因为头结点的子结点超过2，因此不属于二叉树： 同时，二叉树可以继续进行分类，分成了满二叉树和完成二叉树： 满二叉树：如果二叉树中除了叶子结点，每个结点的度都为 2 完成二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布

一、前言 算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别 衡量不同算法之间的优劣主要是通过 时间 和 空间 两个维度去考量： 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述 通常会遇到一种情况，时间和空间维度不能够兼顾，需要在两者之间取得一个平衡点是我们需要考虑的 一个算法通常存在最好、平均、最坏三种情况，我们一般关注的是最坏情况 最坏情况是算法运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，也意味着平均情况和最坏情况一样差 二、时间复杂度 时间复杂度是指执行这个算法所需要的计算工作量，其复杂度反映了程序执行时间「随输入规模增长而增长的量级」，在很大程度上能很好地反映出算法的优劣与否 一个算法花费的时间与算法中语句的「执行次数成正比」，执行次数越多，花费的时间就越多 算法的复杂度通常用大O符号表述，

一、是什么 数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合 前面讲到，一个程序 = 算法 + 数据结构，数据结构是实现算法的基础，选择合适的数据结构可以带来更高的运行或者存储效率 数据元素相互之间的关系称为结构，根据数据元素之间关系的不同特性，通常有如下四类基本的结构： 集合结构：该结构的数据元素间的关系是“属于同一个集合” 线性结构：该结构的数据元素之间存在着一对一的关系 树型结构：该结构的数据元素之间存在着一对多的关系 图形结构：该结构的数据元素之间存在着多对多的关系，也称网状结构 由于数据结构种类太多，逻辑结构可以再分成为： 线性结构：有序数据元素的集合，其中数据元素之间的关系是一对一的关系，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的 非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生关联 ![c6e05cc0899a44da8f93db5eba644e9d](https://static.developers.pub/c6e05c

一、栈 栈（stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表 表尾这一端被称为栈顶，相反地另一端被称为栈底，向栈顶插入元素被称为进栈、入栈、压栈，从栈顶删除元素又称作出栈 所以其按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，具有记忆作用 关于栈的简单实现，如下： js class Stack { constructor() { this.items = []; } / 添加一个（或几个）新元素到栈顶 @param { } element 新元素 / push(element) { this.items.push(element) } / 移除栈顶的元素，同时返回被移除的元素 / pop() { return this.items.pop() } / 返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它） /

一、是什么 排序是程序开发中非常常见的操作，对一组任意的数据元素经过排序操作后，就可以把他们变成一组一定规则排序的有序序列 排序算法属于算法中的一种，而且是覆盖范围极小的一种，彻底掌握排序算法对程序开发是有很大的帮助的 对与排序算法的好坏衡量，主要是从时间复杂度、空间复杂度、稳定性 时间复杂度、空间复杂度前面已经讲过，这里主要看看稳定性的定义 稳定性指的是假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变 即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的 二、有哪些 常见的算法排序算法有： 冒泡排序 选择排序 插入排序 归并排序 快速排序 冒泡排序 一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来 思路如下： 比较相邻的元素，如果第一个比第二个大，就交换它们两个 对每一对相邻元素作同样的工作

一、是什么 集合（Set），指具有某种特定性质的事物的总体，里面的每一项内容称作元素 在数学中，我们经常会遇到集合的概念： 有限集合：例如一个班集所有的同学构成的集合 无限集合：例如全体自然数集合 在计算机中集合道理也基本一致，具有三大特性： 确定性：于一个给定的集合，集合中的元素是确定的。即一个元素，或者属于该集合，或者不属于该集合，两者必居其一 无序性：在一个集合中，不考虑元素之间的顺序，只要元素完全相同，就认为是同一个集合 互异性：集合中任意两个元素都是不同的 二、操作 在 ES6 中，集合本身是一个构建函数 Set ，用来生成 Set 数据结构，如下： js const s = new Set(); 关于集合常见的方法有： add()：增 delete()：删 has()：改 clear()：查 add() 添加某个值，返回 Set 结构本身 当添加实例中已经存在的元素， set 不会进行处理添加 js s.add(1).add(2).add(2); // 2只

一、是什么 选择排序（Selection sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度，所以用到它的时候，数据规模越小越好 其基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置 然后再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾 以此类推，直到所有元素均排序完毕 举个例子，一个数组为 56、12、80、91、29，其排序过程如下： 第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置。此时数组为 12、56、80、91、20 第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置，此时数组为12、20、80、91、56 ![98

一、是什么 快速排序（Quick Sort）算法是在冒泡排序的基础上进行改进的一种算法，从名字上看就知道该排序算法的特点是快、效率高，是处理大数据最快的排序算法之一 实现的基本思想是：通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小 然后继续沿用此方法分别对两部分进行同样的操作，直到每一个小部分不可再分，所得到的整个序列就变成有序序列 例如，对无序表49，38，65，97，76，13，27，49进行快速排序，大致过程为： 首先从表中选取一个记录的关键字作为分割点（称为“枢轴”或者支点，一般选择第一个关键字），例如选取 49 将表格中大于 49 个放置于 49 的右侧，小于 49 的放置于 49 的左侧，假设完成后的无序表为：{27，38，13，49，65，97，76，49} 以 49 为支点，将整个无序表分割成了两个部分，分别为{27，38，13}和{65，97，76，49}，继续采用此种方法分别对两个子表进行排序 前部分子表以 27 为支点，排序后的子表为{13，27，38}，此部分已经有序；后部分子

一、是什么 归并排序（Merge Sort）是建立归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用 将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序 例如对于含有 n 个记录的无序表，首先默认表中每个记录各为一个有序表（只不过表的长度都为 1） 然后进行两两合并，使 n 个有序表变为 n/2 个长度为 2 或者 1 的有序表（例如 4 个小有序表合并为 2 个大的有序表） 通过不断地进行两两合并，直到得到一个长度为 n 的有序表为止 例如对无序表{49，38，65，97，76，13，27}进行归并排序分成了分、合两部分： 如下图所示： 归并合过程中，每次得到的新的子表本身有序，所以最终得到有序表 上述分成两部分，则称为二路归并，如果分成三个部分则称为三路归并，以此类推 ...

一、是什么 链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，由一系列结点（链表中每一个元素称为结点）组成 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域 节点用代码表示，则如下： js class Node { constructor(val) { this.val = val; this.next = null; } } data 表示节点存放的数据 next 表示下一个节点指向的内存空间 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时