圖
- 圖是網(wǎng)絡(luò)結(jié)構(gòu)的抽象模型馅扣，是一組由邊連接的節(jié)點
- 圖可以表示任何二元關(guān)系斟赚，比如道路、航班
- JS中沒有圖差油，但是可以用Object和Array構(gòu)建圖
- 圖的表示法：鄰接矩陣拗军、鄰接表、關(guān)聯(lián)矩陣…
鄰接矩陣
鄰接表
圖的深度/廣度優(yōu)先遍歷
- 深度優(yōu)先遍歷：盡可能深的搜索圖的分支
- 廣度優(yōu)先遍歷：先訪問離根節(jié)點最近的節(jié)點
深度優(yōu)先遍歷算法口訣
- 訪問根節(jié)點
- 對根節(jié)點的沒訪問過的相鄰節(jié)點挨個進行深度優(yōu)先遍歷
深度優(yōu)先遍歷
// 圖蓄喇，后面不會重復寫
const graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
}
const visited = new Set()
const dfs = n => {
console.log(n)
visited.add(n)
graph[n].forEach(c => {
if (!visited.has(c)) {
dfs(c)
}
})
}
dfs(2) // 2 0 1 3
廣度優(yōu)先遍歷算法口訣
- 新建一個隊列发侵，把根節(jié)點入隊
- 把隊頭出隊并訪問
- 把隊頭的沒訪問過的相鄰節(jié)點入隊
- 重復第二、三步妆偏，直到隊列為空
廣度優(yōu)先遍歷
const visited = new Set()
visited.add(2)
const q = [2]
while (q.length) {
const n = q.shift()
console.log(n) // 2 0 3 1
graph[n].forEach(c => {
if (!visited.has(c)) {
q.push(c)
visited.add(c)
}
})
}
有效數(shù)字
- 構(gòu)建一個表示狀態(tài)的圖
- 遍歷字符串刃鳄，并沿著圖走，如果到了某個節(jié)點無路可走就返回false
- 遍歷結(jié)束钱骂，如走到3/5/6叔锐，就返回true挪鹏，否則返回false
有效數(shù)字鄰接表圖
/**
* @param {string} s
* @return {boolean}
* @description 難點在于畫出鄰接表圖，循環(huán)遍歷輸入愉烙，將每一個字符轉(zhuǎn)化為對應(yīng)屬性讨盒，用于獲取當前狀態(tài)
*/
const isNumber = function(s) {
const graph = {
0: { blank: 0, sign: 1, dot: 2, digit: 6 },
1: { digit: 6, dot: 2 },
2: { digit: 3 },
3: { digit: 3, e: 4 },
4: { digit: 5, sign: 7 },
5: { digit: 5 },
6: { digit: 6, dot: 3, e: 4 },
7: { digit: 5 },
}
let state = 0 // 初始狀態(tài)都是0
for (c of s.trim()) { // 題目中前后括號不影響判斷，所以先去除前后空格
if (c === ' ') {
c = 'blank'
} else if (c === '+' || c === '-') {
c = 'sign'
} else if (c === '.') {
c = 'dot'
} else if (c.toLowerCase() === 'e') {
c = 'e'
} else if (!isNaN(c)) {
c = 'digit'
}
state = graph[state][c]
if (state === undefined) return false
}
// 合法的三個狀態(tài)
const validState = [3, 5, 6]
return validState.includes(state)
}
// "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"
const testArr = ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
testArr.forEach(item => {
console.log(isNumber(item))
})
太平洋大西洋水流問題
- 把矩陣想象成圖
- 從海岸線逆流而上遍歷圖步责，所到之處就是可以流到某個大洋的坐標
- 新建兩個矩陣返顺，分別記錄能流到兩個大洋的坐標
- 從海岸線，多管齊下蔓肯，同事深度優(yōu)先遍歷圖遂鹊，過程中填充上述矩陣
- 遍歷兩個矩陣，找出能流到兩個大洋的坐標
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
const pacificAtlantic = function(matrix) {
if (!matrix || !matrix[0]) return []
// 生成兩個空白矩陣
const m = matrix.length
const n = matrix[0].length
const flow1 = Array.from({length: m}, () => new Array(n).fill(false))
const flow2 = Array.from({length: m}, () => new Array(n).fill(false))
const dfs = (r, c, flow) => {
flow[r][c] = true
const location = [[r - 1, c], [r + 1, c], [r, c -1], [r, c + 1]]
location.forEach(([nr, nc]) => {
if (
// 保證在矩陣中
nr >= 0 && nr < m &&
nc >= 0 && nc < n &&
// 防止死循環(huán)
!flow[nr][nc] &&
//保證逆流而上
matrix[nr][nc] >= matrix[r][c]
) {
dfs(nr, nc, flow)
}
})
}
// 沿著海岸線逆流而上
for (let r = 0; r < m; r++) {
dfs(r, 0, flow1)
dfs(r, n - 1, flow2)
}
for (let c = 0; c < n; c++) {
dfs(0, c, flow1)
dfs(m - 1, c, flow2)
}
// 收集能流到兩個大洋里的坐標
let res = []
for (let r = 0; r < m; r += 1) {
for (let c = 0; c < n; c += 1) {
if (flow1[r][c] && flow2[r][c]) {
res.push([r, c])
}
}
}
return res
}
const matrix = [
[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]
]
console.log(pacificAtlantic(matrix))
克隆圖
- 拷貝所有節(jié)點
- 拷貝所有的邊
- 將拷貝的節(jié)點蔗包，按照原圖的連接方法進行連接
這道題沒法模擬秉扑，dfs中會丟失原索引值，導致填充都為0气忠，但如果將索引一起放進去leeCode又跑不過，只能去leeCode上測試
深度優(yōu)先解法：
const cloneGraph = function(node) {
if (!node) return
const visited = new Map()
const dfs = n => {
const nCopy = new Node(n.val)
visited.set(n, nCopy)
const neighbors = n.neighbors || []
neighbors.forEach(ne => {
if (!visited.has(ne)) { // 已被記錄的鄰接邊不再記錄
dfs(ne)
}
nCopy.neighbors.push(visited.get(ne))
})
}
dfs(node)
return visited.get(node)
}
廣度優(yōu)先解法：
const cloneGraph = function(node) {
if (!node) return
const visited = new Map()
visited.set(node, new Node(node.val))
const q = [node]
while (q.length) {
const n = q.shift()
const neighbors = n.neighbors || []
neighbors.forEach(ne => {
if (!visited.has(ne)) {
q.push(ne)
visited.set(ne, new Node(ne.val))
}
visited.get(n).neighbors.push(visited.get(ne))
})
}
return visited.get(node)
}
