一、括號生成
1、題目描述
leetcode鏈接
2、代碼
class Solution
{
public:
// 1、全局變量
string path;
vector<string> ret;
int right = 0, left = 0, n = 0;
vector<string> 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(); // 恢復(fù)現(xiàn)場
left--;
}
if(right < left) // 3、添加右括號
{
path.push_back(')');
right++;
dfs();
path.pop_back(); // 恢復(fù)現(xiàn)場
right--;
}
}
};
3、解析
二、組合
1、題目描述
leetcode鏈接
2、代碼
class Solution
{
public:
// 1、全局變量
int n = 0; // 1-n
int k = 0; // 幾個(gè)數(shù)
vector<int> path; // 路徑
vector<vector<int>> ret; // 增加的路徑函數(shù)
vector<vector<int>> combine(int _n, int _k)
{
n = _n;
k = _k;
dfs(1); // 2、dfs
return ret;
}
void dfs(int _pos)
{
// 1、函數(shù)遞歸出口
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下一個(gè)數(shù)進(jìn)行遞歸實(shí)現(xiàn)剪枝
path.pop_back(); // 回溯--恢復(fù)現(xiàn)場
}
}
};
3、解析
三、目標(biāo)和
1、題目描述
leetcode鏈接
2、代碼
全局變量的超時(shí)代碼：
原因在于nums的長度最長有20，其2^20次方太大了。但是leetcode居然通過了。
class Solution
{
public:
// 1、全局變量
int ret; // 返回
int aim; // 目標(biāo)值
int path; // 路徑
int findTargetSumWays(vector<int>& nums, int target)
{
aim = target;
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
// 1、遞歸出口
if(pos == nums.size())
{
if(path == aim)
{
ret++;
}
return;
}
// 2、加法
path += nums[pos];
dfs(nums, pos + 1);
path -= nums[pos]; // 恢復(fù)現(xiàn)場
// 3、減法
path -= nums[pos];
dfs(nums, pos + 1);
path += nums[pos]; // 恢復(fù)現(xiàn)場
}
};
path作為參數(shù)的正確代碼：
class Solution
{
public:
// 1、全局變量
int ret; // 返回
int aim; // 目標(biāo)值
int findTargetSumWays(vector<int>& nums, int target)
{
aim = target;
dfs(nums, 0, 0);
return ret;
}
void dfs(vector<int>& 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]; // 恢復(fù)現(xiàn)場
// 3、減法
path -= nums[pos];
dfs(nums, pos + 1, path);
path += nums[pos]; // 恢復(fù)現(xiàn)場
}
};
3、解析
四、組合總和
1、題目描述
leetcode鏈接
2、代碼
解法一：
class Solution
{
public:
// 1、全局變量
vector<vector<int>> ret; // 返回
vector<int> path; // 路徑
int aim; // 記錄target
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
aim = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int sum)
{
// 1、遞歸出口
if(sum == aim)
{
ret.push_back(path);
return;
}
if(sum > aim)
{
return;
}
// 循環(huán)
for(int i = pos; i < nums.size(); i++)
{
path.push_back(nums[i]);
sum += nums[i];
dfs(nums, i, sum); // 還是從開始
path.pop_back(); // 恢復(fù)現(xiàn)場
sum -= nums[i];
}
}
};
解法二：
class Solution
{
public:
// 1、全局變量
vector<vector<int>> ret; // 返回
vector<int> path; // 路徑
int aim; // 記錄target
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
aim = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int sum)
{
// 1、遞歸出口
if(sum == aim)
{
ret.push_back(path);
return;
}
if(sum > aim || pos == nums.size())
{
return;
}
// 循環(huán)
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]);
}
// 恢復(fù)現(xiàn)場
for(int k = 1; k * nums[pos] + sum <= aim; k++)
{
path.pop_back();
}
}
};
3、解析
解法一：
解法二：
五、字母大小寫全排列
1、題目描述
leetcode鏈接
2、代碼
class Solution
{
public:
// 全局變量
string path; // 路徑
vector<string> ret; // 返回
vector<string> letterCasePermutation(string s)
{
dfs(s, 0); // 將s這個(gè)字符串的第0個(gè)位置進(jìn)行傳參
return ret;
}
void dfs(string s, int pos)
{
// 遞歸出口
if(pos == s.length())
{
ret.push_back(path);
return;
}
// 先記錄一下當(dāng)前的字母
char ch = s[pos];
// 不改變
path.push_back(ch);
dfs(s, pos + 1);
path.pop_back(); // 恢復(fù)現(xiàn)場
// 改變
if(ch < '0' || ch > '9')
{
// 進(jìn)行改變大小寫函數(shù)
ch = Change(ch);
path.push_back(ch);
dfs(s, pos + 1); // 往下一層遞歸
path.pop_back(); // 恢復(fù)現(xiàn)場
}
}
char Change(char ch)
{
if(ch >= 'a' && ch <= 'z')
{
ch -= 32;
}
else
{
ch += 32;
}
return ch;
}
};
3、解析
六、優(yōu)美的排列
1、題目描述
leetcode鏈接
2、代碼
class Solution
{
public:
// 全局變量
int ret; // 返回
bool check[16]; // 判斷相對應(yīng)位置是true還是false
int countArrangement(int n)
{
dfs(1, n); // 下標(biāo)從1開始
return ret;
}
void dfs(int pos, int n)
{
// 遞歸出口
if(pos == n + 1) // 因?yàn)槭菑?開始的
{
ret++; // 只用做數(shù)的統(tǒng)計(jì)即可
return;
}
// 循環(huán)
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; // 恢復(fù)現(xiàn)場
}
}
}
};
3、解析
七、N皇后
1、題目描述
leetcode鏈接
2、代碼
class Solution
{
public:
// 全局變量
bool checkcol[10]; // 列
bool checkG1[20]; // 主對角線
bool checkG2[20]; // 副對角線
vector<string> path; // 路徑
vector<vector<string>> ret; // 返回
int n; // 全局變量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] == false/*一整列*/ && checkG1[row - col + n] == false/*y-x+n*/ && checkG2[row + col] == false/*y+x*/) // 判斷條件進(jìn)入
{
path[row][col] = 'Q';
checkcol[col] = checkG1[row - col + n] = checkG2[row + col] = true;
dfs(row + 1);
// 恢復(fù)現(xiàn)場
path[row][col] = '.';
checkcol[col] = checkG1[row - col + n] = checkG2[row + col] = false;
}
}
}
};
3、解析
這里我們著重在剪枝方面上面的講解，我們重點(diǎn)需要明白N皇后剪枝的作用，因?yàn)榛屎笫悄艹詸M的一整行，豎的一整列，主對角線和副對角線一整個(gè)，這里原本是要循環(huán)四次，但是我們經(jīng)過想法發(fā)現(xiàn)其實(shí)只需要判斷三個(gè)位置即可，第一個(gè)位置是豎著的，第二個(gè)位置是主對角線，第三個(gè)位置是副對角線，因?yàn)闄M著的一行是不需要進(jìn)行判斷的，因?yàn)槲覀兊乃悸肥且砸徽袨橐粋€(gè)視角，從左往右依次填的！我們根據(jù)簡單的數(shù)學(xué)原理，主對角線是y=x+b的，而由于會(huì)出現(xiàn)負(fù)數(shù)情況，我們左右兩邊各加一個(gè)n即可，我們此時(shí)b就為：y-x+n。我們副對角線是y=-x+b，我們的b為y+x即可！那我們接下來的思路畫出決策樹以后只需要考慮回溯的問題，我們恢復(fù)現(xiàn)場只需要將用過的全部變成沒用過的即可。
八、有效的數(shù)獨(dú)
1、題目描述
leetcode鏈接
文章來源：http://www.zghlxwxcb.cn/news/detail-830305.html
2、代碼
class Solution
{
public:
// 全局變量
bool row[9][10]; // 行坐標(biāo)加值
bool col[9][10]; // 列坐標(biāo)加值
bool grid[3][3][10]; // 棋盤坐標(biāo)加值
bool isValidSudoku(vector<vector<char>>& board)
{
for(int i = 0; i < 9; i++) // 行
{
for(int j = 0; j < 9; j++) // 列
{
if(board[i][j] != '.') // 數(shù)字的時(shí)候
{
int num = board[i][j] - '0'; // 記錄一下數(shù)
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、解析
文章來源地址http://www.zghlxwxcb.cn/news/detail-830305.html
到了這里，關(guān)于【leetcode】深搜、暴搜、回溯、剪枝（C++）2的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
