{"id":207,"date":"2024-01-05T00:22:58","date_gmt":"2024-01-04T16:22:58","guid":{"rendered":"https:\/\/wangqianming.top\/?p=207"},"modified":"2024-01-05T00:22:58","modified_gmt":"2024-01-04T16:22:58","slug":"%e5%9b%9e%e6%ba%af%e6%b3%954","status":"publish","type":"post","link":"https:\/\/wangqianming.top\/index.php\/2024\/01\/05\/%e5%9b%9e%e6%ba%af%e6%b3%954\/","title":{"rendered":"\u56de\u6eaf\u6cd54"},"content":{"rendered":"

\u56de\u6eaf\u6cd54-n\u7687\u540e\u95ee\u9898<\/h1>\n

\u6309\u7167\u56fd\u9645\u8c61\u68cb\u7684\u89c4\u5219\uff0c\u7687\u540e\u53ef\u4ee5\u653b\u51fb\u4e0e\u4e4b\u5904\u5728\u540c\u4e00\u884c\u6216\u540c\u4e00\u5217\u6216\u540c\u4e00\u659c\u7ebf\u4e0a\u7684\u68cb\u5b50\u3002<\/p>\n

n \u7687\u540e\u95ee\u9898 \u7814\u7a76\u7684\u662f\u5982\u4f55\u5c06 n \u4e2a\u7687\u540e\u653e\u7f6e\u5728 n\u00d7n \u7684\u68cb\u76d8\u4e0a\uff0c\u5e76\u4e14\u4f7f\u7687\u540e\u5f7c\u6b64\u4e4b\u95f4\u4e0d\u80fd\u76f8\u4e92\u653b\u51fb\u3002<\/p>\n

\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570 n \uff0c\u8fd4\u56de\u6240\u6709\u4e0d\u540c\u7684 n \u7687\u540e\u95ee\u9898 \u7684\u89e3\u51b3\u65b9\u6848\u3002<\/p>\n

\u6bcf\u4e00\u79cd\u89e3\u6cd5\u5305\u542b\u4e00\u4e2a\u4e0d\u540c\u7684 n \u7687\u540e\u95ee\u9898 \u7684\u68cb\u5b50\u653e\u7f6e\u65b9\u6848\uff0c\u8be5\u65b9\u6848\u4e2d 'Q' \u548c '.' \u5206\u522b\u4ee3\u8868\u4e86\u7687\u540e\u548c\u7a7a\u4f4d\u3002<\/p>\n

\u793a\u4f8b 1\uff1a<\/strong><\/p>\n

\n

\u8f93\u5165\uff1a<\/strong>n = 4
\n\u8f93\u51fa\uff1a<\/strong>[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
\n\u89e3\u91ca\uff1a<\/strong>\u5982\u4e0a\u56fe\u6240\u793a\uff0c4 \u7687\u540e\u95ee\u9898\u5b58\u5728\u4e24\u4e2a\u4e0d\u540c\u7684\u89e3\u6cd5\u3002<\/p>\n<\/blockquote>\n

\u8d34\u4e00\u4e0b\u5e38\u89c4\u89e3\u6cd5\uff1a<\/p>\n

class Solution {\n    public List<List<String>> solveNQueens(int n) {\n        List<List<String>> solutions = new ArrayList<List<String>>();\n        int[] queens = new int[n];\n        Arrays.fill(queens, -1);\n        Set<Integer> columns = new HashSet<Integer>();\n        Set<Integer> diagonals1 = new HashSet<Integer>();\n        Set<Integer> diagonals2 = new HashSet<Integer>();\n        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);\n        return solutions;\n    }\n\n    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {\n        if (row == n) {\n            List<String> board = generateBoard(queens, n);\n            solutions.add(board);\n        } else {\n            for (int i = 0; i < n; i++) {\n                if (columns.contains(i)) {\n                    continue;\n                }\n                int diagonal1 = row - i;\n                if (diagonals1.contains(diagonal1)) {\n                    continue;\n                }\n                int diagonal2 = row + i;\n                if (diagonals2.contains(diagonal2)) {\n                    continue;\n                }\n                queens[row] = i;\n                columns.add(i);\n                diagonals1.add(diagonal1);\n                diagonals2.add(diagonal2);\n                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);\n                queens[row] = -1;\n                columns.remove(i);\n                diagonals1.remove(diagonal1);\n                diagonals2.remove(diagonal2);\n            }\n        }\n    }\n\n    public List<String> generateBoard(int[] queens, int n) {\n        List<String> board = new ArrayList<String>();\n        for (int i = 0; i < n; i++) {\n            char[] row = new char[n];\n            Arrays.fill(row, '.');\n            row[queens[i]] = 'Q';\n            board.add(new String(row));\n        }\n        return board;\n    }\n}\n<\/code><\/pre>\n
\u601d\u8def\u5f88\u7b80\u5355\uff0c\u4e00\u5c42\u4e00\u5c42\u627e\uff0c\u5c42\u6570\u4e4b\u95f4\u7528\u56de\u6eaf\u6cd5\u9012\u5f52\u67e5\u627e\uff0c\u5c42\u5185\u5219\u4f7f\u7528\u4e00\u4e2afor\u5faa\u73af\u9010\u4e00\u6392\u67e5<\/p>\n","protected":false},"excerpt":{"rendered":"
\u56de\u6eaf\u6cd54-n\u7687\u540e\u95ee\u9898 \u6309\u7167\u56fd\u9645\u8c61\u68cb\u7684\u89c4\u5219\uff0c\u7687\u540e\u53ef\u4ee5\u653b\u51fb\u4e0e\u4e4b\u5904\u5728\u540c\u4e00\u884c\u6216\u540c\u4e00\u5217\u6216\u540c\u4e00\u659c\u7ebf\u4e0a\u7684\u68cb\u5b50\u3002 n \u7687\u540e\u95ee\u9898 \u7814\u7a76\u7684\u662f\u5982\u4f55\u5c06 n …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[5,17,9],"class_list":["post-207","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-java","tag-17","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/207","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/comments?post=207"}],"version-history":[{"count":1,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/207\/revisions"}],"predecessor-version":[{"id":208,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/207\/revisions\/208"}],"wp:attachment":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/media?parent=207"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/categories?post=207"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/tags?post=207"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}