日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
遞增子序列，有點(diǎn)難度！

給定一個(gè)整型數(shù)組, 你的任務(wù)是找到所有該數(shù)組的遞增子序列，遞增子序列的長度至少是2。

成都創(chuàng)新互聯(lián)公司自2013年起，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都做網(wǎng)站、網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢想脫穎而出為使命，1280元賓縣做網(wǎng)站,已為上家服務(wù),為賓縣各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575

示例:

  • 輸入: [4, 6, 7, 7]
  • 輸出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

說明:

  • 給定數(shù)組的長度不會(huì)超過15。
  • 數(shù)組中的整數(shù)范圍是 [-100,100]。
  • 給定數(shù)組中可能包含重復(fù)數(shù)字，相等的數(shù)字應(yīng)該被視為遞增的一種情況。

思路

這個(gè)遞增子序列比較像是取有序的子集。而且本題也要求不能有相同的遞增子序列。

這又是子集，又是去重，是不是不由自主的想起了剛剛講過的90.子集II。

就是因?yàn)樘窳?，更要注意差別所在，要不就掉坑里了!

在90.子集II中我們是通過排序，再加一個(gè)標(biāo)記數(shù)組來達(dá)到去重的目的。

而本題求自增子序列，是不能對(duì)原數(shù)組經(jīng)行排序的，排完序的數(shù)組都是自增子序列了。

所以不能使用之前的去重邏輯!

本題給出的示例，還是一個(gè)有序數(shù)組 [4, 6, 7, 7]，這更容易誤導(dǎo)大家按照排序的思路去做了。

為了有鮮明的對(duì)比，我用[4, 7, 6, 7]這個(gè)數(shù)組來舉例，抽象為樹形結(jié)構(gòu)如圖：

遞增子序列1

回溯三部曲

  • 遞歸函數(shù)參數(shù)

本題求子序列，很明顯一個(gè)元素不能重復(fù)使用，所以需要startIndex，調(diào)整下一層遞歸的起始位置。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. vector> result;
    2. 
  
  
  
  
  2. vector path;
    3. 
  
  
  
  
  3. void backtracking(vector& nums, int startIndex)
    4.
  • 終止條件

本題其實(shí)類似求子集問題，也是要遍歷樹形結(jié)構(gòu)找每一個(gè)節(jié)點(diǎn)，所以和回溯算法：求子集問題!一樣，可以不加終止條件，startIndex每次都會(huì)加1，并不會(huì)無限遞歸。

但本題收集結(jié)果有所不同，題目要求遞增子序列大小至少為2，所以代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (path.size() > 1) {
    2. 
  
  
  
  
  2.     result.push_back(path);
    3. 
  
  
  
  
  3.     // 注意這里不要加return，因?yàn)橐渖系乃泄?jié)點(diǎn)
    4. 
  
  
  
  
  4. }
    5.
  • 單層搜索邏輯

在圖中可以看出，同一父節(jié)點(diǎn)下的同層上使用過的元素就不能在使用了

那么單層搜索代碼如下：

 
 
 
 
    
  
  
  
  
  1. unordered_set uset; // 使用set來對(duì)本層元素進(jìn)行去重
    2. 
  
  
  
  
  2. for (int i = startIndex; i < nums.size(); i++) {
    3. 
  
  
  
  
  3.     if ((!path.empty() && nums[i] < path.back())
    4. 
  
  
  
  
  4.             || uset.find(nums[i]) != uset.end()) {
    5. 
  
  
  
  
  5.             continue;
    6. 
  
  
  
  
  6.     }
    7. 
  
  
  
  
  7.     uset.insert(nums[i]); // 記錄這個(gè)元素在本層用過了，本層后面不能再用了
    8. 
  
  
  
  
  8.     path.push_back(nums[i]);
    9. 
  
  
  
  
  9.     backtracking(nums, i + 1);
    10. 
  
  
  
  
  10.     path.pop_back();
    11. 
  
  
  
  
  11. }
    12.

對(duì)于已經(jīng)習(xí)慣寫回溯的同學(xué)，看到遞歸函數(shù)上面的uset.insert(nums[i]);，下面卻沒有對(duì)應(yīng)的pop之類的操作，應(yīng)該很不習(xí)慣吧，哈哈

這也是需要注意的點(diǎn)，unordered_set uset; 是記錄本層元素是否重復(fù)使用，新的一層uset都會(huì)重新定義(清空)，所以要知道uset只負(fù)責(zé)本層!

最后整體C++代碼如下：

 
 
 
 
    
  
  
  
  
  1. // 版本一
    2. 
  
  
  
  
  2. class Solution {
    3. 
  
  
  
  
  3. private:
    4. 
  
  
  
  
  4.     vector> result;
    5. 
  
  
  
  
  5.     vector path;
    6. 
  
  
  
  
  6.     void backtracking(vector& nums, int startIndex) {
    7. 
  
  
  
  
  7.         if (path.size() > 1) {
    8. 
  
  
  
  
  8.             result.push_back(path);
    9. 
  
  
  
  
  9.             // 注意這里不要加return，要取樹上的節(jié)點(diǎn)
    10. 
  
  
  
  
  10.         }
    11. 
  
  
  
  
  11.         unordered_set uset; // 使用set對(duì)本層元素進(jìn)行去重
    12. 
  
  
  
  
  12.         for (int i = startIndex; i < nums.size(); i++) {
    13. 
  
  
  
  
  13.             if ((!path.empty() && nums[i] < path.back())
    14. 
  
  
  
  
  14.                     || uset.find(nums[i]) != uset.end()) {
    15. 
  
  
  
  
  15.                     continue;
    16. 
  
  
  
  
  16.             }
    17. 
  
  
  
  
  17.             uset.insert(nums[i]); // 記錄這個(gè)元素在本層用過了，本層后面不能再用了
    18. 
  
  
  
  
  18.             path.push_back(nums[i]);
    19. 
  
  
  
  
  19.             backtracking(nums, i + 1);
    20. 
  
  
  
  
  20.             path.pop_back();
    21. 
  
  
  
  
  21.         }
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23. public:
    24. 
  
  
  
  
  24.     vector> findSubsequences(vector& nums) {
    25. 
  
  
  
  
  25.         result.clear();
    26. 
  
  
  
  
  26.         path.clear();
    27. 
  
  
  
  
  27.         backtracking(nums, 0);
    28. 
  
  
  
  
  28.         return result;
    29. 
  
  
  
  
  29.     }
    30. 
  
  
  
  
  30. };
    31.

優(yōu)化

以上代碼用我用了unordered_set 來記錄本層元素是否重復(fù)使用。

其實(shí)用數(shù)組來做哈希，效率就高了很多。

注意題目中說了，數(shù)值范圍[-100,100]，所以完全可以用數(shù)組來做哈希。

程序運(yùn)行的時(shí)候?qū)nordered_set 頻繁的insert，unordered_set需要做哈希映射(也就是把key通過hash function映射為唯一的哈希值)相對(duì)費(fèi)時(shí)間，而且每次重新定義set，insert的時(shí)候其底層的符號(hào)表也要做相應(yīng)的擴(kuò)充，也是費(fèi)事的。

那么優(yōu)化后的代碼如下：

 
 
 
 
    
  
  
  
  
  1. // 版本二
    2. 
  
  
  
  
  2. class Solution {
    3. 
  
  
  
  
  3. private:
    4. 
  
  
  
  
  4.     vector> result;
    5. 
  
  
  
  
  5.     vector path;
    6. 
  
  
  
  
  6.     void backtracking(vector& nums, int startIndex) {
    7. 
  
  
  
  
  7.         if (path.size() > 1) {
    8. 
  
  
  
  
  8.             result.push_back(path);
    9. 
  
  
  
  
  9.         }
    10. 
  
  
  
  
  10.         int used[201] = {0}; // 這里使用數(shù)組來進(jìn)行去重操作，題目說數(shù)值范圍[-100, 100]
    11. 
  
  
  
  
  11.         for (int i = startIndex; i < nums.size(); i++) {
    12. 
  
  
  
  
  12.             if ((!path.empty() && nums[i] < path.back())
    13. 
  
  
  
  
  13.                     || used[nums[i] + 100] == 1) {
    14. 
  
  
  
  
  14.                     continue;
    15. 
  
  
  
  
  15.             }
    16. 
  
  
  
  
  16.             used[nums[i] + 100] = 1; // 記錄這個(gè)元素在本層用過了，本層后面不能再用了
    17. 
  
  
  
  
  17.             path.push_back(nums[i]);
    18. 
  
  
  
  
  18.             backtracking(nums, i + 1);
    19. 
  
  
  
  
  19.             path.pop_back();
    20. 
  
  
  
  
  20.         }
    21. 
  
  
  
  
  21.     }
    22. 
  
  
  
  
  22. public:
    23. 
  
  
  
  
  23.     vector> findSubsequences(vector& nums) {
    24. 
  
  
  
  
  24.         result.clear();
    25. 
  
  
  
  
  25.         path.clear();
    26. 
  
  
  
  
  26.         backtracking(nums, 0);
    27. 
  
  
  
  
  27.         return result;
    28. 
  
  
  
  
  28.     }
    29. 
  
  
  
  
  29. };
    30.

這份代碼在leetcode上提交，要比版本一耗時(shí)要好的多。

所以正如在哈希表：總結(jié)篇!(每逢總結(jié)必經(jīng)典)中說的那樣，數(shù)組，set，map都可以做哈希表，而且數(shù)組干的活，map和set都能干，但如果數(shù)值范圍小的話能用數(shù)組盡量用數(shù)組。

總結(jié)

本題題解清一色都說是深度優(yōu)先搜索，但我更傾向于說它用回溯法，而且本題我也是完全使用回溯法的邏輯來分析的。

相信大家在本題中處處都能看到是90.子集II的身影，但處處又都是陷阱。

對(duì)于養(yǎng)成思維定式或者套模板套嗨了的同學(xué)，這道題起到了很好的警醒作用。更重要的是拓展了大家的思路!

就醬，如果感覺「代碼隨想錄」很干貨，就幫Carl宣傳一波吧!

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。


分享標(biāo)題：遞增子序列，有點(diǎn)難度！
標(biāo)題路徑：http://www.dlmjj.cn/article/cdooged.html