数据结构与算法

二叉树 什么是二叉树 简单地理解，满足以下两个条件的树就是二叉树： 本身是有序树； 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2； 二叉树性质 二叉树中，第 i 层最多有 2i-1 个结点。 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。 性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。 同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一种方式表示为 n=n1+2n2+1。 两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。 满二叉树 如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。 满二叉树除了满足普通二叉树的性质，还具有以下性质： 满二叉树中第 i 层的节点数为 2n-1 个。 深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。 具有 n 个节点的满二叉树的深度为 log2(n+1)。 完全二叉树 如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。 ...

什么是回溯法 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。 在二叉树系列中，我们已经不止一次，提到了回溯，例如 二叉树：以为使用了递归，其实还隐藏着回溯。 回溯是递归的副产品，只要有递归就会有回溯。 回溯法的效率 回溯法的性能如何呢，这里要和大家说清楚了，「虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法」。 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案」，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。 那么既然回溯法并不高效为什么还要用它呢？ 因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。 回溯法解决的问题 回溯法，一般可以解决如下几种问题： 组合问题：N个数里面按一定规则找出k个数的集合 排列问题：N个数按一定规则全排列，有几种排列方式 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个N个数的集合里有多少符合条件的子集 棋盘问题：N皇后，解数独等等 组合是不强调元素顺序的，排列是强调元素顺序」。 例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。 记住组合无序，排列有序，就可以了。 如何理解回溯法 所有回溯法的问题都可以抽象为树形结构！ 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。 递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。 回溯法模板 回溯函数模板返回值以及参数 在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。 回溯算法中函数返回值一般为void。 再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。 但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。 回溯函数伪代码如下： void backtracking(参数) 回溯函数终止条件 既然是树形结构，那么我们在讲解 二叉树的递归的时候，就知道遍历树形结构一定要有终止条件。 所以回溯也有要终止条件。 什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。 所以回溯函数终止条件伪代码如下： if (终止条件) { 存放结果; return; } 回溯搜索的遍历过程 回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。 如图： 注意图中，集合大小和孩子的数量是相等的！ 回溯函数遍历过程伪代码如下： for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。 ...

动态规划为什么重要？ 从面试的角度看，动态规划是正规算法面试中无论如何都逃不掉的必考题。 其实最主要的原因就是动态规划非常适合面试，因为动态规划没办法「背」。 我们很多求职者其实是通过背题来面试的，而之前这个做法屡试不爽，什么翻转二叉树、翻转链表，快排、归并、冒泡一顿背，基本上也能在面试中浑水摸鱼过去，其实这哪是考算法能力、算法思维，这就是考谁的备战态度好，愿意花时间去背题而已，把连背都懒得背的筛出去就完事了。 但是随着互联网遇冷，人才供给进一步过热，背题的人越来越多，面试的门槛被增加了，因此这个时候需要一种非常考验算法思维、变化多端而且容易设计的题目类型，动态规划就完美符合这个要求。 比如 LeetCode 中有1261道算法类题目,其中动态规划题目占据了近200道，动态规划能占据总题目的 1/6 的比例,可见其火热程度。 更重要的是，动态规划的题目难度以中高难度为主 所以,既然我们已经知道这是算法面试的必考题了,我们怎么准备都不为过。 什么是动态规划 动态规划(Dynamic programming，简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 态规划与分治方法类似，都是通过组合子问题的解来来求解原问题的。再来了解一下什么是分治方法，以及这两者之间的差别，分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。而动态规划与之相反，动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治方法会做许多不必要的工作，他会反复求解那些公共子子问题。而动态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。 动态规划题目的特点 从「钱」讲起 我们可以算一下，按照贪心算法的策略，我们先拿出3个最大面值的7，再拿出一个面值5然后就没有办法继续了。 这里就有问题了,贪心算法的弊端在这种特殊面值钱币面前展露无疑,原因就在于「只顾眼前，无大局观」，在先拿出最大的 7 面值的硬币后就彻底把周旋余地堵死了,因为剩下的 21 要想凑足付出的代价是非常高的,我们需要依次拿出4个面值为2的硬币。 改进计算策略 那么既然贪心算法已经不适用于这种场景了,我们应该如何改变计算策略呢? 当我们面试过程中遇到这种问题时,如果一时没有思路,也要想到一种万能算法–暴力破解。 我们分析一下上述题目,它的问题其实是「给定一组面额的硬币,我们用现有的币值凑出27最少需要多少个币」。 那么假设最后一个硬币为a[k]的话，那么剩下27 - a[k]，这个时候问题又变成了，我们凑出 27 - a[k]最少需要多少个币 问题可以不断被分解为「我们用现有的币值凑出 n 最少需要多少个币」,比如我们用 f(n) 函数代表 「凑出 n 最少需要多少个币」. 把「原有的大问题逐渐分解成类似的但是规模更小的子问题」这就是最优子结构,我们可以通过自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。 这个时候我们分别假设 2、5、7 三种面值的币分别为最后一个硬币的情况： 最后一枚硬币的面额为 7: min = f(20) + 1 最后一枚硬币的面额为 5: min = f(22) + 1 最后一枚硬币的面额为 2: min = f(25) + 1 这个时候大家发现问题所在了吗?最少找零 min 与 f(20)、f(22)、f(25) 三个函数解中的最小值是有关的，毕竟后面的「+1」是大家都有的。 ...

一、测试模版 数组去重是一个老生常谈的问题，网上流传着有各种各样的解法 为了测试这些解法的性能，我写了一个测试模版，用来计算数组去重的耗时 // distinct.js let arr1 = Array.from(new Array(100000), (x, index)=>{ return index }) let arr2 = Array.from(new Array(50000), (x, index)=>{ return index+index }) let start = new Date().getTime() console.log('开始数组去重') function distinct(a, b) { // 数组去重 } console.log('去重后的长度', distinct(arr1, arr2).length) let end = new Date().getTime() console.log('耗时', end - start) 这里分别创建了两个长度为 10W 和 5W 的数组 然后通过 distinct() 方法合并两个数组，并去掉其中的重复项 数据量不大也不小，但已经能说明一些问题了 二、Array.filter() + indexOf 这个方法的思路是，将两个数组拼接为一个数组，然后使用 ES6 中的 Array.filter() 遍历数组，并结合 indexOf 来排除重复项 function distinct(a, b) { let arr = a.concat(b); return arr.filter((item, index)=> { return arr.indexOf(item) === index }) } 这就是我被吐槽的那个数组去重方法，看起来非常简洁，但实际性能。。。 是的，现实就是这么残酷，处理一个长度为 15W 的数组都需要 8427ms 三、双重 for 循环 最容易理解的方法，外层循环遍历元素，内层循环检查是否重复 当有重复值的时候，可以使用 push()，也可以使用 splice() function distinct(a, b) { let arr = a.concat(b); for (let i=0, len=arr.length; i<len; i++) { for (let j=i+1; j<len; j++) { if (arr[i] == arr[j]) { arr.splice(j, 1); // splice 会改变数组长度，所以要将数组长度 len 和下标 j 减一 len--; j--; } } } return arr } 但这种方法占用的内存较高，效率也是最低的 ...

实现原理 四叉树是什么? 四叉树本身是树结构的一种，如果物体过多的话，先根据物体所处位置划分成四块，如果每个块的中的物体数量还是很多的话，继续划分成四块。如下图红线所示。 检测的时候，就是根据待测试对象的位置，去找属于哪个块，再把这个块中的物体告诉你。如下图中的绿色物体。 那么怎么实现四叉树呢？用好 github 就行了(误)，搜了一下，找到一个库，直接拿来改改就行了。 GitHub - timohausmann/quadtree-js: A lightweight quadtree implementation for javascript 代码解析 构造函数 function Quadtree( bounds, max_objects, max_levels, level ) { this.max_objects = max_objects || 10;　//每个区域可以容纳的最大对象数，超过就需要划分 this.max_levels = max_levels || 4;　//最多划几层四叉树 this.level = level || 0;　//当前树或子树的层，根为0 this.bounds = bounds; //bounds就是对象集，每个点包括x,y,width,height(有些实现是圆形，这个是矩形) this.objects = [];　//属于当前节点的对象，不包括子节点的对象 this.nodes = [];　//属于当前树的节点 }; 划分 当调用Insert函数向树中插入对象的时候，如果当前节点没有被划分过的时候，会判断节点的对象数是否超过的限制的max_objects,如果超过了的话当前节点就会调用这个split方法。 Quadtree.prototype.split = function() { var nextLevel = this.level + 1; var subWidth = Math.round( this.bounds.width / 2 ); var subHeight = Math.round( this.bounds.height / 2 ); var x = Math.round( this.bounds.x ); var y = Math.round( this.bounds.y ); //第一象限，和数学里的坐标轴一样，不过起点变了而已 this.nodes[0] = new Quadtree({ x : x + subWidth, y : y, width : subWidth, height : subHeight }, this.max_objects, this.max_levels, nextLevel); //第二象限 this.nodes[1] = new Quadtree({ x : x, y : y, width : subWidth, height : subHeight }, this.max_objects, this.max_levels, nextLevel); //第三象限 this.nodes[2] = new Quadtree({ x : x, y : y + subHeight, width : subWidth, height : subHeight }, this.max_objects, this.max_levels, nextLevel); //第四象限 this.nodes[3] = new Quadtree({ x : x + subWidth, y : y + subHeight, width : subWidth, height : subHeight }, this.max_objects, this.max_levels, nextLevel); }; ...