17. 电话号码的字母组合 依然是昨天的回溯,思路是根据 index,来确定要回溯的对象:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : vector<string> letterCombinations (string digits) { vector<string> results; if (digits.empty ()) return results; vector<string> posi = {"" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz" }; string current; backtrack (digits, 0 , current, posi, results); return results; } void backtrack (const string& digits, int index, string& current, const vector<string>& posi, vector<string>& results) { if (digits.size () == current.size ()) { results.push_back (current); return ; } int pos = digits[index] - '0' ; string letters = posi[pos]; for (auto letter : letters) { current.push_back (letter); backtrack (digits, index + 1 , current, posi, results); current.pop_back (); } } };
22. 括号生成 这道题目挺难,这里的思路是利用两个规则来构建合法的括号表达式:
1 2 3 4 5 6 if (open < max) { current.push_back ('(' ); } if (close < open) { current.push_back (')' ); }
如果左括号小于 max,就加,如果右括号小于左括号,就加。这两个规则可以确保生成的括号表达式是合法的 。因为这在根本上就规避了这样的组合:)((...
、())...
:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution {public : vector<string> generateParenthesis (int n) { vector<string> result; string current; backtrack (result, current, 0 , 0 , n); return result; } void backtrack (vector<string>& result, string& current, int open, int close, int max) { if (current.size () == max * 2 ) { result.push_back (current); return ; } if (open < max) { current.push_back ('(' ); backtrack (result, current, open + 1 , close, max); current.pop_back (); } if (close < open) { current.push_back (')' ); backtrack (result, current, open, close + 1 , max); current.pop_back (); } } };
79. 单词搜索 这个题目还是回溯,需要一个 helper 数组来标记已经访问过的位置,并且回溯过程中,递归函数也是带有返回值的。在调用函数中,需要对每个位置进行搜索,如果搜索到就返回,相当于示例优化;在被调用函数中,如果board[x][y] != word[index]
就返回 false,相当于剪枝,因此整个过程时间复杂度并不高:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution {public : bool exist (vector<vector<char >>& board, string word) { int m = board.size (), n = board[0 ].size (); vector<vector<bool >> visited (m, vector <bool >(n, false )); for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { if (search (board, word, 0 , i, j, visited)) return true ; } } return false ; }private : bool search (vector<vector<char >>& board, string& word, int index, int x, int y, vector<vector<bool >>& visited) { if (index == word.size ()) return true ; if (x < 0 || x >= board.size () || y < 0 || y >= board[0 ].size () || visited[x][y] || board[x][y] != word[index]) return false ; visited[x][y] = true ; bool found = search (board, word, index + 1 , x + 1 , y, visited) || search (board, word, index + 1 , x - 1 , y, visited) || search (board, word, index + 1 , x, y + 1 , visited) || search (board, word, index + 1 , x, y - 1 , visited); visited[x][y] = false ; return found; } };
131. 分割回文串 这个题目的核心思路是剪枝:当 (s,index,i)
是回文串的时候,纵向深入:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution {public : vector<vector<string>> partition (string s) { vector<vector<string>> result; vector<string> path; backtrace (s, 0 , path, result); return result; }private : void backtrace (string& s, int index, vector<string>& path, vector<vector<string>>& result) { if (index == s.size ()) { result.push_back (path); return ; } for (int i = index; i < s.size (); i++) { if (isPalindrome (s, index, i)) { path.push_back (s.substr (index, i - index + 1 )); backtrace (s, i + 1 , path, result); path.pop_back (); } } } bool isPalindrome (string& str, int start, int end) { while (start < end) { if (str[start] != str[end]) { return false ; } start++; end--; } return true ; } };
51. N 皇后 N 皇后相关的题目很多,但是都大同小异。这个题目的难点在于如果去标记纵向、两个对角线是否被占用,对于第 row 行、col 列,那么对角线为:diag1[row - col + n - 1]
、diag2[row + col]
。其中:
1 2 vector<bool > diag1 (2 * n - 1 , false ) ; vector<bool > diag2 (2 * n - 1 , false ) ;
最好把这个记住,可以加快做题速度。
解决了这个问题之后,其他就很简单了,在 row 上进行回溯就行了:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution {public : vector<vector<string>> solveNQueens (int n) { vector<vector<string>> solutions; vector<string> board (n, string(n, '.' )) ; vector<bool > cols (n, false ) ; vector<bool > diag1 (2 * n - 1 , false ) ; vector<bool > diag2 (2 * n - 1 , false ) ; backtrack (solutions, board, cols, diag1, diag2, 0 , n); return solutions; }private : void backtrack (vector<vector<string>>& solutions, vector<string>& board, vector<bool >& cols, vector<bool >& diag1, vector<bool >& diag2, int row, int n) { if (row == n) { solutions.push_back (board); return ; } for (int col = 0 ; col < n; ++col) { if (cols[col] || diag1[row - col + n - 1 ] || diag2[row + col]) { continue ; } board[row][col] = 'Q' ; cols[col] = diag1[row - col + n - 1 ] = diag2[row + col] = true ; backtrack (solutions, board, cols, diag1, diag2, row + 1 , n); board[row][col] = '.' ; cols[col] = diag1[row - col + n - 1 ] = diag2[row + col] = false ; } } };
总结 这些题目都是经典的回溯算法问题,每个问题都利用了回溯的核心思想:探索所有可能的解决方案,并在遇到死路时撤销上一步或几步的决定(回溯),然后尝试其他可能的选项。以下是每个问题的详细解析和核心思想。
17. 电话号码的字母组合 核心思想 :对于每个数字字符,有一组对应的字母。使用回溯法逐一探索每个数字对应的所有字母,组合成所有可能的字母组合。
解题步骤 :
创建一个映射列表posi
,将每个数字映射到相应的字符串。
使用递归函数backtrack
,从左到右处理每个数字,并尝试每个数字对应的所有可能字母。
当当前组合的长度等于输入数字字符串的长度时,将其添加到结果列表中。
22. 括号生成 核心思想 :确保在任何时刻插入的右括号数量不超过左括号的数量,从而确保生成的括号字符串有效。
解题步骤 :
使用递归函数backtrack
,维护当前的括号字符串和左、右括号的计数。
如果左括号数量小于n
,可以添加一个左括号并递归。
如果右括号数量小于左括号数量,可以添加一个右括号并递归。
当字符串长度达到2*n
时,说明找到了一个有效的组合,添加到结果中。
79. 单词搜索 核心思想 :在二维网格中使用回溯法搜索每个单元格,尝试找到目标单词的路径。
解题步骤 :
遍历整个网格,以每个单元格作为起点尝试搜索单词。
使用递归函数search
,探索上下左右四个方向寻找单词的下一个字符。
使用一个辅助数组visited
标记已访问过的单元格,防止重复访问。
如果在某个方向上的探索成功,返回true
;如果所有方向都失败,回溯到上一步。
131. 分割回文串 核心思想 :递归地尝试所有可能的分割方案,并使用剪枝策略只保留那些分割后是回文的结果。
解题步骤 :
递归函数backtrace
从索引index
开始尝试所有可能的分割点。
对于每个可能的分割点,检查从index
到当前点的子字符串是否是回文。
如果是回文,则将其添加到当前路径中,并从下一个位置继续尝试。
当达到字符串末尾时,将当前路径添加到结果中。
51. N 皇后 核心思想 :在n*n
的棋盘上放置n
个皇后,使得它们互不攻击。这通过确保每行、每列及两个方向的对角线上最多只有一个皇后来实现。
解题步骤 :
使用递归函数backtrack
探索每一行的所有列,尝试放置皇后。
通过三个布尔数组cols
, diag1
, diag2
来检查当前列和对角线上是否已放置皇后。
如果找到有效的位置,放置皇后并递归地尝试下一行。
如果所有行都成功放
置了皇后,记录当前的棋盘配置。 5. 否则回溯,尝试当前行的其他列。
每个问题都采用了回溯策略,这种策略不仅能找到一个解,还能找到所有可能的解,并在适当的时候进行剪枝,优化搜索过程。