分治、回溯的实现和特性

分治、回溯本质上就是一种特殊的递归,它是递归的一个细分类。

遇见题目要找重复性,重复性分为最近重复性和最优重复性。
最优重复性就是动态规划,最近重复性根据重复性如何构造,以及如何分解,就分为分治、回溯等各种办法。

分治 Divide & Conquer

分治针对递归状态树,可以将一个问题化解为多个子问题。

代码模板

function divide_conquer (problem, param1, params2, ... ){ // recursion terminator if (!problem) { process_result return }; // prepare data data = prepare_data(problem); subprobems = split_problem(problem, data); // conquer subproblems subresult1 = divide_conquer(subprobems[0], p1, ...); subresult2 = divide_conquer(subprobems[1], p1, ...); subresult3 = divide_conquer(subprobems[2], p1, ...); ... // process and generate the final result result = process_result(subresult1, subresult2, subresult3, ...); // revert the current level states }

回溯 Backtracking

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

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

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

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

相关题目

Pow(x, n) (Facebook 在半年内面试常考)

子集(Facebook、字节跳动、亚马逊在半年内面试中考过)

参考链接:

牛顿迭代法原理

牛顿迭代法代码

// Pow(x, n) // 思路1:暴力法,循环 n 次,O(n) // 思路2:分治 O(log n) // pow(x, n) // subproblem: subresult = pow(x, n / 2) // merge: // n % 2 == 1,result = subresult * subresult * x // else,subresult * subresult /** * @param {number} x * @param {number} n * @return {number} */ var myPow = function (x, n) { if (n === 0) return 1; if (n < 0) return 1 / myPow(x, -n); const mul = myPow(x * x, (n / 2) >> 0); return n % 2 ? x * mul : mul; }
// 子集 /** * @param {number[]} nums * @return {number[][]} */ var subsets = function(nums) { const ans = []; const backtrack = (path, l, start) => { if (path.length === l) { ans.push(path); return; } for (let i = start; i < nums.length; i++) { backtrack(path.concat(nums[i]), l, i + 1); } } for (let i = 0; i <= nums.length; i++) { backtrack([], i, 0); } return ans; }; /** * @param {number[]} nums * @return {number[][]} */ var subsets = function(nums) { const ans = []; if (!nums) return ans; const dfs = (nums, list, index) => { if (index === nums.length) { ans.push(list); return; } dfs(nums, list.slice(), index + 1); list.push(nums[index]); dfs(nums, list.slice(), index + 1); }; dfs(nums, [], 0); return ans; };

多数元素 (亚马逊、字节跳动、Facebook 在半年内面试中考过)

电话号码的字母组合(亚马逊在半年内面试常考)

// 多数元素 // 思路1: hashTable // 思路2: 排序取中间值 // 思路3:抵消(栈方法降维) // 思路4:分治 /** * 抵消(栈方法降维) * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { let x = 0, m = 0; for (let n of nums) { if(m === 0) x = n; m += x === n ? 1 : -1; } return x; }; /** * 分治 * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { return getMode(nums, 0, nums.length - 1); }; function getMode (nums, left, right) { if (left === right) return nums[left]; const mid = left + ((right - left) >> 1); const low = getMode(nums, left, mid), high = getMode(nums, mid + 1, right); if (low == high) return low; const lowCount = getCount(nums, low, left, right), highCount = getCount(nums, high, left, right); return lowCount > highCount ? low : high; } function getCount (nums, target, left, right) { let count = 0; for (let i = left; i <= right; i++) { if (nums[i] === target) count++; } return count; }
// 电话号码的字母组合 /** * dfs * @param {string} digits * @return {string[]} */ var letterCombinations = function(digits) { if (digits.length === 0) return []; const ans = []; const map = new Map([ ['2', 'abc'], ['3', 'def'], ['4', 'ghi'], ['5', 'jkl'], ['6', 'mno'], ['7', 'pqrs'], ['8', 'tuv'], ['9', 'wxyz'] ]); const dfs = (cur, i) => { if (i > digits.length - 1) { ans.push(cur); return; } const letters = map.get(digits[i]); for (const letter of letters) { dfs(cur + letter, i + 1); } } dfs('', 0); return ans; }; /** * bfs * @param {string} digits * @return {string[]} */ var letterCombinations = function(digits) { if (digits.length === 0) return []; const map = new Map([ ['2', 'abc'], ['3', 'def'], ['4', 'ghi'], ['5', 'jkl'], ['6', 'mno'], ['7', 'pqrs'], ['8', 'tuv'], ['9', 'wxyz'] ]); const queue = ['']; for (let i = 0; i < digits.length; i++) { let size = queue.length; for (let j = 0; j < size; j++) { const cur = queue.shift(); const letters = map.get(digits[i]); for (const l of letters) { queue.push(cur + l); } } } return queue; };

N 皇后(字节跳动、苹果、谷歌在半年内面试中考过)

二叉树的层次遍历

// N 皇后(困难) /** * @param {number} n * @return {string[][]} */ var solveNQueens = function (n) { function isValid(row, col, chessBoard, n) { for (let i = 0; i < row; i++) { if (chessBoard[i][col] === 'Q') { return false } } for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chessBoard[i][j] === 'Q') { return false } } for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chessBoard[i][j] === 'Q') { return false } } return true } function transformChessBoard(chessBoard) { let chessBoardBack = [] chessBoard.forEach(row => { let rowStr = '' row.forEach(value => { rowStr += value }) chessBoardBack.push(rowStr) }) return chessBoardBack } const result = []; function backtracing(row, chessBoard) { if (row === n) { result.push(transformChessBoard(chessBoard)) return } for (let col = 0; col < n; col++) { if (isValid(row, col, chessBoard, n)) { chessBoard[row][col] = 'Q' backtracing(row + 1, chessBoard) chessBoard[row][col] = '.' } } } const chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.')); backtracing(0, chessBoard); return result };
// 二叉树的层次遍历 /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { if (!root) return []; const ans = []; const queue = [root]; while (queue.length) { let len = queue.length; ans.push([]); while (len--) { const n = queue.shift(); ans[ans.length - 1].push(n.val); n.left && queue.push(n.left); n.right && queue.push(n.right); } } return ans; };