算法思想 - 搜索算法 - 《算法学习》

题目一览图
零、搜索算法概述
一、暴力搜索
- 题目概述**
- 题目详解
  - 电话号码的字母组合">1.1.1 电话号码的字母组合
  - 括号生成">1.1.2 括号生成
  - 组合总和">1.1.3 组合总和
二、回溯算法
- 题目概述**
- 题目详解
  - 全排列">1.1.1 全排列
  - 全排列 II">1.1.2 全排列 II
  - 排列序列">1.1.3 排列序列
  - 复原IP地址">1.1.4 复原IP地址
  - 分割回文串">1.1.5 分割回文串
  - 子集">1.1.6 子集
  - 子集 II">1.1.7 子集 II
  - 组合">1.1.8 组合
  - 组合总和 II">1.1.9 组合总和 II
  - 解数独">1.2.1 解数独
  - N 皇后">1.2.2 N 皇后
  - N皇后 II">1.2.3 N皇后 II
  - 单词搜索">1.2.4 单词搜索

题目一览图

搜索算法 - 图1

零、搜索算法概述

【搜索搜索】本质是一个决策树的遍历问题，我们只需要考虑三个问题：

【路径】已经做出的选择。
【选择列表】当前可以做的选择。
【结束条件】达到决策树的底端。

一、暴力搜索

题目概述**

【暴力搜索】与后面【回溯算法】的区别在于，【暴力搜索】每一次选择相互独立，即选择列表相互不冲突。

var fun = function(nums) {
    const res = [];
    const backtrack = (idx,path)=>{
        if( check(idx) ) res.push(path);
          else backtrack(idx+1,changePath(path))
    }
    backtrack(0,'');
    return res;
};

题目详解

1.1.1 电话号码的字母组合

【概述】搜索
【题目描述**】
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
【题目分析**】本题的目的是将数字翻译成对应的字符，而这种映射关系不唯一，所以需要遍历。

【选择列表**】**每个选择列表相互独立，对应的字母互不相同。
【结束条件**】**序号 idx 等于长度时，说明数字和字符已经一一对应。
【路径更新**】**选一种映射方式，并将其添加至路径 path 的末尾。
```
var letterCombinations = function(digits) {
  if (digits.length == 0) return [];
  const res = [];
  const strs = ['','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
  const backtrack = (idx,path)=>{
      if(idx === digits.length) res.push(path);
      else for(let c of strs[digits[idx]-'1']) backtrack(idx+1,path+c); 
  }
  backtrack(0,'');
  return res;
};
```
1.1.2 括号生成
【概述】搜索括号
【题目描述**】
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
【题目分析**】本题的目的是给出所有有效括号组合，所以我们要通过括号规则造长度为 2n 的组合。
【选择列表**】**每个选择列表相互独立，都是左右括号选其一。
【结束条件**】**右括号数 r 等于 n 时，说明已经生成 n 对括号。
【**路径更新**】
- 左括号数 l 小于 n ，说明还可以加左括号 path+( 。
- 右括号数 r 小于 n 且小于 l ，说明还可以加右括号 path+) 。
```
var generateParenthesis = function(n) {
const res = [];
const backtrack = (l,r,path)=>{
   if( l < n ) backtrack(l+1,r,path+'(');
   if( r < n && r < l ) backtrack(l,r+1,path+')');
   if( r === n ) res.push(path);
}
backtrack(0,0,'');
return res;
};
```
  1.1.3 组合总和
  【概述】搜索有无
  【题目描述**】
  给定一个无重复元素的数组 candidates 和一个目标数 target ，找candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
  【题目分析**】本题的目的是给出数字和为 target 的组合。
【选择列表**】**candidates 中的数字，但是可以无限次拿取，所以选择之间独立。
【结束条件**】**
- 达到目标数 target ，满足要求输出结果。
- candidates 数组遍历完，但未达到目标数 target ，直接跳过。

【**路径更新**】

【选当前数】只要当前目标数还能被【当前数】减，就可以一直添加到路径。

【不选当前数】直接读取下一个数，不对路径操作。

var combinationSum = function(candidates, target) {
const res = [];
const backtrack = (index,target,path)=>{
   if( target === 0 ) {
       res.push(path);
       return;
   }
   if( index === candidates.length) return;
   backtrack(index+1,target,path);
   // 选择当前数
   if (target - candidates[index] >= 0) {
       backtrack(index, target - candidates[index], [...path, candidates[index]]);
   }
}
backtrack(0,target,[]);
return res;
};

二、回溯算法

题目概述**

【回溯算法】与后面【暴力搜索】的区别在于，【回溯算法】每一次选择相互不独立，每一次选择都会影响后续选择。

var fun = function(choices) {
      const n = choices.length;
    const res = [] , mono = new Array(n).fill(false);
    const backtrack = (idx,path)=>{
        if( check(idx) ){
            res.push(path);
          return;
        }
          for( let choice of choices){
          if(!mono[i]) continue;
            do();
          backtrack(idx+1,path)
          undo();
        }
    }
    backtrack(0,[]);
    return res;
};

题目详解

1.1.1 全排列

【概述】回溯算法完整遍历
【题目描述**】
给定一个没有重复数字的序列，返回其所有可能的全排列。
【题目分析**】

【选择列表】nums 中【未被使用过】的数字，需要用【备忘录】记录。
【结束条件】idx === nums.length 。

【**路径更新**】选择没有被【备忘录】记录过的数字。

const permute = (nums)=>{
  const mono  = new Array(m) , res = [];
  const backtrack = (idx, path)=>{
      if( idx === nums.length ) {
          res.push([...path]);
          return;
      }
      for(let i = 0 ; i < nums.length ; i++) {
          if( mono [i] ) continue;
          mono[i] = true;
          backtrack(idx+1,[...path,nums[i]]);
          mono[i] = false;
      }
  }
  backtrack(0,[]);
  return res;
}

1.1.2 全排列 II

【概述】回溯算法完整遍历
【题目关系】

全排列 - 增加了重复字符的条件。

【题目描述**】
给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
【题目分析**】为了寻找相同元素，需要先排序让相同数字相邻。

【选择列表】nums 中【未被使用过】的数字，需要用【备忘录】记录。
【结束条件】idx === nums.length 。

【**路径更新**】选择没有被【备忘录】记录过的数字。

【重复字符处理】先排序让相同数字相邻，然后通过 nums[i] === nums[i-1] 判断是否重复。但是在全排序中，相同元素也是有顺序的。那如何去确保这个顺序？每次都确保前一个重复元素被选择过，即 !mono[i-1] 。

var permuteUnique = function(nums) {
const res = [] ,  mono = new Array(m).fill(false);
nums.sort((a,b)=>a-b);
const backtrack = (idx,path)=>{
   if(idx===nums.length){
       res.push([...path]);
       return;
   }
   for(let i = 0 ; i < nums.length ; i++){
       if( mono[i] || i && nums[i] === nums[i-1] && !mono[i-1] ) continue;
       mono[i] = true;
       backtrack(idx+1,[...path,nums[i]]);
       mono[i] = false;
   }
}
backtrack(0,[]);
return res;
};

1.1.3 排列序列

【概述】回溯算法完整遍历
【题目关系】

全排列 - 寻找全排序中的第 k 个。

【题目描述**】
给出集合[1,2,3,...,n]，其所有元素共有 n! 种排列。给定 n 和 k，返回第 k 个排列。
【题目分析**】本题要求输出所有全排序中第 k 个元素。给全排序加个计数功能即可。

【选择列表】nums 中【未被使用过】的数字，需要用【备忘录】记录。
【结束条件】idx === nums.length && 第 k 次找到符合的全排序。

【**路径更新**】选择没有被【备忘录】记录过的数字。

var getPermutation = function(n, k) {
  const mono = new Array(n).fill(false);
  let count = 0 , res = '';
  const backtrack = (idx,path) =>{
      if( count > k ) return;
      if( idx === n ){
          count++;
          if(count===k) res = path.join('');
          return;
      }
      for( let i = 1 ; i <=n ; i++){
          if( mono[i] ) continue;
          mono[i] = true;
          backtrack(idx+1,[...path,i]);
          mono[i] = false;
      }
  }
  backtrack(0,[]);
  return res;
};

1.1.4 复原IP地址

【概述】回溯算法完整遍历分割字符串
【题目关系】

全排列 - 结束条件更为复杂。

【题目描述**】
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
【题目分析**】本题要求输出所有可能的 IP 地址格式。

【选择列表】索引 idx 不断更新，确保遍历整个选择列表。每次的选择列表是 s[idx... idx+2] 。
【结束条件】IP地址被分割为 4 个部分，且被完全遍历idx === s.length 。

【**路径更新**】路径存在于 s[idx],s[idx,idx+1],s[idx,idx+1,idx+2] 之间，只要满足数字在 0-255 之间，且开头不能为 0 （ 0 除外），就可以当做新的路径。

var restoreIpAddresses = function(s) {
  const n  = s.length , res = [];
  const backtrack = (idx,path)=>{
      if( path.length === 4 ){
          if( idx === n ) res.push(path.join('.'));
          return;
      }
      for( let i = 0 ; i < 3 ; i++ ){
          if( idx + i > n || i && s[idx] === '0' ) return;
          const str = s.substr(idx,i+1);
          if( i === 2 && +str > 255 ) return;
          path.push(str);
          backtrack(idx+i+1,path);
          path.pop();
      }
  }
  backtrack(0,[]);
  return res;
};

1.1.5 分割回文串

【概述】回溯算法完整遍历分割字符串
【题目关系】

复原IP地址 - 同样是对字符串进行分割。

【题目描述**】
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
【题目分析**】本题要求输出所有可能的回文串分割方式。第一个难点在于如何标记回文串的范围，第二就是如何遍历出所有方案。

【回文问题】需要通过【动态规划】定位回文数组。dp[idx][i] 表示从 idx 到 i 的子字符串是不是回文串。
【选择列表】索引 idx 不断更新，确保遍历整个选择列表。每次的选择列表是 s[idx... n] 。
【结束条件】本题目的是分割 s ，所以最终回文子串的总长度要等于总长， idx === s.length 。

【**路径更新**】在 idx 的基础上进行遍历，索引是 i 。如果 s[idx... i] 是回文串，添加子回文串。

var partition = function(s){
  const n = s.length;
  if(!n) return [];
  const res  = [];
  const dp = new Array(n).fill(false).map(()=>new Array(n).fill(false));
  for( let i = n - 1 ; i >= 0 ; i--){
      for( let j = i ; j < n ; j++){
          dp[i][j] = s[i]===s[j] && ( j-i<2 || dp[i+1][j-1])
      }
  }

  const backtrack = (idx,path) =>{
      if( idx === s.length ) {
          res.push([...path]);
          return;
      }
      for( let i = idx ; i < n ; i++){
          if(!dp[idx][i]) continue;
          path.push(s.substring(idx, i + 1));
          backtrack(i+1,path);
          path.pop();
      }
  }
  backtrack(0,[]);
  return res;
};

1.1.6 子集

【概述】回溯算法部分遍历无顺序
【题目关系】

全排列 - 不需用完整遍历

【题目描述**】
给你一个整数数组 nums ，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。
【题目分析**】

【选择列表】索引 idx 不断更新，确保遍历整个选择列表。每次的选择列表是 nums[idx... n] 。
【结束条件】直接输出。
【**路径更新**】idx... n 每个字符都有【选】和【不选】两种可能。
- 【选】path.push(i) ，将选择后的 path 放入下一轮递归。
- 【不选】撤销之前的选择 path.pop() ，进入下一轮 for 循环。**
```
var subsets = function(nums) {
const res = [];

const backtrack = (idx,path)=>{
   res.push([...path]);
   for( let i = idx ; i < nums.length ; i++ ){
       path.push(nums[i]);
       backtrack(i+1,path);
       path.pop();
   }
}
backtrack(0,[]);
return res;
};
```
  1.1.7 子集 II
  【概述】回溯算法部分遍历无顺序
  【题目关系】
子集 - 增加有重复元素的条件。
全排列 II - 子集无顺序之分。

【题目描述**】
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
【题目分析**】为了寻找相同元素，需要先排序让相同数字相邻。

【选择列表】索引 idx 不断更新，确保遍历整个选择列表。每次的选择列表是 nums[idx... n] 。
【结束条件】直接输出。
【**路径更新**】idx... n 每个字符都有【选】、【不选】和【重复】三种可能。
- 【选】path.push(i) ，将选择后的 path 放入下一轮递归。
- 【不选】撤销之前的选择 path.pop() ，进入下一轮 for 循环。
- 【重复】如何 nums[i] === nums[i-1] ，说明出现重复，直接跳过。
```
var subsetsWithDup = function(nums) {
const res = [];
nums.sort((a,b)=>a-b);
const backtrack = (nums,idx,path)=>{
   res.push([...path]);
   for( let i = idx ; i < nums.length ; i++ ){
       if( i > idx &&  nums[i] === nums[i-1] ) continue;
       path.push(nums[i]);
       backtrack(nums,i+1,path);
       path.pop();
   }
}
backtrack(nums,0,[]);
return res;
};
```
  1.1.8 组合
  【概述】回溯算法部分遍历无顺序
  【题目关系】
子集 - 增加了长度限制。

【题目描述**】
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
【题目分析**】

【选择列表】索引 idx 不断更新，确保遍历整个选择列表。每次的选择列表是 idx... n 。
【结束条件】路径长度等于 k 。
【**路径更新**】idx... n 每个字符都有【选】和【不选】两种可能。
- 【选】path.push(i) ，将选择后的 path 放入下一轮递归。
- 【不选】撤销之前的选择 path.pop() ，进入下一轮 for 循环。
```
var combine = function(n, k) {
const res = [];
if (k <= 0 || n <= 0) return res;
const backtrack = (idx,path)=>{
   if( path.length > k ) return;
   if( path.length === k ){
       res.push([...path]);
       return;
   }
   for( let i = idx ; i <= n ; i++){
       path.push(i);
       backtrack(i+1,path);
       path.pop();
   }
}
backtrack(1,[]);
return res;
};
```
  1.1.9 组合总和 II
  【概述】回溯算法部分遍历无顺序
  
  【题目描述**】**
  给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

【题目分析**】**为了寻找相同元素，需要先排序让相同数字相邻。

【选择列表】索引 idx 不断更新，确保遍历整个选择列表。每次的选择列表是 candidates[idx ... n] 。
【结束条件】数字和大于 0 时，说明不符合条件，直接跳出。数字和等于于 0 时，说明符合条件。
【**路径更新**】candidates[idx ... n]每个数字都有【选】和【不选】两种可能。
- 【选】path.push(i) ，将选择后的 path 和数字和放入下一轮递归。
- 【不选】撤销之前的选择 path.pop() ，进入下一轮 for 循环。 ```javascript const combinationSum2 = (candidates, target) => { const res = []; candidates.sort((a,b) => a - b );
  
  const backtrack = (idx, path, target) => { if (target<0) return; if (!target) {
```
   res.push([...path]); 
   return;
```
  } for (let i = idx; i < candidates.length; i++) {
```
   if (i  > idx && candidates[i - 1] == candidates[i]) continue;
   path.push(candidates[i]);          
   backtrack(i + 1, path, target - candidates[i]); 
   path.pop();
```
  } };
backtrack(0, [], target); return res; }; ```

1.2.1 解数独
【概述】回溯算法二维

【题目描述**】
编写一个程序，通过填充空格来解决数独问题。
【题目分析**】
【遍历方式**】**索引改为 x y ，y 每走到 9 ，相当于走完一行，跳转至下一行，即 x++ 。
【选择列表】每次的选择列表是 0-9 ，但【同行】、【同列】以及【同框】不能有重复元素。
【结束条件】遍历完所有格子，x === 9 。

【**路径更新**】从 0-9 选【同行】、【同列】以及【同框】没有的数字。【选】和【不选】两种可能。

【同行】x 不一样。
【同列】y 不一样。

【同框】boxIndex 不一样，其中 boxIndex = Math.floor(x/3)*3 + Math.floor(y/3)。

var solveSudoku = function(board) {
const row = {} , col = {} , box = {};

for( let i = 0 ; i < 9 ; i++){
   for( let j = 0 ; j < 9 ; j++){
       if( board[i][j] !== '.'){
           const num = board[i][j], boxIndex = Math.floor(i/3)*3 + Math.floor(j/3);
           row[`${i}-${num}`] = true;
           col[`${j}-${num}`] = true;
           box[`${boxIndex}-${num}`] = true;
       }
   }
}

const backtrack = (x,y)=>{
   if( y === 9 ) x++, y = 0;
   if( x === 9 ) return true;

   if(board[x][y]!=='.') return dfs(x,y+1);
   for( let i = 1 ; i <= 9 ; i++){
       const boxIndex = Math.floor(x/3)*3 + Math.floor(y/3)
       if(row[`${x}-${i}`]===undefined && col[`${y}-${i}`]===undefined && box[`${boxIndex}-${i}`]===undefined ){
           board[x][y] = ''+i;
           row[`${x}-${i}`]  = col[`${y}-${i}`] = box[`${boxIndex}-${i}`] = true;
           if(backtrack(x,y+1)) return true;
           board[x][y]='.';
           row[`${x}-${i}`] = col[`${y}-${i}`] = box[`${boxIndex}-${i}`] = undefined;
       }
   }
   return false;
}
backtrack(0,0);
};

1.2.2 N 皇后

【概述】回溯算法二维

【题目描述**】
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
【题目分析**】

【遍历方式**】**由于 n 皇后问题是以行、对角线为单位，所以不用将索引改为 x y ，采用 idx 遍历 n 行。
【选择列表】每次的选择列表是是否放 Q 。由于 idx 遍历的是 n 行，可以确保 Q 在不同行，所以只要考虑【同列】、【正对角】以及【反对角】不能有重复元素即可。
【结束条件】遍历完所有行，idx === n 。

【**路径更新**】从 0-9 选【同列】、【正对角】以及【反对角】没有涉及的位置。

【同列】i 不一样。
【正对角】idx-i+n

【反对角】idx+i

var solveNQueens = function(n) {
const col = new Array(n);
const dg = new Array(2 * n) , udg = new Array(2 * n);
const res = [] ;

const backtrack = (idx , path)=>{    
   if( idx === n ) {
       const newPath = path.map((item)=>item.join(''));
       res.push(newPath);
       return;
   }
   for( let i = 0 ; i < n ; i++){
       if(!col[i] && !dg[idx-i+n] && !udg[idx + i]){
           col[i] = true , dg[idx-i+n] = true , udg[idx + i] = true;
           path[idx][i] = 'Q';
           backtrack(idx+1,[...path]);
           col[i] = false , dg[idx-i+n] = false , udg[idx + i] = false;
           path[idx][i] = '.';
       }
   }
}

backtrack(0,new Array(n).fill('.').map(()=>new Array(n).fill('.')));
return res;
};

1.2.3 N皇后 II

【概述】回溯算法二维

【题目描述**】
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
【题目分析**】具体见【N 皇后】，只是从输出所有可能，变成了计数。

var totalNQueens = function(n) {
const col = new Array(n);
const dg = new Array(2*n) , ndg = new Array(2*n);
let count = 0;

const backtrack = (idx)=>{
   if(idx===n){
       count++;
       return;
   }
   for(let i = 0 ; i < n ; i++){
       if(col[i]||dg[i-idx+n]||ndg[i+idx])continue;
       col[i] = dg[i-idx+n] = ndg[i+idx] =true;
       backtrack(idx+1);
       col[i] = dg[i-idx+n] = ndg[i+idx] =false;
   }
}
backtrack(0);
return count;
};

1.2.4 单词搜索

【概述】回溯算法二维

【题目描述**】
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
【题目分析**】

【遍历方式**】**索引为 x y 和 idx 。x y 表示二维矩阵的位置，idx 表示字符串的长度。
【选择列表】每次的选择列表是 【上下左右】 四个方向移动。【同行】、【同列】以及【同框】不能有重复元素。
【结束条件】**【上下左右】** 四个方向有一方向走通。
- 【单路结束】
  - 【成功】idx === word.length
  - 【失败】走到边界 || 回头路 || 字符不相同 ```javascript var exist = function(board, word) { const m = board.length , n = board[0].length; const mono = new Array(m).fill(false).map(()=>new Array(n));
  const backtrack = (idx,x,y) =>{ if( idx === word.length ) return true; if( x < 0 || x >= m || y < 0 || y >= n || mono[x][y] || board[x][y] !== word[idx]) return false; mono[x][y] = true; const res = backtrack(idx+1,x+1,y)||backtrack(idx+1,x-1,y)||backtrack(idx+1,x,y+1)||backtrack(idx+1,x,y-1); if(res) return true; mono[x][y] = false; return false; }
  
  for(let i = 0 ; i < m ; i++){ for( let j = 0 ; j < n ; j++){
```
   if(board[i][j]===word[0] && backtrack(0,i,j)) {
       return true
   }
```
  } } return false; }; ```

搜索算法

题目一览图

零、搜索算法概述

一、暴力搜索

题目概述**

题目详解

1.1.1 电话号码的字母组合

1.1.2 括号生成

1.1.3 组合总和

二、回溯算法

题目概述**

题目详解

1.1.1 全排列

1.1.2 全排列 II

1.1.3 排列序列

1.1.4 复原IP地址

1.1.5 分割回文串

1.1.6 子集

1.1.7 子集 II

1.1.8 组合

1.1.9 组合总和 II

1.2.1 解数独

1.2.2 N 皇后

1.2.3 N皇后 II

1.2.4 单词搜索