js常见算法题-白红宇

1.如下是tries树的实现，请书写结果。

var s = []var arr = sfor (var i = 0; i < 3; i++) {    var pusher = {      value: 'item' + i      },tmp        if (i !== 2) {        tmp = []        pusher.children = tmp    }    arr.push(pusher)    arr = tmp // arr每次都等于上一次的children,js指针的移动,arr的指针从s移动到了tmp，缓存了上次的children.}console.log(s[0]) // {value: "item0", children: [ {value: "item2"}]}pusher.children = []pusher = {value: 'item0',children: []  }arr = [{value: 'item0',children: []  }]arr = []复制代码

2.分别简述队列、栈、堆的区别？

队列是先进先出：就像一条路，有一个入口和一个出口，先进去的就先出去。

栈是后进先出：就像摞盘子一样，摞在上边的先被使用。

堆是在程序运行时，而不是在程序编译时，申请某个大小的内存空间。即动态分配内存，对其访问和对一般内存的访问没有区别。类似于钱包，可以用钱，用完了还回去。

栈(Stack)是操作系统在建立某个进程时或者线程为这个线程建立的存储区域。在编程中，例如C/C++中，所有的局部变量都是从栈中分配内存空间，实际上也不是分配，只是从栈顶向上用就行，在退出函数的时候，只是修改栈指针就可以把栈中的内容销毁，所以速度最快。

堆(Heap)是应用程序在运行的时候请求操作系统分配给自己的内存，一般是申请/给与的过程。由于从操作系统管理的内存分配所以在分配和销毁时都要占用时间，所以用堆的效率低的多！但是堆的好处是可以做的很大，C/C++对分配的Heap是不初始化的。

总结:栈(stack)会自动分配内存空间，会自动释放。堆(heap)动态分配的内存，大小不定也不会自动释放。

3.基本类型和引用类型（接2）

基本类型：简单的数据段，存放在栈内存中，占据固定大小的空间。包括undefined、string、boolean、null、Number

引用类型：指那些可能有多个值构成的对象，保存在堆内存中，包含引用类型的变量实际上保存的不是变量本身，而是指向该对象的指针。

4.按值传递和按引用传递（接3）

从一个向另一个变量复制引用类型的值，复制的其实是指针，因此两个变量最终指向同一个对象。即复制的事栈中的地址而不是堆中的对象。

从一个变量复制另一个变量的基本类型的值，会创建这个值的副本。

5.用JavaScript实现二分法查找

二分法查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤：

（1）首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。

（2）如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

二分查找：A为已按‘升序排列’的数组，x为要查询的元素返回目标元素的下标

function binarySearch(A, x) {    var low = 0,high = A.length -1    while (low <= high) {        var mid = Math.floor((low + high) / 2)                if (x == A[mid]) {            return mid        }                if (x < A[mid]) {            high = mid -1        } else {            low = mid + 1        }    }    return -1}复制代码

6.用JavaScript实现数组快速排序

关于快排算法的详细说明，可以参考阮一峰老是的文章快速排序“快速排序”的思想很简单，整个排序过程只需要三步：

（1）在数据集之中，选择一个元素作为“基准”（pivot）

（2）所有小于“基准”的元素，都移动到“基准”的左边；所有大于“基准”的元素都移到“基准”的右边

（3）对“基准”左边和右边的两个子集，不断重复第一步和第二步，知道所有子集只剩下一个元素为止。

方法一（尽可能不用js数组方法）:

function qSort(arr,low,high) {    if(low < high) {        var partKey = partition(arr,low,high)        qSort(arr,low,partKey - 1)        qSort(arr,partKey + 1, high)    }}function partition(arr,low,high) {    var key = arr[low]    while(low < high) {        while(low < high && arr[high] >= arr[key]) {            high--            arr[low] = arr[high]        }                while(low < high && arr[low] <= arr[key]) {            low++            arr[high] = arr[low]        }        arr[low] = key        return low    }}复制代码

方法二（使用js数组方法）：

function quickSort(arr) {    if (arr.length <= 1) {        return arr    }    var index = Math.floor(arr.length / 2)    var key = arr.splice(index,1)[0]    var left = [],right = []    arr.forEach(function(v){      v <= key ? left.push(v) : right.push(v)    })    return quickSort(left).concat([key],quickSort(right))}复制代码

方法三：递归法

复制代码

7.编写一个方法，求一个字符串的字节长度

算法题一般都是一成不变的

假设:一个英文字符占用一个字节，一个中文字符占用两个字节

function GetBytes(str) {    var len = str.length    var bytes = len    for (var i = 0; i < len; i++) {        if (str.charCodeAt(i) > 255) {            bytes++        }    }    return bytes}alert(GetBytes('你好，world'))复制代码

8.找出下列正数组的最大差值

输入[20, 3, 11, 19, 16, 14]

竟然输出 16，正确应该是17，原因待查

function getMaxProfit(arr) {    var minPrice = arr[0]     var maxProfit = 0         for (var i = 0; i < arr.length; i++) {        var currentPrice = arr[i]        // 获取最小值        minPrice = Math.min(minPrice, currentPrice)         // 获取当前值与最小值的差值        var potentialProfit = Math.abs(currentPrice - minPrice)        // 获取差值中的最大值        maxProfit = Math.max(maxProfit, potentialProfit)            }    return maxProfit}复制代码

9.判断一个单词是否是回文

回文：回文指把相同的词汇或句子，在下文中调换位置或者颠倒过来，产生首尾回环的情况，叫做回文，也叫回环。比如mamam 、redivider

function checkPalindrom(str) {    return str == str.split('').reverse().join('')}// while loopconst isPalindromicB = (w) => {    let len = w.length        let start = Math.ceil(len / 2)        while(start < len) {        if (s[start] !== w[len - start - 1]) {            return false        }        start++    }    return true}复制代码

10.如何消除一个数组里面重复的元素

基本数组去重（最好）

Array.prototype.unique = function() {    var result = []    this.forEach(function(v){        if(result.indexOf(v) < 0) {            result.push(v)        }    })    return result}复制代码

利用hash表去重，这是一种空间换时间的方法

Array.prototype.unique = function () {    var result = [],hash = {}    this.forEach(function(v) {        if (!hash[v]) {            hash[v] = true            result.push(v)        }    })    reutrn result}复制代码

上面的方法存在一个bug，对于数组[1,2,'1','2',3],去重结果为[1,2,3]，原因在于对象索引时会进行强制类型转换，arr['1']和arr[1]得到的都是arr[1]的值，因此需做一些改变：

Array.prototype.unique = function () {    var result = [],hash = {}    this.forEach(function(v){        var type = typeof(v) // 获取元素类型        hash[v] || (hash[v] = new Array())        if (hash[v].indexOf(type) < 0) {            hash[v].push(type) //存储类型            result.push(v)        }    })    return result}复制代码

先排序后去重

Array.prototype.unique = function() {    var result = [this[0]]    this.sort()    this.forEach(function(v){      v != result[result.length -1] && result.push(v) // 仅与result最后一个元素比较    })}复制代码

11.统计字符串中字母个数或统计最多字母数

输入： afijghiaaafsaadaes

输出： a

统计字符串中字母个数与统计最多字母数的思路相同

把每一道题的思路先写出来

思路：

统计字符串中字母个数：我们需要遍历所给的字符串，先拿一个字符放到新空间中，然后再拿第二个，与第一个进行比较，如果相同则丢弃，如果不相同则放到新数组中...,处理完则获得了字符串中的字母个数，将对应的长度返回即可。

统计最多字母数，并返回个数：比第一个多了个记录对应个数的操作。找到相同的元素时，将对于的元素的计数器加1.找到最大的计数，并返回。

function findMaxDuplicateChar(str) {    if (str.length == 1) {        return str    }    let charObj = {}    for(let i = 0; i< str.length; i++) {        if (!charOjb[str.charAt(i)) {            charObj[str.charAt(i)] = 1        } else {            charObj[str.charAt(i)] += 1        }    }    let maxChar = ''    maxValue = 1    for(var k in charObj) {        if (charObj[k] >= maxValue) {            maxChar = k            maxValue = charObj[k]        }    }    return maxChar}复制代码

秒杀与数组结合的个方法，找出数组中相同的项，写文章出来

12.随机生成指定长度的字符串 -. 整理Math的常用方法

function randomString(n) {    let str = 'abcdefghijklmnopqrstuvwxyz9876543210'    let tmp = '',i = 0, len = str.length        for (i = 0; i < n; i ++) {        tmp += str.charAt(Math.floor(Math.random() * len))    }    return tmp}复制代码

13.写一个isPrime()函数，当其为质数时返回true，否则返回false.

最基础的要把所有的偶数先排除掉。

质数：又称素数。指整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的作用。质数的分布规律是以36N（N+1）为单位，随着N的增大，素数的个数以波浪形式渐渐增多。

首先，因为JavaScript不同于C或者Java，因此你不能信任传递来的数据类型。如果面试官没有明确地告诉你，你应该询问他是否需要做输入检查，还是不进行检查直接写函数。严格上说，应该对函数的输入进行检查。

第二点要记住，负数不是质数。同样的，1和0也不是，因此，首先测试这些数字。此外，2是质数中唯一的偶数。没有必要用一个循环来验证4，6，8。再则，如果一个数字不能被2整除，那么它不能被4，6，8等整除。因此，你的循环必须跳过这些数字。如果你测试输入偶数，你的算法将慢2倍（你测试双倍数字）。可以采取其他一些更明智的优化手段，我这里采用的是适用于大多数情况的。例如，如果一个数字不能被5整除，它也不会被5的倍数整除。所以，没有必要检测10，15，20等等。

最后一点，你不需要检查比输入数字的开方还要大的数字。我感觉人们会漏掉这一点，并且也不会因此而获得消极的反馈。但是，展示出这一方面的知识会额外加分。

function isPrime(number) {    if (typeof number !== 'number' || !Number.isInteger(number)) {        return false    }    if (number < 2) {        return false    }    if (number === 2) {        return true    } else if (number % 2 === 0) {        return false    }        var squareRoot = Math.sqrt(number)    for (var i = 3; i <= squareRoot; i += 2) {        if (number % i === 0) {            return false        }    }    return true}复制代码

14.有100格台阶，可以跨1步可以跨2步。那么一共有多少种走法

本质是斐波那契数列算法(数学公式) 总会遇到自己不会的东西，不会了就去积累

方法一function step() {    this.n1 = 1    this.n2 = 2    this.total = 100    this.getFunction = getFunction}var Stairs = new step()function getFunction() {    for (i = 2;i < this.tatal; i++) {        res = this.n1 + this.n2        this.n1 = this.n2        this.n2 = res    }    return res}var totalStairs = Stairs.getFunction()alert(totalStairs)方法二function fib (n) {    let array = new Array(n + 1).fill(null)    array[0] = 0    array[1] = 1    for (let i = 2; i <= n; i++) {        array[i] = array[i - 1] + array[i - 2]    }    return array[n]}复制代码

延伸：斐波那契数列指的是类似于以下的数列：

1, 1, 2, 3, 5, 8, 13, ....复制代码

也就是，第 n 个数由数列的前两个相加而来：f(n) = f(n - 1) + f(n -2)

请你完成 fibonacci 函数，接受 n 作为参数，可以获取数列中第 n 个数，例如：

fibonacci(1) // => 1fibonacci(2) // => 1fibonacci(3) // => 2...复制代码

解法

递归解法const fibonacci = (n) => {    if (n <= 2) {        return 1    } else {        return fibonacci(n-1) + fibonacci(n-2)    }}复制代码

15.链表与数组的区别(数据结构)

数组数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素。，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少插入和删除元素，就应该用数组，

链表链表中的元素是不存在顺序存储的，而是通过存在元素中的指针联系在一起，每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针。如果要访问链表中的一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。

内存存储区别

数组从栈中分配空间，对于程序员方便快速，但自由度小。

链表从堆中分配空间，自由度大，但申请管理比较麻烦。 逻辑结构区别

数组必须实现定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。

链表动态地进行存储分配，可以适应数据动态增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

总结

存取方式上，数组可以顺序存取或随机存取，而链表只能顺序存取；

存储位置上，数组逻辑上相邻的元素在物理逻辑上也相邻，而链表不一定；

存储空间上，链表由于带有指针域，存储密度不如数组大；

按序号查找时，数组可以随机访问，时间复杂度为o(1),而链表不支持随机访问，平均需要o(n);

按值查找时，若数组无序。数组和链表时间复杂度为o(n),但是当数组有序时，可以采用折半查找将时间复杂度降为o(logn);

插入和删除时，数组平均需要移动n/2个元素，而链表只需要修改指针即可；

空间分配方面：数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败；

链表存储的节点空间值在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；

经典数据结构涵盖了多种抽象数据类型（ADT），其中包括栈、队列、有序列表、排序表、哈希表及分散表、树、优先队列、集合和图等。对于每种情况，都可以选用数组或某一种链表数据结构来实现其抽象数据类型（ADT）。由于数组和链表几乎是建立所有ADT的基础，所以称数组与链表为基本数据结构。

16.快速排序

快速排序是冒泡排序的优化。

思路：在数组列表中选择一个元素作为基准值，围绕这个基准值进行排序,比它大的放到该元素后边，比它小的放到该元素前边，如此重复直至全局正序排列。通常默认以第一个元素为初始值。可利用递归思想。

function quickSort(arr) {    if (arr.length < 2) {        return arr    }    let flag = arr[0]    let left = []    let right = []    // 从第二个元素开始循环    for (let i = 1; i < arr.length; i ++) {        if (arr[i] < flag) {            left.push(arr[i])        }        if (arr[i] > flag) {            right.push(arr[i])        }    }    return quickSort(left).concat(flag, quickSort(right))}复制代码

上述方法会将重复的元素忽略掉。

17.将一个数组打乱

function shuffle (arr) {    var len = arr.length, i = len, nTemp, iRandom;        while (i--) {        if (i !== (iRandom = Math.floor(Math.random()*len)) {                    }    }    }复制代码

18.二叉树

二叉树是一种非线性的数据结构，分层存储。

树被用来存储具有层级关系的数据，还被用来存储有序列表。

二叉树进行查找特别快，二叉树添加和删除元素也非常快。

集合中不允许相同成员存在。

定义：

树由一组以边连接的节点组成。

一棵树最上边的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。没有任何节点的子节点称为叶子节点。

二叉树是一种特殊的树，子节点个数不超过两个。

从一个节点走到另一个节点的这一组变称为路径。

以某种特定顺序访问书中的所有节点称为树的遍历。

树分为几个层次，根节点是第0层，它的子节点为第1层，以此类推。我们定义书的层数就是树的深度。

每个节点都有一个与之相关的值，该值有时被称为键。

一个父节点的两个子节点分别称为左节点和右节点。二叉树是一种特殊的二叉树，相对较小的值保存在左节点，较大的值保存在右节点，这一特性使得查找效率很高。

树一般有3种遍历方法：

先序遍历：会先遍历根，再遍历左节点，再遍历右节点。

中序遍历：先遍历左节点，再遍历根，最后遍历右节点。

后序遍历：先遍历左节点，再遍历右节点，然后再遍历根节点。

遍历、最大宽度

function Node(data, left, right) {    this.data = data    this.left = left    this.right = right    this.show = show}function show () {    return this.data}function BST () {   this.root = null   this.insert = insert   this.inOrder = inOrder   this.getSmallest = this.getSmallest   this.getMax = getMax   this.find = find   this.remove = remove}function insert(data) {    var n = new Node(data,null,null)    if (this.root == null) {        this.root = n    } else {        var current = this.root        var parent        while(true) {            parent = current            if (data < current.data) {                current = current.left                if (current == null) {                    parent.left = n                    break                } else {                    current = current.right                    if (current == null) {                        parent.right = n                        break                    }                }            }        }    }}// 中序遍历function inOrder(node) {    if (node !== null) {        inOrder(node.left)        inOrder(node.right)    }}// 查找最小值function getSmallest(root) {   var current = this.root || root   while(!(current.left == null)) {       current = current.left   }   return current.data}// 查找最大值function getMax(root) {    var current = this.root || root    while(!(current.right == null)) {        current = current.right    }    return current.data}// 查找特定值function find(data) {    var current = this.root    while(current != null) {        if(current.data == data) {            reutrn current        } else if (data < current.data) {            current = current.left        } else {            current = current.right        }    }    return null}// 删除function remove(data) {    removeNode(this.root,data)}function removeNode(node,data) {    if (node == null) {        return null    }    if (data == node.data) {        if (node.left == null && node.right == null) {            return null        }        if (node.left == null) {            return node.right        }        if (node.right == null) {            return node.left        }        var tempNode = getSmallest(node.right)        node.data = tempNode.data        node.right = removeNode(node.right, tempNode.data)        return node    } else if (data < node.data) {        node.left = removeNode(node.left,data)        return node    } else {        node.right = removeNode(node.right,data)        return node    }}var nums = new BST()nums.insert(23)nums.insert(45)nums.insert(16)nums.insert(37)nums.insert(3)nums.insert(99)nums.insert(22)console.log('遍历节点')nums.inOrder(nums.root)console.log("最小节点", nums.getSmallest())console.log("最大节点", nums.getMax())复制代码

leetCode 98题给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入:    2   / \  1   3输出: true示例 2:输入:    5   / \  1   4     / \    3   6输出: false解释: 输入为: [5,1,4,null,null,3,6]。     根节点的值为 5 ，但是其右子节点值为 4 。复制代码

19.快速排序及其时间复杂度

思路：在列表中选择一个元素作为基准值，围绕这个基准值进行排序。然后再把基准值左边的排好，把右边的排好。如此重复直至全部正序排列。

通常默认以第一个元素为初始值（标尺）。利用递归的思想进行解决。

下面方法占用内存较多

function quickSort (arr) {    if (arr.length < 2) {        return arr    }    let flag = arr[0]    let left = []    let right = []    for (let i = 1; i < arr.length; i++) {        if (arr[i] < flag) {            left.push(arr[i])        }        if (arr[i] > flag) {            right.push(arr[i])        }    }    return quickSort(left).concat(flag, quickSort(right))}复制代码

快速排序的平均时间复杂度也是：O(nlogn) 快速排序最优的情况下时间复杂度为：O( nlogn ) 快速排序最差的情况下时间复杂度为：O( n^2 )