摘要

• 今天以嘗試較難的題目為主，為日后復(fù)習(xí)做準(zhǔn)備。
• DFS可以看做一個(gè)“拆邊”的過程，用回溯法來搜索合適的“拆邊”方案。
• N皇后和數(shù)獨(dú)問題都可以通過模擬過程，抽象出構(gòu)造答案的樹形結(jié)構(gòu)，用回溯法搜索答案。
• 數(shù)獨(dú)問題的有一個(gè)剪枝條件隱含在枚舉[1-9]仍不能填入當(dāng)前位置，說明之前填入的數(shù)字也要調(diào)整，應(yīng)該直接返回到上一層進(jìn)行調(diào)整，而不能跳過當(dāng)前位置。

LeetCode332 重新安排行程

332. 重新安排行程 - 力扣（Leetcode）

• 這道題目也是圖論DFS的經(jīng)典題目，雖然目前復(fù)習(xí)進(jìn)度還沒有到圖的部分，但這道題目套用回溯法的模板也還算能寫。
• 直觀地去理解DFS，就是一個(gè)“拆邊”的過程，把所有邊拆完了（在本題中是將所有邊拆完，即“用完所有的機(jī)票”），就到達(dá)回溯法樹形結(jié)構(gòu)的葉節(jié)點(diǎn)了，此時(shí)就要判斷是否要收集答案。
• 以LeetCode的示例2為例，先模擬一下“安排行程”的過程

• 題目還要求按字典序返回最小的行程組合，為了滿足這一要求，每次選取下一個(gè)目的地時(shí)，應(yīng)該優(yōu)先選取字典序最小的目的地，這蘊(yùn)含了“貪心”的思想。
• 拆邊的過程如下圖，當(dāng)前所在節(jié)點(diǎn)用青藍(lán)色表示，題目要求從“JFK”開始

• 取以上每一步的當(dāng)前節(jié)點(diǎn)，即得到答案：["JFK","ATL","JFK","SFO","ATL","SFO"]

• 這道題目如果不使用STL的話，要自己實(shí)現(xiàn)從地點(diǎn)名到數(shù)組下標(biāo)的映射，以便保存機(jī)票數(shù)組對應(yīng)的圖的鄰接矩陣。我目前階段的復(fù)習(xí)以邏輯和概念為主，這次先不重復(fù)造輪子了，之后補(bǔ)一個(gè)不用STL的map的題解。

• 既然要DFS，首先肯定要在代碼中把圖表示出來，圖的實(shí)現(xiàn)有兩種，一是鄰接表，二是鄰接矩陣。使用STL的map能很方便的實(shí)現(xiàn)鄰接矩陣，通過哈希映射，就不需要我們自己手動(dòng)將地點(diǎn)名映射到數(shù)組下標(biāo)來構(gòu)建鄰接矩陣了。這道題目的圖是可以有很多重邊的，所以鄰接矩陣的值是可以大于1的，用來記錄到底從起點(diǎn)到終點(diǎn)有幾條邊。

unordered_map<string, map<string, int>> ticketsMap;
for (auto& iter : tickets) {
    ticketsMap[iter[0]][iter[1]]++;
}

• 以上代碼的含義為：unordered_map<起點(diǎn)機(jī)場，map<終點(diǎn)機(jī)場，有幾張票>>

• 另外要注意的是，map會自動(dòng)按key值對存入的二元組進(jìn)行排序，這里key值為終點(diǎn)機(jī)場string，所以用map保存時(shí)自動(dòng)按字典序升序排列了終點(diǎn)機(jī)場。這樣就能保證先嘗試的下一個(gè)機(jī)場的字典序是較小的，從而我們第一次得到的一條合法路徑的字典序應(yīng)該是最小的。

• 其實(shí)，處理好如何保存圖的鄰接矩陣，并利用map解決了字典序的問題，這道題目用回溯法的模板就比較好解決了，至于再往后的優(yōu)化，還是之后復(fù)習(xí)到圖的部分后再回來繼續(xù)學(xué)習(xí)吧。

• 另外要注意的是，對于圖的問題，葉節(jié)點(diǎn)的深度是不確定的，所以沒有明確的遞歸終止條件。但有收集答案的條件，即第一次得到合法路徑時(shí)直接返回當(dāng)前路徑到主函數(shù)。

完整的題解代碼如下

class Solution {
public:
    void backtracking(unordered_map<string, map<string, int>>& ticketsMap,
                    vector<string>& res, int ticketsNum, bool& reach)
    {
        if (res.size() == ticketsNum + 1) {
            reach = true;
            return;
        }
        for (auto& iter :  ticketsMap[res.back()]) {
            if (iter.second) {
                res.push_back(iter.first);
                iter.second--;
                backtracking(ticketsMap, res, ticketsNum, reach);
                if (reach) return;
                iter.second++;
                res.pop_back();
            }
        }
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, map<string, int>> ticketsMap;
        for (auto& iter : tickets) {
            ticketsMap[iter[0]][iter[1]]++;
        }
        vector<string> res;
        res.push_back("JFK");
        bool reach = false;
        backtracking(ticketsMap, res, tickets.size(), reach);
        return res;
    }
};

LeetCode51 N皇后

51. N 皇后 - 力扣（Leetcode）

• 在放下一枚皇后之前，應(yīng)該判斷當(dāng)前位置是否能讓皇后彼此之間不互相攻擊。即判斷在同一行、同一列，同一條斜線（注意有兩條，一條平行于主對角線，一條垂直于主對角線）上不能有兩枚皇后。不難直接寫出以下函數(shù)：（cur表示當(dāng)前棋盤的狀態(tài)）

bool isNotValid(vector<string>& cur, int row, int col, int n) {
    // 同一行
    for (int i = 0; i < n; i++) {
        if (cur[row][i] == 'Q' && i != col) return true;
    }
    // 同一列
    for (int i = 0; i < n; i++) {
        if (cur[i][col] == 'Q' && i != row) return true;
    }
    
    // 同一斜線（平行于主對角線的斜線）
    for (int i = 1; row - i >= 0 && col - i >= 0; i++) {
        if (cur[row - i][col - i] == 'Q') return true;
    }
    for (int i = 1; row + i < n && col + i < n; i++) {
        if (cur[row + i][col + i] == 'Q') return true;
    }
    
    // 同一斜線（垂直于主對角線的斜線）
    for (int i = 1; row - i >= 0 && col + i < n; i++) {
        if (cur[row - i][col + i] == 'Q') return true;
    }
    for (int i = 1; row + i < n && col - i >= 0; i++) {
        if (cur[row + i][col - i] == 'Q') return true;
    }
    return false;
}

• 當(dāng)然，這是最直接也是最簡陋的判斷方式。簡潔的判斷方式有很多，之后再繼續(xù)復(fù)習(xí)。
• 有了以上函數(shù)，就可以在回溯法中對不符合要求的擺放方式進(jìn)行剪枝，最終收集到符合要求的擺放方式。
  • 逐行放置皇后，判斷當(dāng)前的擺放方案是否合法
  • 不合法則直接剪枝，無需再繼續(xù)嘗試
  • 遞歸的終止條件為最后一行擺放完成。

class Solution {
public:
    bool isNotValid(vector<string>& cur, int row, int col, int n) {
        for (int i = 0; i < n; i++) {
            if (cur[i][col] == 'Q' && i != row) return true;
        }
        for (int i = 1; row - i >= 0 && col - i >= 0; i++) {
            if (cur[row - i][col - i] == 'Q') return true;
        }
        for (int i = 1; row + i < n && col + i < n; i++) {
            if (cur[row + i][col + i] == 'Q') return true;
        }
        for (int i = 1; row - i >= 0 && col + i < n; i++) {
            if (cur[row - i][col + i] == 'Q') return true;
        }
        for (int i = 1; row + i < n && col - i >= 0; i++) {
            if (cur[row + i][col - i] == 'Q') return true;
        }
        return false;
    }
    void backtracking(vector<vector<string>>& res, int n,
                    int row, vector<string>& cur)
    {
        if (row >= n) {
            res.push_back(cur);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isNotValid(cur, row, i, n)) continue;
            cur[row][i] = 'Q';
            backtracking(res, n, row + 1, cur);
            cur[row][i] = '.';
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> cur(n, string(n, '.'));
        backtracking(res, n, 0, cur);
        return res; 
    }
};

• N皇后問題還有很多可以深入討論的地方，以上這種模擬擺放的實(shí)現(xiàn)方式雖然直觀，但不是效率最高的方法。直觀有時(shí)候意味著對問題的抽象程度還不夠，所以效率不夠高也是自然的。

LeetCode37 解數(shù)獨(dú)

37. 解數(shù)獨(dú) - 力扣（Leetcode）

• 回溯法基本都是在模擬構(gòu)造答案的過程，將答案的構(gòu)造過程抽象為樹形結(jié)構(gòu)進(jìn)行搜索：。填寫數(shù)獨(dú)，首先就要判斷當(dāng)前位置能填寫什么數(shù)字，不難根據(jù)數(shù)獨(dú)的規(guī)則直接寫出如下剪枝函數(shù)

bool isValid(int row, int col, char k, vector<vector<char>>& board) {
    // 同一行或同一列
    for (int i = 0; i < board.size(); i++) {
        if (i != col && board[row][i] == k) return false;
        if (i != row && board[i][col] == k) return false; 
    }
    // 同一個(gè)九宮格
    int Row = row / 3 * 3;
    int Col = col / 3 * 3;
    for (int i = Row; i < Row + 3; i++) {
        for (int j = Col; j < Col + 3; j++)
            if (i != row && j != col && board[i][j] == k) return false;
    }
    return true;
}

• 遞歸的終止條件：先統(tǒng)計(jì)輸入的矩陣已經(jīng)有多少個(gè)數(shù)字，保存在count中，當(dāng)count等于81時(shí)，說明已經(jīng)數(shù)獨(dú)的矩陣已經(jīng)被填滿，可以直接返回結(jié)果了。

完整的題解代碼如下，用row控制逐行填寫矩陣，減少不必要的遍歷

class Solution {
public:
    bool isValid(int row, int col, char k, vector<vector<char>>& board) {
        // 同一行或同一列
        for (int i = 0; i < board.size(); i++) {
            if (i != col && board[row][i] == k) return false;
            if (i != row && board[i][col] == k) return false; 
        }
        // 同一個(gè)九宮格
        int Row = row / 3 * 3;
        int Col = col / 3 * 3;
        for (int i = Row; i < Row + 3; i++) {
            for (int j = Col; j < Col + 3; j++)
                if (i != row && j != col && board[i][j] == k) return false;
        }
        return true;
    }
    void backtracking(vector<vector<char>>& board, bool& solved,
                    int& count, int row)
    {
        if (count == board.size() * board.size()) {
            solved = true;
            return;
        }
        for (int i = row; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] != '.') continue;

                for (char k = '1'; k <= '9'; k++) {
                    if (isValid(i, j, k, board)) {
                        count++;
                        board[i][j] = k;
                        // 用三目表達(dá)式控制換行
                        backtracking(board, solved, count, j < 8 ? row : row + 1);
                        if (solved) return;
                        board[i][j] = '.';
                        count--;
                    }
                }
                // 如果程序執(zhí)行到這里
                // 表示這個(gè)位置不能填入任何數(shù)，前面填入的數(shù)字也需要調(diào)整，直接返回
                return;
                // 不能跳過當(dāng)前位置再去填下一個(gè)位置
            }
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        bool solved = false;
        int count = 0;
        // 統(tǒng)計(jì)固定好的數(shù)字個(gè)數(shù)
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] != '.') count++;
            }
        }
        backtracking(board, solved, count, 0);
    }
};

• 填數(shù)獨(dú)問題中，有一個(gè)剪枝方式和之前的題目都不同，我在這里卡了一會

for (int i = row; i < board.size(); i++) {
    for (int j = 0; j < board[0].size(); j++) {
        if (board[i][j] != '.') continue;

        for (char k = '1'; k <= '9'; k++) {
            if (isValid(i, j, k, board)) {
                count++;
                board[i][j] = k;
                // 用三目表達(dá)式控制換行
                backtracking(board, solved, count, j < 8 ? row : row + 1);
                if (solved) return;
                board[i][j] = '.';
                count--;
            }
        }
        // 如果程序執(zhí)行到這里
        // 表示這個(gè)位置不能填入任何數(shù)，前面填入的數(shù)字也需要調(diào)整，直接返回
        return;/**/
        // 不能跳過當(dāng)前位置再去填下一個(gè)位置
    }
}

• 后跟/**/的那句return是很關(guān)鍵的剪枝，
  • 這個(gè)剪枝不是在嘗試填入數(shù)字之前進(jìn)行的，
  • 而是嘗試完所有數(shù)字后仍然不能進(jìn)入下一層遞歸才進(jìn)行的剪枝
  • 與在嘗試枚舉當(dāng)前位置的元素之前進(jìn)行的剪枝不同，這種剪枝是在嘗試枚舉當(dāng)前位置的元素之后進(jìn)行的。
  • 因?yàn)闆]有顯式的if來描述剪枝條件，剪枝條件暗含在嘗試了所有元素仍不能填入當(dāng)前位置，只有短短的一句return，非常容易忘記寫，導(dǎo)致代碼邏輯不對。