1.3. 回溯算法
-
回溯問題：決策樹 的遍歷過程挂洛，純暴力枚舉
- 路徑：已做出 的選擇
- 選擇列表：當(dāng)前能做 的選擇
- 結(jié)束條件：無法再做 選擇的條件
result = []
def backtrack( 路徑, 選擇列表 ):
if 滿足結(jié)束條件:
result.add( 路徑 )
return
for 選擇 in 選擇列表:
做選擇
backtrack( 路徑, 選擇列表 )
撤銷選擇
1.3.1. 全排列問題
n 個不重復(fù)的數(shù)的全排列共有 n! 個
- 路徑：[2]
- 選擇列表：[1, 3]
- 結(jié)束條件：選擇列表為空
全排列問題的回溯樹
- 時間復(fù)雜度 O(n * n!)，遞歸總次數(shù) * 每次遞歸中的操作次數(shù)
- 空間復(fù)雜度 O(n)，遞歸深度 * 每次遞歸的輔助空間
// 全排列鏈表
List<List<Integer>> res = new LinkedList<>();
/* 主函數(shù)宪祥，輸入一組不重復(fù)的數(shù)字，返回它們的全排列 */
List<List<Integer>> permute(int[] nums) {
// 記錄 “路徑”
LinkedList<Interger> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路徑：記錄在 track 中
// 選擇列表：nums 中不存在于 track 中的元素
// 結(jié)束條件：nums 中元素全部都在 track 中
void backtrack(int[] nums, LinkedList<Integer> track) {
// 觸發(fā)結(jié)束條件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的選擇
if (track.contains(nums[i])) {
continue;
}
// 做選擇
track.add(nums[i]);
// 進入下一層決策樹
backtrack(nums, track);
// 撤銷選擇
track.removeLast();
}
}
1.3.2. N 皇后問題
N × N 的棋盤仗处，放置 N 個皇后胳喷，使它們不能從八個方向互相攻擊
List<List<String>> res = new LinkedList<>();
/* 輸入棋盤邊長 n，返回所有合法的放置方法*/
List<List<String>> solveNQueens(int n) {
// '.' 表示空席吴，'Q' 表示皇后赌结，初始化空棋盤
List<String> board = new LinkedList<>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
board.add(new String(row));
}
backtrack(board, 0);
return res;
}
// 路徑：board 中小于 row 的行已經(jīng)成功放置皇后
// 選擇列表：第 row 行所有列都是放置皇后的選擇
// 結(jié)束條件：row 大于 board 的最后一行捞蛋，說明棋盤已滿
void backtrack(List<String> board, int row) {
// 觸發(fā)結(jié)束條件
if (board.size() == row) {
res.add(new LinkedList(board));
return;
}
int n = board.get(row).length();
for (int col = 0; col < n; col++) {
// 排除不合法選擇
if (!isValid(board, row, col)) {
continue;
}
// 做選擇
char[] arr = new char[n];
Arrays.fill(arr, '.');
arr[col] = 'Q';
board.set(row, new String(arr));
// 進入下一行決策
backtrack(board, row + 1);
// 撤銷選擇
arr[col] = '.';
board.set(row, new String(arr));
}
}
/* 檢查 board.get(row).charAt(col) 處是否可以放置皇后 */
boolean isValid(List<String> board, int row, int col) {
int n = board.get(row).length();
// 檢查列中是否有皇后沖突
for (int i = 0; i < row; i++) {
if (board.get(i).charAt(col) == 'Q') {
return false;
}
}
// 檢查左上方是否有皇后沖突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
// 檢查右上方是否有皇后沖突
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
return true;
}
- 注意此算法每次遞歸都需要開辟新數(shù)組，導(dǎo)致空間復(fù)雜度大柬姚，原因是 String 無法直接修改元素
1.4. BFS 算法
-
DFS 算法：深度優(yōu)先
- 利用 遞歸拟杉，遍歷決策樹
- 全排列 / 可行路徑
- 時間復(fù)雜度大
-
BFS 算法：廣度優(yōu)先
- 利用 隊列，圖的起點到終點
- 最短路徑
- 空間復(fù)雜度大
- 核心數(shù)據(jù)結(jié)構(gòu)：Queue
- 避免走回頭路（圖）：visited
// 計算從起點 start 到終點 target 的最短距離
int BFS( Node start, Node target) {
Queue<Node> q; // 核心數(shù)據(jù)結(jié)構(gòu)
Set<Node> visited; // 避免走回頭路
q.offer(start); // 將起點加入隊列
visited.add(start);
int step = 0; // 記錄步數(shù)
while (q not empty) {
int sz = q.size();
/* 將當(dāng)前隊列中的所有節(jié)點向四周擴散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 判斷是否到達終點 */
if (cur is target) {
return step;
}
/* 若未訪問過量承，則將 cur 的相鄰節(jié)點加入隊列 */
for (Node x : cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
/* 更新步數(shù) */
step++;
}
}
1.4.1. 二叉樹的最小高度
輸入一棵二叉樹搬设，計算從根節(jié)點到葉子節(jié)點的最短距離
葉子節(jié)點：左右子節(jié)點都為空
if (cur.left == null && cur.right == null)
int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
/* 將當(dāng)前隊列中的所有節(jié)點向四周擴散 */
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
/* 判斷是否到達終點，即葉子節(jié)點 */
if (cur.left == null && cur.right == null) {
return depth;
}
/* 將 cur 的子節(jié)點加入隊列 */
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
/* 更新高度 */
depth++;
}
return depth;
}
1.4.2. 解開密碼鎖的最小次數(shù)
帶有四個圓形撥輪的轉(zhuǎn)盤鎖撕捍，每次旋轉(zhuǎn)只能將一個撥輪旋轉(zhuǎn)一次拿穴，計算從初始狀態(tài) "0000" 撥出 target 的最少次數(shù)，同時避免撥出 deadends
int openLock(String[] deadends, String[] target) {
// 記錄需要避免的死亡密碼
Set<String> deads = new HashSet<>();
for (String s : deadends) {
deads.add(s);
}
// 記錄已經(jīng)窮舉過的密碼忧风，避免走回頭路
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
// 從初始狀態(tài)開始啟動 BFS 算法
int step = 0;
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
int sz = q.size();
// 將當(dāng)前隊列中的所有節(jié)點向周圍擴散
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// 判斷密碼是否是死亡密碼
if (deads.contains(cur)) {
continue;
}
// 判斷密碼是否到達終點
if (cur.equals(target)) {
return step;
}
// 將四個撥輪未遍歷的相鄰節(jié)點加入隊列
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
q.offer(up);
visited.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
q.offer(down);
visited.add(down);
}
}
}
// 增加步數(shù)
step++;
}
// 找不到 target 密碼默色，返回 -1
return -1;
}
// 將 s[j] 向上撥動一次
String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9') {
ch[j] = '0';
}
else {
ch[j] += 1;
}
return new String(ch);
}
// 將 s[j] 向下?lián)軇右淮?String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0') {
ch[j] = '9';
}
else {
ch[j] -= 1;
}
return new String(ch);
}
注意：遍歷與否在加入相鄰節(jié)點時檢查
- 時間復(fù)雜度 O(N * AN)，遍歷全部密碼需要 O(AN)狮腿，每個密碼撥動每一位需要 O(N)
- 空間復(fù)雜度 O(AN)
- A 為數(shù)字個數(shù)腿宰，N 為密碼位數(shù)
