前端Jeek

DFS-回溯算法

算法

回溯算法的框架：

result = []

def backtracking(路径, 层级):
    if 满足结束条件:
        result.add(路径)
        return
    
    // 决策树
    for 选择 in 选择列表:
        做选择
        backtracking(路径, 下一层)
        撤销选择
1
2
3
4
5
6
7
8
9
10
11
12

类比多叉树的遍历框架:

var traverse = function(root) {
    for (var i = 0; i < root.children.length; i++) {
        // 前序位置
        traverse(root.children[i]);
        // 后序位置
    }
}
1
2
3
4
5
6
7

🌙 1. Flood Fill算法 (opens new window)

leetcode-颜色填充 (opens new window)

颜色填充
  输入：
  image = [
            [1, 1, 1],
            [1, 1, 0],
            [1, 0, 1]
          ]
  已知： sr = 1, sc = 1, newColor = 2
  输出：
          [
            [2, 2, 2],
            [2, 2, 0],
            [2, 0, 1]
          ]     

  解析：
    坐标（sr,sc） = (1,1),在图像的正中间，与其相连的所有符合条件的像素点的颜色都被更改为2。
    注意，右下角的像素没有被更改为2，因为它不是上下左右四个方向与初始点相连的像素点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, newColor) {
    if (!image) return;
    let originColor = image[sr][sc];
    fill(image, sr, sc, originColor, newColor);
    return image;
  };

function fill(image, sr, sc, originColor, newColor) {
  // 出界
  if (!isValid(image, sr, sc)) return;
  // 碰壁
  if (image[sr][sc] !== originColor) return;
  // 已访问过
  if (image[sr][sc] === -1) return;
  // 打标记
  image[sr][sc] = -1;
  fill(image, sr - 1, sc, originColor, newColor);
  fill(image, sr + 1, sc, originColor, newColor);
  fill(image, sr, sc - 1, originColor, newColor);
  fill(image, sr, sc + 1, originColor, newColor);
  // 回溯
  image[sr][sc] = newColor;
}

function isValid(image, sr, sc) {
  return sr >= 0 && sr < image.length && sc >= 0 && sc < image[0].length;
}
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

🌙 2.组合 (opens new window)

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

 

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
示例 2：

输入：n = 1, k = 1
输出：[[1]]
 

提示：

1 <= n <= 20
1 <= k <= 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
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
    let res = []
    if (n < 1) return res
    let path = []
    backtracking(res, path,n, k, 1)
    return res
  }

function backtracking(res, path, n, k, start) {
  // terminal
  if (path.length === k) {
    res.push([...path])
    return
  }

  // sub problem
  for (let i = start; i <= n; i++) {
    // record
    path.push(i)
    // recursion
    backtracking(res, path, n, k, i+1)
    // revert
    path.pop()
  }
}
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

🌙 3.全排列 (opens new window)

给定一个**不含重复**数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]
 

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    let res = []
    let path = []
    let used = new Set()

    backtracking(res, path, nums, used)

    return res
  };

function backtracking(res, path, nums, used) {
  if (path.length === nums.length) {
    res.push([...path])
    return
  }

  for (let i = 0; i < nums.length; i++) {
    // 此处可以使用path.includes判断
    if (used.has(nums[i])) {
      continue
    }
    used.add(nums[i])
    path.push(nums[i])
    backtracking(res, path, nums, used)
    path.pop()
    used.delete(nums[i])
  }
}
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

🌙 4.全排列II (opens new window)

给定一个可**包含重复**数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    let res = []
    let path = []
    let used = new Set()

    backtracking(res, path, nums, used)

    return res.map(s => s.split(','))
  };

function backtracking(res, path, nums, used) {
  if (path.length === nums.length) {
    // 使用字符串拼接便于去重
    if (!res.includes(path.join(','))) {
      res.push(path.join(','))
    }
    return
  }

  for (let i = 0; i < nums.length; i++) {
    if (used.has(i)) {
      continue
    }
    used.add(i)
    path.push(nums[i])
    backtracking(res, path, nums, used)
    path.pop()
    used.delete(i)
  }
}
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

如果不使用字符串去重，可以先排序:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    let res = []
    let used = new Set()
    // 升序
    nums.sort((a, b) => a - b)

    backtracking(res, path, nums, used)

    return res
  };

function backtracking(res, path, nums, used) {
  if (path.length === nums.length) {
    res.push([...path])
    return
  }

  for (let i = 0; i < nums.length; i++) {
    // 以下两种写法都可以
    // 同层剪枝
    if (used.has(i) || i > 0 && nums[i] === nums[i - 1] && !used.has(i - 1)) {
      // 非同层剪枝
      // if (used.has(i) || i>0 && nums[i] === nums[i-1] && used.has(i - 1)) {
      continue
    }
    used.add(i)
    path.push(nums[i])
    backtracking(res, path, nums, used)
    path.pop()
    used.delete(i)
  }
}
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

🌙 5.子集 (opens new window)

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  let res = []
  let path = []
  backtracking(res, nums, path, 0)
  return res;
};

// 相当于遍历多叉树
function backtracking(res, nums, path, index) {
  // 前序遍历位置
  res.push([...path])

  // 遍历children
  for (let i = index; i < nums.length; i++) {
    path.push(nums[i])
    backtracking(res, nums, path, i + 1)
    path.pop()
  }
}
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

🌙 6.N皇后 (opens new window)

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

示例 2：
输入：n = 1
输出：[["Q"]]
 

提示：

1 <= n <= 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    // 保存结果
    let res = [];

    // 当前空棋盘
    let board = new Array(n).fill([]).map(() => new Array(n).fill('.'));

    backtracking(res, board, n, 0);

    return res;
  };

function backtracking(res, board, n, row) {
  if (row === n) {
    res.push(board.map(d => d.join('')))
  }

  for (let col = 0; col < n; col++) {
    // 判断是否可以放置Q
    if (!isValid(board, row, col, n)) {
      continue;
    }
    // 回溯
    board[row][col] = 'Q';
    backtracking(res, board, n, row + 1);
    board[row][col] = '.';
  }
}

function isValid(board, row, col, n) {
  // 判断列
  for (let i = 0; i < row; i++) {
    if (board[i][col] === 'Q') {
      return false;
    }
  }

  // 判断左上
  for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] === 'Q') {
      return false;
    }
  }

  // 判断右上
  for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
    if (board[i][j] === 'Q') {
      return false;
    }
  }

  return true;
}
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
56
57

🌙 7.括号生成 (opens new window)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 

提示：

1 <= n <= 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    let res = []
    let path = []

    generate(res, path, n, 0, 0)

    return res
  };

function generate(res, path, n, left, right) {
  if (right === n) {
    res.push(path.join(''))
    return
  }

  if (left < n) {
    path.push('(')
    generate(res, path, n, left + 1, right)
    path.pop()
  }

  if (right < left) {
    path.push(')')
    generate(res, path, n, left, right + 1)
    path.pop()
  }
}
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

优化一下：

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    let res = []

    generate(res, '', n, 0, 0)

    return res
  };

function generate(res, s, n, left, right) {
  if (s.length === n * 2) {
    res.push(s)
    return
  }

  // 必须先使用用左括号，才能保证有效
  // 左括号没用完
  if (left < n) {
    generate(res, s + '(', n, left + 1, right)
  }

  // 右括号还没用完
  if (right < left) {
    generate(res, s + ')', n, left, right + 1)
  }
}
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

🌙 8.电话号码的字母组合 (opens new window)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
1
2
3

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]
 

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    if (digits.length === 0) return []

    const arr = [
      '', // 0
      '', // 1
      'abc', // 2
      'def', // 3
      'ghi', // 4
      'jkl', // 5
      'mno', // 6
      'pqrs', // 7
      'tuv', // 8
      'wxyz' // 9
    ]
    const res = []
    const path = []
    const len = digits.length
    backtracking(digits, 0)

    function backtracking(str, s) {
      // terminal
      if (path.length === len) {
        res.push(path.join(''))
        return
      }

      const letters = arr[str[s]]
      // backtrack
      for (let i = 0; i < letters.length; i++) {
        path.push(letters[i])
        backtracking(str, s + 1)
        path.pop()
      }
    }
    
    return res
  };
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

递归-分治算法