北京好用的h5建站,做电影网站涉及的侵权问题,上海微信网站建设公司电话,建设银行官方网站面试详细信息文章目录 leetcode37leetcode17 回溯跟枚举差不多。要注意“回溯”#xff0c;别忘记“回”之前把之前的改动都复原。
leetcode37 leetcode37是解数独问题。本题保证有且仅有唯一解。
思路#xff1a;先把空格子的位置存下来#xff0c;然后对每一个空位置挨个枚举1-9。枚… 文章目录 leetcode37leetcode17 回溯跟枚举差不多。要注意“回溯”别忘记“回”之前把之前的改动都复原。
leetcode37 leetcode37是解数独问题。本题保证有且仅有唯一解。
思路先把空格子的位置存下来然后对每一个空位置挨个枚举1-9。枚举之前先建立一个一维数组把要排除的数先排除效率会高些。
class Solution {// 空格的信息int x[100], y[100], cnt 0;bool dfs(int i, vectorvectorchar 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(vectorvectorchar 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 {vectorstring 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:vectorstring letterCombinations(string digits) {d digits;dfs(0, );return ans;}
};
