基础算法-白红宇

基础算法

阅读量：4082 次

发布时间：2019-05-25

本文共 15494 字，大约阅读时间需要 51 分钟。

起手诗

从今天起，做一个牛X的人，早起，健身，修炼算法

从今天起，关心代码质量，我有一个梦想，朝九晚五，年薪百万

从今天起，和每一个亲人通信，告诉他们我的决心

那成功的天使告诉我的

我想告诉每一个人

给每一个文件、每一个变量取一个温暖的名字

陌生人，我也为你祝福

愿你有一个灿烂的前程

愿你的头发不再减少

愿你明天仍是公司栋梁

而我，只愿朝九晚五，年薪百万

第一天【2018-03-25】

写一个函数判断一个括号表达式是否平衡，例如：balance('[()') = false,balance('[()()[]]') = true。

function balance(str) {    let [first, ...others] = str;    let stack = [first]    while(others.length) {        let stact_last = stack[stack.length-1];        let others_first = others.shift();        if(!if_match(stact_last,others_first)) {            stack.push(others_first);        }else{            stack.pop();        }        return stack.length?false:true;    }}function if_match(left,right) {    return (left === '[' && right === ']') || (left === '(' && right === ')');}复制代码

思路：

这个解法基于栈(后进先出)。首先，如果只有一个字符，则必然不平衡。

如果大于一个字符。我们把字符串中的每一个字符取出并依次放入栈中，假如最新放入栈中的字符与栈的最后一个字符匹配(match方法返回true)，则删掉栈中的最后一个。

就这样把字符串循环一遍后，如果栈中的字符被删光，则说明这个字符串是平衡的。

如图，我们可以把它想象成“消消乐”，字符串中的字符依次放到栈中,如果相邻两个不匹配，则放在栈的顶端；如果匹配，则“消掉”。

第二天【2018-03-26】

实现一个斐波那契数列生成函数，fibonacci(10) = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

递归解法:

斐波那契数列的前两项是1,后面的每一项都等于前两项之和，所以用递归很容易实现，不过需要注意性能问题。

如果直接递归的话会出现大量重复计算，试想递归数字10的时候会依次递归数字9、8、7、6……，但是当再递归数字9的时候会在递归数字8、7、6……，其中8、7、6……被多次递归。所以声明了一个catch数组用来缓存，递归之前判断如果该项没有值才会进行递归。

function fibonacciCatch(num) {    let cache = [1, 1];    (function fibonacci(n) {        return typeof cache[n] == 'number' ? cache[n] : (cache[n] = fibonacci(n - 1) + fibonacci(n - 2))    })(num - 1);    return cache;}console.log(fibonacciCatch(10))   //[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]复制代码

Generator解法:

下面是另一种解法，这种解法不存在多次计算问题，思路是：

首先记录前两个值，之后的每一个yeild都返回前两个值之和，当然还要更新前两个值为最新的。

对generator不了解的同学可以参考阮一峰老师的书籍：

function* fibonacci(n) {    let a = 1, b = 1    yield a    yield b    while (true) {        const t = b        b = a + b        a = t        yield b    }}let it = fibonacci()let result = Array.from(Array(10), it.next, it).map(x => x.value)console.log(result)  //[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]复制代码

第三天【2018-03-27】

写一个方法，求任意长度数组的笛卡尔积。例如：cartesian([[1,2],['a','b']]) = [[1,'a'],[1,'b'],[2,'a'],[2,'b']]

笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尓积(Cartesianproduct)又称直积，表示为X×Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员

function cartesion(...arys) {    if (arys.length == 0) return []    if (arys.length == 1) return arys    return arys.reduce((prev, item) => {        let temp = []        for (let i = 0; i < prev.length; i++) {            for (let j = 0; j < item.length; j++) {                temp.push(Array.isArray(prev[i]) ? [...prev[i], item[j]] : [prev[i], item[j]])            }        }        return temp    })}console.log(cartesion([1, 2, 3], ['a', 'b'], ['x', 'y']))//[[1, 'a', 'x'],[1, 'a', 'y'],[1, 'b', 'x'],[1, 'b', 'y'],[2, 'a', 'x'],[2, 'a', 'y'],[2, 'b', 'x'],[2, 'b', 'y'],[3, 'a', 'x'],[3, 'a', 'y'],[3, 'b', 'x'],[3, 'b', 'y']]复制代码

思路：

这道题主要是训练reduce的用法，我们依次组合两个数组中的每一项，然后把结果作为一个整体继续和接下来的数组进行组合。

这里还需要注意es6扩展符...的用法，大家可以把这个符号去掉再执行一遍程序，看看有什么不同。

第四天【2018-03-28】

假设有一个数组，它的第 i 个元素是一个给定的股票在第i 天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易（多次买卖股票）。然而，你不能同时参与多个交易（你必须在再次购买前出售股票）。

var maxProfit = function (prices) {    if (!prices.length) return 0 //越界判断    var max = 0    for (var i = 0; i < prices.length; i++) {        var diff = prices[i] - prices[i - 1]        if (diff > 0) {            max += diff        }    }    return max};复制代码

思路是：

1、声明一个max记录利润

2、从第二项开始循环数组，判断明天的价格是否高于今天

3、如果高于前一天，为了利润最大，今天应该买入，所以最大利润max增加相应的差价

第五天【2018-03-29】

今天是一个二叉查找树，地址在这里：，分两天写。

第六天【2018-03-30】

今天还是写二叉树，地址在这里：。

第七天【2018-04-01】

今天写一个超级简单的冒泡排序：

function bubbleSort(ary) {    for (let i = 0; i < ary.length; i++) {        for (let j = i + 1; j < ary.length; j++) {            if (ary[i] > ary[j]) {                //交换位置                let temp = ary[i]                ary[i] = ary[j]                ary[j] = temp            }        }    }    return ary}console.log(bubbleSort([1, 9, 4, 2, 55, 3, 0, -14]))   //[ -14, 0, 1, 2, 3, 4, 9, 55 ]复制代码

思路：冒泡排序的思路就是两个循环，就是让数组中的每一项都与后面所有的数比较，如果这一项比后面的数字大，则交换位置。

冒泡排序的思路简单易于理解，但是它的时间复杂度是所有排序中最高的O(n²)，这种排序方法基本不会在项目中使用。

第八天【2018-03-31】

今天再写一个简单的选择排序：

function slectionSort(ary) {    let min    for (var i = 0; i < ary.length - 1; i++) {        min = i        for (var j = i + 1; j < ary.length; j++) {            if (ary[j] < ary[min]) {                min = j            }        }        let temp = ary[min]        ary[min] = ary[i]        ary[i] = temp    }    return ary}console.log(slectionSort([1, 9, 4, 2, 55, 3, 0, -14]))   //[ -14, 0, 1, 2, 3, 4, 9, 55 ]复制代码

思路：

选择排序的思路跟冒泡相似，都是两个for循环。

冒泡是比较前后两个交换位置，而选择排序是先找到后面所有数字最小的，再与当前数字交换位置。

代码中min记录了内层循环的最小值，循环结束，交换外层循环当前项与min项

第九天【2018-04-02】

今天接着写插入排序：

function insertSort(ary) {    for(let i=1;i
   
    0 && ary[j - 1]>temp){            ary[j] = ary[j-1]            j--        }        //把第j项赋值为temp，相当于把temp插入到第j-1项后面了        ary[j] = temp    }    return ary}复制代码

哎，昨天虽然把插入排序写了，但是没有时间写分析了，这是第二天补上的，罪过罪过。

插入排序也属于比较慢的排序，因为也是用了两个循环。它的思路就是从第二项开始拿数字，然后用这个数字逐个与前面的数字比较，找到比它小的然后放到它后面。

第十天【2018-04-03】

基本排序终于写完了 --> 进化了 --> 今天写一个高级的归并排序：

归并排序是一个性能很好的排序算法，Firefox浏览器的Array.prototype.sort就是归并排序，Chrome浏览器用的是快速排序。

function mergeSort(ary) {    if (ary.length == 1) {        return ary    }    let mindle = Math.floor(ary.length / 2)    let left = ary.slice(0, mindle)    let right = ary.slice(mindle)    return merge(mergeSort(left), mergeSort(right))}function merge(left, right) {    let result = []    let il = 0    let ir = 0    while (il < left.length && ir < right.length) {        if (left[il] < right[ir]) {            result.push(left[il++])        } else {            result.push(right[ir++])        }    }    while (il < left.length) {        result.push(left[il++])    }    while (ir < right.length) {        result.push(right[ir++])    }    return result}console.log(mergeSort([1, 9, 4, 2, 55, 3, 0, -14]))   //[ -14, 0, 1, 2, 3, 4, 9, 55 ]复制代码

思路：归并排序的思想是分而治之。我理解就是把一个数组从中间无限分割，直到只剩一个元素，然后把这些数组的item取出来放入最后的数组中。

放的过程就涉及到比较，也就是上面代码的第一个while循环,这里面的代码保证了永远把最小的先放入数组中。

之前有一个问题困扰这我，如果两个数组中有一个先被取光，那那个剩下的岂不是没有排序？

其实剩下的那个已经是排序好的了，因为递归的关系，数组是从小逐渐变大的，所一之前的已经排好顺序了。

第十一天【2018-04-04】

今天写快速排序：

快排是处理大数据集最快的算法之一，它和归并排序一样也是一种分而治之的算法。

function fastSort(ary) {    if (ary.length == 0) {        return []    }    let pivot = ary[0]    let left = [], right = []    for (let i = 1; i < ary.length; i++) {        let current = ary[i]        if (current < pivot) {            left.push(current)        } else {            right.push(current)        }    }    return fastSort(left).concat(pivot, fastSort(right))}console.log(fastSort([1, 9, 4, 2, 55, 3, 0, -14]))   //[ -14, 0, 1, 2, 3, 4, 9, 55 ]复制代码

思路：

快排采用的是递归的方法，将数据依次分解为较小的数据集合(left)和较大的数据集合(right)，最后把这左中右三个数组组合在一起。

快排应用广泛，但是我的一个算法大牛兄弟曾经偷偷告诉我，当数据少的时候快排相对慢，可以使用归并排序进行优化。

第十二天【2018-04-05】

写一个简单的只能搜索：根据“80-20”原则，我们常用的数据其实只占20%，所以希望随着搜说次数的增加能够使我们能够更快的搜到常用数据：

function seqSearch(ary, data){    for(let i = 0; i< ary.length; i++){        if(ary[i] == data){            if(i > 0){                let temp = ary[i]                ary[i] = ary[i-1]                ary[i-1] = temp            }            return true        }    }    return false}复制代码

思路：

这个算法很简单，如果搜到这个数据返回true，否则返回false。只不过如果搜到的话会把这个数据向前移动一位，这样随着搜索次数的增加，常用的数据会一直往前移动，从而逐渐减少搜索次数。

第十三天【2018-04-06】

今天写一个二分搜索。

function binSearch(ary, data) {    let up = ary.length - 1    let down = 0    while (down <= up) {        let min = Math.floor((up + down) / 2)        if (ary[min] < data) {            down = min + 1        } else if (ary[min] > data) {            up = min - 1        } else {            return data        }    }    return -1}复制代码

思路：

二分搜索的前提条件是数据必须有序，起初设置一个上限和下限，然后通过循环比较中间的数字和数据的大小来缩小查找范围。

如果中间的数字比数据小，那么就把新的下限设置为中间的索引+1。

大的话就把上限设置为索引-1。

如果相等则返回数据。

第十四天【2018-04-07】

给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。你的算法应该是一个线性时间复杂度。你可以不用额外空间来实现它吗？

var singleNumber = function(nums) {    nums = nums.sort()    for (var i = 0; i < nums.length; i = i + 2) {        var prev = nums[i]        var next = nums[i + 1]        if (prev != next) {            return prev        }    }};console.log(singleNumber([1, 2, 1, 3, 2, 222, 4, 222, 4, 3, 8]))  //8复制代码

这是letCode上的一道题，思路是：

先对数组排序，然后一次两项循环数组，比较这两项如果不同，则返回第一项。

第十五天【2018-04-08】

实现一个任意对象的深拷贝：

function deepClone(obj){    if(obj == null || typeof obj != 'object') return obj    let newObj = obj.constructor()    for(let key in obj.getOwnPropertyDescriptors()){      newObj[key] = deepClone(obj[key])    }    return newObj}复制代码

这是一个递归实现，思路：

首先设递归终止条件，递归到不是对象为止

通过constructor创建一个新的对象

循环老对象的所有私有属性，递归赋值给新的对象

第十六天【2018-04-09】

写一个截流函数：

函数截流：就是防止短时间内的多次函数触发。例如，我们想在鼠标滚动的时候调用某个接口，鼠标滚动事件触发很快会造成短时间内多次调用接口造成性能损耗。

function throttle(fn, interval){    let prevTime = 0    return function(){        let thisTime = new Date()        if(thisTime - prevTime >= interval){            fn.apply(null, arguments)            prevTime = thisTime        }    }}let throttleFn = throttle(fn, 100)复制代码

思路：

函数截流使用了一个高阶函数实现，在闭包里储存一个上次函数执行的时间，返回一个新的函数。

判断上次的时间和这次时间差是否大于传入的间隔，大于的话执行函数并更新记录时间。

第十七天【2018-04-10】

写一个防抖函数：

函数防抖：与截流相似，防抖也是防止短时间内函数多次触发，只不过截流的目的是过滤掉不符合要求的操作，而防抖是符合要求之后才会调用函数。例如，我们监听输入框的change事件，但是想在用户输入完成时（也就是他停止输入一小段时间后）调用接口。

function shake(fn, interval) {    let timer = null;    return function(){        clearTimeout(timer);        let t_fn = fn.call(this)        timer = setTimeout(t_fn, interval)     }}复制代码

第十八天 - 第二十五天【2018-04-11】- 【2018-04-18】

最没有每天更新，但是也没有偷懒，用了一周时间写了domDiff算法，地址在这里。

第二十六天【2018-04-19】

给定两个数组，写一个方法来计算它们的交集。例如:给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

var intersect = function(nums1, nums2) {    let result = []    if(nums1.length>nums2.length){        let temp = nums1        nums1 = nums2        nums2 = temp    }    for (let i = 0; i < nums1.length; i++) {        let item = nums1[i]        let index = nums2.indexOf(item)        if (index > -1) {            let eve = nums2.splice(index, 1)[0]            result.push(eve)        }    }    return result};复制代码

思路：

首先，我们找到比较短的那个数组(当然这不是必须的)，然后循环它，如果其中一项在另一个数组中也存在，那么把它记录下来，同时删掉另一项里面的这一项。最后返回记录的数组。

第二十七天【2018-04-20】

给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。最高位数字存放在数组的首位,数组中每个元素只存储一个数字。你可以假设除了整数0之外，这个整数不会以零开头。

例如：输入: [1,2,3]；输出: [1,2,4]；解释: 输入数组表示数字 123。
输入: [1,2,9]；输出: [1,3,0]；解释: 输入数组表示数字 130

function plusOne(digits) {    let result = []    function next(currentAry) {        if (currentAry.length) {            let l = currentAry.pop()            //如果小于9，l+1入列，否则0入列，再递归上一位            if (l > 8) {                result.unshift(0)                //判断上一位有没有值，如果没有，给他创建一位，值为1                !currentAry.length && result.unshift(1)                next(currentAry)            } else {                result.unshift(l + 1)            }        }    }    next(digits)    return digits.concat(result)}复制代码

思路：

这个问题不难，就是把最后的一个数字+1，只不过涉及到如果最后一个是9，那么就需要进一位+1。

还需要注意一个问题，就是如果第一位是9的情况，例如92，9这一位的上一位已经没有值了，所以要自己新建一位。我在代码中已经标注。

第二十八天【2018-04-21】

letCode上的一道题目，判断一个 9x9 的数独是否有效。

function isValidSudoku(board) {    let columns = []    let box = {}    //循环每一列    for (let i = 0; i < board.length; i++) {        let row = board[i]        let boxRowIndex = Math.floor(i / 3)        let tempAry = []        //循环每一行        for (let j = 0; j < row.length; j++) {            let item = row[j]            //判断每一行的重复            if (item != '.' && tempAry.indexOf(item) > -1) {                return false            } else {                tempAry.push(item)            }            //判断每一列的重复            if (typeof columns[j] != 'undefined') {                if (item != '.' && columns[j].indexOf(item) > -1) {                    return false                } else {                    columns[j].push(item)                }            } else {                columns[j] = []                columns[j].push(item)            }            //判断每一个九宫格的重复            let boxColumnsIndex = Math.floor(j / 3) + ''            let boxIndex = boxRowIndex + boxColumnsIndex            if (typeof box[boxIndex] != 'undefined') {                if (item != '.' && box[boxIndex].indexOf(item) > -1) {                    return false                } else {                    box[boxIndex].push(item)                }            } else {                box[boxIndex] = []                box[boxIndex].push(item)            }        }    }    return true}复制代码

思路：

首先，这是个二维数组，至少需要两个循环遍历。我们需要判断三种情况：

每一行是否又重复

每一列是否有重复

每一个九宫格是否有重复

每一行好说，我们只需要维护一个数组tempAry，把每一行的每一个元素放进去，发现相同就返回false。并且在循环下一行的时候清空tempAry。

下面看每一列，和每一行思路差不多，我们维护一个二维数组columns，它记录着每一列的元素，同样是遇到重复返回false。

九宫格稍微麻烦一些，我们需要维护一个对象box，因为一个九宫格占用三行散列，所有我们使用了boxRowIndex和boxColumnsIndex的拼接来标记每一个九宫格，后面的思路还是一样，遇见相同的返回false。

第二十九天【2018-04-22】

请编写一个函数，其功能是将输入的字符串反转过来。

var reverseString = function(s) {    return s.split('').reverse().join('')};复制代码

这几天有些忙，落了几天，只能在letcode上找些简单的追上进度了,不用解释了，转成数组，反转后再转回来……

第三十一天【2018-04-23】

给定一个 32 位有符号整数，将整数中的数字进行反转。

例如：输入: 123，输出: 321；输入: -123，输出: -321；输入: 120，输出: 21。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

var reverse = function(x) {    x = x.toString()    let minus = x[0] === '-' ? '-' : ''    let result = x.split('').reverse().join('').replace(/^0+|-$/g, '')    result = Number(minus + result)    return Math.abs(result) < Math.pow(2,31)?result:0};复制代码

思路：

这个很简单，跟前一天的思路一样，只不过需要处理“-”和“0”，同时，判断是否反转后的数值溢出。

第三十二天【2018-04-24】

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

var firstUniqChar = function(s) {    for (let i = 0; i < s.length; i++) {        let ifEqual = false        for (let j = 0; j < s.length; j++) {            if (i != j && s[i] === s[j]) {                ifEqual = true            }        }        if (!ifEqual) {            return i        }    }    return -1}复制代码

var firstUniqChar = function(s) {    let obj = {}    for (let i = 0; i < s.length; i++) {        let item = s[i]        if (obj[item]) {            obj[item].num++        } else {            obj[item] = {                index: i,                num: 1            }        }    }    for (let key in obj) {        if (obj[key].num == 1) {            return obj[key].index        }    }    return -1};复制代码

思路：

这道题有两种解法，第一种不需要额外空间，但是时间复杂度为O(n2)，第二种时间复杂度为O(n)但是需要申请额外空间。具体用哪一种应该根据实际的场景选择，例如字符串长度较短，可以选择第一种，如果太长，那么应该选择第二种。

第三十三天【2018-05-22】

实现一个方法getKeys，返回字符串str在data中所有上级节点的名称，例如：

var data = {    key1: 'str1',    key2: {        key3: 'str3',        key4: 'str4',        key5: {            key6: 'str6'        }    }}getKeys(data, 'str1')  //'key1'getKeys(data, 'str3')  //'key2 key3'getKeys(data, 'str6')  //'key2 key5 key6'复制代码

实现：

function getKeys(data, str) {    let result = []    function search(d) {        for (let key in d) {            if (d[key] == str) {                result.push(key)                return            }            if (typeof d[key] == 'object') {                result.push(key)                search(d[key])            }        }    }    search(data)    return result.join(' ')}复制代码

第三十四天【2018-05-23】

实现一个数组随机打乱方法shuffle

性能差但是简单的解法

function shuffle2(a) {    return a.sort(function (a, b) {        return Math.random() > .5 ? 1 : -1    })}复制代码

性能好的解法：

function shuffle(a) {    let len = a.length;    for (let i = 0; i < len - 1; i++) {        let index = parseInt(Math.random() * (len - i));        let top = len - i - 1;        [a[index], a[top]] = [a[top], a[index]]    }}复制代码

第三十五天【2018-05-25】

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

例如：
输入: s = "anagram", t = "nagaram"；输出: true
输入: s = "rat", t = "car";输出: false

var isAnagram = function(s, t) {    if (s.length != t.length) return false;    for (let i = 0; i < s.length; i++) {        let item = s[i]        t = t.replace(new RegExp(item), '')    }    return t == ''};复制代码