2024.06.24 刷题日记

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. 电话号码的字母组合

核心思想:对于每个数字字符,有一组对应的字母。使用回溯法逐一探索每个数字对应的所有字母,组合成所有可能的字母组合。

解题步骤

  1. 创建一个映射列表posi,将每个数字映射到相应的字符串。
  2. 使用递归函数backtrack,从左到右处理每个数字,并尝试每个数字对应的所有可能字母。
  3. 当当前组合的长度等于输入数字字符串的长度时,将其添加到结果列表中。

22. 括号生成

核心思想:确保在任何时刻插入的右括号数量不超过左括号的数量,从而确保生成的括号字符串有效。

解题步骤

  1. 使用递归函数backtrack,维护当前的括号字符串和左、右括号的计数。
  2. 如果左括号数量小于n,可以添加一个左括号并递归。
  3. 如果右括号数量小于左括号数量,可以添加一个右括号并递归。
  4. 当字符串长度达到2*n时,说明找到了一个有效的组合,添加到结果中。

79. 单词搜索

核心思想:在二维网格中使用回溯法搜索每个单元格,尝试找到目标单词的路径。

解题步骤

  1. 遍历整个网格,以每个单元格作为起点尝试搜索单词。
  2. 使用递归函数search,探索上下左右四个方向寻找单词的下一个字符。
  3. 使用一个辅助数组visited标记已访问过的单元格,防止重复访问。
  4. 如果在某个方向上的探索成功,返回true;如果所有方向都失败,回溯到上一步。

131. 分割回文串

核心思想:递归地尝试所有可能的分割方案,并使用剪枝策略只保留那些分割后是回文的结果。

解题步骤

  1. 递归函数backtrace从索引index开始尝试所有可能的分割点。
  2. 对于每个可能的分割点,检查从index到当前点的子字符串是否是回文。
  3. 如果是回文,则将其添加到当前路径中,并从下一个位置继续尝试。
  4. 当达到字符串末尾时,将当前路径添加到结果中。

51. N 皇后

核心思想:在n*n的棋盘上放置n个皇后,使得它们互不攻击。这通过确保每行、每列及两个方向的对角线上最多只有一个皇后来实现。

解题步骤

  1. 使用递归函数backtrack探索每一行的所有列,尝试放置皇后。
  2. 通过三个布尔数组cols, diag1, diag2来检查当前列和对角线上是否已放置皇后。
  3. 如果找到有效的位置,放置皇后并递归地尝试下一行。
  4. 如果所有行都成功放

置了皇后,记录当前的棋盘配置。
5. 否则回溯,尝试当前行的其他列。

每个问题都采用了回溯策略,这种策略不仅能找到一个解,还能找到所有可能的解,并在适当的时候进行剪枝,优化搜索过程。


2024.06.24 刷题日记
http://blog.luliang.online/2024/06/24/2024.06.24 刷题日记/
作者
Luyoung
发布于
2024年6月24日
许可协议