訓練營第二十七天 | 491.遞增子序列46.全排列47.全排列 II332.重新安排行程51. N皇后

491.遞增子序列

力扣題目鏈接(opens new window)

給定一個整型數組, 你的任務是找到所有該數組的遞增子序列，遞增子序列的長度至少是2。

示例:

輸入: [4, 6, 7, 7]
輸出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

說明:

給定數組的長度不會超過15。
數組中的整數范圍是?[-100,100]。
給定數組中可能包含重復數字，相等的數字應該被視為遞增的一種情況。

思路：

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startindex) {if (path.size() > 1) result.push_back(path);for (int i = startindex; i < nums.size(); i++) {if (i > startindex && nums[i] == nums[i - 1]) continue;  // 跳過重復元素if (path.empty() || nums[i] >= path.back()) {  // 確保遞增順序path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

初始代碼：

沒有正確處理重復元素的情況。如果輸入數組中有重復元素，直接跳過重復的元素，這樣會遺漏一些合法的遞增子序列。

為了正確處理重復元素，需要在每一層遞歸中使用一個集合（如 unordered_set）來記錄當前層中已經使用過的元素，以確保每個元素在每一層遞歸中只使用一次，但在不同的遞歸路徑中可以使用相同的元素。

unordered_set<int> used; ?// 使用集合來記錄當前層使用過的元素

if (used.find(nums[i]) != used.end()) continue; ?// 當前層已經使用過的元素跳過

if (path.empty() || nums[i] >= path.back()) { ?// 確保遞增順序

改正后的代碼：

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startindex) {if (path.size() > 1) result.push_back(path);unordered_set<int> used;  // 使用集合來記錄當前層使用過的元素for (int i = startindex; i < nums.size(); i++) {if (used.find(nums[i]) != used.end()) continue;  // 當前層已經使用過的元素跳過if (path.empty() || nums[i] >= path.back()) {  // 確保遞增順序used.insert(nums[i]);  // 記錄當前元素path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

46.全排列

力扣題目鏈接(opens new window)

給定一個沒有重復數字的序列，返回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路：

該題在回溯法的基礎上加了一個used數組，存儲數組對應元素是否使用過，以此作為條件判斷是否將該數加入path。

            if (used[i]) continue;used[i] = true;path.push_back(nums[i]);backtrack(nums, used);path.pop_back();used[i] = false;

同時，該題不需要startindex，因為每次循環都是將未加入path的所有元素依次遍歷加入path。而是用used代替了，作為參數值傳入backtrack函數。

class Solution {
private:vector<vector<int>> result;vector<int> path; // 全局變量void backtrack(vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (used[i]) continue;used[i] = true;path.push_back(nums[i]);backtrack(nums, used);path.pop_back();used[i] = false;}}public:vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtrack(nums, used);return result;}
};

47.全排列 II

力扣題目鏈接(opens new window)

給定一個可包含重復數字的序列 nums ，按任意順序返回所有不重復的全排列。

示例 1：

輸入：nums = [1,1,2]
輸出： [[1,1,2], [1,2,1], [2,1,1]]

示例 2：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

思路：

該題就多了一個去重操作。先給數組排序，然后還是使用used的方式遞歸。

其中特別注意：if (i > 0 && nums[i] == nums[i - 1]&& !used[i - 1]) continue;中不要忘記“!used[i - 1]”。!used[i - 1]：確保在當前層級中，前一個相同元素沒有被使用。如果前一個相同元素沒有被使用，則跳過當前元素。這一步的目的是避免在同一層級中選擇相同的元素，從而防止生成重復的排列。如果used[i - 1] == true。則同一樹枝重復，是被允許的。

class Solution {private:vector<vector<int>> result;vector<int> path;void backtrack(vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if (used[i]) continue;           if (i > 0 && nums[i] == nums[i - 1]&& !used[i - 1]) continue;used[i] = true;path.push_back(nums[i]);backtrack(nums, used);path.pop_back();used[i] = false;}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());backtrack(nums, used);return result;}
};

332.重新安排行程

力扣題目鏈接(opens new window)

給定一個機票的字符串二維數組 [from, to]，子數組中的兩個成員分別表示飛機出發和降落的機場地點，對該行程進行重新規劃排序。所有這些機票都屬于一個從 JFK（肯尼迪國際機場）出發的先生，所以該行程必須從 JFK 開始。

提示：

如果存在多種有效的行程，請你按字符自然排序返回最小的行程組合。例如，行程 ["JFK", "LGA"] 與 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的機場都用三個大寫字母表示（機場代碼）。
假定所有機票至少存在一種合理的行程。
所有的機票必須都用一次且只能用一次。

示例 1：

輸入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
輸出：["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2：

輸入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
輸出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解釋：另一種有效的行程是?["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

思路：?

使用unordered_map<string, map<string, int>> targets;?來記錄航班的映射關系，定義為全局變量。參數里還需要ticketNum，表示有多少個航班（終止條件會用上）。

代碼如下：

// unordered_map<出發機場, map<到達機場, 航班次數>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {

返回值用bool！

因為只需要找到一個行程，就是在樹形結構中唯一的一條通向葉子節點的路線，所以找到了這個葉子節點了直接返回。

遞歸終止條件

拿題目中的示例為例，輸入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] ，這是有4個航班，那么只要找出一種行程，行程里的機場個數是5就可以了。

所以終止條件是：回溯遍歷的過程中，遇到的機場個數，如果達到了（航班數量+1），那么我們就找到了一個行程，把所有航班串在一起了。

單層搜索的邏輯

在選擇映射函數的時候，不能選擇unordered_map<string, multiset<string>> targets，因為一旦有元素增刪multiset的迭代器就會失效。

可以說本題既要找到一個對數據進行排序的容器，而且還要容易增刪元素，迭代器還不能失效。

所以我選擇了unordered_map<string, map<string, int>> targets?來做機場之間的映射。

class Solution {
private:
// unordered_map<出發機場, map<到達機場, 航班次數>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {if (result.size() == ticketNum + 1) {return true;}for (pair<const string, int>& target : targets[result[result.size() - 1]]) {if (target.second > 0 ) { // 記錄到達機場是否飛過了result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second++;}}return false;
}
public:vector<string> findItinerary(vector<vector<string>>& tickets) {targets.clear();vector<string> result;for (const vector<string>& vec : tickets) {targets[vec[0]][vec[1]]++; // 記錄映射關系}result.push_back("JFK"); // 起始機場backtracking(tickets.size(), result);return result;}
};

51. N皇后

力扣題目鏈接(opens new window)

n?皇后問題研究的是如何將 n?個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回所有不同的?n?皇后問題的解決方案。

每一種解法包含一個不同的?n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

示例 1：

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋：如上圖所示，4 皇后問題存在兩個不同的解法。

示例 2：

輸入：n = 1
輸出：[["Q"]]

class Solution {
private:vector<vector<string>> result;void backtrack(int n, int i, vector<vector<char>>& chessboard, vector<bool>& used) {if (i == n) {vector<string> board;for (const auto& row : chessboard) {board.push_back(string(row.begin(), row.end()));}result.push_back(board);return;}for (int j = 0; j < n; j++) {if (used[j] || !valid(i, j, chessboard, n)) continue;chessboard[i][j] = 'Q'; // 放置皇后used[j] = true;backtrack(n, i + 1, chessboard, used);chessboard[i][j] = '.'; // 回溯，撤銷皇后used[j] = false;}}bool valid(int i, int j, vector<vector<char>>& chessboard, int n) {// 檢查左上對角線for (int k = i - 1, h = j - 1; k >= 0 && h >= 0; k--, h--) {if (chessboard[k][h] == 'Q') return false;}// 檢查右上對角線for (int k = i - 1, h = j + 1; k >= 0 && h < n; k--, h++) {if (chessboard[k][h] == 'Q') return false;}return true;}public:vector<vector<string>> solveNQueens(int n) {vector<vector<char>> chessboard(n, vector<char>(n, '.'));vector<bool> used(n, false);backtrack(n, 0, chessboard, used);return result;}
};

37. 解數獨

力扣題目鏈接(opens new window)

編寫一個程序，通過填充空格來解決數獨問題。

一個數獨的解法需遵循如下規則：數字 1-9 在每一行只能出現一次。數字 1-9 在每一列只能出現一次。數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。空白格用 '.' 表示。

解數獨

一個數獨。

解數獨

答案被標成紅色。

提示：

給定的數獨序列只包含數字 1-9 和字符 '.' 。
你可以假設給定的數獨只有唯一解。
給定數獨永遠是 9x9 形式的。

思路：

樹枝是board的每一個空格，用雙層for循環（行、列）遍歷，如果等于‘.‘ ，則填入數字。樹層是每個空格可以填入的數字，可以設置一個輔助函數判斷該數字是否符合要求，若符合則繼續填入下一個空格。其中特別注意，這個回溯函數是一個bool函數，因為解數獨找到一個符合的條件（就在樹的葉子節點上）立刻就返回，相當于找從根節點到葉子節點一條唯一路徑，所以需要使用bool返回值。

找九宮格的時候，可以通過int startRow = (row / 3) * 3;找到特定位置。

class Solution {
private:bool backtrack(vector<vector<char>>& board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {for (char n = '1'; n <= '9'; n++) {if (valid(i, j, n, board)) {board[i][j] = n;if (backtrack(board)) {return true;}board[i][j] = '.';}}return false;}}}return true;}bool valid(int row, int col, char val, vector<vector<char>>& board) {for (int i = 0; i < 9; i++) {if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) {if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) {for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val) {return false;}}}return true;}public:void solveSudoku(vector<vector<char>>& board) {backtrack(board);}
};