Algorithm

Fisher–Yates shuffle 核心思想是从1到n之间随机取出一个数和最后一个数(n)交换，然后从1到n-1之间随机取出一个数和倒数第二个数(n-1)交换… 步骤： 写下从 1 到 N 的数字 取一个从 1 到剩下的数字（包括这个数字）的随机数 k 从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位 重复第 2 步，直到所有的数字都被取出 第 3 步写出的这个序列，现在就是原始数字的随机排列 经典实现 步骤： 给定一组待混排的有限序列P 新初始化一个空的序列Q 从P中随机选取一个元素 将该元素放到序列Q的最后面，并从序列P中移除该元 …

堆排序 1、参考代码 class HeapSort { //建堆 buildHeap(array) { //下标为0的位置保留 const arr = [0].concat(array); for (let i = arr.length; i > 0; i--) { this._heapify(arr, arr.length, i); } return arr; } // 排序 sort(array) { const arr = this.buildHeap(array); // 先建堆 let len = arr.length - 1; while (len > 1) { …

理解堆 堆是一个完全二叉树； 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值； 完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。 几个例子： 堆1：大顶堆 10 / \ 9 8 /\ /\ 6 5 7 4 / 3 堆2：大顶堆 10 / \ 8 9 /\ /\ 7 3 5 6 / 4 堆3：小顶堆 3 / \ 4 6 /\ /\ 5 8 9 10 / 7 堆的存储及操作 1、堆的存储 完全二叉树适合用数组来存储。 7 / \ 5 6 / \ / 4 2 1 用数组来存储： arr = [, 7, 5, 6, 4, 2, 1] idx = 0 1 …

实现1 var division = (list, left, right) => { // 以最左边的数(left)为基准 var base = list[left]; while (left < right) { // 从序列右端开始，向左遍历，直到找到小于base的数 while (left < right && list[right] >= base) { right--; } // 找到了比base小的元素，将这个元素放到最左边的位置 list[left] = list[right]; // 从序列左端开始，向右遍历，直到找到大于base …

题目 求二叉树的最大深度； 求二叉树的最小深度； 求二叉树中节点的个数； 求二叉树中叶子节点的个数； 求二叉树中第k层节点的个数； 判断二叉树是否是平衡二叉树； 判断二叉树是否是完全二叉树； 判断两个二叉树是否完全相同； 判断两个二叉树是否互为镜像； 翻转二叉树/镜像二叉树； 求两个二叉树的最低公共祖先节点； 二叉树的前序遍历； 二叉树的中序遍历； 二叉树的后序遍历； 构造二叉树（前序遍历和中序遍历/后序遍历和中序遍历）； 二叉树中插入/删除节点； 输入一个二叉树和一个整数，打印出二叉树中节点值的和等于输入整数所有的路径； 二叉树的搜索区间； 二叉树的层次遍历； 二叉树内两个节点的最长距离； …

题目 翻转链表； 判断链表是否有环； 链表排序； 链表相加求和； 获取链表倒数第n个节点； 删除链表倒数第n个节点； 删除链表中重复元素； 旋转链表； 重排链表； 链表划分； 翻转链表的n到m之间的节点； 合并K个排序过的链表； More 一篇文章搞定面试中的链表题目(java实现) https://www.jianshu.com/p/a64d1ef95980

算法度量 1、算法内存使用 原地排序（Sorted in place）算法，特指空间复杂度是 O(1) 的排序算法。 2、算法的稳定性 经过某种排序算法排序之后： 如果两个元素的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法； 如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。 冒泡排序 var bubbleSort = (arr) => { const n = arr.length; if (n <= 1) { return; } for (let i = 0; i < n; i++) { for (let j = 0; j < n - i - …

桶排序 （Bucket sort） 核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 比如对 9,10,20,45,40,27,32,35,31,50,53,63进行桶排序： 桶1（0-9）: 9 桶2（10-19）: 19 桶3（20-29）: 20,27 桶4（30-39）: 32,35,31 桶5（40-49）: 45,40, 桶6（50-59）: 50,53 桶6（60-69）: 63 桶排序的时间复杂度为什么是 O(n) 呢? 如果要排序的数据有 n 个，我们把它们均匀地划分到 m …

排列 一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(permutation)。特别地，当m=n时，这个排列被称作全排列(all permutation)。 var permute = (nums, k) => { let result = []; /* * 生成排列 * index表示向当前排列添加第index个元素。 * p表示当前的排列，其中拥有index-1个元素。 */ var generatePermutation = (nums, index, p) => { if (index === k) { …

二叉树【 每个节点最多有两个子节点。 10 / \ 9 20 / \ 15 35 二叉树的特点： 每个节点最多有两个子树，节点的度最大为2； 左子树和右子树是有顺序的，次序不能颠倒； 即使某节点只有一个子树，也要区分左右子树； 对称二叉树 如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 10 / \ 5 5 / \ / \ 1 4 4 1 实现思路: 判断根节点相同； 左子树的右节点和右子树的左节点相同； 右子树的左节点和左子树的右节点相同； 模拟一个对称二叉树和非对称二叉树： //对称二叉树 const symmetricalTree = { val: 8, left: { …