Yinode Blog

基础

递归

const recursion = (level,param1,param2)=>{
  // 终止条件
  if(level > xx) {
    return xx
  }

  // 处理当前层的数据
  processData()

  // 继续向下递归
  recursion(level+1,param1,param2)

  // 进行状态后处理 组装
  moreProcess()
}

DFS

let visited = new Set()

const dfs = (node,visited)=>{
  visited.add(node)
  
  for(let childNode of node.children){
    if(!visited.has(childNode)){
      dfs(childNode,visited)
    }
  }
}

BFS

const bfs = (G,start)=>{
  let q = [start]
  let visited = new Set()

  while(q.length > 0){
    node = q.shift()
    visited.add(node)

    // 如果需要按层级递进 那么这里需要创建一个 for 循环

    process(node)
    for(let childNode of node.children){
    if(!visited.has(childNode)){
      q.add(node)
    }
  }
  }
}

排列组合类

排列

var permute = function(nums) {
  let res = []
  // 如果有重复的数量那么事先进行排序
  helper([], nums, res, nums.length, new Array(nums.length).fill(false))
  return res
}

const helper = (chooses, options, res, r, used) => {
  // 终止条件 看 R 到位了没有

  for (let i = 0, len = options.length; i < len; i++) {
    if (used[i]) continue
    // 如果有重复 必须做重复判断
    // if ((i > 0 && options[i] === options[i - 1] && !used[i - 1]) || used[i])
    used[i] = true
    chooses.push(options[i])
    helper(chooses, options, res, r - 1, used)
    used[i] = false
    chooses.pop()
  }
}

组合

var combinationSum = function(candidates, target) {
  let res = []
  helper([], candidates, target, res, 0)
  return res
}

const helper = (choose, options, res, start) => {
  // 结束判断 比如达到规定的 R 或者完成某个限制条件
  // 一般组合都能利用一些手段进行剪枝 要注意
  // 如果是求全组合 那么 直接 push 即可

  for (let i = start, len = options.length; i < len; i++) {
    // 重复判断取决于是否有重复数据
    //  if (i > start && options[i] === options[i - 1]) continue
    choose.push(options[i])
    // 最后的区间限制要看情况 是允许多次使用某个数还是不允许
    // 不允许就 i+1 否则 i
    helper(choose, options, res, i)
    choose.pop()
  }
}

let s =

x1y1 x2y1 x3y1 x2y1 x2y2 x2y3

x1y1 x1y2 x1y3

TOC

基础

递归

DFS

BFS

排列组合类

排列

组合

FEATURED TAGS