酒泉市住房和城乡建设局网站,邯郸最穷的三个县,如何查看网站的点击量,徐州英才网最新招聘信息深搜、暴搜、回溯、剪枝#xff08;C#xff09;2 一、括号生成1、题目描述2、代码3、解析 二、组合1、题目描述2、代码3、解析 三、目标和1、题目描述2、代码3、解析 四、组合总和1、题目描述2、代码3、解析 五、字母大小写全排列1、题目描述2、代码3、解析 六、优美的排列1… 深搜、暴搜、回溯、剪枝C2 一、括号生成1、题目描述2、代码3、解析 二、组合1、题目描述2、代码3、解析 三、目标和1、题目描述2、代码3、解析 四、组合总和1、题目描述2、代码3、解析 五、字母大小写全排列1、题目描述2、代码3、解析 六、优美的排列1、题目描述2、代码3、解析 七、N皇后1、题目描述2、代码3、解析 八、有效的数独1、题目描述2、代码3、解析 一、括号生成
1、题目描述
leetcode链接
2、代码
class Solution
{
public:// 1、全局变量string path;vectorstring ret;int right 0, left 0, n 0;vectorstring generateParenthesis(int _n) {n _n;dfs();return ret;}void dfs(){// 1、出口if(right n){ret.push_back(path);return;}// 2、添加左括号if(left n){path.push_back(();left;dfs();path.pop_back(); // 恢复现场left--;}if(right left) // 3、添加右括号{path.push_back());right;dfs();path.pop_back(); // 恢复现场right--;}}
};3、解析 二、组合
1、题目描述
leetcode链接 2、代码
class Solution
{
public:// 1、全局变量int n 0; // 1-nint k 0; // 几个数vectorint path; // 路径vectorvectorint ret; // 增加的路径函数vectorvectorint combine(int _n, int _k) {n _n;k _k;dfs(1); // 2、dfsreturn ret;}void dfs(int _pos){// 1、函数递归出口if(path.size() k){ret.push_back(path);return;}// 2、遍历--剪枝for(int pos _pos; pos n; pos){path.push_back(pos);dfs(pos 1); // pos下一个数进行递归实现剪枝path.pop_back(); // 回溯--恢复现场 }}
};3、解析 三、目标和
1、题目描述
leetcode链接
2、代码
全局变量的超时代码 原因在于nums的长度最长有20其2^20次方太大了。但是leetcode居然通过了。
class Solution
{
public:// 1、全局变量int ret; // 返回int aim; // 目标值int path; // 路径int findTargetSumWays(vectorint nums, int target) {aim target;dfs(nums, 0);return ret;}void dfs(vectorint nums, int pos){// 1、递归出口if(pos nums.size()){if(path aim){ret;}return;}// 2、加法path nums[pos];dfs(nums, pos 1);path - nums[pos]; // 恢复现场// 3、减法path - nums[pos];dfs(nums, pos 1);path nums[pos]; // 恢复现场}
};path作为参数的正确代码
class Solution
{
public:// 1、全局变量int ret; // 返回int aim; // 目标值int findTargetSumWays(vectorint nums, int target) {aim target;dfs(nums, 0, 0);return ret;}void dfs(vectorint nums, int pos, int path){// 1、递归出口if(pos nums.size()){if(path aim){ret;}return;}// 2、加法path nums[pos];dfs(nums, pos 1, path);path - nums[pos]; // 恢复现场// 3、减法path - nums[pos];dfs(nums, pos 1, path);path nums[pos]; // 恢复现场}
};3、解析 四、组合总和
1、题目描述
leetcode链接
2、代码
解法一
class Solution
{
public:// 1、全局变量vectorvectorint ret; // 返回vectorint path; // 路径int aim; // 记录targetvectorvectorint combinationSum(vectorint candidates, int target) {aim target;dfs(candidates, 0, 0);return ret;}void dfs(vectorint nums, int pos, int sum){// 1、递归出口if(sum aim){ret.push_back(path);return;}if(sum aim){return;}// 循环for(int i pos; i nums.size(); i){path.push_back(nums[i]);sum nums[i];dfs(nums, i, sum); // 还是从开始path.pop_back(); // 恢复现场sum - nums[i];}}
};解法二
class Solution
{
public:// 1、全局变量vectorvectorint ret; // 返回vectorint path; // 路径int aim; // 记录targetvectorvectorint combinationSum(vectorint candidates, int target) {aim target;dfs(candidates, 0, 0);return ret;}void dfs(vectorint nums, int pos, int sum){// 1、递归出口if(sum aim){ret.push_back(path);return;}if(sum aim || pos nums.size()){return;}// 循环for(int k 0; k * nums[pos] sum aim; k){if(k){path.push_back(nums[pos]);}dfs(nums, pos 1, sum k * nums[pos]);}// 恢复现场for(int k 1; k * nums[pos] sum aim; k){path.pop_back();}}
};3、解析
解法一 解法二
五、字母大小写全排列
1、题目描述
leetcode链接
2、代码
class Solution
{
public:// 全局变量string path; // 路径vectorstring ret; // 返回vectorstring letterCasePermutation(string s) {dfs(s, 0); // 将s这个字符串的第0个位置进行传参return ret;}void dfs(string s, int pos){// 递归出口if(pos s.length()){ret.push_back(path);return;}// 先记录一下当前的字母char ch s[pos];// 不改变path.push_back(ch);dfs(s, pos 1);path.pop_back(); // 恢复现场// 改变if(ch 0 || ch 9){// 进行改变大小写函数ch Change(ch);path.push_back(ch);dfs(s, pos 1); // 往下一层递归path.pop_back(); // 恢复现场}}char Change(char ch){if(ch a ch z){ch - 32;}else{ch 32;}return ch;}
};3、解析 六、优美的排列
1、题目描述
leetcode链接
2、代码
class Solution
{
public:// 全局变量int ret; // 返回bool check[16]; // 判断相对应位置是true还是falseint countArrangement(int n) {dfs(1, n); // 下标从1开始return ret;}void dfs(int pos, int n){// 递归出口if(pos n 1) // 因为是从1开始的{ret; // 只用做数的统计即可return;}// 循环for(int i 1; i n; i){if(check[i] false (pos % i 0 || i % pos 0)){check[i] true; // 表示用了dfs(pos 1, n); // 递归到下一层check[i] false; // 恢复现场}}}
};3、解析 七、N皇后
1、题目描述
leetcode链接 2、代码
class Solution
{
public:// 全局变量bool checkcol[10]; // 列bool checkG1[20]; // 主对角线bool checkG2[20]; // 副对角线vectorstring path; // 路径vectorvectorstring ret; // 返回int n; // 全局变量nvectorvectorstring 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] false/*一整列*/ checkG1[row - col n] false/*y-xn*/ checkG2[row col] false/*yx*/) // 判断条件进入{path[row][col] Q;checkcol[col] checkG1[row - col n] checkG2[row col] true;dfs(row 1);// 恢复现场path[row][col] .;checkcol[col] checkG1[row - col n] checkG2[row col] false;}}}
};3、解析
这里我们着重在剪枝方面上面的讲解我们重点需要明白N皇后剪枝的作用因为皇后是能吃横的一整行竖的一整列主对角线和副对角线一整个这里原本是要循环四次但是我们经过想法发现其实只需要判断三个位置即可第一个位置是竖着的第二个位置是主对角线第三个位置是副对角线因为横着的一行是不需要进行判断的因为我们的思路是以一整行为一个视角从左往右依次填的我们根据简单的数学原理主对角线是yxb的而由于会出现负数情况我们左右两边各加一个n即可我们此时b就为y-xn。我们副对角线是y-xb我们的b为yx即可那我们接下来的思路画出决策树以后只需要考虑回溯的问题我们恢复现场只需要将用过的全部变成没用过的即可。
八、有效的数独
1、题目描述
leetcode链接
2、代码
class Solution
{
public:// 全局变量bool row[9][10]; // 行坐标加值bool col[9][10]; // 列坐标加值bool grid[3][3][10]; // 棋盘坐标加值bool isValidSudoku(vectorvectorchar 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] true || col[j][num] true || grid[i / 3][j / 3][num] true){return false;}row[i][num] col[j][num] grid[i / 3][j / 3][num] true;}}}return true;}
};3、解析
