leetcode面試題 08.12. 八皇后(回溯)

設計一種算法,打印 N 皇后在 N × N 棋盤上的各種擺法,其中每個皇后都不同行、不同列,也不在對角線上。這里的“對角線”指的是所有的對角線,不只是平分整個棋盤的那兩條對角線。

注意:本題相對原題做了擴展

示例:

輸入:4
輸出:[[".Q…","…Q",“Q…”,"…Q."],["…Q.",“Q…”,"…Q",".Q…"]]
解釋: 4 皇后問題存在如下兩個不同的解法。
[
[".Q…", // 解法 1
“…Q”,
“Q…”,
“…Q.”],

["…Q.", // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]

代碼

class Solution {List<List<String>> cList=new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chars=new char[n][n];for(int i=0;i<n;i++)Arrays.fill(chars[i],'.');//全部都沒放皇后solveNQ(n,chars,0);return cList;}public void solveNQ(int n,char[][] chars,int row) {if(row==n)//返回結果{List<String> temp=new ArrayList<>();for(int i=0;i<n;i++){temp.add(String.valueOf(chars[i]));}cList.add(temp);return;}for(int i=0;i<n;i++)//選擇列{if(isOk(i,chars,row)){chars[row][i]='Q';solveNQ(n,chars,row+1);//下一行chars[row][i]='.';//回溯}}}public boolean isOk(int col,char[][] chars,int row) {//檢查位置是否合法for(int i=row-1;i>=0;i--){if(chars[i][col]=='Q')return false;if(col+row-i<chars.length&&chars[i][col+row-i]=='Q')return false;if(col-row+i>=0&&chars[i][col-row+i]=='Q')return false;}return true;}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/393814.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/393814.shtml
英文地址,請注明出處:http://en.pswp.cn/news/393814.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

linux 進入redis 數據庫,Linux下Redis數據庫的安裝方法與自動啟動腳本分享

安裝Redis(1) 下載Rediswget http://redis.googlecode.com/files/redis-2.2.11.tar.gztar xzvf redis-2.2.11.tar.gz(2) 編譯并安裝Redismake && make install(3) 復制并修改配置文件cp redis.conf /etc/redis.confvi /etc/redis.conf注意修改以下幾項&#xff1a;daem…

Flutter 36: 圖解自定義 View 之 Canvas (三)

小菜繼續學習 Canvas 的相關方法&#xff1a; drawVertices 繪制頂點 小菜上次沒有整理 drawVertices 的繪制方法&#xff0c;這次補上&#xff1b;Vertice 即頂點&#xff0c;通過繪制多個頂點&#xff0c;在進行連線&#xff0c;多用于 3D 模型中&#xff1b; drawVertices 包…

sphinx 項目根目錄_如何使用Sphinx工具記錄Django項目

sphinx 項目根目錄I recently visited a company where I had a nice talk with one of its employees. We talked about technology and programming. Then we touched the subject of project documentation. Specifically how React does it automatically but Django doesn…

程序員必知之浮點數運算原理詳解

導讀&#xff1a;浮點數運算是一個非常有技術含量的話題&#xff0c;不太容易掌握。許多程序員都不清楚使用操作符比較float/double類型的話到底出現什么問題。 許多人使用float/double進行貨幣計算時經常會犯錯。這篇文章是這一系列中的精華&#xff0c;所有的軟件開發人員都應…

axure選中后橫線切換_3、開關狀態切換 —— Axure實用交互

寫在開頭:開關的制作在幾乎所有原型設計中都會用到&#xff0c;所以美觀自然的交互開關可以給你的原型設計加分不少。本次開關設計主要用到的是邏輯為&#xff1a;選中狀態的切換首先&#xff0c;來看一下演示動畫開始原型設計一、創建元件首先需要打開Axure軟件&#xff0c;并…

Django框架——模型(數據庫操作)

-- models.py-- ORM(object-relation mapping) 實現數據模型與數據庫的解耦&#xff1b;# 對象&#xff0c;關系&#xff0c;映射&#xff1b;1.根 據對象的類型生成表結構&#xff1b;2.將對象、列表的操作&#xff0c;轉換為sql語句&#xff1b;3.將sql查詢到的結果轉換為對象…

leetcode140. 單詞拆分 II(回溯+記憶化)

給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict&#xff0c;在字符串中增加空格來構建一個句子&#xff0c;使得句子中所有的單詞都在詞典中。返回所有這些可能的句子。 說明&#xff1a; 分隔時可以重復使用字典中的單詞。 你可以假設字典中沒有重復的單詞。 …

#loj 3058 [HNOI2019] 白兔之舞

單位根反演思博題 模數是亂給的記得整個任意模數ntt k為p-1的約數意味著一定存在k次單位根&#xff0c;設g是p的原根則\(w_{k}^{1}g^{\frac{k-1}{p}}\) 既然k次單位根存在自然考慮單位根反演了 設\(f(i)\)表示跳了i步并且停在了第二維為y的頂點的方案數 設\(st\)表示初始向量而…

標桿徐2018 Linux自動化運維實戰,標桿徐2018 Linux自動化運維系列⑦: SaltStack自動化配置管理實戰...

結合企業自動化集群場景講解&#xff0c;輕松玩轉SaltStack自動化配置管理工具第1章 SaltStack基礎應用SaltStack安裝SaltStack認證Saltstack遠程執行SaltStack配置管理第2章 SaltStack數據系統SaltStack數據系統-Grains 客戶端向服務端發送狀態SaltStack數據系統-paiil 服務…

JS 對象引用問題

var a {n:1}; var b a; a {n:2}; a.x a ;console.log(a.x);console.log(b.x); var a {n:1}; var b a; a.x a {n:2}; console.log(a.x);console.log(b.x); 這兩個問題主要理解兩點就很簡單了。 對象是引用類型&#xff0c;改變賦值只是改變指針的引用。運算符相當于改變…

工程代碼_Egret開發筆記(二)基礎工程代碼閱讀

代碼目錄結構在Egret Wing中打開上一節中我們創建的項目工程&#xff0c;查看代碼目錄結構&#xff0c;Forward在如下圖中標記了各個目錄的及關鍵文件的用途。代碼閱讀理解接下來我們從web入口一步一步閱讀初始代碼。首先打開index.html文件&#xff0c;我們看到index文件內容如…

知曉云助力小程序開發

小程序開發遇到瓶頸雖然騰訊提供了小程序解決方案&#xff0c;https://cloud.tencent.com/solution/la。但是對于普通開發者或者小企業的開發人員來說&#xff0c;購買域名&#xff0c;網站備案、部署SSL證書&#xff0c;安裝會話服務器。業務邏輯上要使用數據庫&#xff0c;緩…

leetcode131. 分割回文串(回溯)

給定一個字符串 s&#xff0c;將 s 分割成一些子串&#xff0c;使每個子串都是回文串。 返回 s 所有可能的分割方案。 示例: 輸入: “aab” 輸出: [ [“aa”,“b”], [“a”,“a”,“b”] ] 代碼 class Solution {List<List<String>> stringListnew ArrayList…

Cracer滲透-windows基礎(系統目錄,服務,端口,注冊表)

系統目錄C:\Windows\system32\config\SAM (保存系統密碼) 無法正常修改&#xff0c;可以進入PE系統進行修改&#xff08;先備份在清空&#xff09;利用結束后&#xff0c;再將之前備份的恢復C:\Windows\System32\drivers\hosts&#xff08;域名解析文件&#xff09;hosts欺騙&a…

java--xml文件讀取(SAX)

SAX解析原理&#xff1a; 使用Handler去逐個分析遇到的每一個節點 SAX方式解析步奏&#xff1a; 創建xml解析需要的handler&#xff08;parser.parse(file,handler)&#xff09; package com.imooc_xml.sax.handler;import java.util.ArrayList;import org.xml.sax.Attributes…

算法訓練營 重編碼_編碼訓練營之后該做什么-以及如何獲得成功

算法訓練營 重編碼by Anthony Morris安東尼莫里斯(Anthony Morris) 編碼訓練營之后該做什么-以及如何獲得成功 (What to do — and how to find success — after a coding bootcamp) It’s almost been two years since I graduated from the Lighthouse Labs Web Developmen…

leetcode860. 檸檬水找零(貪心)

在檸檬水攤上&#xff0c;每一杯檸檬水的售價為 5 美元。 顧客排隊購買你的產品&#xff0c;&#xff08;按賬單 bills 支付的順序&#xff09;一次購買一杯。 每位顧客只買一杯檸檬水&#xff0c;然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零&#xff0…

linux防火墻開啟某端口命令行,linux上防火墻 開啟某個端口

linux下防火墻 開啟某個端口直接在/etc/sysconfig/iptables中增加一行&#xff1a;-A RH-Firewall-1-INPUT -m state –state NEW -m tcp -p tcp –dport 8080 -j ACCEPT注意添加位置:-A RH-Firewall-1-INPUT -m state --state NEW -m tcp -p tcp --dport 25 -j ACCEPT-A RH-Fi…

imp命令導入指定表_Sqoop 使用shell命令的各種參數的配置及使用方法

點擊上方藍色字體&#xff0c;選擇“設為星標”回復”資源“獲取更多資源本文作者&#xff1a;Sheep Sun本文鏈接&#xff1a;https://www.cnblogs.com/yangxusun9/p/12558683.html大數據技術與架構點擊右側關注&#xff0c;大數據開發領域最強公眾號&#xff01;暴走大數據點擊…

黑客頻繁來襲 關注云計算的安全與保障

本文講的是 : 黑客頻繁來襲 關注云計算的安全與保障 , 【IT168 資訊】日前&#xff0c;虎嗅網遭受網絡攻擊的事件&#xff0c;引起業內關注。2月27日晚&#xff0c;虎嗅網中斷訪問&#xff0c;虎嗅網新浪官方微博隨即發表聲明&#xff0c;表示網站受到惡意攻擊&#xff0c;隨…