77. 組合77. 組合77. 組合
給定兩個整數 n 和 k，回傳范圍 [1, n] 中所有可能的 k 個數的組合，
你可以按 任何順序 回傳答案，
思路：
如果解決一個問題有多個步驟，每一個步驟有多種方法，題目又要我們找出所有的方法，可以使用回溯演算法；
回溯演算法是在一棵樹上的 深度優先遍歷（因為要找所有的解，所以需要遍歷）；
為什么說是在一棵樹上的深度優先遍歷呢？比如說，你現在要解決一個問題，這個問題被分為了若干的步驟，對于每一個步驟都有多個方法到下一個步驟，（聽君一席話，就是一席話，嘿嘿嘿！！），就是說我們么一個步驟的選擇都是可以回傳來更換的，
就拿本題來說：
比如說給了4和3這兩個資料；我們要從1,2,3,4,這4個數里面取3個數，很容易分析出來：當我們第一個數取1的時候，第二個數可以去2,3,4,.........，一次推下去，我們會得到一棵一棵的樹，樣子就是這個樣子（這個不是我畫的，我去LeetCode的題解上找到哈哈哈哈！！）
想明白這個程序，那我們的解題辦法就來了，對于[1 n]里面的每一個數，在最后選擇的k個數里面的只有兩種狀態，要么它在，要么它不在，所以我們只需要去遍歷這n個數，然后用一個陣列temp把放入最后結果的數記錄下來，由于我們是從小到大遍歷，所以當我們把當前元素在最后結果里面的記錄完以后，后面再記錄的結果就不會再包含當前元素了，
class Solution {
public:
//temp 用來存放每一個可能的結果
vector<int> temp;
//最終結果
vector<vector<int>> ans;
//深度優先遍歷
void dfs(int cur, int n, int k) {
// 剪枝：當遍歷到底cur個數是，如果temp的元素個數s+剩余元素個數t<k時，就不滿足條件了
if (temp.size() + (n - cur + 1) < k) {
return;
}
// temp中元素個數達到k，表示深度優先遍歷到達最深處了，此時需要回溯了，
if (temp.size() == k) {
ans.push_back(temp);
return;
}
// 選擇當前位置，加入temp
temp.push_back(cur);
dfs(cur + 1, n, k);
// 不選擇當前位置，從temp里面洗掉
temp.pop_back();
dfs(cur + 1, n, k);
}
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
};46. 全排列
思路：通過上一題，這一題理解起來就更方便了，全部排列順序，就是上面的那個圖，第二次先選擇了2以后還可以繼續選擇1；所以我們只需要把每次選取的元素交換到陣列左邊，這樣就可以和上一題的流程一樣了，不過記住記住排列的時候，未選擇的元素都可以來占當前cur的位置，由于我們將未選擇的元素都交換到cur的右邊，所以從cur遍歷一遍就可以了，就是這么簡單，k默認為n就可以了，
class Solution {
public:
void dfs(vector<vector<int>>& res, vector<int>& output, int cur, int len){
// 所有數都填完了
if (cur == len) {
res.emplace_back(output);
return;
}
//這里每一個陣列右邊的數都可以當做第cur個元素
for (int i = cur; i < len; ++i) {
// 動態維護陣列，將未選取的元素交換到陣列右邊
swap(output[i], output[cur]);
// 繼續遞回填下一個數
dfs(res, output, cur + 1, len);
// 撤銷交換操作
swap(output[i], output[cur]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
dfs(res, nums, 0, (int)nums.size());
return res;
}
};
784. 字母大小寫全排列
給定一個字串S，通過將字串S中的每個字母轉變大小寫，我們可以獲得一個新的字串，回傳所有可能得到的字串集合，
思路： 注意理解題目要求，題目是說每個子母可以進行大小寫變換，但是沒有說可以改變位置哦，
class Solution {
public:
void dfs(vector<string> &res,int cur,string &s,int len){
//數字不變
while(cur<len&&s[cur] >= '0' && s[cur] <= '9')
cur++;
if(cur == len){
res.emplace_back(s);
return ;
}
//子母轉變大小寫
if(s[cur]>='a'&&s[cur]<='z')
s[cur] = toupper(s[cur]);
else
s[cur] = tolower(s[cur]);
dfs(res,cur+1,s,len);
//子母不轉變大小寫
if(s[cur]>='a'&&s[cur]<='z')
s[cur] = toupper(s[cur]);
else
s[cur] = tolower(s[cur]);
dfs(res,cur+1,s,len);
}
vector<string> letterCasePermutation(string s) {
vector<string> res;
int len = s.length();
dfs(res,0,s,len);
return res;
}
};蕪湖~~~~~~~~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/357035.html
標籤：其他
上一篇：LeetCode 677 鍵值映射[Map] HERODING的LeetCode之路
下一篇：Java狀況