大廠算法面試之leetcode精講11剪枝&回溯
視頻講解（高效學(xué)習(xí)）:點擊學(xué)習(xí)
目錄：
剪枝
排除那些不符合條件的分支塌鸯。提高程序的運行效率蓖议。
ds_2
回溯：
一層層遞歸，嘗試搜素答案股毫，
- 找到答案：返回結(jié)果，嘗試其他的分支
- 找不到答案：返回上一層，嘗試其他分支
回溯模版：
result = [];
function backtrack (path, list) {
if (滿足條件) {
result.push(path);
return
}
for () {
// 單層邏輯
backtrack (path, list)
// 撤銷選擇 重置狀態(tài)
}
}
回溯四部曲：
- 回溯參數(shù)
- 終止條件
- 單層遞歸邏輯
- 選擇其他分支（撤銷選擇 重置狀態(tài)）
22. 括號生成 （medium）
ds_52
方法1:暴力
復(fù)雜度分析：時間復(fù)雜度O(2^2n*n)谚鄙，字符串的長度為2n稠曼，每個位置有兩種選擇，選擇左或者右括號磷脯，驗證字符串是否有效復(fù)雜度O(n)蛾找，剪枝之后會優(yōu)化，最壞的情況是O(2^2n*n)赵誓〈蛎空間復(fù)雜度O(n),遞歸次數(shù)最多2n
方法2.遞歸dfs
- 思路：采用遞歸，終止條件是字符串的長度等于
2n俩功，遞歸函數(shù)傳入構(gòu)建的字符串幻枉，左右括號剩余多少，每個位置有兩種選擇诡蜓，選擇左或者右括號熬甫，這里可以進行剪枝優(yōu)化，只有右括號的保有數(shù)量大于左括號的保有數(shù)量蔓罚，才能選右括號椿肩，否則肯定不能構(gòu)成有效括號
Js:
const generateParenthesis = (n) => {
const res = []; // 輸出的結(jié)果數(shù)組
const generate = (str, left, right) => {
if (str.length == 2 * n) { // 字符串構(gòu)建完成
res.push(str); // 將字符串加入res
return; // 結(jié)束當(dāng)前遞歸（結(jié)束當(dāng)前搜索分支）
}
if (left > 0) { // 只要左括號有剩，可以選它豺谈，繼續(xù)遞歸做選擇
generate(str + '(', left - 1, right);
}
if (right > left) { // 右括號的保有數(shù)量大于左括號的保有數(shù)量郑象，才能選右括號
generate(str + ')', left, right - 1);
}
};
generate('', n, n); // 遞歸的入口，初始字符串是空字符串茬末，初始括號數(shù)量都是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.回溯
- 思路：當(dāng)左括號剩下的多厂榛，說明字符串中的左括號數(shù)量少于右括號，不合法团南，對字符串嘗試添加左括號噪沙，然后回溯，嘗試添加右括號吐根，然后嘗試回溯
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) {
// 數(shù)量小于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分別記錄列和兩個對角線可以攻擊到的坐標(biāo)爆哑，嘗試在每個空位放置皇后淮摔，放置之后更新三個可以攻擊到的set坐標(biāo)，然后繼續(xù)下一層遍歷占调，完成下一層之后，嘗試回溯當(dāng)前層，也就是撤銷當(dāng)前層放置的皇后泛源，同時撤銷三個可以攻擊到的set坐標(biāo)，不斷回溯忿危，直到遍歷完成达箍，找到所有可能的解。
- 復(fù)雜度分析：時間復(fù)雜度：
O(N!)铺厨，其中 N 是皇后數(shù)量缎玫，由于每個皇后必須位于不同列，因此已經(jīng)放置的皇后所在的列不能放置別的皇后解滓。第一個皇后有 N 列可以選擇赃磨，第二個皇后最多有 N-1列可以選擇...》サ伲空間復(fù)雜度：O(N)煞躬，其中 N 是皇后數(shù)量，空間復(fù)雜度主要取決于遞歸調(diào)用層數(shù)逸邦、記錄每行放置的皇后列下標(biāo)的數(shù)組以及三個集合恩沛，遞歸調(diào)用層數(shù)不會超過 N，數(shù)組的長度為 N缕减，每個集合的元素個數(shù)都不會超過 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(); // 列集，記錄出現(xiàn)過皇后的列
const diag1 = new Set(); // 正對角線集
const diag2 = new Set(); // 反對角線集
const res = [];//結(jié)果數(shù)組
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++) {
// 如果當(dāng)前點的所在的列桥狡，所在的對角線都沒有皇后搅裙，即可選擇，否則裹芝，跳過
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); // 對應(yīng)的記錄也刪一下
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.位運算
ds_54
js:
var totalNQueens = function (n) {
if (n < 1) return
let count = 0;
dfs(n, 0, 0, 0, 0)
return count
//n:皇后的數(shù)量
//row：當(dāng)前行
//cols：放置皇后的位置
//diag1：可以攻擊的左傾斜對角線
//diag2：可以攻擊的右傾斜對角線
function dfs(n, row, cols, diag1, diag2) {
if (row >= n) {//遞歸終止 統(tǒng)計解法
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. 有效的數(shù)獨 (medium)
方法1：回溯
ds_55
- 思路：準備行、列怜械、3 * 3小方塊颅和，三個哈希表或者set或者9 * 9的二維數(shù)組傅事，都可以，只要能判重復(fù)即可峡扩，從上到下蹭越，從左到右循環(huán)，依次檢查行教届、列响鹃、3 * 3小方塊中是否有重復(fù)的數(shù)字，如果有則返回false巍佑，然后更新哈希表或者set茴迁。
- 復(fù)雜度分析：時間復(fù)雜度：
O(1)，數(shù)獨共有 81 個單元格萤衰，每個單元格遍歷一次即可〔卵空間復(fù)雜度：O(1)脆栋，數(shù)獨的大小固定，因此哈希表的空間也是固定的洒擦。
Js:
var isValidSudoku = function(board) {
// 方向判重
let rows = {};//行
let columns = {};//列
let boxes = {};//3*3小方塊
// 遍歷數(shù)獨
for(let i = 0;i < 9;i++){
for(let j = 0;j < 9;j++){
let num = board[i][j];
if(num != '.'){//遇到有效的數(shù)字
let boxIndex = parseInt((i/3)) * 3 + parseInt(j/3);// 子數(shù)獨序號
if(rows[i+'-'+num] || columns[j+'-'+num] || boxes[boxIndex+'-'+num]){//重復(fù)檢測
return false;
}
// 方向 + 數(shù)字 組成唯一鍵值椿争，若出現(xiàn)第二次，即為重復(fù)
// 更新三個對象
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];//用數(shù)組同樣實現(xiàn)
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. 解數(shù)獨(hard)
- 思路：循環(huán)行和列熟嫩，嘗試在每個位置放置1-9秦踪，并檢驗合法性，包括行掸茅、列椅邓、3 * 3方塊的合法性，如果合法繼續(xù)循環(huán)昧狮，直到找到一個合法的解景馁，如果不合法，則回溯狀態(tài)逗鸣，并繼續(xù)嘗試其他的可能性
- 復(fù)雜度分析：同36題
js:
var solveSudoku = function(board) {
function isValid(row, col, val, board) {
let len = board.length
// 行中的數(shù)字不能重復(fù)
for(let i = 0; i < len; i++) {
if(board[row][i] === val) {
return false
}
}
// 列中的數(shù)字不能重復(fù)
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
//方塊中的數(shù)字不能重復(fù)
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() {//回溯函數(shù)
for(let i = 0; i < board.length; i++) {
for(let j = 0; j < board[0].length; j++) {//循環(huán)行和列
if(board[i][j] !== '.') continue
for(let val = 1; val <= 9; val++) {//嘗試在當(dāng)前單元格放置1-9
if(isValid(i, j, `${val}`, board)) {//判斷放置數(shù)字的合法性
board[i][j] = `${val}`//放置數(shù)字
if (backTracking()) {//合法返回ture
return true
}
board[i][j] = `.`//不合法回溯狀態(tài)
}
}
return false//1-9的數(shù)字都不合法合住，返回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++){ //嘗試在當(dāng)前位置放置1-9
if (isValid(i, j, k, board)){
board[i][j] = k;//放置數(shù)字
if (backTracking(board)){ //合法返回ture
return true;
}
board[i][j] = '.';
}
}
return false;//1-9的數(shù)字都不合法，返回false
}
}
return true;//全部可能性都嘗試完成 返回true 說明有解
}
private boolean isValid(int row, int col, char val, char[][] board){
// 同行是否重復(fù)
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
// 同列是否重復(fù)
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
// 小方塊中的元素是否重復(fù)
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）
ds_83
-
思路：從上到下撒璧，左到右遍歷網(wǎng)格透葛，每個坐標(biāo)遞歸調(diào)用
check(i, j, k)函數(shù)，i,j表示網(wǎng)格坐標(biāo)卿樱，k表示word的第k個字符僚害，如果能搜索到第k個字符返回true，否則返回false殿如，check函數(shù)的終止條件有2種情況- 如果i贡珊，j位置的字符和字符串位置k的字符不相等最爬，則這條搜索路徑搜索失敗 返回false
- 如果搜索到了字符串的結(jié)尾，則找到了網(wǎng)格中的一條路徑门岔，這條路徑上的字符正好可以組成字符串s
兩種情況都不滿足則把當(dāng)前網(wǎng)格節(jié)點加入
visited數(shù)組爱致，visited表示節(jié)點已經(jīng)訪問過了，然后順著當(dāng)前網(wǎng)格坐標(biāo)的四個方向繼續(xù)嘗試寒随，如果沒找到k開始的子串糠悯，則回溯狀態(tài)visited[i] [j] = false，繼續(xù)后面的嘗試妻往。 復(fù)雜度分析：時間復(fù)雜度
O(MN?3^L)互艾，M,N 為網(wǎng)格的長度與寬度，L 為字符串 word 的長度讯泣，第一次調(diào)用check函數(shù)的時候纫普，進行4個方向的檢查，其余坐標(biāo)的節(jié)點都是3個方向檢查好渠，走過來的分支不會反方向回去昨稼，所以check函數(shù)的時間復(fù)雜度是3^L，而網(wǎng)格有M*N個坐標(biāo)拳锚，且存在剪枝假栓，所以最壞的情況下時間復(fù)雜度是O(MN?3^L)』舨簦空間復(fù)雜度是O(MN)匾荆，visited數(shù)組空間是O(MN)，check遞歸棧的最大深度在最壞的情況下是O(MN)
方法1:回溯
Js:
var exist = function(board, word) {
const h = board.length, w = board[0].length;//網(wǎng)格的長和寬
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];//方向數(shù)組
const visited = new Array(h);//標(biāo)記是否訪問過的數(shù)組
for (let i = 0; i < visited.length; ++i) {//初始化visited數(shù)組
visited[i] = new Array(w).fill(false);
}
const check = (i, j, s, k) => {//檢查從網(wǎng)格i杆烁，j出發(fā)是否能搜索到0-k的字符組成的子串
//如果i牙丽，j位置的字符和第k個的字符不相等，則這條搜索路徑搜索失敗 返回false
if (board[i][j] != s.charAt(k)) {
return false;
//如果搜索到了字符串的結(jié)尾连躏，則找到了網(wǎng)格中的一條路徑剩岳，這條路徑上的字符正好可以組成字符串s
} else if (k == s.length - 1) {
return true;
}
visited[i][j] = true;//標(biāo)記i，j被訪問過了
let result = false;
for (const [dx, dy] of directions) {//向i入热，j的四個方向繼續(xù)嘗試尋找
let newi = i + dx, newj = j + dy;
if (newi >= 0 && newi < h && newj >= 0 && newj < w) {//新的坐標(biāo)位置合法檢查
if (!visited[newi][newj]) {//新的坐標(biāo)不能存在于visited中拍棕，也就是不能是訪問過的
const flag = check(newi, newj, s, k + 1);//繼續(xù)檢查新的坐標(biāo)
if (flag) {//如果在網(wǎng)格中找到了字符串 則跳過循環(huán)
result = true;
break;
}
}
}
}
visited[i][j] = false;//回溯狀態(tài)
return result;//返回結(jié)果
}
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）
ds_131
- 思路：準備path數(shù)組，存放每一個回溯遞歸的分支中的數(shù)字排列勺良，調(diào)用回溯函數(shù) 傳入nums绰播，nums長度，used數(shù)組尚困，used表示已經(jīng)使用的數(shù)字蠢箩，回溯函數(shù)中循環(huán)nums中的數(shù)，每層循環(huán)將nums中的元素加入path中，然后遞歸調(diào)用回溯函數(shù)谬泌，調(diào)用完成之后滔韵，回溯之前的狀態(tài)，當(dāng)path數(shù)組的長度和nums的長度相同就找到了一種排列掌实。
- 復(fù)雜度：時間復(fù)雜度
O(n*n!)陪蜻。空間復(fù)雜度O(n)贱鼻，遞歸棧深度
js：
var permute = function(nums) {
const res = [], path = [];
backtracking(nums, nums.length, []);//調(diào)用回溯函數(shù) 傳入nums宴卖，nums長度，used數(shù)組
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;//已經(jīng)使用過了就跳過本輪循環(huán)
path.push(n[i]);
used[i] = true;
backtracking(n, k, used);//遞歸
path.pop();//回溯 將push進的元素pop出來 然后標(biāo)記成未使用 繼續(xù)其他分支
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)
ds_132
- 思路：回溯函數(shù)傳入n邻悬，k和選擇的元素位置startIndex症昏，在每層遞歸中，從startIndex開始循環(huán)到
n - (k - path.length) + 1的位置父丰，將這些數(shù)加入path肝谭，然后startIndex加1，繼續(xù)遞歸函數(shù)進入下一個分支蛾扇，完成調(diào)用之后回溯狀態(tài)分苇，當(dāng)path的長度等于k的時候終止這層分支，加入結(jié)果中屁桑。 - 復(fù)雜度：時間復(fù)雜度：
O(C(n, k) * k)，枚舉結(jié)果總數(shù)為C(n, k)栏赴，每次得到一個結(jié)果需要O(k)時間蘑斧。空間復(fù)雜度：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(); //回溯狀態(tài)
}
};
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+回溯
ds_133
- 思路：深度優(yōu)先遍歷，遍歷函數(shù)傳入每一層形成的字符串和一個指向字符的位置指針花颗，打給你指針的位置到達字符串的結(jié)尾時捕传，將形成的字符串加入結(jié)果數(shù)組，遞歸的每一層遍歷這一層的數(shù)字對應(yīng)的字符扩劝，然后傳入新的字符庸论，指針向后移動一次，不斷遞歸
- 復(fù)雜度：時間復(fù)雜度
O(3^m * 4^n)棒呛，m聂示，n分別是三個字母和四個字母對應(yīng)的數(shù)字個數(shù)〈孛耄空間復(fù)雜度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 = {//建立電話號碼和字母的映射關(guān)系
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; //結(jié)束遞歸分支锋边，進入另一個分支
}
const letters = map[digits[i]]; //取出數(shù)字對應(yīng)的字母
for (const l of letters) {
//進入不同字母的分支
dfs(curStr + l, i + 1); //參數(shù)傳入新的字符串，i右移编曼，繼續(xù)遞歸
}
};
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
ds_134
- 思路：用隊列廣度優(yōu)先遍歷灵巧，先循環(huán)數(shù)字數(shù)組搀矫，然后取出對應(yīng)的字母，與當(dāng)前層的字符串組成新的字符串加入隊列刻肄，遍歷完成之后瓤球，隊列的最后一層就是解。
- 復(fù)雜度：時間復(fù)雜度
O(3^m * 4^n)敏弃，m卦羡，n分別是三個字符和四個字母對應(yīng)的數(shù)組個數(shù)÷蟮剑空間復(fù)雜度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++) {//循環(huán)數(shù)字的每個字符
const levelSize = queue.length; //當(dāng)前層的節(jié)點個數(shù)
for (let j = 0; j < levelSize; j++) {
const curStr = queue.shift(); //當(dāng)前層的字符串
const letters = map[digits[i]];//獲取數(shù)字對應(yīng)的字母字符
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)
ds_146
- 思路：回溯函數(shù)傳入字符開始的位置startIndex瓶颠，不斷遞歸拟赊，每一層startIndex加1，當(dāng)一個分支結(jié)束之后在粹淋，開始回溯吸祟，進入另一個分支。
- 復(fù)雜度：時間復(fù)雜度
O(n*2^n)桃移，如圖遞歸出來的狀態(tài)是2^n個狀態(tài)屋匕，每個狀態(tài)構(gòu)建path數(shù)組復(fù)雜度是O(n)〗杞埽空間復(fù)雜度O(n)过吻，也就是遞歸棧的空間
js：
//例子：nums = [1,2,3]
var subsets = function(nums) {
let result = []//存放結(jié)果
let path = []//存放一個分支的結(jié)果
function backtracking(startIndex) {//startIndex字符遞歸開始的位置
result.push(path.slice())//path.slice()斷開和path的引用關(guān)系
for(let i = startIndex; i < nums.length; i++) {//從startIndex開始遞歸
path.push(nums[i])//當(dāng)前字符推入path
backtracking(i + 1)//startIndex向后移動一個位置 繼續(xù)遞歸
path.pop()//回溯狀態(tài)
}
}
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)
ds_164
- 思路 ：排序nums數(shù)組，減少回溯的次數(shù)蔗衡。不斷嘗試將nums中的元素放入4個桶中纤虽，如果都能放的下，則能拼成正方形
js：
//例子：[1,2,2,2,1]
var makesquare = function (nums) {
function backtrack(i, nums, edge, bucket) {
if (i >= nums.length) {//遞歸結(jié)束條件
return true;
}
for (let j = 0; j < 4; j++) {//循環(huán)4個桶
if (bucket[j] + nums[i] > edge) {//這個桶裝不下 繼續(xù)找下一個桶
continue;
}
bucket[j] += nums[i];//將當(dāng)前元素加入桶中
if (backtrack(i + 1, nums, edge, bucket)) {//索引i加1 繼續(xù)遞歸下一個nums中的元素
return true;//下一個元素能放進桶中
}
bucket[j] -= nums[i];//回溯狀態(tài)
}
return false;//循環(huán)結(jié)束都沒放進合適的桶 那不能構(gòu)成正方形
}
if (nums.length < 4) {//nums長度小于4 直接不能構(gòu)成正方形
return false;
}
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 4) {//nums的和不能整除4 不能構(gòu)成正方行
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
};
