資訊專欄INFORMATION COLUMN
摘要：用來存放每一個可能的結果最終結果深度優先遍歷剪枝當遍歷到底個數是，如果的元素個數剩余元素個數時，就不滿足條件了中元素個數達到，表示深度優先遍歷到達最深處了。
給定兩個整數?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 temp; //最終結果 vector> ans; //深度優先遍歷 void dfs(int cur, int n, int k) { // 剪枝：當遍歷到底cur個數是，如果temp的元素個數s+剩余元素個數t> combine(int n, int k) { dfs(1, n, k); return ans; }}; 思路：通過上一題，這一題理解起來就更方便了。全部排列順序，就是上面的那個圖，第二次先選擇了2以后還可以繼續選擇1；所以我們只需要把每次選取的元素交換到數組左邊，這樣就可以和上一題的流程一樣了，不過記住記住排列的時候，未選擇的元素都可以來占當前cur的位置，由于我們將未選擇的元素都交換到cur的右邊，所以從cur遍歷一遍就可以了。就是這么簡單，k默認為n就可以了。
class Solution {public: void dfs(vector>& res, vector& 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> permute(vector& nums) { vector > res; dfs(res, nums, 0, (int)nums.size()); return res; }}; 給定一個字符串S，通過將字符串S中的每個字母轉變大小寫，我們可以獲得一個新的字符串。返回所有可能得到的字符串集合。
思路： 注意理解題目要求，題目是說每個子母可以進行大小寫變換，但是沒有說可以改變位置哦。
class Solution {public: void dfs(vector &res,int cur,string &s,int len){ //數字不變 while(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 letterCasePermutation(string s) { vector res; int len = s.length(); dfs(res,0,s,len); return res; }}; 蕪湖~~~~~~~~~
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/123336.html
摘要：斬從第題開始，到現在也差不多快一年了，回顧紀念一下。當時對回溯動態規劃也都只是上課的時候學過，也并不熟練。最經典的例子就是斐波那契數列了，求第項數列的值。 leetcode 100 斬！從第 1 題開始，到現在也差不多快一年了，回顧紀念一下。 showImg(https://segmentfault.com/img/bVbu461?w=661&h=191); 為什么開始刷題？ 從大一就...
摘要：現在發出來的版本，我重新使用了語言實現。其實我之前介紹的老師課程也大量參考和使用算法這本書上的思路和例題。看這本書主要是讓我覺得算法可以以比較輕松的方式入門。劍指這本書主要用于準備算法面試，在網絡上備受好評。 我是一個半路出家的程序員，在我剛開始從事編碼工作的頭幾年，我沒有接觸過算法和數據結構，覺得它們是只會在我找工作的時候用得到的知識。盡管有很多人跟我說過算法和數據結構無比重要，我也...
馬上就要開始啦這次共組織15個組隊學習 涵蓋了AI領域從理論知識到動手實踐的內容 按照下面給出的最完備學習路線分類 難度系數分為低、中、高三檔 可以按照需要參加 - 學習路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...
閱讀 2611·2021-11-18 10:02
閱讀 2639·2021-11-15 11:38
閱讀 3718·2021-11-12 10:36
閱讀 708·2021-11-12 10:34
閱讀 2910·2021-10-21 09:38
閱讀 1499·2021-09-29 09:48
閱讀 1508·2021-09-29 09:34
閱讀 1103·2021-09-22 10:02
