回溯例题（leetcode17/37）

本文主要是介绍回溯例题（leetcode17/37），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

leetcode37
leetcode17

回溯跟枚举差不多。要注意“回溯”，别忘记“回”之前把之前的改动都复原。

leetcode37

在这里插入图片描述

leetcode37是解数独问题。本题保证有且仅有唯一解。

思路：先把空格子的位置存下来，然后对每一个空位置挨个枚举1-9。枚举之前，先建立一个一维数组，把要排除的数先排除，效率会高些。

class Solution {// 空格的信息int x[100], y[100], cnt = 0;bool dfs(int i, vector<vector<char>>& board) {if (i == cnt) return true;bool s[60] = {false};// 检查行、列for (int j = 0; j < 9; j++) s[board[x[i]][j]] = s[board[j][y[i]]] = true;// 检查九宫格for (int j = x[i] / 3 * 3; j < x[i] / 3 * 3 + 3; j++)for (int k = y[i] / 3 * 3; k < y[i] / 3 * 3 + 3; k++)s[board[j][k]] = true;// 枚举尝试1-9for (char c = '1'; c <= '9'; c++) {if (s[c] == false) {board[x[i]][y[i]] = c;if (dfs(i + 1, board))return true;}}board[x[i]][y[i]] = '.';return false;}public:void solveSudoku(vector<vector<char>>& board) {// 检索空格子for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {x[cnt] = i;y[cnt++] = j;}}}dfs(0, board);return;}
};

leetcode17

在这里插入图片描述
leetcode17是纯纯的枚举问题。

逐位处理那串数字，把记录好的当作参数string alreadyHave。由于这个形参是每递归一下就新开辟一个栈帧，所以这样写不涉及到“改动复原”的事。如果占用空间太大了，就需要把这个参数改为引用，那么就需要“复原”了。

class Solution {vector<string> ans;string d;void dfs(int index, string alreadyHave) // index是待处理下标{if (index == d.length()) {if (alreadyHave != "")ans.push_back(alreadyHave);return;}int num = d[index] - '0', start, end;if (num >= 2 && num <= 7) {start = (num - 2) * 3 + 'a';end = start + 2;}if (num == 7)end++;if (num == 8) {start = 't';end = 'v';}if (num == 9) {start = 'w';end = 'z';}for (int i = start; i <= end; i++) {dfs(index + 1, alreadyHave + (char)(i));}return;}public:vector<string> letterCombinations(string digits) {d = digits;dfs(0, "");return ans;}
};