??
?
優美的排列
? ? 題目解析? ??
? ? 算法原理? ??
? ? 解法? ：暴搜? ??
? ? 決策樹? ??
紅色剪枝：用于剪去該節點的值在對應分支中，已經被使用的情況，可以定義一個 check[ ]
紫色剪枝：perm[i] 不能夠被 i 整除，i 不能夠被 perm[i] 整除，此時分支就要執行紫色剪枝
? ? 設計函數? ??
? ? 編寫代碼? ??
?N皇后
? ? 題目解析? ??
本題的算法原理是比較簡單的，難點在于剪枝操作和代碼實現能力；?
? ? 算法原理? ??
? ? 解法：暴搜? ??
? ? 決策樹? ??
決策樹的任務：給一個行數，每次枚舉這一行的一個格子，枚舉的格子看是否同列或者主副對角線是否有皇后，沒有則在該格子放一個皇后，并停止枚舉這一行剩下的格子，遞歸下一行；?
綠色剪枝：剪去遍歷的格子所在列，出現其他皇后的情況；
紫色剪枝：剪去遍歷的格子所在主副對角線，出現其他皇后的情況；
所以 N = 3，3皇后是沒有合法的放置方法的?；
當我們的行數為 N+1，說明已經枚舉到了一種合法的結果；
? ? 如何剪枝：考慮當前位置，能否放上皇后? ??
? ? ?策略一：無腦循環? ??
我們在遍歷到一個格子的時候，使用四個循環判斷當前格子所在行，列，左對角線，右對角線是否放有其他皇后，總體時間復雜度 O(N) = 4N * (2 ^N)；雖然時間復雜度高，但是也是可以通過的；
我們可以對這個方法進行優化，因為我們的決策樹是每一行的其中一個格子用來放皇后，所以行是一定不會出現皇后攻擊的情況的，所以只用看列，左對角線，右對角線是否放有其他皇后；
? ? ?策略二：類似哈希表的策略? ???
對于棋盤，我們分別定義兩個 boolean 類型的數組?row[ ]，col[ ] ，用于判斷某一行或者某一列是否放置皇后;
?如果某個格子放置有皇后，對應的 row[ i ] ，col [ j ] 要置為 true ；后續再進行決策的時候，就可以先看看對應的 row，col 是否為 true，任意一個為 true 則不用再考慮本次枚舉的格子；
接下來，我們來解決主對角線和副對角線的情況；
我們通過觀察可以發現，當皇后要放置 N 個時，對應的主對角線和副對角線都是 2 * N - 1；
并且斜率分別是 1 和 -1，所以對于一條對角線，可以用y = x + b 或者 y = -x +b 來表示；
- 對于主對角線，則有 y -? x = b ，縱坐標 + 橫坐標為一個定值；
- 對于副對角線，則有 x + y = b ， 縱坐標 - 橫坐標為一個定值；
所以我們再次定義兩個 boolean 類型的數組 ，dig1，dig2 ，分別表示主對角線和副對角線；這兩個數組的長度為 2*N ，用于存儲所有的主對角線，或者副對角線；
用 b = y - x ，b = y + x 來表示某一條對角線的映射關系，當 dig1[ b ] == true ||?dig2 [ b ] == true，則說明該格子所在對角線放有其他皇后；
但是還有一個細節問題：
對于上圖的主對角線，y - x? 是一個負數，如果直接使用 dig1 [ b ] 會越界；
解決辦法：添加上一個偏移量 n：y - x + n = b + n，讓對角線統一向上移動 n 個單位，來處理截距為負數的情況；所以針對主對角線，我們判斷的是 dig1[ b + n ] 是否是 true 即可；
? ? 編寫代碼? ??
? ? 前期初始化操作? ??
? ? ?主邏輯? ??
有效的數獨
? ? 題目解析? ??
本題并不是關于暴搜的題目，而是一個哈希表的題；我們通過講解這道題的算法原理?，為下一道題?解數獨 做好鋪墊
? ? 算法原理? ??
? ? 解法：暴搜? ??
?我們先來定義一個 boolean 類型的數組?row [ ?] [ ?]：
第一個 [ i ] 表示的是數獨表中的第 i 行， 第二個 [ j ] 表示的是在這一行有沒有出現 j 這個數字；
如：row [ 2 ][ 4 ] 表示的是第二行有沒有出現 4 這個數字，有的話 row [ 2 ][ 4 ] == true；
col[ i ][ j ] 數組同理，表示的是第 i 列是否出現了 j 這個數字?;
除了用數組來表示數度表外，我們也可以用哈希表來表示數獨表，并且用哈希表非常巧妙：
我們是以一個3 x 3 的小數獨表作為一個單位格子的，此時下標就只有 0，1，2；
我們設置一個 boolean 類型的數組 grid :?
grid [ 0 ][ 0 ] 表示左上角第一個 3x3 的大方格；
為了查看一個 3x3 的大方格所有數是否都出現過，我們再開一個空間給 grid：?
如何定義小方格和大方格下標的映射關系呢？
?當有一個元素的位置為 [ x , y ] ，映射的九宮格下標位置為 [ x/3 , y/3 ]；
? ? 編寫代碼? ??
解數獨
? ? 題目解析? ??
? ? 算法原理? ??
? ? 解法 : 暴搜? ?
? ? 決策樹? ??
上圖代表決策樹的某一條分支，我們可以發現，當按照其中一條分支填到第一行最后一個格子時，第一行每使用過的最后一個元素可能是不能填入該格子中的；
那我們怎么知道這條分支的選擇不能填滿數獨表呢？在遍歷某個 ' . ' 的格子時，如果所有數都不符合題意，我們返回 false 即可；
這個代碼的報錯原因，就是沒有對【因為前面的選擇，導致某一個格子 1 到 9 都不能填入】的情況進行處理；
所以如果遇到【某一個格子 1 到 9 都不能填入】的情況，我們就應該向上返回 false，因此，我們的 dfs 應該設置 boolean 類型的返回值，告訴上一層，這種選法是否可以得到正確的數獨，如果返回 false，我們就要讓上一層的格子嘗試下一個數；
dfs 的參數其實可以直接把 board 數組傳入即可；在 dfs 中遍歷 board ，專門處理 board[ i ][ j ] == '.'? 的情況；
? ? 編寫代碼? ??
? ? 初始化? ? ?
? ? 填數邏輯? ???
? ? 攻克難點? ? ?
本題難點就是要想到 dfs 是 boolean 類型，并且要找到?dfs 中合適的位置進行返回；
? ? 對這三處 return 的解讀? ??
單詞搜索
? ? 題目解析? ??
? ? 算法原理? ??
? ? 解法 ：深度優先遍歷? ?
? ? 模擬過程? ??
我們以下面這個矩陣和 word 為例子來模擬過程：?
剛開始，會先遍歷矩陣中所有的元素，直到找到word 的第一個字符 ' A?'
此時會對當前?A 的格子上下左右進行掃描，直到找到 B：
對于當前位置的 A ，上下左右位置并沒有 B ，說明這個 A 不是我們要找的 A ，我們尋找下一個 A:
此時，我們發現當前 A 的位置右邊和下方都有 B ，就需要遞歸這兩種情況：
下方的 B 上下左右查找，并沒有找到 C，我們遍歷右邊的 B?
此時的情況和上面同理：?
最終得到結果，返回 true：?
如果按照上面的模擬過程，矩陣找不到 word ，則返回 false；?
? ? 決策樹? ??
? ? 函數設計? ? ?
? ? 細節問題一：如何避免走重復路徑? ??
? ? 問題描述? ? ?
? ? 模擬過程? ??
? ? ?解決方法一： 設置一個 boolean 數組? ??
定義一個跟原始矩陣相同規模的 boolean 數組 ：
用 visit 來標記當前位置，下次遍歷到某一個位置時，通過 visit 查看這個位置是否已經被使用過；
? ? ?解決方法二： 修改原始矩陣的值? ???
當我們對某一個格子進行上下左右查找，查找到下一個字符時，把這個位置修改成 ' . '?
面試的時候要問問面試官可不可以修改原始矩陣，修改原始矩陣的行為不保險；
? ? 細節問題二：用向量數組映射??( i , j ) 位置的上下左右坐標? ???
設置兩個一維數組 dx[ 4 ] ， dy [ 4 ] ：?
dx[ i ] 和 dy [ i?] 要能映射到同一個方向，映射關系如下：
我們使用一個 for 循環，就可以一個坐標的上下左右關系全部找到；如果要找 8 個方向，我們就定義兩個長度為 8 的數組，來表示 8 個不同的方向；這種方法在二維數組表示方向的時候，是非常好用的；
? ? 編寫代碼? ??
? ? 準備工作? ??
在主函數中，先遍歷一次矩陣，找到第一個 word[ 0 ] ，然后調用 dfs，從第一個 word[ 0 ] 所在位置開始找 word 剩下的元素；
? ? 主邏輯? ? ?
? ? 代碼細節詳解? ? ?
?模擬上述對?return? 會遇到的情況?：
黃金礦工
? ? 題目解析? ??
? ? 算法原理? ??
本題的算法原理和上一題是一類題型，解法大差不差，只是一些細節問題不同；這一題先嘗試自己編寫代碼，再根據老師的視頻改進；
? ? 解法：暴搜? ???
? ? 編寫代碼? ??
? ? 編寫歷程? ??
那么，我們什么時候在主函數更新結果呢？如果要設置遞歸出口，就要再寫一層 for 循環，判斷上下左右的 vis ==true || grid == 0，對于這道題是沒有必要設置遞歸出口的；
只需要找到一輪遞歸的最大值 tmp 即可，并且更新 ret 即可；所以我們一進入 dfs 就更新 ret；
? ? 總結? ? ?
關于更新結果的問題是難點：尤其是在哪里更新結果？這么更新結果有什么用？為什么要這樣更新結果？
每次作出一題，都要想清楚這幾個問題，并且學會新的處理細節問題的方式，如：
- 二維矩陣搜索路徑時，避免走重復路徑的方法；
- 使用向量坐標表示一個格子不同的方向；
不同路徑Ⅲ
? ? 題目解析? ??
? ? 算法原理? ??
? ? 解法 ：暴搜? ?
? ? 編寫代碼? ??
? ? 優化? ??
減少循環次數：?
? ? 繼續優化? ??
我們可以對遞歸出口進行優化，原來是只有合法路徑才 return ，現在是只要走到終點就 return：?
總結?
關于暴搜的題目，算法原理其實并不難，重點考察的就是我們的代碼能力，以及能否發現細節問題，并且對細節問題進行合理的處理；?
?
?
