河北电子网站建设,企业查询卡在哪里打印,宁晋网站建设设计,向google提交网站摘要#xff1a;最近#xff0c;看了下慕课2周刷完n道面试题#xff0c;记录下...
1. 求一个二叉搜索树的第k小值 二叉树(Binary Tree) 是一棵树 每个节点最多两个子节点 树节点的数据结构{value, left?, right?} 二叉树的遍历 前序遍历#xff1a;root→left→right 中…摘要最近看了下慕课2周刷完n道面试题记录下...
1. 求一个二叉搜索树的第k小值 二叉树(Binary Tree) 是一棵树 每个节点最多两个子节点 树节点的数据结构{value, left?, right?} 二叉树的遍历 前序遍历root→left→right 中序遍历left→root→right 后序遍历left→right→root 二叉搜索树BSTBinary 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指向第一个0i指向j后面的第一个非0 交换i和j的值继续向后移动 只遍历一次所以时间复杂度是O(n)
/**
* 移动0到数组末尾(双指针)
*/
function moveZero2(arr:number[]):void {const length arr.lengthif(length 0) returnlet ilet j -1 // 指向第一个0for(i0; 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和jj不动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
5. 用JS实现快速排序并说明时间复杂度 6. 获取1-10000之前所有的对称数 7. 如何实现高效的英文单词前缀匹配 未完待续……
