<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0052. N皇后 II ## 題目地址(52. N皇后 II) <https://leetcode-cn.com/problems/n-queens-ii/> ## 題目描述 n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上,并且使皇后彼此之間不能相互攻擊。 ![](https://img.kancloud.cn/75/db/75db669990e3bc45c6bf1bc05b955e19_258x276.png) ``` <pre class="calibre18">``` 給定一個整數 n,返回 n 皇后不同的解決方案的數量。 示例: 輸入: 4 輸出: 2 解釋: 4 皇后問題存在如下兩個不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] ``` ``` ## 前置知識 - 回溯 - 深度優先遍歷 ## 公司 - 阿里 - 百度 - 字節 ## 思路 使用深度優先搜索配合位運算,二進制為 1 代表不可放置,0 相反 利用如下位運算公式: - x & -x :得到最低位的 1 代表除最后一位 1 保留,其他位全部為 0 - x & (x-1):清零最低位的 1 代表將最后一位 1 變成 0 - x & ((1 << n) - 1):將 x 最高位至第 n 位(含)清零 ## 關鍵點 - 位運算 - DFS(深度優先搜索) ## 代碼 - 語言支持:JS ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number} n * @return {number} * @param row 當前層 * @param cols 列 * @param pie 左斜線 * @param na 右斜線 */</span> <span class="hljs-keyword">const</span> totalNQueens = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">let</span> res = <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> dfs = (n, row, cols, pie, na) => { <span class="hljs-keyword">if</span> (row >= n) { res++; <span class="hljs-keyword">return</span>; } <span class="hljs-title">// 將所有能放置 Q 的位置由 0 變成 1,以便進行后續的位遍歷</span> <span class="hljs-title">// 也就是得到當前所有的空位</span> <span class="hljs-keyword">let</span> bits = (~(cols | pie | na)) & ((<span class="hljs-params">1</span> << n) - <span class="hljs-params">1</span>); <span class="hljs-keyword">while</span> (bits) { <span class="hljs-title">// 取最低位的1</span> <span class="hljs-keyword">let</span> p = bits & -bits; <span class="hljs-title">// 把P位置上放入皇后</span> bits = bits & (bits - <span class="hljs-params">1</span>); <span class="hljs-title">// row + 1 搜索下一行可能的位置</span> <span class="hljs-title">// cols | p 目前所有放置皇后的列</span> <span class="hljs-title">// (pie | p) << 1 和 (na | p) >> 1) 與已放置過皇后的位置 位于一條斜線上的位置</span> dfs(n, row + <span class="hljs-params">1</span>, cols | p, (pie | p) << <span class="hljs-params">1</span>, (na | p) >> <span class="hljs-params">1</span>); } } dfs(n, <span class="hljs-params">0</span>, <span class="hljs-params">0</span>, <span class="hljs-params">0</span>, <span class="hljs-params">0</span>); <span class="hljs-keyword">return</span> res; }; ``` ``` ***復雜度分析*** - 時間復雜度:O(N!) - 空間復雜度:O(N)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看