【递归、回溯和剪枝】综合训练＜二＞

1.组合总和

组合总和

解法一：

class Solution {
public:vector<vector<int>> ret;vector<int> path;int aim;vector<vector<int>> combinationSum(vector<int>& nums, int target) {aim = target;dfs(nums, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){if(sum == aim){ret.push_back(path);return;}if(sum > aim || pos == nums.size()) return;for(int i = pos; i < nums.size(); i++){path.push_back(nums[i]);dfs(nums, i, sum + nums[i]);path.pop_back();}}
};

解法二：

class Solution {
public:vector<vector<int>> ret;vector<int> path;int aim;vector<vector<int>> combinationSum(vector<int>& nums, int target) {aim = target;dfs(nums, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){if(sum == aim){ret.push_back(path);return;}if(sum > aim || pos == nums.size()) return;//枚举选择每个元素的个数for(int k = 0; sum + k * nums[pos] <= aim; k++){if(k) path.push_back(nums[pos]);dfs(nums, pos + 1, sum + k * nums[pos]);}//恢复现场for(int k = 1; sum + k * nums[pos] <= aim; k++){path.pop_back();}}
};

2.字母大小写全排列

字母大小写全排列

class Solution {
public:vector<string> ret;string path;vector<string> letterCasePermutation(string s) {dfs(s, 0);return ret;}void dfs(string& s, int pos){if(pos == s.size()){ret.push_back(path);return;}char ch = s[pos];//不改变path.push_back(s[pos]);dfs(s, pos + 1);path.pop_back();//改变if(ch < '0' || ch > '9'){char tmp = change(ch);path.push_back(tmp);dfs(s, pos + 1);path.pop_back();}}char change(char ch){if(ch >= 'a' && ch <= 'z') ch -= 32;else ch += 32;return ch;}
};

3.优美的排列

优美的排列

class Solution {
public:int ret;bool check[16];int countArrangement(int n) {dfs(1, n);return ret;}void dfs(int pos, int n){if(pos == n + 1){ret++;return;}for(int i = 1; i <= n; i++){if(!check[i] && (pos % i == 0 || i % pos == 0)){check[i] = true;dfs(pos + 1, n);check[i] = false;}}}
};

4.N皇后

N皇后

class Solution {
public:bool checkCol[10], checkDig1[20], checkDig2[20];vector<vector<string>> ret;vector<string> path;int n;vector<vector<string>> solveNQueens(int _n) {n = _n;path.resize(n);for(int i = 0; i < n; i++)path[i].append(n, '.');dfs(0);return ret;}void dfs(int row){if(row == n){ret.push_back(path);return;}for(int col = 0; col < n; col++)//尝试在这一行放皇后{//剪枝if(!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[col + row]){path[row][col] = 'Q';checkCol[col] = checkDig1[row-col + n] = checkDig2[row + col] = true;dfs(row + 1);path[row][col] = '.';checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;}}}
};

5.有效的数独

有效的数独

class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++)for(int j = 0; j < 9; j++){if(board[i][j] != '.'){int num = board[i][j] - '0';if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num])return false;row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}return true;}
};

6.解数独

解数独

class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];void solveSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++)for(int j = 0; j < 9; j++){if(board[i][j] != '.'){int num = board[i][j] - '0';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.'){//填数for(int num = 1; num <= 9; num++){if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]){board[i][j] = '0' + num;row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;if(dfs(board) == true) return true;//恢复现场board[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;}}return false;}}}return true;}
};

7.单词搜索

单词搜索

class Solution {
public:bool vis[7][7];int m, n;bool exist(vector<vector<char>>& board, string word) {m = board.size(), n = board[0].size();for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board, i, j, word, 1)) return true;vis[i][j] = false;}}        return false;}int dx[4] = {0, 0, 1, -1};int dy[4] = {-1, 1, 0, 0};bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos){if(pos == word.size()) return true;//向量的方式定义上下四个位置for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board, x, y, word, pos + 1)) return true;vis[x][y] = false;}}return false;}
};

8.黄金矿工

黄金矿工

class Solution {
public:int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};bool vis[16][16];int m, n;int ret;int getMaximumGold(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(grid[i][j]){vis[i][j] = true;dfs(grid, i, j, grid[i][j]);vis[i][j] = false;}}return ret;}void dfs(vector<vector<int>>& grid, int i, int j, int path){ret = max(ret, path);for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]){vis[x][y] = true;dfs(grid, x, y, path + grid[x][y]);vis[x][y] = false;}}}
};

9.不同路径iii

不同路径iii

class Solution {
public:int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};bool vis[21][21];int m, n, ret, step;int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int bx = 0, by = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(grid[i][j] == 0) step++;else if(grid[i][j] == 1){bx = i;by = j;}}step += 2;vis[bx][by] = true;dfs(grid, bx, by, 1);return ret;}void dfs(vector<vector<int>>& grid, int i, int j, int count){if(grid[i][j] == 2){if(count == step) //判断是否合法{ret++;return;}}for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[i][j] != -1){vis[x][y] = true;dfs(grid, x, y, count + 1);vis[x][y] = false;}}}
};