数据结构
分类
线性结构 - 数组，链表，栈，队列，哈希表
树
-
图（graph） 多对多关联关系
衡量指标：
- 时间复杂度
- 把执行时间简化为一个数量级
- 二分查找O(logn)
- 空间复杂度
- 把代码运行过程中占用的空间成本
数组
- 顺序存储
- 适用于读取操作：O(1)，插入／删除：O(n)
- 超长度插入，则会创建新数组：创建一个长度为旧数组长度2倍的新数组，将旧数组中的值依次加入到新数组
链表
- 绿皮火车车箱，类型地下党，只知上级下级，不知其他
- 随机存储
- 读取：O(n), 插入／删除:O(1)
栈／队列
- 栈 stack ,追溯历史，面包屑导航，后进先出
- 队列 Queue 历史回放, 先进先出
散列表
- 也叫哈希表，键值对映射
- 本质上是数组，下标不是数组，而是key
- 哈希函数，将key和数组下标进行转换，通过位运算
读写操作
- 将key转换为数组下标值
- 查找数组下标有无对应值，无则填充，有则改写
哈希冲突
通过哈希函数将key转换为数组下标，当已有相同的下标时，称为哈希冲突
如何解决？
- 开放寻址法， 向后推一位
- 链表法， java中的hashMap,有冲突，变为链表
扩容
- 创建一个长度为之前2倍的新数组
- 将之前的元素依次放入新数组中
树
节点，根节点，叶子结点
可以通过链表或数组实现
二叉树
遍历：
- 前序遍历： 根节点，左子树，右子树 （深度优先）
- 中序遍历： 左子树，根节点，右子树（深度优先）
- 后序遍历： 左子树，右子树，根节点（深度优先）
- 层序遍历- 广度优先，通过队列实现
二叉堆
有序完全二叉树
最大堆
最小堆
自我调整
- 插入，O(logn), 从最后一个位置，向上浮动对比
- 删除，O(logn), 从堆顶的位置，堆顶元素删除后，将最后一个位置临时补到堆顶的位置，之后向下调整
顺序存储
计算下标： 如果父节点下标为parent，左孩子下标为 2parent + 1, 右孩子下标为2parent + 2
优先队列
最大优先队列，最大元素优先出队
最小优先队列，最小元素优先出队
使用二叉堆来实现
排序算法
-
冒泡排序
-
双层循环
function bubbleSort(arr){ for(var i=0; i<arr.length-1; i++) { for(var j=0;j<arr.length-1-i;i++){ if(arr[j]>arr[j+1]){ [arr[j], arr[j+1]] = [arr[j+1], arr[j]] } } } } -
优化点：当数组已经是有序的时候，直接break
function bubbleSort(arr){ for(var i=0; i<arr.length-1; i++) { // 有序标记，每轮初始值为true var isSorted = true for(var j=0;j<arr.length-1-i;i++){ if(arr[j]>arr[j+1]){ [arr[j], arr[j+1]] = [arr[j+1], arr[j]] // 元素有交换，说明无序 isSorted = false } if(isSorted) break } } } -
优化二：记录最后一次元素交换的位置，该位置则为无序数列的边界，后面是有序区
function bubbleSort(arr){ // 记录最后一次交换的位置 let lastChangeIndex = 0 // 无序数列的边界，每次比较到这里就可以了 let sortBorder = arr.length -1 for(var i=0; i<arr.length-1; i++) { // 有序标记，每轮初始值为true var isSorted = true for(var j=0;j < sortBorder;i++){ if(arr[j]>arr[j+1]){ [arr[j], arr[j+1]] = [arr[j+1], arr[j]] // 元素有交换，说明无序 isSorted = false // 更新最后一次交换的位置 lastChangeIndex = j } sortBorder = lastChangeIndex if(isSorted) break } } }
-
-
鸡尾酒排序 -基于冒泡排序的一种升级排序法
-
比较和交换过程是双向的，第一轮从左到右，第二轮从右到左，依次进行
function fn(arr) { let tmp = 0 for(var i=0; i<arr.length/2; i++) { var isSorted = true //有序标记 //从左到右 for(var j = i; i<arr.length-1-i; j++){ if(arr[j]> arr[j+1]){ [arr[j], arr[j+1]] = [arr[j+1], arr[j]] // 元素有交换，说明无序 isSorted = false } } if(isSorted) break //从右到左 isSorted = true //有序标记重新初始 for(var j = arr.length-1-i;j>i;j--){ if(arr[j-1]> arr[j]){ [arr[j-1], arr[j]] = [arr[j], arr[j-1]] // 元素有交换，说明无序 isSorted = false } } if(isSorted) break } }
-
选择排序
插入排序
-
快速排序
分治法， O(nlogn)，最坏情况O(n*n)
选择基准元素（pivot），一般第一个元素
-
双边循环法
首元素为基准元素，首尾元素为left和right，从right开始对比基准元素，如果大于基准，切换成left, 对比基准元素，依次进行，当指针重合，循环结束
-
单边循环法
function quickSort(arr){ if(arr.length<=1) return arr let pivot = arr.shift() let left = [] let right = [] for(var i = 0;i<arr.length;i++){ if(i>pivot){ right.push(arr[i]) }else{ left.push(arr[i]) } } return quickSort(left).concat(pivot, quickSort(right)) }非递归实现
归并排序
-
堆排序
1.把无序数组构建成二叉堆，需要从小到大排序则构建成最大堆，需要从大到小排序，则构建最小堆
2.循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶
时间复杂度O(nlogn)
-
计数排序
不需要元素之间比较，通过数组下标来确定元素的正确位置
创建一个统计数组，长度为arr的最大值和最小值的差值，遍历arr，新数组对应的下标符合则加1
适用于一定范围内的整数排序
-
桶排序
时间复杂度O(n)
针对计数排序的局限性（一定范围内的整数排序）的升级
算法题
-
如何判断一个链表是否有环？
-
利用hashmap,遍历的时候，加入hashMap,对比在hashMap中是否有相同的
时间 O(n),空间O(n)
-
双指针
时间 O(n),空间O(1)
创建两个指针，先都指向第一个节点，每次遍历时，第一个指针走一步，第一个指针走两步，依次对比
function double(node) { let p1 = node.head let p2 = node.head while(p2 != null && p2.next != null) { p1 = p1.next p2 = p2.next.next if(p1 == p2) return true } return false }
-
-
实现最小栈
栈a,和备胎栈b，依次进栈a，最小值进栈b,依次进行，碰到比b栈顶小的元素，则再进栈b
进栈出栈取最小值的时间复杂度都是O(1)
-
如何求出最大公约数
-
暴力法 O(min(a,b))
取最小值的一半，开始遍历，如果满足被两个数模为0（%／i == 0），则最大公约数为i
-
辗转相除法 --欧几里得算法
a和b的最大公约数等于 a % b,和 b 的最大公约数，然后递归 这里a>b，
function mord(a,b) { let big = a> b?a:b let small = a<b ?a :b if(big % small == 0) return small return mord(big%small, small) }-
更相减损术 O(max(a-b))
和欧几里得算法的区别是 mord(big - small, small)， 是差值不是模值，其他一样
避免俩个大整数取模的性能问题，但是当差值过大时，会遍历多次，比如最大值1000，最小值1，得遍历999次
-
位运算符 O(log(max(a-b)))
解决上面的问题，将上面两种算法优势结合起来
a&1 == 0代表偶数，否则为奇数
function gcd(a, b) { if(a == b) return a if(a&1 == 0 && b&1 ==0){ return gcd(a>>1, b>>1)<<1 }else if(a&1 == 0 && b&1 !=0){ return gcd(a>>1, b) }else if(a&1 != 0 && b&1 ==0){ return gcd(a, b>>1) }else{ let big = a>b?a:b let small = a<b?a:b return gcd(big-small, small) } }
-
- 如何判断一个数是否是2的整数次幂
// O(logn)
function rr(n){
let temp = 1
while(temp <= n){
if(temp == n)return true
temp = temp *2
// 位移替代 * ，性能高
//temp = temp<<1
}
return false
}
O(1)复杂度解法
// 利用2的次幂转换为2进制
function rr3(n) {
return (n&n-1) == 0
}
-
无序整数数组排序（有序）后的，任意两个相邻元素的最大差值
- 先排序，再遍历算两两相邻的差值，性能差
- 利用计数排序的思想
- 利用桶排序的思想
-
如何用栈实现队列
用两个栈来实现
元素依次进入栈a，栈a中元素出栈进入栈b
入队进栈a，出队用栈b
function likeQueue() { let stackA = new Stack() let stackB = new Stack() // 入对 O(1) let enQueue = (el)=>{ statckA.push(el) } // 出对 O(n) let deQueue = ()=>{ if(statckB.isEmpty()) { if(statckA.isEmpty()) return null transfer() } return statckB.pop() } //将栈a元素移动到栈b let transfer = ()=>{ while(!statckA.isEmpty()) { statckB.push(statckA.pop()) } } return { enQueue, deQueue } }
-
给出一个正整数，请找出这个正整数所有数字全排列的下一个数
就是在数字的全部组合中个，找到一个大于且仅大于原数的新整数
eg: 输入12345，result: 12354
输入12354，则返回：12435
输入12435，则返回：12453
逆排序，最大54321
-
顺排序，最小12345
eg: 12354
- 从后向前查看逆序区域（54），找到逆序区域的前一位(3)
- 让逆序区域的前一位（3）和逆序区域（54）中最小的数字（4），交换位置（12453）
- 把现在的逆序区域（53）转为顺序（35）=》 12435
