1. 前言
后面的練習(xí)是接著下面鏈接中的文章所繼續(xù)的，在對后面的題練習(xí)之前，可以先將下面的的文章進行了解??：
【算法】{畫決策樹 + dfs + 遞歸 + 回溯 + 剪枝} 解決排列、子集問題（C++）
2. 算法題
22.括號生成
思路文章來源：http://www.zghlxwxcb.cn/news/detail-835610.html
-
題意分析：要求根據(jù)給出的數(shù)字，算出合法的括號組成個數(shù)。根據(jù)題目，我們可以總結(jié)出下面的規(guī)則：
- 解法：dfs + 根據(jù)決策樹設(shè)計遞歸、回溯、剪枝
-
決策樹：
- 根據(jù)上圖決策樹，即可直接著手編寫代碼：
-
細節(jié)問題：
代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-835610.html
class Solution {
public:
int left, right, _n; // 分別記錄左右括號的數(shù)量
vector<string> ret; // 結(jié)果數(shù)字
string path;
vector<string> generateParenthesis(int n) {
_n = n;
dfs();
return ret;
}
void dfs()
{
if(right == _n) // 當前path序列有效，加入結(jié)果
{
ret.push_back(path);
return;
}
if(left < _n) // 添加左括號
{
path.push_back('('); left++;
dfs();
path.pop_back(); left--;
}
if(right < left) // 添加右括號
{
path.push_back(')'); right++;
dfs();
path.pop_back(); right--;
}
}
};
494.目標和
思路
- 題意分析：對于數(shù)組給出的數(shù)字，通過向所有數(shù)字前補加減號，使最后的值為 target
-
解法：dfs + 根據(jù)決策樹設(shè)計遞歸、回溯、剪枝
- 該解法并非最優(yōu)解法，但這里依然用dfs做，并引出一些寫法問題。
- 決策樹：（省略了后面的步驟）
- 根據(jù)決策樹的思路，不難看出實際上與 題目 78.子集 非常相似，代碼也是如此，但有一個需要注意的細節(jié)，先看代碼：
代碼1
class Solution {
public:
int ret, path, _target;
int findTargetSumWays(vector<int>& nums, int target) {
_target = target;
dfs(nums, 0); // 從0位置開始
return ret;
}
void dfs(vector<int>& nums, int pos)
{
// 終止條件
if(pos == nums.size())
{
if(path == _target) ret++;
return;
}
// 正號
path += nums[pos];
dfs(nums, pos + 1);
path -= nums[pos];
// 負號
path -= nums[pos];
dfs(nums, pos + 1);
path += nums[pos];
}
};
- 最開始我們提到，深搜dfs并非該題的最優(yōu)解法， 時間開銷很大，對于上面的代碼，更是面臨超時的風(fēng)險，上面的代碼將 path作為全局變量
- 我們可以 進行優(yōu)化：將path作為參數(shù)傳遞
- 更改后的代碼，時間開銷會小一些
代碼2
class Solution {
public:
int ret, _target;
int findTargetSumWays(vector<int>& nums, int target) {
_target = target;
dfs(nums, 0, 0); // 從0位置開始
return ret;
}
void dfs(vector<int>& nums, int pos, int path)
{
// 終止條件
if(pos == nums.size())
{
if(path == _target) ret++;
return;
}
// 正號
dfs(nums, pos + 1, path + nums[pos]);
// 負號
dfs(nums, pos + 1, path - nums[pos]);
}
};
path定義形式的理由
- 頻繁的執(zhí)行 + - 操作，是一比不小的時間消耗，直接傳參可以只需要將計算后的結(jié)果直接作為參數(shù)遞歸。
- 而對于 [78.子集]，我們將path定義為全局變量，因為對于該題情況，path 本身為vector類型，作為參數(shù)傳遞會導(dǎo)致頻繁的創(chuàng)建vector，不利于節(jié)省時間。
39.組合總和
思路
- 題意分析：即通過給定的數(shù)組任意分配，組成和為目標值的序列，求序列的種類。
- 解法：dfs + 根據(jù)決策樹設(shè)計遞歸、回溯、剪枝
解法1
-
決策樹：如圖所示：
- 即每次分支都進行所有數(shù)字的選擇，符合條件的繼續(xù)，由于題目要去重，同層下選過的不再復(fù)選
- 剪枝：同層的選過的剪掉 + 該路徑和超出目標值或該位置超出數(shù)組范圍的剪掉
代碼
class Solution {
public:
int _target;
vector<int> path;
vector<vector<int>> ret;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int pathSum)
{
// 路徑和等于目標值，記錄結(jié)果，向上返回
if(pathSum == _target)
{
ret.push_back(path);
return;
}
// 路徑和大于目標值 / 當前位置超出數(shù)組； 向上返回
if(pathSum > _target || pos >= nums.size()) return;
for(int i = pos; i < nums.size(); ++i)
{
path.push_back(nums[i]);
dfs(nums, i, pathSum + nums[i]);
path.pop_back();
}
}
};
解法2
-
決策樹：
對于上圖，有一個需要注意的細節(jié)問題：
- 對于恢復(fù)現(xiàn)場：
此時我們可以編寫代碼：
代碼
class Solution {
public:
int _target;
vector<int> path;
vector<vector<int>> ret;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int pathSum)
{
// 路徑和等于目標值，記錄結(jié)果，向上返回
if(pathSum == _target)
{
ret.push_back(path);
return;
}
// 路徑和大于目標值 / 當前位置超出數(shù)組； 向上返回
if(pathSum > _target || pos >= nums.size()) return;
for(int k = 0; k * nums[pos] <= _target; ++k)
{
if(k) path.push_back(nums[pos]); // 枚舉 當前值的個數(shù)，添加到數(shù)組中
dfs(nums, pos + 1, pathSum + k*nums[pos]);
}
// 恢復(fù)現(xiàn)場
for(int k = 1; k * nums[pos] <= _target; ++k)
{
// 將每個元素添加過的個數(shù)值 都恢復(fù)
path.pop_back();
}
}
};
784.字母大小寫全排列
思路
- 題意分析：即返回所有轉(zhuǎn)換字母大小寫后的字符串
-
決策樹：如下圖所示
- 當當前位置是字母時，進行變與不變的分支，當是數(shù)字時，直接繼續(xù)，無分支，最后葉子節(jié)點處即為結(jié)果。
- 當當前位置是字母時，進行變與不變的分支，當是數(shù)字時，直接繼續(xù)，無分支，最后葉子節(jié)點處即為結(jié)果。
代碼
class Solution {
public:
string path; // 記錄當前字母序列
vector<string> ret;
vector<string> letterCasePermutation(string s) {
dfs(s, 0);
return ret;
}
void dfs(string s, int pos)
{
if(path.size() == s.size())
{
ret.push_back(path);
return;
}
char ch = s[pos];
// 不改變的情況：數(shù)字 以及 字母的第一種情況
path += ch;
dfs(s, pos + 1);
path.pop_back();
if(isalpha(ch)) // 需要改變
{
// 改變大小寫
if(ch <= 'z' && ch >= 'a') ch -= 32;
else ch += 32;
path += ch;
dfs(s, pos + 1);
path.pop_back();
}
}
};
526. 優(yōu)美的排列
思路
- 題意分析：即找出所有的符合規(guī)則（優(yōu)美排列）的排列
-
解法：利用全排列 與 規(guī)則
- 決策樹：這里不再畫決策樹了，相當于全排列的思路
- 全排列的思路即：如果該位置未被檢索過，則加入path中并繼續(xù)dfs
- 這里我們增加一條判定，即當前位置的下標與perm[i]滿足整除關(guān)系時，才進行dfs
代碼
class Solution {
public:
bool used[16];
int ret;
int countArrangement(int n) {
dfs(1, n); // 從下標為1處填n個數(shù)
return ret;
}
void dfs(int pos, int n)
{
if(pos == n + 1){ // 更新結(jié)果
ret += 1;
return;
}
// 全排列 + 判斷是否符合優(yōu)美排列
for(int i = 1; i <= n; ++i)
{
if(!used[i] && (i % pos == 0 || pos % i == 0))
{
used[i] = true;
dfs(pos + 1, n);
used[i] = false; // 恢復(fù)現(xiàn)場
}
}
}
};
到了這里，關(guān)于【算法】遞歸、回溯、剪枝、dfs 算法題練習(xí)（組合、排列、總和問題；C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
