初级搜索

优化方式：不重复（fibonacci）、剪枝（生成括号问题）

搜索方向：

  • DFS：深度优先搜索
  • BFS：广度优先搜索

双向搜索、启发式搜索（优先级搜索）

剪枝

状态树进行搜索的时候，如果发现这个分支已经处理过，我们可以把它暂存在缓存里面，整个分支就可以剪掉，不需要手动进行计算。

有些时候分支不够好，是比较差的分支或者次优的分支，我们也可以把它剪掉。

AlphaZero Explained

棋类复杂度

回溯法

回溯法采用试错的思想，尝试分布的去解决一个问题。在分布解决问题的过程中，当它通过尝试发现现有的分布答案不能得到有效的正确的解答的时候，它讲取消上一步甚至是上几步的计算，再通过其它的可能的分布解答再次尝试寻找问题的答案。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

  • 找到一个可能存在的正确的答案
  • 在尝试了所有可能的分布方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

相关题目

爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）

括号生成（亚马逊、Facebook、字节跳动在半年内面试中考过）

N 皇后（亚马逊、苹果、字节跳动在半年内面试中考过）

有效的数独（亚马逊、苹果、微软在半年内面试中考过）

解数独（亚马逊、华为、微软在半年内面试中考过）

  1. // 有效的数独
  3. /**
  4.  * @param {character[][]} board
  5.  * @return {boolean}
  6.  */
  7. var isValidSudoku = function(board) {
  8.   const rows = new Array(9).fill(0).map(() => new Array(9).fill(0));
  9.   const columns = new Array(9).fill(0).map(() => new Array(9).fill(0));
  10.   const subboxes = new Array(3).fill(0).map(() => new Array(3).fill(0).map(() => new Array(9).fill(0)));
  12.   for (let i = 0; i < 9; i++) {
  13.     for (let j = 0; j < 9; j++) {
  14.       const c = board[i][j];
  16.       if (c !== '.') {
  17.         const index = c.charCodeAt() - '0'.charCodeAt() - 1;
  19.         rows[i][index]++;
  20.         columns[j][index]++;
  21.         subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index]++;
  23.         if (
  24.           rows[i][index] > 1 ||
  25.           columns[j][index] > 1 ||
  26.           subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index] > 1
  27.         ) {
  28.           return false;
  29.         }
  30.       }
  31.     }
  32.   }
  33.   return true;
  34. };
  1. // 解数独
  3. /**
  4.  * @param {character[][]} board
  5.  * @return {void} Do not return anything, modify board in-place instead.
  6.  */
  7. var solveSudoku = function(board) {
  8.   backTracking(board);
  9.   return board;
  11. };
  13. function backTracking(board) {
  14.   for(let i = 0; i < board.length; i++) {
  15.     for(let j = 0; j < board[0].length; j++) {
  16.       if(board[i][j] !== '.') continue;
  18.       for(let val = 1; val <= 9; val++) {
  19.         if(isValid(i, j, `${val}`, board)) {
  20.           board[i][j] = `${val}`
  21.           if (backTracking(board)) {
  22.               return true;
  23.           }
  25.           board[i][j] = `.`;
  26.         }
  27.       }
  28.       return false;
  29.     }
  30.   }
  31.   return true;
  32. }
  34. function isValid(row, col, val, board) {
  35.   let len = board.length;
  37.   for(let i = 0; i < len; i++) {
  38.     if(board[row][i] === val) {
  39.       return false;
  40.     }
  41.   }
  43.   for(let i = 0; i < len; i++) {
  44.     if(board[i][col] === val) {
  45.       return false;
  46.     }
  47.   }
  48.   let startRow = Math.floor(row / 3) * 3;
  49.   let startCol = Math.floor(col / 3) * 3;
  51.   for(let i = startRow; i < startRow + 3; i++) {
  52.     for(let j = startCol; j < startCol + 3; j++) {
  53.       if(board[i][j] === val) {
  54.         return false;
  55.       }
  56.     }
  57.   }
  59.   return true;
  60. }