写点什么

大厂算法面试之 leetcode 精讲 11 剪枝 & 回溯

作者:全栈潇晨
  • 2021 年 11 月 30 日
  • 本文字数:14778 字

    阅读完需:约 48 分钟

大厂算法面试之 leetcode 精讲 11 剪枝 &回溯

视频讲解(高效学习):点击学习

目录:

1.开篇介绍


2.时间空间复杂度


3.动态规划


4.贪心


5.二分查找


6.深度优先&广度优先


7.双指针


8.滑动窗口


9.位运算


10.递归&分治


11剪枝&回溯


12.堆


13.单调栈


14.排序算法


15.链表


16.set&map


17.栈


18.队列


19.数组


20.字符串


21.树


22.字典树


23.并查集


24.其他类型题

剪枝

排除那些不符合条件的分支。提高程序的运行效率。


回溯:

一层层递归,尝试搜素答案,


  • 找到答案:返回结果,尝试其他的分支

  • 找不到答案:返回上一层,尝试其他分支


回溯模版:


result = [];function backtrack (path, list) {    if (满足条件) {        result.push(path);        return    }        for () {        // 单层逻辑        backtrack (path, list)        // 撤销选择 重置状态    }}
复制代码


回溯四部曲:


  • 回溯参数

  • 终止条件

  • 单层递归逻辑

  • 选择其他分支(撤销选择 重置状态)

22. 括号生成 (medium)

方法 1:暴力

复杂度分析:时间复杂度O(2^2n*n),字符串的长度为2n,每个位置有两种选择,选择左或者右括号,验证字符串是否有效复杂度O(n),剪枝之后会优化,最坏的情况是O(2^2n*n)。空间复杂度O(n),递归次数最多 2n

方法 2.递归 dfs
  • 思路:采用递归,终止条件是字符串的长度等于2n,递归函数传入构建的字符串,左右括号剩余多少,每个位置有两种选择,选择左或者右括号,这里可以进行剪枝优化,只有右括号的保有数量大于左括号的保有数量,才能选右括号,否则肯定不能构成有效括号


Js:


const generateParenthesis = (n) => {    const res = []; // 输出的结果数组
const generate = (str, left, right) => { if (str.length == 2 * n) { // 字符串构建完成 res.push(str); // 将字符串加入res return; // 结束当前递归(结束当前搜索分支) } if (left > 0) { // 只要左括号有剩,可以选它,继续递归做选择 generate(str + '(', left - 1, right); } if (right > left) { // 右括号的保有数量大于左括号的保有数量,才能选右括号 generate(str + ')', left, right - 1); } };
generate('', n, n); // 递归的入口,初始字符串是空字符串,初始括号数量都是n return res;};
复制代码


Java:


class Solution {    List<String> res = new ArrayList<>();    public List<String> generateParenthesis(int n) {        generate(n, n, "");        return res;    }
private void generate(int left, int right, String curStr) { if (left == 0 && right == 0) { res.add(curStr); return; }
if (left > 0) { generate(left - 1, right, curStr + "("); } if (right > left) { generate(left, right - 1, curStr + ")"); } }}
复制代码
方法 3.回溯
  • 思路:当左括号剩下的多,说明字符串中的左括号数量少于右括号,不合法,对字符串尝试添加左括号,然后回溯,尝试添加右括号,然后尝试回溯


Js:


var generateParenthesis = function(n) {    if (n == 0) return []    const res = []    let track = []    backtrack(n, n, track, res)    return res    function backtrack(left, right, track, res) {        // 数量小于0,不合法        if (left < 0 || right < 0) return        // 若左括号剩下的多,说明不合法        if (right < left) return        // 所有括号用完,得到合法组合        if (left == 0 && right == 0) {            res.push(track.join(''))            return        }
// 尝试添加左括号 track.push('(') //这个地方一定要注意 需要拷贝一份track,也就是采用[...track], 不然会影响其他分支 backtrack(left - 1, right, [...track], res) track.pop()
// 尝试添加右括号 track.push(')') backtrack(left, right - 1, [...track], res) track.pop() }};
复制代码


Java:


class Solution {    public List<String> generateParenthesis(int n) {        List<String> res = new ArrayList<String>();        backtrack(res, new StringBuilder(), 0, 0, n);        return res;    }
public void backtrack(List<String> res, StringBuilder cur, int left, int right, int max) { if (cur.length() == max * 2) { res.add(cur.toString()); return; } if (left < max) { cur.append('('); backtrack(res, cur, left + 1, right, max); cur.deleteCharAt(cur.length() - 1); } if (right < left) { cur.append(')'); backtrack(res, cur, left, right + 1, max); cur.deleteCharAt(cur.length() - 1); } }}
复制代码

51. N 皇后 (hard)

方法 1.回溯

动画过大,点击查看


  • 思路:从上到下,从左到右遍历棋盘,准备好三个 set 分别记录列和两个对角线可以攻击到的坐标,尝试在每个空位放置皇后,放置之后更新三个可以攻击到的 set 坐标,然后继续下一层遍历,完成下一层之后,尝试回溯当前层,也就是撤销当前层放置的皇后,同时撤销三个可以攻击到的 set 坐标,不断回溯,直到遍历完成,找到所有可能的解。

  • 复杂度分析:时间复杂度:O(N!),其中 N 是皇后数量,由于每个皇后必须位于不同列,因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择,第二个皇后最多有 N-1 列可以选择...。空间复杂度:O(N),其中 N 是皇后数量,空间复杂度主要取决于递归调用层数、记录每行放置的皇后列下标的数组以及三个集合,递归调用层数不会超过 N,数组的长度为 N,每个集合的元素个数都不会超过 N。


js:


const solveNQueens = (n) => {    const board = new Array(n);    for (let i = 0; i < n; i++) {        board[i] = new Array(n).fill('.');//生成board    }
const cols = new Set(); // 列集,记录出现过皇后的列 const diag1 = new Set(); // 正对角线集 const diag2 = new Set(); // 反对角线集 const res = [];//结果数组
const backtrack = (row) => { if (row == n) {//终止条件 const stringsBoard = board.slice(); for (let i = 0; i < n; i++) {//生成字符串 stringsBoard[i] = stringsBoard[i].join(''); } res.push(stringsBoard); return; } for (let col = 0; col < n; col++) { // 如果当前点的所在的列,所在的对角线都没有皇后,即可选择,否则,跳过 if (!cols.has(col) && !diag1.has(row + col) && !diag2.has(row - col)) { board[row][col] = 'Q'; // 放置皇后 cols.add(col); // 记录放了皇后的列 diag2.add(row - col); // 记录放了皇后的正对角线 diag1.add(row + col); // 记录放了皇后的负对角线 backtrack(row + 1); board[row][col] = '.'; // 撤销该点的皇后 cols.delete(col); // 对应的记录也删一下 diag2.delete(row - col); diag1.delete(row + col); } } }; backtrack(0); return res;};
复制代码


java:


class Solution {    public List<List<String>> solveNQueens(int n) {        List<List<String>> res = new ArrayList<List<String>>();        int[] queens = new int[n];        Arrays.fill(queens, -1);        Set<Integer> cols = new HashSet<Integer>();        Set<Integer> diag1 = new HashSet<Integer>();        Set<Integer> diag2 = new HashSet<Integer>();        backtrack(res, queens, n, 0, cols, diag1, diag2);        return res;    }
public void backtrack(List<List<String>> res, int[] queens, int n, int row, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) { if (row == n) { List<String> board = generateBoard(queens, n); res.add(board); } else { for (int i = 0; i < n; i++) { if (cols.contains(i)) { continue; } int diagonal1 = row - i; if (diag1.contains(diagonal1)) { continue; } int diagonal2 = row + i; if (diag2.contains(diagonal2)) { continue; } queens[row] = i; cols.add(i); diag1.add(diagonal1); diag2.add(diagonal2); backtrack(res, queens, n, row + 1, cols, diag1, diag2); queens[row] = -1; cols.remove(i); diag1.remove(diagonal1); diag2.remove(diagonal2); } } }
public List<String> generateBoard(int[] queens, int n) { List<String> board = new ArrayList<String>(); for (int i = 0; i < n; i++) { char[] row = new char[n]; Arrays.fill(row, '.'); row[queens[i]] = 'Q'; board.add(new String(row)); } return board; }}
复制代码

52. N皇后 II(hard)

方法 1.位运算


js:


var totalNQueens = function (n) {    if (n < 1) return    let count = 0;    dfs(n, 0, 0, 0, 0)    return count
//n:皇后的数量 //row:当前行 //cols:放置皇后的位置 //diag1:可以攻击的左倾斜对角线 //diag2:可以攻击的右倾斜对角线 function dfs(n, row, cols, diag1, diag2) { if (row >= n) {//递归终止 统计解法 count += 1; return } //~(cols | diag1 | diag2):攻击的位置合起来 取反之后,1的位置就是可以放置皇后的位置 //(1 << n) - 1:从右向左,大于n的位置都变成0 //(~(cols | diag1 | diag2)) & ((1 << n) - 1):从右向左,可以放置皇后的位置,大于n的位置都变成0 let bits = (~(cols | diag1 | diag2)) & ((1 << n) - 1) while (bits) { let p = bits & -bits//取到从右向左第一个1 bits = bits & (bits - 1)//去掉从右向左第一个1 //列和两个对角线合上不可以放置的二进制位 dfs(n, row + 1, cols | p, (diag1 | p) << 1, (diag2 | p) >>> 1) } }};
复制代码


Java:


class Solution {    public int totalNQueens(int n) {        return dfs(n, 0, 0, 0, 0);    }
public int dfs(int n, int row, int clos, int diag1, int diag2) { if (row == n) { return 1; } else { int count = 0; int bits = ((1 << n) - 1) & (~(clos | diag1 | diag2)); while (bits != 0) { int position = bits & (-bits); bits = bits & (bits - 1); count += dfs(n, row + 1, clos | position, (diag1 | position) << 1, (diag2 | position) >> 1); } return count; } }}
复制代码

36. 有效的数独 (medium)

方法 1:回溯


  • 思路:准备行、列、3 * 3 小方块,三个哈希表或者 set 或者 9 * 9 的二维数组,都可以,只要能判重复即可,从上到下,从左到右循环,依次检查行、列、3 * 3 小方块中是否有重复的数字,如果有则返回 false,然后更新哈希表或者 set。

  • 复杂度分析:时间复杂度:O(1),数独共有 81 个单元格,每个单元格遍历一次即可。空间复杂度:O(1),数独的大小固定,因此哈希表的空间也是固定的。


Js:


var isValidSudoku = function(board) {    // 方向判重    let rows = {};//行    let columns = {};//列    let boxes = {};//3*3小方块    // 遍历数独    for(let i = 0;i < 9;i++){        for(let j = 0;j < 9;j++){            let num = board[i][j];            if(num != '.'){//遇到有效的数字                let boxIndex = parseInt((i/3)) * 3 + parseInt(j/3);// 子数独序号                if(rows[i+'-'+num] || columns[j+'-'+num] || boxes[boxIndex+'-'+num]){//重复检测                    return false;                }                // 方向 + 数字 组成唯一键值,若出现第二次,即为重复                // 更新三个对象                rows[i+'-'+num] = true;                columns[j+'-'+num] = true;                boxes[boxIndex+'-'+num] = true;            }        }    }    return true;};
复制代码


Java:


class Solution {    public boolean isValidSudoku(char[][] board) {        int[][] rows = new int[9][9];//用数组同样实现        int[][] columns = new int[9][9];        int[][][] boxes = new int[3][3][9];        for (int i = 0; i < 9; i++) {            for (int j = 0; j < 9; j++) {                char c = board[i][j];                if (c != '.') {                    int index = c - '0' - 1;                    rows[i][index]++;                    columns[j][index]++;                    boxes[i / 3][j / 3][index]++;                    if (rows[i][index] > 1 || columns[j][index] > 1 || boxes[i / 3][j / 3][index] > 1) {                        return false;                    }                }            }        }        return true;    }}
复制代码

37. 解数独(hard)

  • 思路:循环行和列,尝试在每个位置放置 1-9,并检验合法性,包括行、列、3 * 3 方块的合法性,如果合法继续循环,直到找到一个合法的解,如果不合法,则回溯状态,并继续尝试其他的可能性

  • 复杂度分析:同 36 题


js:


var solveSudoku = function(board) {    function isValid(row, col, val, board) {        let len = board.length        // 行中的数字不能重复        for(let i = 0; i < len; i++) {            if(board[row][i] === val) {                return false            }        }        // 列中的数字不能重复        for(let i = 0; i < len; i++) {            if(board[i][col] === val) {                return false            }        }        let startRow = Math.floor(row / 3) * 3        let startCol = Math.floor(col / 3) * 3
//方块中的数字不能重复 for(let i = startRow; i < startRow + 3; i++) { for(let j = startCol; j < startCol + 3; j++) { if(board[i][j] === val) { return false } } }
return true }
function backTracking() {//回溯函数 for(let i = 0; i < board.length; i++) { for(let j = 0; j < board[0].length; j++) {//循环行和列 if(board[i][j] !== '.') continue for(let val = 1; val <= 9; val++) {//尝试在当前单元格放置1-9 if(isValid(i, j, `${val}`, board)) {//判断放置数字的合法性 board[i][j] = `${val}`//放置数字 if (backTracking()) {//合法返回ture return true } board[i][j] = `.`//不合法回溯状态 } } return false//1-9的数字都不合法,返回false } } return true//全部可能性都尝试完成 返回true 说明有解 } backTracking() return board };
复制代码


Java:


class Solution {    public void solveSudoku(char[][] board) {        backTracking(board);    }
private boolean backTracking(char[][] board){ for (int i = 0; i < 9; i++){ // 遍历行 for (int j = 0; j < 9; j++){ // 遍历列 if (board[i][j] != '.'){ continue; } for (char k = '1'; k <= '9'; k++){ //尝试在当前位置放置1-9 if (isValid(i, j, k, board)){ board[i][j] = k;//放置数字 if (backTracking(board)){ //合法返回ture return true; } board[i][j] = '.'; } } return false;//1-9的数字都不合法,返回false } } return true;//全部可能性都尝试完成 返回true 说明有解 }
private boolean isValid(int row, int col, char val, char[][] board){ // 同行是否重复 for (int i = 0; i < 9; i++){ if (board[row][i] == val){ return false; } } // 同列是否重复 for (int j = 0; j < 9; j++){ if (board[j][col] == val){ return false; } } // 小方块中的元素是否重复 int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; for (int i = startRow; i < startRow + 3; i++){ for (int j = startCol; j < startCol + 3; j++){ if (board[i][j] == val){ return false; } } } return true; }}
复制代码

79. 单词搜索(medium)


  • 思路:从上到下,左到右遍历网格,每个坐标递归调用check(i, j, k)函数,i,j 表示网格坐标,k 表示 word 的第 k 个字符,如果能搜索到第 k 个字符返回 true,否则返回 false,check 函数的终止条件有 2 种情况

  • 如果 i,j 位置的字符和字符串位置 k 的字符不相等,则这条搜索路径搜索失败 返回 false

  • 如果搜索到了字符串的结尾,则找到了网格中的一条路径,这条路径上的字符正好可以组成字符串 s

  • 两种情况都不满足则把当前网格节点加入visited数组,visited表示节点已经访问过了,然后顺着当前网格坐标的四个方向继续尝试,如果没找到 k 开始的子串,则回溯状态visited[i] [j] = false,继续后面的尝试。

  • 复杂度分析:时间复杂度O(MN⋅3^L),M,N 为网格的长度与宽度,L 为字符串 word 的长度,第一次调用check函数的时候,进行 4 个方向的检查,其余坐标的节点都是 3 个方向检查,走过来的分支不会反方向回去,所以check函数的时间复杂度是3^L,而网格有M*N个坐标,且存在剪枝,所以最坏的情况下时间复杂度是O(MN⋅3^L)。空间复杂度是O(MN)visited数组空间是O(MN)check递归栈的最大深度在最坏的情况下是O(MN)

方法 1:回溯

Js:


var exist = function(board, word) {    const h = board.length, w = board[0].length;//网格的长和宽    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];//方向数组    const visited = new Array(h);//标记是否访问过的数组    for (let i = 0; i < visited.length; ++i) {//初始化visited数组        visited[i] = new Array(w).fill(false);    }    const check = (i, j, s, k) => {//检查从网格i,j出发是否能搜索到0-k的字符组成的子串        //如果i,j位置的字符和第k个的字符不相等,则这条搜索路径搜索失败 返回false        if (board[i][j] != s.charAt(k)) {            return false;         //如果搜索到了字符串的结尾,则找到了网格中的一条路径,这条路径上的字符正好可以组成字符串s        } else if (k == s.length - 1) {            return true;        }        visited[i][j] = true;//标记i,j被访问过了        let result = false;        for (const [dx, dy] of directions) {//向i,j的四个方向继续尝试寻找            let newi = i + dx, newj = j + dy;            if (newi >= 0 && newi < h && newj >= 0 && newj < w) {//新的坐标位置合法检查                if (!visited[newi][newj]) {//新的坐标不能存在于visited中,也就是不能是访问过的                    const flag = check(newi, newj, s, k + 1);//继续检查新的坐标                    if (flag) {//如果在网格中找到了字符串 则跳过循环                        result = true;                        break;                    }                }            }        }        visited[i][j] = false;//回溯状态        return result;//返回结果    }
for (let i = 0; i < h; i++) { for (let j = 0; j < w; j++) { const flag = check(i, j, word, 0); if (flag) { return true; } } } return false;};
复制代码


Java:


class Solution {    public boolean exist(char[][] board, String word) {        int h = board.length, w = board[0].length;        boolean[][] visited = new boolean[h][w];        for (int i = 0; i < h; i++) {            for (int j = 0; j < w; j++) {                boolean flag = check(board, visited, i, j, word, 0);                if (flag) {                    return true;                }            }        }        return false;    }
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) { if (board[i][j] != s.charAt(k)) { return false; } else if (k == s.length() - 1) { return true; } visited[i][j] = true; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean result = false; for (int[] dir : directions) { int newi = i + dir[0], newj = j + dir[1]; if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) { if (!visited[newi][newj]) { boolean flag = check(board, visited, newi, newj, s, k + 1); if (flag) { result = true; break; } } } } visited[i][j] = false; return result; }}
复制代码

46. 全排列 (medium)


  • 思路:准备 path 数组,存放每一个回溯递归的分支中的数字排列,调用回溯函数 传入 nums,nums 长度,used 数组,used 表示已经使用的数字,回溯函数中循环 nums 中的数,每层循环将 nums 中的元素加入 path 中,然后递归调用回溯函数,调用完成之后,回溯之前的状态,当 path 数组的长度和 nums 的长度相同就找到了一种排列。

  • 复杂度:时间复杂度O(n*n!)。空间复杂度O(n),递归栈深度


js:


var permute = function(nums) {    const res = [], path = [];    backtracking(nums, nums.length, []);//调用回溯函数 传入nums,nums长度,used数组    return res;        function backtracking(n, k, used) {        if(path.length === k) {//递归终止条件            res.push(Array.from(path));            return;        }        for (let i = 0; i < k; i++ ) {            if(used[i]) continue;//已经使用过了就跳过本轮循环            path.push(n[i]);            used[i] = true;             backtracking(n, k, used);//递归            path.pop();//回溯 将push进的元素pop出来 然后标记成未使用 继续其他分支            used[i] = false;        }    }};
复制代码


java:


class Solution {
List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); boolean[] used; public List<List<Integer>> permute(int[] nums) { if (nums.length == 0){ return result; } used = new boolean[nums.length]; permuteHelper(nums); return result; }
private void permuteHelper(int[] nums){ if (path.size() == nums.length){ result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++){ if (used[i]){ continue; } used[i] = true; path.add(nums[i]); permuteHelper(nums); path.removeLast(); used[i] = false; } }}
复制代码

77. 组合 (medium)


  • 思路:回溯函数传入 n,k 和选择的元素位置 startIndex,在每层递归中,从 startIndex 开始循环到 n - (k - path.length) + 1的位置,将这些数加入 path,然后 startIndex 加 1,继续递归函数进入下一个分支,完成调用之后回溯状态,当 path 的长度等于 k 的时候终止这层分支,加入结果中。

  • 复杂度:时间复杂度:O(C(n, k) * k),枚举结果总数为C(n, k),每次得到一个结果需要O(k)时间。空间复杂度:O(n),最大是 n 层递归栈。


js:


const combine = (n, k) => {  const res = [];
const helper = (startIndex, path) => { //startIndex表示搜索的起点位置 path是每条分支的一个组合) if (path.length == k) { res.push(path.slice()); //需要拷贝一份 避免受其他分支的影响 return; } for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {//剪枝 path.push(i); //加入path helper(i + 1, path); //下一层递归 path.pop(); //回溯状态 } };
helper(1, []); //递归入口 return res;}
复制代码


java:


class Solution {    List<List<Integer>> result = new ArrayList<>();    LinkedList<Integer> path = new LinkedList<>();    public List<List<Integer>> combine(int n, int k) {        combineHelper(n, k, 1);        return result;    }
private void combineHelper(int n, int k, int startIndex){ if (path.size() == k){ result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){ path.add(i); combineHelper(n, k, i + 1); path.removeLast(); } }}
复制代码

17. 电话号码的字母组合 (medium)

方法 1.dfs+回溯


  • 思路:深度优先遍历,遍历函数传入每一层形成的字符串和一个指向字符的位置指针,打给你指针的位置到达字符串的结尾时,将形成的字符串加入结果数组,递归的每一层遍历这一层的数字对应的字符,然后传入新的字符,指针向后移动一次,不断递归

  • 复杂度:时间复杂度O(3^m * 4^n),m,n 分别是三个字母和四个字母对应的数字个数。空间复杂度O(m+n),递归栈的深度,最大为m+n


js:


//输入:digits = "23"//输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]var letterCombinations = (digits) => {    if (digits.length == 0) return [];    const res = [];    const map = {//建立电话号码和字母的映射关系        2: "abc",        3: "def",        4: "ghi",        5: "jkl",        6: "mno",        7: "pqrs",        8: "tuv",        9: "wxyz",    };
const dfs = (curStr, i) => {//curStr是递归每一层的字符串,i是扫描的指针 if (i > digits.length - 1) {//边界条件,递归的出口 res.push(curStr); //其中一个分支的解推入res return; //结束递归分支,进入另一个分支 } const letters = map[digits[i]]; //取出数字对应的字母 for (const l of letters) { //进入不同字母的分支 dfs(curStr + l, i + 1); //参数传入新的字符串,i右移,继续递归 } }; dfs("", 0); // 递归入口,传入空字符串,i初始为0的位置 return res;};
复制代码


java:


class Solution {    String[] map = { " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return new ArrayList<>(); } dfs(digits, new StringBuilder(), 0); return res; }
List<String> res = new ArrayList<>();
void dfs(String digits, StringBuilder curStr, int index) { if (index == digits.length()) { res.add(curStr.toString()); return; } char c = digits.charAt(index); int pos = c - '0'; String map_string = map[pos]; for (int i = 0; i < map_string.length(); i++) { curStr.append(map_string.charAt(i)); dfs(digits, curStr, index + 1); curStr.deleteCharAt(curStr.length() - 1); } }}
复制代码
方法 2.bfs


  • 思路:用队列广度优先遍历,先循环数字数组,然后取出对应的字母,与当前层的字符串组成新的字符串加入队列,遍历完成之后,队列的最后一层就是解。

  • 复杂度:时间复杂度O(3^m * 4^n),m,n 分别是三个字符和四个字母对应的数组个数。空间复杂度O(3^m * 4^n),队列的空间大小,最大为3^m * 4^n


js:


var letterCombinations = (digits) => {    if (digits.length == 0) return [];    const map = {        2: "abc",        3: "def",        4: "ghi",        5: "jkl",        6: "mno",        7: "pqrs",        8: "tuv",        9: "wxyz",    };
const queue = []; queue.push(""); for (let i = 0; i < digits.length; i++) {//循环数字的每个字符 const levelSize = queue.length; //当前层的节点个数 for (let j = 0; j < levelSize; j++) { const curStr = queue.shift(); //当前层的字符串 const letters = map[digits[i]];//获取数字对应的字母字符 for (const l of letters) { queue.push(curStr + l); //新生成的字符串入列 } } } return queue; //最后一层生成的字符串就是解};
复制代码


java:


class Solution {    public List<String> letterCombinations(String digits) {        if (digits == null || digits.length() == 0) {            return new ArrayList<String>();        }        String[] map = { " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };        List<String> res = new ArrayList<>();
res.add(""); for (int i = 0; i < digits.length(); i++) { String letters = map[digits.charAt(i) - '0']; int levelSize = res.size(); for (int j = 0; j < levelSize; j++) { String tmp = res.remove(0); for (int k = 0; k < letters.length(); k++) { res.add(tmp + letters.charAt(k)); } } } return res; }}
复制代码

78. 子集 (medium)


  • 思路:回溯函数传入字符开始的位置 startIndex,不断递归,每一层 startIndex 加 1,当一个分支结束之后在,开始回溯,进入另一个分支。

  • 复杂度:时间复杂度O(n*2^n),如图递归出来的状态是2^n个状态,每个状态构建 path 数组复杂度是O(n)。空间复杂度O(n),也就是递归栈的空间


js:


//例子:nums = [1,2,3]var subsets = function(nums) {    let result = []//存放结果    let path = []//存放一个分支的结果    function backtracking(startIndex) {//startIndex字符递归开始的位置        result.push(path.slice())//path.slice()断开和path的引用关系        for(let i = startIndex; i < nums.length; i++) {//从startIndex开始递归            path.push(nums[i])//当前字符推入path            backtracking(i + 1)//startIndex向后移动一个位置 继续递归            path.pop()//回溯状态        }    }    backtracking(0)    return result};
复制代码


java:


class Solution {    List<List<Integer>> result = new ArrayList<>();    LinkedList<Integer> path = new LinkedList<>();    public List<List<Integer>> subsets(int[] nums) {        if (nums.length == 0){            result.add(new ArrayList<>());            return result;        }        backtracking(nums, 0);        return result;    }
private void backtracking(int[] nums, int startIndex){ result.add(new ArrayList<>(path)); if (startIndex >= nums.length){ return; } for (int i = startIndex; i < nums.length; i++){ path.add(nums[i]); backtracking(nums, i + 1); path.removeLast(); } }}
复制代码

473. 火柴拼正方形 (medium)


  • 思路 :排序 nums 数组,减少回溯的次数。不断尝试将 nums 中的元素放入 4 个桶中,如果都能放的下,则能拼成正方形


js:


//例子:[1,2,2,2,1]var makesquare = function (nums) {    function backtrack(i, nums, edge, bucket) {        if (i >= nums.length) {//递归结束条件            return true;        }        for (let j = 0; j < 4; j++) {//循环4个桶            if (bucket[j] + nums[i] > edge) {//这个桶装不下 继续找下一个桶                continue;            }            bucket[j] += nums[i];//将当前元素加入桶中            if (backtrack(i + 1, nums, edge, bucket)) {//索引i加1 继续递归下一个nums中的元素                return true;//下一个元素能放进桶中            }            bucket[j] -= nums[i];//回溯状态        }        return false;//循环结束都没放进合适的桶 那不能构成正方形    }
if (nums.length < 4) {//nums长度小于4 直接不能构成正方形 return false; } let sum = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i]; } if (sum % 4) {//nums的和不能整除4 不能构成正方行 return false; } nums.sort((a, b) => b - a);//排序nums let bucket = Array(4).fill(0);//准备4个桶 return backtrack(0, nums, sum / 4, bucket);//传入nums元素的索引i,nums,一个边长,和桶bucket};
复制代码


用户头像

全栈潇晨

关注

还未添加个人签名 2021.02.17 加入

还未添加个人简介

评论

发布
暂无评论
大厂算法面试之leetcode精讲11剪枝&回溯