练习

LeetCode:65.有效的数字

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function (s) {
    const graph = {
        0: {
            "blank": 0,
            "sign": 1,
            ".": 2,
            "digit": 6
        },
        1: {
            ".": 2,
            "digit": 6
        },
        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;
    for (c of s.trim()) {
        if (c >= '0' && c <= "9") {
            c = "digit";
        } else if (c === ' ') {
            c = "blank"
        } else if (c === "+" || c === "-") {
            c = "sign"
        } else if (c === "e") {
            c = "E"
        }
        state = graph[state][c];
        if (state === undefined) {
            return false
        }
    }
    if (state === 3 || state === 5 || state === 6) {
        return true
    }
    return false
};

LeetCode:417.太平洋大西洋水流问题

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function (matrix) {
    if (!matrix || !matrix[0]) {
        return []
    }
    let m = matrix.length;
    let n = matrix[0].length;
    let flow1 = Array.from({ length: m }, () => new Array(n).fill(false));//太平洋
    let flow2 = Array.from({ length: m }, () => new Array(n).fill(false));//大西洋

    const dfs = function (r, c, flow) {
        flow[r][c] = true;
        //上下左右
        [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]].forEach(([nr, nc]) => {
            if (
                nr >= 0 && nr < m &&
                nc >= 0 && nc < 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++) {
        for (let c = 0; c < n; c++) {
            if (flow1[r][c] && flow2[r][c]) {
                res.push([r, c])
            }
        }
    }

    return res

};

LeetCode:133.克隆图

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {
    if (!node) {
        return
    }
    let visited = new Map();
    let dfs = (n) => {
        if (!n) return
        const nCopy = new Node(n.val)
        visited.set(n, nCopy);
        n.neighbors && n.neighbors.forEach((ne) => {
            if (!visited.has(ne)) {
                dfs(ne)
            }
            nCopy.neighbors.push(visited.get(ne))
        })
    }
    dfs(node)
    return visited.get(node)
};