【C++刷题】优选算法——递归第二辑

1. 全排列

vector<vector<int>> vv;
void dfs(vector<int>& nums, vector<int>& v, vector<bool>& check)
{if(v.size() == nums.size()){vv.push_back(v);return;}for(int i = 0; i < nums.size(); ++i){if(check[i] == false){v.push_back(nums[i]);check[i] = true;dfs(nums, v, check);// 回溯 -- 恢复现场v.pop_back();check[i] = false;}}
}
vector<vector<int>> permute(vector<int>& nums) 
{vector<int> v;vector<bool> check(nums.size(), false);dfs(nums, v, check);return vv;
}

2. 子集

// 解法一
vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& nums, int step)
{if(step == nums.size()){vv.push_back(v);return;}// 不选 nums[step]dfs(nums, step + 1);// 选 nums[step]v.push_back(nums[step]);dfs(nums, step + 1);v.pop_back();
}
vector<vector<int>> subsets(vector<int>& nums)
{dfs(nums, 0);return vv;
}// 解法二
vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& nums, int step)
{vv.push_back(v);for(int i = step; i < nums.size(); ++i){v.push_back(nums[i]);dfs(nums, i + 1);v.pop_back();}
}
vector<vector<int>> subsets(vector<int>& nums)
{dfs(nums, 0);return vv;
}

3. 找出所有子集的异或总和再求和

int total = 0;
int val = 0;
void dfs(vector<int>& nums, int step = 0)
{total += val;for(int i = step; i < nums.size(); ++i){val ^= nums[i];dfs(nums, i + 1);val ^= nums[i];}
}
int subsetXORSum(vector<int>& nums)
{dfs(nums, 0);return total;
}

4. 全排列 II

vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& nums, vector<bool>& check)
{if(v.size() == nums.size()){vv.push_back(v);return;}for(int i = 0; i < nums.size(); ++i){if(check[i] == false){if(i == 0 || check[i-1] == true || nums[i-1] != nums[i]){v.push_back(nums[i]);check[i] = true;dfs(nums, check);check[i] = false;v.pop_back();}}}
}
vector<vector<int>> permuteUnique(vector<int>& nums)
{sort(nums.begin(), nums.end());vector<bool> check(nums.size(), false);dfs(nums, check);return vv;
}

5. 电话号码的字母组合

unordered_map<char, string> m = {{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}
};
vector<string> vs;
string s;
void dfs(string& digits, int step)
{if(step == digits.size()){vs.push_back(s);return;}for(int i = 0; i < m[digits[step]].size(); ++i){s += m[digits[step]][i];dfs(digits, step + 1);s.pop_back();}
}
vector<string> letterCombinations(string digits)
{if(digits.size() == 0) return vs;dfs(digits, 0);return vs;
}

6. 括号生成

vector<string> vs;
string s;
void dfs(int left, int right)
{if(right == 0){vs.push_back(s);return;}if(left > 0){s += "(";dfs(left - 1, right);s.pop_back();}if(right > left){s += ")";dfs(left, right - 1);s.pop_back();}
}
vector<string> generateParenthesis(int n)
{dfs(n, n);return vs;
}

7. 组合

vector<vector<int>> vv;
vector<int> v;
void dfs(int n, int k, int step)
{if(v.size() == k){vv.push_back(v);return;}for(int i = step; i <= n; ++i){v.push_back(i);dfs(n, k, i + 1);v.pop_back();}
}
vector<vector<int>> combine(int n, int k)
{dfs(n, k, 1);return vv;
}

8. 目标和

int ret = 0;
void dfs(vector<int>& nums, int target, int step, int sum)
{if(step == nums.size()){if(sum == target) ret += 1;return;}dfs(nums, target, step + 1, sum + nums[step]);dfs(nums, target, step + 1, sum - nums[step]);
}
int findTargetSumWays(vector<int>& nums, int target)
{dfs(nums, target, 0, 0);return ret;
}

9. 组合总和

vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& candidates, int target, int step, int sum)
{if(sum > target) return;if(sum == target){vv.push_back(v);return;}for(int i = step; i < candidates.size(); ++i){v.push_back(candidates[i]);dfs(candidates, target, i, sum + candidates[i]);v.pop_back();}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{dfs(candidates, target, 0, 0);return vv;
}

10. 字母大小写全排列

vector<string> vs;
string path;
void dfs(string& s, int step)
{if(step == s.size()){vs.push_back(path);return;}path += s[step];dfs(s, step + 1);path.pop_back();if(s[step] >= 'a' && s[step] <= 'z'){path += toupper(s[step]);dfs(s, step + 1);path.pop_back();}else if(s[step] >= 'A' && s[step] <= 'Z'){path += tolower(s[step]);dfs(s, step + 1);path.pop_back();}
}
vector<string> letterCasePermutation(string s)
{dfs(s, 0);return vs;
}

11. 优美的排列

int ret = 0;
void dfs(int n, int step, vector<bool>& check)
{if(step > n) ret += 1;for(int i = 1; i <= n; ++i){if(check[i] == false){if(i % step == 0 || step % i == 0){check[i] = true;dfs(n, step + 1, check);check[i] = false;}}}
}
int countArrangement(int n)
{vector<bool> check(n + 1, false);dfs(n, 1, check);return ret;
}

12. N 皇后

vector<vector<string>> vvs;
void dfs(vector<string>& vs, vector<vector<bool>*>& check3, int step)
{if(step == vs.size()){vvs.push_back(vs);return;}for(int j = 0; j < vs.size(); ++j){if((*check3[0])[j] == false && (*check3[1])[step - j + vs.size() - 1] == false&& (*check3[2])[step+j] == false){(*check3[0])[j] = (*check3[1])[step - j + vs.size() - 1] = (*check3[2])[step+j] = true;vs[step][j] = 'Q';dfs(vs, check3, step + 1);vs[step][j] = '.';(*check3[0])[j] = (*check3[1])[step - j + vs.size() - 1] = (*check3[2])[step+j] = false;}}
}
vector<vector<string>> solveNQueens(int n)
{vector<string> vs(n);for(int i = 0; i < n; ++i)vs[i].append(n, '.');vector<vector<bool>*> check3 = {new vector<bool>(n, false),new vector<bool>(2 * n - 1, false),new vector<bool>(2 * n - 1, false)};dfs(vs, check3, 0);delete check3[0];delete check3[1];delete check3[2];return vvs;
}

13. 解数独

vector<vector<bool>>* row = new vector<vector<bool>>(10, vector<bool>(10, false));
vector<vector<bool>>* col = new vector<vector<bool>>(10, vector<bool>(10, false));
vector<vector<vector<bool>>>* check = new vector<vector<vector<bool>>>(3, vector<vector<bool>>(3, vector<bool>(10, false)));
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 n = 1; n <= 9; ++n){if(!(*row)[i][n] && !(*col)[j][n] && !(*check)[i/3][j/3][n]){board[i][j] = '0' + n;(*row)[i][n] = (*col)[j][n] = (*check)[i / 3][j / 3][n] = true;if(dfs(board) == true) return true;board[i][j] = '.';(*row)[i][n] = (*col)[j][n] = (*check)[i / 3][j / 3][n] = false;}}return false;}}}return true;
}
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] = (*check)[i / 3][j / 3][num] = true;}}}dfs(board);delete row;delete col;delete check;
}

14. 单词搜索

unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
// 循环 - 方式
bool dfs(vector<vector<char>>& board, string& word, vector<vector<bool>>& visit, int i, int j, int step)
{if(step == word.size()) return true;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < board.size())&& (y >= 0 && y < board[0].size())&& (visit[x][y] == false)&& (board[x][y] == word[step])){visit[x][y] = true;if(dfs(board, word, visit, x, y, step + 1)) return true;visit[x][y] = false;}}return false;
}
// 分支 - 方式
bool dfs(vector<vector<char>>& board, string& word, vector<vector<bool>>& visit, int i, int j, int step)
{if(step == word.size()) return true;        if(i - 1 >= 0 && visit[i-1][j] == false && board[i-1][j] == word[step]){visit[i-1][j] = true;if(dfs(board, word, visit, i - 1, j, step + 1)) return true;visit[i-1][j] = false;}if(i + 1 < board.size() && visit[i+1][j] == false && board[i+1][j] == word[step]){visit[i+1][j] = true;if(dfs(board, word, visit, i + 1, j, step + 1)) return true;visit[i+1][j] = false;}if(j - 1 >= 0 && visit[i][j-1] == false && board[i][j-1] == word[step]){visit[i][j-1] = true;if(dfs(board, word, visit, i, j - 1, step + 1)) return true;visit[i][j-1] = false;}if(j + 1 < board[0].size() && visit[i][j+1] == false && board[i][j+1] == word[step]){visit[i][j+1] = true;if(dfs(board, word, visit, i, j + 1, step + 1)) return true;visit[i][j+1] = false;}return false;
}
bool exist(vector<vector<char>>& board, string word)
{vector<vector<bool>> visit = vector<vector<bool>>(board.size(), vector<bool>(board[0].size(), false));for(int i = 0; i < board.size(); ++i){for(int j = 0; j < board[0].size(); ++j){if(board[i][j] == word[0]){visit[i][j] = true;if(dfs(board, word, visit, i, j, 1)) return true;visit[i][j] = false;}}}return false;
}

15. 黄金矿工

int ret = 0;
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int i, int j, int quantity)
{if(quantity > ret) ret = quantity;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < grid.size())&& (y >= 0 && y < grid[0].size())&& (visit[x][y] == false)&& (grid[x][y] != 0)){visit[x][y] = true;dfs(grid, visit, x, y, quantity + grid[x][y]);visit[x][y] = false;}}
}
int getMaximumGold(vector<vector<int>>& grid)
{vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size(), false));for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] != 0){visit[i][j] = true;dfs(grid, visit, i, j, grid[i][j]);visit[i][j] = false;}}}return ret;
}

16. 不同路径 III

int ret = 0;
int count = 0;
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, 
int i, int j, int step)
{if(grid[i][j] == 2){if(count == step) ret += 1;return;}for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < grid.size())&& (y >= 0 && y < grid[0].size())&& (visit[x][y] == false)&& (grid[x][y] != -1)){visit[x][y] = true;dfs(grid, visit, x, y, step + 1);visit[x][y] = false;}}
}
int uniquePathsIII(vector<vector<int>>& grid)
{vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size()));int si, sj;for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] != -1) ++count;if(grid[i][j] == 1){si = i;sj = j;}}}visit[si][sj] = true;dfs(grid, visit, si, sj, 1);return ret;
}