广度优先搜索:求解《429. N 叉树的层序遍历》和 《675. 为高尔夫比赛砍树》

2022-04-08 05:10:03
广度优先搜索,求解《429. N 叉树的层序遍历》和 《675. 为高尔夫比赛砍树》

思路

广度优先搜索,使用队列,先进先出

代码

广度优先搜索 · 层序遍历 · 出队

const dfs = root => {
  if (root === null) return []
  const queue = [root], r = []
  while (queue.length) {
    const n = queue.shift()
    r.push(n.val)
    if (n.left) queue.push(n.left)
    if (n.right) queue.push(n.right)
  }
  return r
}

广度优先搜索 · 移动指针 · 不出队

数据较多时,可以提高性能

const dfs = root => {
  if (root === null) return []
  const queue = [root], r = []
  let index = 0
  while (index < queue.length) {
    const n = queue[index++]
    r.push(n.val)
    if (n.left) queue.push(n.left)
    if (n.right) queue.push(n.right)
  }
  return r
}

广度优先搜索 · 深度 / 层次 / 距离

适用于利用广度优先搜索,求深度 / 层次 / 距离的问题

const dfs = root => {
  if (root === null) return 0
  const queue = [root]
  let deepth = -1
  while (queue.length) {
    let l = queue.length
    deepth++
    while (l--) {
      const n = queue.shift()
      if (n.left) queue.push(n.left)
      if (n.right) queue.push(n.right)
    }
  }
  return deepth
}

以上三种代码可作为模板,可以组合使用

例题

429. N 叉树的层序遍历

给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。 树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。

答案

var levelOrder = function(root) {
  if (root === null) return []
  const queue = [root], r = []
  while (queue.length) {
    let l = queue.length
    r.push([])
    while (l--) {
      const n = queue.shift()
      r[r.length - 1].push(n.val)
      for (let i = 0; i < n.children.length; i++) {
        queue.push(n.children[i])
      }
    }
  }
  return r
};

675. 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示, 在这个矩阵中: 0 表示障碍,无法触碰 1 表示地面,可以行走 比 1 大的数 表示有树的单元格,可以行走,数值表示树的高度 每一步,你都可以向上、下、左、右四个方向之一移动一个单位,如果你站的地方有一棵树,那么你可以决定是否要砍倒它。 你需要按照树的高度从低向高砍掉所有的树,每砍过一颗树,该单元格的值变为 1(即变为地面)。 你将从 (0, 0) 点开始工作,返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树,返回 -1 。 可以保证的是,没有两棵树的高度是相同的,并且你至少需要砍倒一棵树。

答案

  1. 有树的点放入新数组,按树的高度升序排列
  2. (0,0)及有序数组中,两两距离累加,广度优先搜索求距离
var cutOffTree = function (forest) {
  const m = forest.length, n = forest[0].length
  const forests = []
  for (let i = 0; i < m; i++) 
    for (let j = 0; j < n; j++) 
      if (forest[i][j] > 1) forests.push([i, j, forest[i][j]])
  forests.sort((a, b) => a[2] - b[2])
  let minStep = 0
  for (let i = 0; i < forests.length; i++) {
    const step = getStep(forests[i - 1] || [0, 0], forests[i], m, n, forest)
    if (step === -1) return -1
    minStep += step
  }
  return minStep
};
const getStep = ([x1, y1], [x2, y2], m, n, forest) => {
  const dr = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  const queue = [[x1, y1]], visited = Array.from({length: m}, _ => new Uint8Array(n))
  let deepth = -1, index = 0
  while (index < queue.length) {
    let l = queue.length
    deepth++
    while (index < l) {
      const [x, y] = queue[index++]
      if (x === x2 && y === y2) return deepth
      for (let i = 0; i < 4; i++) {
        const [dx, dy] = dr[i]
        const xNew = x + dx, yNew = y + dy
        if (xNew < 0 || xNew >= m || yNew < 0 || yNew >= n) continue
        if (forest[xNew][yNew] === 0) continue
        if (visited[xNew][yNew]) continue
        visited[xNew][yNew] = 1
        queue.push([xNew, yNew])
      }
    }
  }
  return -1
}
代码
动态规划,中心扩散:求解《647. 回文子串》和《5. 最长回文子串》
动态规划,递归和迭代两种方式中心扩散,求解《647. 回文子串》和《5. 最长回文子串》
代码
正则零宽断言和负向零宽断言:正则、栈和递归求解《1556.千位分隔符》
什么是正则的捕获型分组和非捕获型分组,什么是引用和反向应用,什么是零宽断言和负向零宽断言,用正则、迭代(栈)和递归 3 种算法求解《1556. 千位分隔数》
代码
双指针判断回文字符串:求解《125. 验证回文串》《018. 有效的回文》《680. 验证回文字符串 Ⅱ》和《019. 最多删除一个字符得到回文》
使用双指针判断回文字符串,求解《125. 验证回文串》《剑指 Offer II 018. 有效的回文》《680. 验证回文字符串 Ⅱ》和《剑指 Offer II 019. 最多删除一个字符得到回文》