本文主要是介绍leetcode:N-Queens II 【Java】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、问题描述
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
二、问题分析
参考问题leetcode:N-Queens 【Java】
三、算法代码
public class Solution {public int totalNQueens(int n) {int [] total = new int [] {0};if (n <= 0) return total[0];char[][] board = new char[n][n];for (char[] row : board) {Arrays.fill(row, '.');}boolean[] col_occupied = new boolean[n];placeQueen(total, board, col_occupied, 0, n);return total[0];}private void placeQueen(int [] total, char[][] board, boolean[] col_occupied, int rowNum, int n) {if (rowNum == n) {total[0]++;return;}for (int colNum = 0; colNum < n; colNum++) {if (isValid(board, col_occupied, rowNum, colNum, n)){board[rowNum][colNum] = 'Q';col_occupied[colNum] = true;placeQueen(total, board, col_occupied, rowNum + 1, n);board[rowNum][colNum] = '.'; //回溯,尝试皇后rowNum的下一个位置col_occupied[colNum] = false;}}}private boolean isValid(char[][]board, boolean[] col_occupied, int row, int col, int n) {if (col_occupied[col]) return false;for (int i = 1; row - i >= 0 && col - i >= 0; i++) {//反对角斜线if (board[row - i][col - i] == 'Q') return false;}for (int i = 1; row - i >= 0 && col + i < n; i++) {//正对角斜线if (board[row - i][col + i] == 'Q') return false;}return true;}
}
这篇关于leetcode:N-Queens II 【Java】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!