算法图解笔记

二分查找

二分查找是一种算法，其输入是一个有序的元素列表（必须有序的是因为每次二分后，能通过中间值与目标值得大小关系判断出答案所在区间）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

时间复杂度：log2n(如果不知道什么是时间复杂度可以看这篇)

使用场景1：假设要在电话簿中找一个名字以K打头的人，（现在谁还用电话簿！）可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。

使用场景2：1-100内随便想一个数字，不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字。（假设猜想的数字为1，猜测过程则为50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1）

代码实现

/**
    * 获取数组开始位置(索引值，一般为0)，结束位置(数组的长度减1)，中间位置(向下取整(start + end) / 2)
    * 判断中间位置的值是否是需要猜测的值，如果中间位置的值大于需要猜测的值则修改结束位置(end - 1)，反之则修改开始位置(start + 1)
*/
const binary_search = (array, item) => {
    let start = 0,
        end = array.length - 1;
    while (start <= end) {
        const middle = Math.floor((start + end) / 2),
            guess = array[middle];
        if (guess === item) {
            return middle;
        }
        if (guess > item) {
            end = middle - 1;
        } else if (guess < item) {
            start = middle + 1;
        }
    }
    return -1
}

数组和链表

需要存储多项数据时，有两种基本方式——数组和链表。但它们并非都适用于所有的情形，因此知道它们的差别很重要。接下来介绍数组和链表以及它们的优缺点。

数组的优缺点

数组在内存中存储的数据都是相连的，编程中数组用得更多一点，因为它支持随机访问。

数组的缺陷在于插入元素时则必须将后面的元素都向后移，删除元素时所有的元素都要往前移。

链表的优缺点

链表中的元素可存储在内存的任何地方，链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。删除同理，只需修改前一个元素的指向地址即可。

链表的缺陷在于，需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3的地址，以此类推，直到访问最后一个元素。

小结

❑ 数组的读取速度很快。❑ 链表的插入和删除速度很快。

常见的数组和链表操作的运行时间

| 数组 | 链表
:- | :- | :-
读取 | O(1) | O(n)
插入 | O(n) | O(1)
删除 | O(n) | O(1)

选择排序

选择排序是一种灵巧的算法，但其速度不是很快。

有一个歌单，里面有歌曲和播放次数。现在有一个需求，需要对歌单按照播放次数进行排序。
实现思路，遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。然后继续再次这样做，找出播放次数第二多的乐队，如此循环…
其实这就是选择排序。

代码实现

const selectionSort = arr => {
    let smallest = 0,
        len = arr.length;
    for (let i = 0; i < len; i++) {
        smallest = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[smallest]) {
                smallest = j
            }
        }
        [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
    }
    return arr
}

书中的代码则是另外一个版本，虽然代码冗余，但是…似乎更通俗易懂？

const findSmallestIndex = arr => {
    let smallestIndex = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < arr[smallestIndex]) {
            smallestIndex = i
        }
    }
    return smallestIndex
}
const selectionSort = arr => {
    let copyArr = [...arr], // 浅拷贝防止改变原数组
        len = copyArr.length,
        ans = []
    for (let i = 0; i < len; i++) {
        let smallestIndex = findSmallestIndex(copyArr);
        ans.push(copyArr.splice(smallestIndex, 1)[0]) // opyArr.splice(smallestIndex, 1)[0]就是最小的元素
    }
    return ans
}

递归函数

编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

栈

栈（stack）又名堆栈，是一种遵循后进先出（last-in，first-out，LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称作栈顶，另一端称作栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
就好比：一个死胡同，前面是“此路不通”，只有一个入口，如果一队人进入，只能队尾变对首出去。

快速排序

分而治之

分而治之（divide and conquer, D&C）——一种著名的递归式问题解决方法。
使用D&C解决问题的过程包括两个步骤：
(1) 找出基线条件，这种条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。

代码实现1 数组求和

给定一个数字数组。将这些数字相加，并返回结果。

基线条件，数组为空或者数组只有一个元素
递归条件，每次相加后剔除当前元素

function sum(array) {
  let ans = 0
  if (array.length === 0) {
    return 0
  }
  if (array.length > 0) {
    ans = array[0] + sum(array.slice(1))
  }
  return ans
}

console.log(sum([0, 1, 2, 3, 4, 5])) // 15

// es6写法
const sum = (array) => array.length === 0 ? 0 : (array[0] += sum(array.slice(1)))
console.log(sum([0, 1, 2, 3, 4, 5])) // 15

代码实现2 找出数组中最大的数字

const findMax = (array, max = 0) => array.length === 0 ? max : findMax(array.slice(1), array[0] > max ? array[0] : max)
console.log(findMax([0, 12, 2, 3, 4, 5])) // 12

快速排序算法

快速排序是最快的排序算法之一，也是D&C典范。
D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。

代码实现

原理及es5版本可以看这里

const quicksort = array => {
    if (array.length < 2) {
        return array
    }
    const pivot = array[0]; // 基准值
    // slice(1)是为了去除当前基准值
    const left = array.slice(1).filter(item => item <= pivot);
    const right = array.slice(1).filter(item => item > pivot);
    return [...quicksort(left), pivot, ...quicksort(right)]
}
console.log(quicksort([1, 3, 1, 2, 3, 4, 55, 23, 4, 23, 2, -1, -3, 0]))

散列表

散列函数

哈希表(Hash table，也叫散列表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

代码实现

假设你负责管理一个投票站。显然，每人只能投一票，但如何避免重复投票呢？

const voted = {}

const checkVoter = (name) => {
  if (voted[name]) {
    console.log("kick them out!")
  } else {
    voted[name] = true
    console.log("let them vote!")
  }
}

checkVoter("tom") // let them vote!
checkVoter("mike") // let them vote!
checkVoter("mike") // kick them out!

使用场景

缓存

假设你有个侄女，总是没完没了地问你有关星球的问题。火星离地球多远？月球呢？木星呢？每次你都得在Google搜索，再告诉她答案。这需要几分钟。现在假设她老问你月球离地球多远，很快你就记住了月球离地球238900英里。因此不必再去Google搜索，你就可以直接告诉她答案。这就是缓存的工作原理：网站将数据记住，而不再重新计算。

缓存如下两个优点。❑ 用户能够更快地看到网页，就像你记住了月球与地球之间的距离时一样。下次你侄女再问你时，你就不用再使用Google搜索，立刻就可以告诉她答案。❑ Facebook需要做的工作更少。

缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！

散列表适合用于：❑ 模拟映射关系；❑ 防止重复；❑ 缓存/记住数据，以免服务器再通过处理来生成它们。

哈希冲突

由于散列函数具有无限的输入长度和预定义的输出长度，因此不可避免地存在两个不同的输入产生相同输出散列的可能性。如果两个单独的输入产生相同的哈希输出，则称为冲突。

散列表、数组和链表操作的运行时间

	散列表(平均情况)	散列表(最糟情况)	数组	链表
查找	O(1)	O(n)	O(1)	O(n)
插入	O(1)	O(n)	O(n)	O(1)
删除	O(1)	O(n)	O(n)	O(1)

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。因此，在使用散列表时，避开最糟情况至关重要。而要避免冲突，需要有：❑ 较低的填装因子；❑ 良好的散列函数。

填装因子

散列表的填装因子很容易计算，计算方式：散列表包含的元素数 / 散列表位置总数

填装因子2/5，即0.4

假设你要在散列表中存储100种商品的价格，而该散列表包含100个位置。那么在最佳情况下，每个商品都将有自己的位置。这个散列表的填装因子则为1
如果这个散列表只有50个位置呢？填充因子将为2。不可能让每种商品都有自己的位置，因为没有足够的位置！填装因子大于1意味着商品数量超过了数组的位置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）。

一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

广度优先搜索

广度优先搜索(breadth-first search,BFS)是一种图算法，能找出两样东西之间的最短距离。
可帮助回答两类问题:
❑ 第一类问题：从节点A出发，有前往节点B的路径吗？
❑ 第二类问题：从节点A出发，前往节点B的哪条路径最短？

代码实现

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。如何在好友及好友的好友中寻找到芒果销售商？

实现原理

ps:更新队列时，我使用术语“入队”和“出队”，但你也可能遇到术语“压入”和“弹出”。压入大致相当于入队，而弹出大致相当于出队。

const graph = {};
graph.you = ["alice", "bob", "claire"];
graph.bob = ["anuj", "peggy"];
graph.alice = ["peggy"];
graph.claire = ["thom", "jonny"];
graph.anuj = [];
graph.peggy = [];
graph.thom = [];

/*
* 这个函数检查人的姓名是否以m结尾：如果是，他就是芒果销售商。
*/
const isSeller = name => name[name.length - 1] === "m";

const search = name => {
    let searchQueue = [...graph[name]];
    // 已经查找过的人
    const searched = [];
    while (searchQueue.length > 0) {
        // person为当前查找的人
        const person = searchQueue.shift();
        if (searched.indexOf(person) === -1) {
            if (isSeller(person)) {
                console.log(`${person}是芒果商人`)
                return true
            }
            searched.push(person)
            // 将当前查找人的好友加入查找队列
            searchQueue = searchQueue.concat(graph[person])
        }
    }
};
search('you')

队列

队列是一种先进先出（First In First Out, FIFO）的数据结构，而栈是一种后进先出（Last In First Out, LIFO）的数据结构。

你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。

狄克斯特拉算法

1. 狄克斯特拉算法用于在加权图中查找最短路径。
2. 仅当权重为正时狄克斯特拉算法才管用。
3. 如果图中包含负权边，请使用贝尔曼-福德算法。

贪婪算法

贪婪算法很简单：每步都采取最优的做法。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。