js常见算法题

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

var s = []
var arr = s
for (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 loop
const 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. 统计字符串中字母个数：我们需要遍历所给的字符串，先拿一个字符放到新空间中，然后再拿第二个，与第一个进行比较，如果相同则丢弃，如果不相同则放到新数组中...,处理完则获得了字符串中的字母个数，将对应的长度返回即可。

2. 统计最多字母数，并返回个数：比第一个多了个记录对应个数的操作。找到相同的元素时，将对于的元素的计数器加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) // => 1
fibonacci(2) // => 1
fibonacci(3) // => 2
...
复制代码

解法

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

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

• 数组 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素。，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少插入和删除元素，就应该用数组，
• 链表 链表中的元素是不存在顺序存储的，而是通过存在元素中的指针联系在一起，每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针。 如果要访问链表中的一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。

内存存储区别

1. 数组从栈中分配空间，对于程序员方便快速，但自由度小。
2. 链表从堆中分配空间，自由度大，但申请管理比较麻烦。 逻辑结构区别
3. 数组必须实现定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
4. 链表动态地进行存储分配，可以适应数据动态增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

总结

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

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

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

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

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

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

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

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

8. 经典数据结构涵盖了多种抽象数据类型（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.二叉树

1. 二叉树是一种非线性的数据结构，分层存储。
2. 树被用来存储具有层级关系的数据，还被用来存储有序列表。
3. 二叉树进行查找特别快，二叉树添加和删除元素也非常快。
4. 集合中不允许相同成员存在。

定义：

1. 树由一组以边连接的节点组成。
2. 一棵树最上边的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。没有任何节点的子节点称为叶子节点。
3. 二叉树是一种特殊的树，子节点个数不超过两个。
4. 从一个节点走到另一个节点的这一组变称为路径。
5. 以某种特定顺序访问书中的所有节点称为树的遍历。
6. 树分为几个层次，根节点是第0层，它的子节点为第1层，以此类推。我们定义书的层数就是树的深度。
7. 每个节点都有一个与之相关的值，该值有时被称为键。
8. 一个父节点的两个子节点分别称为左节点和右节点。二叉树是一种特殊的二叉树，相对较小的值保存在左节点，较大的值保存在右节点，这一特性使得查找效率很高。

树一般有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 )