11、图
11-1图是什么?
-
图是网络结构的抽象模型,是一-组由边连接的节点。
-
图可以表示任何二元关系,比如道路、航班。
-
JS中没有图,但是可以用
Object
和Array
构建图。 -
图的表示法:邻接矩阵、邻接表、关联矩….
如果节点A能连接到节点B,那么矩阵B对应的行或者列表示为1,否则为0
节点A能连接到节点B,那么A:[“B”],这个比较好理解的。
图的常用操作
- 深度优先遍历
- 广度优先遍历
11-2图的深度优先遍历算法口诀
- 访问根节点。
- 对根节点的没访问过的相邻节点挨个进行深度优先遍历。
没访问过的相邻节点:如上图所示,如果从节点2开始遍历,优先遍历节点0,节点0在返回到节点2就会造成死循环,如果加个没访问过的相邻节点判断,就会寻找下个非访问过的节点了。
代码实现
// graph.js
const graph = {
0:[1,2],
1:[2],
2:[0,3],
3:[3]
}
module.exports = graph;
// dfs.js
const graph = require('./graph');
// 声明一个集合,记录已遍历过的节点
const isVistive = new Set();
const dfs =(n) => {
console.log(n); // 2,0,1,3
isVistive.add(n); // 记录已遍历过的节点
graph[n].forEach(item => {
if(!isVistive.has(item)) {
dfs(item)
}
})
}
dfs(2);
复制代码
11-3图的广度优先遍历算法口诀
- 新建一个队列,把根节点入队。
- 把队头出队并访问。
- 把队头的没访问过的相邻节点入队。
- 重复第二、三步,直到队列为空。
代码实现
const graph = require('./graph');
// 声明一个集合,记录已遍历过的节点
const isVistive = new Set();
isVistive.add(2) // 先把初始节点添加到集合
const bfs = () => {
const q = [2];
while (q.length) {
const n = q.shift();
console.log(n);// 2,0,3,1
graph[n].forEach(item => {
if (!isVistive.has(item)) {
q.push(item)
isVistive.add(item);
}
})
}
}
bfs();
复制代码
11-4 算法题
65. 有效数字
图片描述: 编号1,开始走节点6的位置,最终停留在节点6,所以0是有效数字。编号3,a开头无路可走,所以编号3是无效数字。只有遍历到节点3、5、6的时候,数字才是有效数字。
解题步骤
- 构建一个表示状态的图。
- 遍历字符串,并沿着图走,如果到了某个节点无路可走就返false
- 遍历结束,如走到3/5/6,就返回true,否则返回false。
/**
* @param {string} s
* @return {boolean}
*/
var isNumber = function(s) {
const graph = {
0:{'blank':0,'digit':6,'sign':1,'.':2},
1:{'digit':6, '.':2},
2:{'digit':3},
3:{'digit':3, 'e':4},
4:{'digit':5,'sign':7},
5:{'digit':5},
6:{'digit':6, '.':3, 'e':4},
7:{'digit':5}
}
let state = 0; // 初始状态值为0;
for(item of s.trim()) {
if(item >= '0' && item <= '9') {
item = 'digit'
}else if(item === '') {
item = 'blank'
}else if(item === '+' || item === '-') {
item = 'sign'
}else if(item === 'e' || item === 'E') {
item = 'e'
}
state = graph[state][item]
if(state == undefined) {
return false;
}
}
if(state == 3 || state == 6 || state == 5) {
return true;
}
return false;
};
复制代码
417. 太平洋大西洋水流问题
给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
复制代码
解题步骤
- 新建两个矩阵,分别记录能流到两个大洋的坐标。
- 从海岸线,多管齐下,同时深度优先遍历图,过程中填充上述矩阵。
- 遍历两个矩阵,找出能流到两个大洋的坐标。
/**
* @param {number[][]} heights
* @return {number[][]}
*/
var pacificAtlantic = function (heights) {
if (!heights || !heights[0] || !heights[0].length) return []
const m = heights.length
const n = heights[0].length
// 逆流而上,走出一条通道
// 存放太平洋->大西洋的路径
const flow1 = Array.from({ length: m }, () => {
return Array.from({ length: n }, () => false)
})
// 存放大西洋->太平洋的路径
const flow2 = Array.from({ length: m }, () => {
return Array.from({ length: n }, () => false)
})
const dfs = (r, c, flow) => {
flow[r][c] = true;
[[r - 1, c], [r, c + 1], [r + 1, c], [r, c - 1]].forEach(([nr, nc]) => {
if (nr >= 0 && nr < m &&
nc >= 0 && nc < n &&
!flow[nr][nc] &&
heights[nr][nc] >= heights[r][c]
) {
dfs(nr, nc, flow)
}
})
}
//多管齐下, 第一行遍历到最后行,第一列遍历到最后列
for (let i = 0; i < m; i++) {
dfs(i, 0, flow1)
dfs(i, n - 1, flow2)
}
for (let i = 0; i < n; i++) {
dfs(0, i, flow1)
dfs(m - 1, i, flow2)
}
// 找出两条路都能走通的节点
const res = []
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (flow1[i][j] && flow2[i][j]) {
res.push([i, j])
}
}
}
return res
};
复制代码
133. 克隆图
12、堆
12-1堆是什么?
上图解释:index指的是数组的下标索引。
12-2堆的应用
- 堆能高效、快速地找出最大值和最小值,时间复杂度: 0(1)。
- 找出第K个最大(小)元素。
找出第K个最大元素
- 构建一个最小堆,并将元素依次插入堆中。
- 当堆的容量超过K,就删除堆顶。
- 插入结束后,堆顶就是第K个最大元素。
实现最小堆类
实现步骤:
- 在类里,声明-一个数组,用来装元素。
- 主要方法:插入、删除堆顶、获取堆顶、获取堆大小。
插入方法
- 将值插入堆的底部,即数组的尾部。
- 然后上移:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
- 大小为k的堆中插入元素的时间复杂度为O(logk)。
代码实现
// 插入方法,获取第K个最小元素
class MinHeap {
constructor() {
this.heap = [];
}
// 交换函数
swap(i1,i2){
let temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp;
}
// 获取父节点的位置 (index -1 ) / 2 的余数
getParentIndex(i) {
return (i - 1) >> 1
}
// 上移操作:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
shiftUp(index){
// index == 0 到栈顶了, 就返回
if(index == 0) {return;}
const parentIndex = this.getParentIndex(index);
// 和父节点交换
if(this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex,index)
this.shiftUp(parentIndex)
}
}
// 将值插入堆的底部
insert(value) {
this.heap.push(value)
this.shiftUp(this.heap.length - 1)
}
}
const h = new MinHeap();
h.insert(3)
h.insert(2)
h.insert(1)
复制代码
删除堆顶
- 用数组尾部元素替换堆顶(直接删除堆顶会破坏堆结构)。
- 然后下移:将新堆顶和它的子节点进行交换,直到子节点大于等于这个新堆顶。
- 大小为k的堆中删除堆顶的时间复杂度为O(logk)。
代码实现
// 插入方法,获取第K个最小元素
class MinHeap {
constructor() {
this.heap = [];
}
// 交换函数
swap(i1,i2){
let temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp;
}
// 获取父节点的位置 (index -1 ) / 2 的余数
getParentIndex(i) {
return (i - 1) >> 1
}
// 获取左节点的位置 index * 2 + 1
getLeftIndex(i) {
return i * 2 + 1;
}
// 获取右节点的位置 index * 2 + 2
getRightIndex(i) {
return i * 2 + 2;
}
// 上移操作:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
shiftUp(index){
// index == 0 到栈顶了, 就返回
if(index == 0) {return;}
const parentIndex = this.getParentIndex(index);
// 和父节点交换
if(this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex,index)
this.shiftUp(parentIndex)
}
}
// 下移,将新堆顶和它的子节点进行交换,直到子节点大于等于这个新堆顶。
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if(this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex,index)
this.shiftDown(leftIndex);
}
if(this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex,index)
this.shiftDown(rightIndex);
}
}
// 将值插入堆的底部
insert(value) {
this.heap.push(value)
this.shiftUp(this.heap.length - 1)
}
pop() {
this.heap[0] = this.heap.pop(); // 用数组尾部元素替换堆顶
this.shiftDown(0)
}
}
const h = new MinHeap();
h.insert(3)
h.insert(2)
h.insert(1)
h.pop();
复制代码
获取堆顶和堆的大小
- 获取堆顶,返回数组的头部
- 获取堆得大小:返回数组的长度
// 获取堆顶,返回数组的头部
peek() {
return this.heap[0]
}
// 获取堆得大小:返回数组的长度
size() {
return this.heap.length
}
复制代码
12-3算法题解
215. 数组中的第K个最大元素
解题思路
- 构建一个最小堆,一次把元素插入堆中
- 如果堆得大小超过 k ,就删除堆顶
- 元素插入结束后,返回堆顶,即最大的第k个元素
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// 获取最小堆类,前面已经写过了,直接拿来用即可
var findKthLargest = function(nums, k) {
const h = new MinHeap();
nums.forEach(item => {
h.insert(item);
if(h.size() > k) {
h.pop();
}
})
return h.peek();
};
复制代码
347. 前 K 个高频元素
// 插入方法,获取第K个最小元素
class MinHeap {
constructor() {
this.heap = [];
}
// 交换函数
swap(i1, i2) {
let temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp;
}
// 获取父节点的位置 (index -1 ) / 2 的余数
getParentIndex(i) {
return (i - 1) >> 1
}
// 获取左节点的位置 index * 2 + 1
getLeftIndex(i) {
return i * 2 + 1;
}
// 获取右节点的位置 index * 2 + 2
getRightIndex(i) {
return i * 2 + 2;
}
// 上移操作:将这个值和它的父节点进行交换,直到父节点小于等于这个插入的值。
shiftUp(index) {
// index == 0 到栈顶了, 就返回
if (index == 0) {
return;
}
const parentIndex = this.getParentIndex(index);
// 和父节点交换
if (this.heap[parentIndex]&&this.heap[parentIndex].value > this.heap[index].value) {
this.swap(parentIndex, index)
this.shiftUp(parentIndex)
}
}
// 下移,将新堆顶和它的子节点进行交换,直到子节点大于等于这个新堆顶。
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex]&&this.heap[leftIndex].value < this.heap[index].value) {
this.swap(leftIndex, index)
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex]&&this.heap[rightIndex].value < this.heap[index].value) {
this.swap(rightIndex, index)
this.shiftDown(rightIndex);
}
}
// 将值插入堆的底部
insert(value) {
this.heap.push(value)
this.shiftUp(this.heap.length - 1)
}
pop() {
this.heap[0] = this.heap.pop(); // 用数组尾部元素替换堆顶
this.shiftDown(0)
}
// 获取堆顶,返回数组的头部
peek() {
return this.heap[0]
}
// 获取堆得大小:返回数组的长度
size() {
return this.heap.length
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const map = new Map();
nums.forEach(n => {
map.set(n, map.has(n) ? map.get(n) + 1: 1)
})
const h = new MinHeap();
map.forEach((value,key) => {
h.insert({value, key})
if(h.size() > k) {
h.pop();
}
})
return h.heap.map( n => n.key)
};
复制代码
13、进阶算法-搜索排序
JS
中的排序:数组的sort
方法。
JS
中的搜索:数组的indexOf
方法。
-
十大经典算法排序总结对比
名词解释:
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存
稳定性:排序后2个相等键值的顺序和排序之前它们的顺序相同
13-1 排序算法常见类型
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序 等等
13-2搜索算法常见类型
- 顺序搜索
- 二分搜索
13-3冒泡排序
冒泡排序的思路
- 比较所有相邻元素,如果第一个比第二个大,则交换它们。
- 一轮下来,可以保证最后一个数是最大的。
- 执行n-1轮,就可以完成排序。
- 冒泡排序动图演示
代码实现
Array.prototype.bubbleSort = function () {
for (let i = 0; i < this.length - 1; i++) {
for (let j = 0; j < this.length - 1 - i; j++) {
if (this[j] > this[j + 1]) {
const temp = this[j]
this[j] = this[j + 1];
this[j + 1] = temp;
}
}
}
}
const arr = [5, 4, 3, 2, 1]
arr.bubbleSort();
复制代码
13-4选择排序
选择排序思路
- 找到数组中的最小值,选中它并将其放置在第一位。
- 接着找到第二小的值,选中它并将其放置在第二位。
- 以此类推,执行n- 1轮。
选择排序须知:
在时间复杂度上表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
选择排序动图演示:
代码实现
Array.prototype.selectionSort = function () {
for (let i = 0; i < this.length - 1; i++) {
let indexMin = i;
for (let j = i; j < this.length; j++) {
if (this[j] < this[indexMin]) {
indexMin = j;
}
}
if (indexMin !== i) { // 当前索引的值不需要和自己比
const temp = this[i];
this[i] = this[indexMin]
this[indexMin] = temp;
}
}
}
const arr = [5, 4, 3, 2, 1]
arr.selectionSort();
复制代码
13-5插入排序
插入排序思路
- 从第二个数开始往前比。
- 比它大就往后排。
- 以此类推进行到最后一个数。
插入排序动图演示:
代码实现
Array.prototype.insertionSort = function () {
for (let i = 1; i < this.length; i++) {
const temp = this[i];
let j = i;
while (j > 0) {
if (this[j - i] > temp) {
this[j] = this[j - i];
} else {
break;
}
j--;
}
this[j] = temp;
}
}
const arr = [5, 4, 3, 2, 1]
arr.insertionSort();
复制代码
13-6归并排序
- 分:把数组劈成两半,再递归地对子数组进行,“分”操作,直到分成一个个单独的数。
- 合:把两个数合并为有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组。
合并两个有序数组
- 新建一个空数组res,用于存放最终排序后的数组。
- 比较两个有序数组的头部,较小者出队并推入res中。
- 如果两个数组还有值,就重复第二步。
归并排序动画:
代码实现
Array.prototype.mergeSort = function () {
// 把数组劈成两半,再递归地对子数组进行分,直到把数组分成一个个元素
const rec = (arr) => {
if (arr.length == 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid)
let right = arr.slice(mid, arr.length)
const orderLeft = rec(left) // 有序左数组
const orderRight = rec(right) // 有序右数组
const res = []; // 新建一个空数组res,用于存放最终排序后的数组。
while (orderLeft.length || orderRight.length) {
if (orderLeft.length && orderRight.length) {
// 比较两个有序数组的头部,较小者出队并推入res中。
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
} else if (orderLeft.length) { // 如果两个数组还有值,就重复第二步。
res.push(orderLeft.shift())
} else if (orderRight.length) { // 如果两个数组还有值,就重复第二步。
res.push(orderRight.shift())
}
}
return res;
}
// 挂到原始数组里去
const res = rec(this)
res.forEach((n, i) => {
this[i] = n;
})
}
const arr = [5, 4, 3, 2, 1]
arr.mergeSort();
复制代码
13-7快速排序
快速排序思路
- 分区:从数组中任意选择一个“基准”,所有比基准小的元素放在基准前面,比基准大的元素放在基准的后面。
- 递归:递归地对基准前后的子数组进行分区。
快速排序动画:
代码实现
Array.prototype.quickSort = function () {
const rec = (arr) => {
if (arr.length === 1) {
return arr;
}
const left = []; // 存放基准前面的元素
const right = []; // 存放基准前面的元素
const base = arr[0]; // 基准,这里选择第一个元素
for (let i = 1; i < arr.length; i++) {
if (arr[i] < base) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...rec(left), base, ...rec(right)]
}
// 挂到原始数组里去
const res = rec(this)
res.forEach((n, i) => {
this[i] = n;
})
}
const arr = [2, 4, 5, 3, 1]
arr.quickSort();
复制代码
13-8顺序搜索
顺序搜索思路
- 遍历数组
- 找到跟目标值相等的元素,就返回它的下标。
- 遍历结束后,如果没有搜索到目标值,就返回-1
代码实现
Array.prototype.sequenceSeach = function (target) {
for (let i = 0; i < this.length; i++) {
if (this[i] == target) {
return i
}
}
return -1;
}
const res = [1, 2, 3, 4, 5].sequenceSeach(3)
复制代码
13-9二分搜索
二分搜索思路
- 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束。
- 如果目标值大于或者小于中间元素,则在大于或小于中间元素的那一半数组中搜索。
代码实现
Array.prototype.binarySearch = function (target) {
let low = 0; // 最小索引
let heigh = this.length - 1; // 最大索引
while (low <= heigh) {
const mid = Math.floor((low + heigh) / 2) // 获取中间元素下标
const ele = this[mid] // 获取中间元素的值
if (ele < target) {
low = mid + 1;
} else if (ele > target) {
heigh = mid - 1
} else {
return mid; // 如果中间元素正好是目标值,则搜索结束。
}
}
return -1;
}
const res = [1, 2, 3, 4, 5].binarySearch(4)
复制代码
13-10算法题
21. 合并两个有序链表
解题步骤
- 新建一个新链表,作为返回结果。
- 用指针遍历两个有序链表,并比较两个链表的当前节点较小者先接入新链表,并将指针后移一步。
- 链表遍历结束,返回新链表。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
const res = new ListNode(0);
let p = res;
let p1 = l1;
let p2 = l2;
while(p1 && p2) {
if(p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
}else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if(p1) {
p.next = p1;
}
if(p2) {
p.next = p2;
}
return res.next;
};
复制代码
374. 猜数字大小
解题步骤
二分搜索思路
- 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束。
- 如果目标值大于或者小于中间元素,则在大于或小于中间元素的那一半数组中搜索。
/**
* Forward declaration of guess API.
* @param {number} num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* var guess = function(num) {}
*/
/**
* @param {number} n
* @return {number}
*/
var guessNumber = function(n) {
let low = 1;
let heigh = n;
while(low <= heigh) {
// 获取中间元素的值
const mid = Math.floor((low + heigh) / 2);
const res = guess(mid) // 来获取猜测结果,也就是中间元素
if(res === 0) {
return mid
}else if(res === 1) {
low = mid + 1;
}else {
heigh = mid - 1;
}
}
};
复制代码