前端面试拼图-数据结构与算法（二）

摘要：最近，看了下慕课2周刷完n道面试题，记录下...

1. 求一个二叉搜索树的第k小值

二叉树(Binary Tree)

是一棵树

每个节点最多两个子节点

树节点的数据结构{value, left?, right?}

二叉树的遍历

前序遍历：root→left→right

中序遍历：left→root→right

后序遍历：left→right→root

二叉搜索树BST（Binary Search Tree）

left（包括其后代） value ≤ root value

right （包括其后代） value ≥ root value

可使用二分法进行快速查找

解题思路：BST中序遍历，从小到大的排序

找到排序后的第k个值

/**
* 二叉搜索树
*/
interface ITreeNode {value: numberleft: ITreeNode | nullright: ITreeNode | null
}const arr: number[] = []/**
* 二叉树前序遍历
*/
function preOrderTraverse(node: ITreeNode | null) {if ( node == null) return//console.log(node.value)arr.push(node.value)preOrderTraverse(node.left)preOrderTraverse(node.right)
}/**
* 二叉树中序遍历
*/
function inOrderTraverse(node: ITreeNode | null) {if ( node == null) returninOrderTraverse(node.left)// console.log(node.value)arr.push(node.value)inOrderTraverse(node.right)
}/**
* 二叉树后序遍历
*/
function postOrderTraverse(node: ITreeNode | null) {if ( node == null) returnpostOrderTraverse(node.left)postOrderTraverse(node.right)// console.log(node.value)arr.push(node.value)
}/**
* **寻找BST中的第k小值**
*/
function getKthValue(node: ITreeNode, k: number): number | null {inOrderTraverse(node)console.log(arr)return arr[k-1] || null
}const bst: ITreeNode = {value: 5,left: {value: 3,left: {value: 2,left: null,right: null},right: {value: 4,left: null,right: null}},right: {value: 7,left: {value: 6,left: null,right: null},right: {value: 8,left: null,right: null}}
}//preOrderTraverse(tree)

平衡二叉树 | HZFE - 剑指前端 Offer题目描述https://febook.hzfe.org/awesome-interview/book1/algorithm-balanced-binary-trees 扩展：为何二叉树如此重要，而不是三叉树、四叉树？

性能、性能、还是性能！重要的事情说三遍

数组：查找快O(1)，增删慢O(n)；链表：查找慢O(n)，增删快O(1)

二叉搜索树BST：查找快、增删快—"木桶效应"

平衡二叉树

BST如果不平衡，那就又成了链表

所以要尽量平衡：平衡二叉搜索树BBST(其增删查，时间复杂度都是O(logn)，即树的高度)

红黑树：本质是一种自平衡二叉树

分为红/黑两种颜色，通过颜色转换来维持输的平衡

相对于普通平衡二叉树，它维持平衡的效率更高

B树

物理上是多叉树，但逻辑上是二叉树

一般用于高效I/O，关系型数据库常用B树来组织数据

扩展2：堆有什么特点？和二叉树又什么关系？

堆栈模型

JS执行时，值类型变量，存储在栈中；引用类型变量，存储在堆中

堆是完全二叉树

最大堆：父节点 ≥子节点

最小堆：父节点≤子节点

满二叉树(又叫完美二叉树)：所有层的节点都被填满；

完全二叉树：最底层节点靠左填充，其它层节点全被填满

7.1 二叉树 - Hello 算法动画图解、一键运行的数据结构与算法教程https://www.hello-algo.com/chapter_tree/binary_tree/#1_1 逻辑结构 VS 物理结构

堆：逻辑结构是一颗二叉树，但它的物理结构式一个数组

堆的使用场景

特别适合"堆栈模型"

堆的数据，都是在栈中引用的，不需要从root遍历

堆恰巧是数组形式，根据栈的地址，可用O(1)找到目标

2. JS计算斐波那契数列的第n个值

/**
* 斐波那契额数列(递归)
*/
function fibonacci(n:number): number{if(n <=1 ) return nreturn fibonacci(n-1) + fibonacci(n-2)
}

递归有大量重复计算，其时间复杂度是O(2^n)

优化：不用递归用循环，记录中间结果，时间复杂度O(n)

/**
* 斐波那契额数列(循环)
*/
function fibonacci(n:number): number{if(n <=1 ) return nlet n1 = 1  //记录n-1的结果let n2 = 0  //记录n-2的结果let res = 0for(let i = 2; i <= n; i++) {res = n1 + n2;// 记录中间结果n2 = n1n1 = res} return res
}

动态规划：

把一个大问题，拆解为一个小问题，逐级向下拆解

用递归的思想去分析问题，再改用循环来实现

算法三大思维：贪心、二分、动态规划

扩展：青蛙跳台阶问题，一只青蛙，一次可跳1级，也可跳两级，请问青蛙跳到n级台阶，总共有多少种方式？

第一次跳1级则有f(n-1)种方式，跳2级则有f(n-2)种方式，则结果和斐波那契额数列一样。

3. 将数组的0 移动到末尾

如输入[1,0,3,0,11,0]，输出[1,3,11,0,0,0]，只移动0，其他顺序不变；必须在原数组进行操作

传统思路

遍历数组，遇到0则push到数组末尾

用splice截取当前元素

时间复杂度O(n^2)—算法不可用

数组是连续存储，要慎用splice unshift 等API

/**
* 移动0到数组末尾(嵌套循环)
*/
function moveZero1(arr:number[]):void {const length = arr.lengthif(length === 0) returnlet zeroLength = 0// **O(n^2)**for (let i = 0; i < length - zeroLength; i++) {if (arr[i] === 0) {arr.push(0)arr.splice(i,1)  // 本身就有O(n)i-- //数组接去了一个元素，i要递减，否则连续0就会有错误zeroLength++ // 累加0的长度}}
}

双指针思路(解决嵌套循环的有效)

定义j指向第一个0，i指向j后面的第一个非0

交换i和j的值，继续向后移动

只遍历一次，所以时间复杂度是O(n)

/**
* 移动0到数组末尾(双指针)
*/
function moveZero2(arr:number[]):void {const length = arr.lengthif(length === 0) returnlet ilet j = -1 // 指向第一个0for(i=0; i < length; i++) {if(arr[i] === 0) {if (j < 0) {   // 第一个0j = i}}if(arr[i] !== 0 && j >=0 ) {const n = arr[i]arr[i] = arr[j]arr[j] = nj++}}
}

4. 获取字符串中连续最多的字符，以及次数

如输入'abbcccddeeee1234'，计算得到连输最多的字符是'e'，为4次

传统思路

嵌套循环，找出每个字符的连续次数，并记录

看似时间复杂度是O(n^2)

但实际时间复杂度是多少？—O(n),因为有'跳步'

/**
* 求连续最多的字符和次数（嵌套循环）
*/
interface IRes {char: stringlength: number
}
function findContinuousChars1(str:string):IRes {const res:IRes = {char: '',length: 0}const length = str.lengthif (length === 0) return reslet tempLength = 0 //临时记录当前连续字符串的长度// 时间复杂度O(n)for(let i = 0; i < length; i++) {tempLength = 0 // 重置for(let j = i; j < length; j++) {if (str[i] === str[j]) {tempLength++}if(str[i] !== str[j] || j === length-1) {// 不相等，或者已经到最后一个元素。要去判断最大值if (tempLength > res.length) {res.char = str[i]res.length = tempLength}if (i < length - 1) {i = j -1   // 跳步}break}}}  return res
}

双指针思路(适用于解决嵌套循环类问题)

定义指针i和j；j不动，i继续移动

如果i和j的值一直相等，则i继续移动

直到i和j的值不相等，记录处理，让j追上i。继续第一步

/**
* 求连续最多的字符和次数（双指针）
*/
interface IRes {char: stringlength: number
}
function findContinuousChars2(str:string):IRes {const res:IRes = {char: '',length: 0}const length = str.lengthif (length === 0) return reslet tempLength = 0 //临时记录当前连续字符串的长度// 时间复杂度O(n)let i = 0let j = 0for(; i < length; i++) {if(str[i] === str[j]) {tempLength++}if(str[i] !== str[j] || i === length-1) {// 不相等，或者i到了字符串的末尾if(tempLength > res.length) {res.char = str[j]res.length = tempLength}tempLength = 0  //重置长度if(i < length - 1) {j = i //让j"追上" ii--}}}return res
}

ps：算法题尽量使用低级的代码，慎用语法糖或者高级API