leetcode華為面試算法題-51. N 皇後

#頭條創作挑戰賽#

N皇後問題一直是大廠面試的常見算法問題，也是在學習回溯算法時的一個經典案例問題。這裡和全排列問題差不多，都是不斷的選擇然後撤銷選擇，當滿足結束條件，記錄選擇的路徑。本文主要寫的就是回溯算法對N皇後問題的解決

本質上回溯算法是一個暴力算法，複雜度都比較高。不像動态規劃存在“重疊子問題”，然後通過DP數組或者存儲狀态的手段，來進行“剪枝”操作，提高執行效率。回溯算法一般用于求解可以窮舉的，結果是有多少種的這類問題；動态規劃常用于求解最值的問題。

class Solution {

    List<List<String>> res = new ArrayList<>();

    /* 輸入棋盤的邊長n，傳回所有合法的放置 */
    public List<List<String>> solveNQueens(int n) {
        // "." 表示空，"Q"表示皇後，初始化棋盤
        char[][] board = new char[n][n];
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        backtrack(board, 0);
        return res;
    }

    public void backtrack(char[][] board, int row) {
        // 每一行都成功放置了皇後，記錄結果
        if (row == board.length) {
            res.add(charToList(board));  
            return;
        }

        int n = board[row].length;
        // 在目前行的每一列都可能放置皇後
        for (int col = 0; col < n; col++) {
            // 排除可以互相攻擊的格子
            if (!isValid(board, row, col)) {
                continue;
            }
            // 做選擇
            board[row][col] = 'Q';
            // 進入下一行放皇後
            backtrack(board, row + 1);
            // 撤銷選擇
            board[row][col] = '.';
        }
    }

    /* 判斷是否可以在 board[row][col] 放置皇後 */
    public boolean isValid(char[][] board, int row, int col) {
        int n = board.length;
        // 檢查列是否有皇後沖突
        for (int i = 0; i < n; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // 檢查右上方是否有皇後沖突
        for (int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        // 檢查左上方是否有皇後沖突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    public List charToList(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] c : board) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}
           

本題是回溯算法的一個經典題目。本質上就是暴力窮舉的問題。

需要注意的是判斷目前皇後位置是否會被攻擊。如果使用的是二維數組來記錄的話，需要注意，正方向的斜着，行号加列号相等的在同一斜線，反方向斜着，行号減列号相等的在同一斜線，這個是判斷目前位置是否合法的一個比較簡單的方法。