📚 递归

思维要点：

  1. 不要人肉进行递归（最大误区）
  2. 找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）
  3. 数学归纳法思维

递归代码模板：（验证方法）

  1. 保证 n = 1, n =2 时，结果正确
  2. 可以证明当 n 成立时，推导出来的 n + 1 也成立
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const recursion = (level, params) {
  // recursion terminator 递归终结条件
  if (level > MAX_LEVEL) {
    process_result
    return
  }

  // process current level 处理当前层逻辑
  process(level, params)

  // drill down 下探到下一层
  recursion(level + 1, parms)

  // clean current level status if need 清理当前层
}


🤔 DFS 深度优先搜索

搜索顺序：以树为例，从根节点开始，先搜索左子树，一直走左子树走到底，再搜索右子树。

  • 推荐的递归写法
1
2
3
4
5
6
7
8
// 递归写法
const visited = new Set();
const dfs = (node) => {
  if (visited.has(node)) return;
  visited.add(node);
  dfs(node.left);
  dfs(node.right);
};
  • 非递归写法
1
2
3
4
5
6
7
8
9
10
11
12
13
const dfs = (node) => {
  if (!node) return;
  const visited = [];
  const stack = node;
  while (stack.length > 0) {
    const node = stack.pop();
    visited.push(node);
    process(node);

    const nodes = generate_related_nodes(node);
    stack.push(nodes);
  }
};


🏫 经典题目

22.括号生成

给定 n 对括号，请编写一个函数，用于生成所有可能的并且有效的括号组合）如((()))、()()()、(())()。每个格子都可以放左括号或者右括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const generateParenthesis = (n) => {
  const res = [];
  const walk = (l, r, str) => {
    if (str.length === 2 * n) {
      return res.push(str);
    }

    if (l < n) {
      walk(l + 1, r, str + "(");
    }
    if (r < l) {
      walk(l, r + 1, str + ")");
    }
  };
  walk(0, 0, "");
  return res;
};


50. pow(x,n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
题解：直接 for 循环 x*x*x... x 时间复杂度是 n。但是如果我们分解成 (x^n-1) x (x^n-1)，每次往下分解，时间复杂度就是 logn。

1
2
3
4
5
6
7
8
9
10
11
12
const myPow = (x, n) => {
  if (n === 0) return 1;
  if (n < 0) {
    return 1 / myPow(x, -n);
  }
  const half = myPow(x, Math.floor(n / 2));
  if (n % 2 === 0) {
    return half * half;
  } else {
    return half * half * x;
  }
};

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
题解：每个格子里可以选和不选，形成递归的形式，最后把结果输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const subsets = (nums) => {
  const result = [];
  const dfs = (list, index) => {
    // list当前结果
    // index走到第几个元素
    if (index === nums.length) {
      result.push(list);
      return;
    }

    dfs(list.slice(), index + 1);
    list.push(nums[index]);
    dfs(list.slice(), index + 1);
  };
  dfs([], 0);
  return result;
};

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var letterCombinations = function (digits) {
  const obj = {
    2: ["a", "b", "c"],
    3: ["d", "e", "f"],
    4: ["g", "h", "i"],
    5: ["j", "k", "l"],
    6: ["m", "n", "o"],
    7: ["p", "q", "r", "s"],
    8: ["t", "u", "v"],
    9: ["w", "x", "y", "z"],
  };

  let arr = obj[digits[0]] || []; // ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

  for (let i = 1; i < digits.length; i++) {
    const newArr = obj[digits[i]]; // ['a', 'b', 'c']
    const curArr = [];
    for (let j = 0; j < arr.length; j++) {
      for (let k = 0; k < newArr.length; k++) {
        curArr.push((arr[j] || "") + newArr[k]);
      }
    }
    arr = curArr;
  }
  return arr;
};

N 皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let totalResult = [];
  let result = []; // 下标表示行，值表示列 [1,2,undefined, ...]

  function cal8queens(row) {
    // n个棋子都放置好了，打印结果
    if (row === n) {
      printQueens(result);
      return false;
    }

    for (let column = 0; column < n; column++) {
      if (isOk(row, column)) {
        // 如果满足要求
        result[row] = column; // 第row行的棋子放到colum列
        cal8queens(row + 1); // 考察下一行
      }
    }
  }

  function isOk(row, column) {
    let leftup = column - 1;
    let rightup = column + 1;

    for (let i = row - 1; i >= 0; i--) {
      // 逐行往上考察
      // 正上方，左上对角线，右上对角线
      if (result[i] === column) return false;
      if (leftup >= 0 && result[i] === leftup) return false;
      if (rightup < n && result[i] === rightup) return false;
      leftup--;
      rightup++;
    }
    return true;
  }

  function printQueens(result) {
    let arr = [];
    for (let i = 0; i < n; i++) {
      let str = "";
      for (let j = 0; j < n; j++) {
        str += result[i] === j ? "Q" : ".";
      }
      arr.push(str);
    }
    totalResult.push(arr);
  }

  cal8queens(0);
  return totalResult;
};

🤔 什么时候适合用 DFS，什么时候适合用 BFS？

  • 适合用 DFS 的场景：
    • 路径探索：DFS 会沿着一条路径尽可能深地探索，当遇到死路时回溯到上一个节点继续探索。
    • 岛屿数量、省份数量
    • 求全排列、全组合
  • 适合用 BFS 的场景：
    • 寻找最短路径：BFS 按照层次遍历节点，能保证找到的路径是最短的
    • 层级相关问题


📚 BFS 广度优先搜索 - 代码模板

搜索顺序：不用递归，而是用队列，一层一层向下扩展, 像水纹一样。常用在求最短路径的问题上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const bfs = (root) => {
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const level = [];
    const n = queue.length;
    for (let i = 0; i < n; i++) {
      const node = queue.pop();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
};


分治

1
2
3
4
5
6
7
8
9
10
const divide_conquer = (problem, params) => {
  if (problem == null) {
    process_result;
    return;
  }

  // process current problem
  subproblem = split_problem(problem, data);
  sub_result1 = divide_conquer(subproblem[0], p1);
};

启发式搜索 A* search

启发式函数：h(n), 用来评价哪些节点最有希望会是我们要找的节点。常用于推荐算法，搜索顺序不是广度优先，也不是深度优先，而是优先级优先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function AstartSearch (graph, start, end) {
  const pq = collection.priority_queue() // 按优先级排序 -> 估价函数
  pq.append([start])
  visited.add(start)

  while (pq.length > 0) {
    node = pq.pop() // can we add more intelligence here?
    visited.add(node)

    process(node)
    unvisited = [node in nodes if node not in visited]
    pq.push(unvisited)
  }
}