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. 否则回溯，尝试当前行的其他列。

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

LeetCode
#算法 #数据结构 #leetcode
2024.06.24 刷题日记
http://blog.luliang.online/2024/06/24/2024.06.24 刷题日记/
作者
Luyoung
发布于
2024年6月24日
许可协议