專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

一網友發文稱自己所在公司部門人員的學歷都是高配版的，學歷最差的就是他自己，中央民族大學。

實際上這種情況在大廠很常見，2024屆大廠校招中，985和211的比例分別為50%+和30%+?。此外，投遞者中985和211高校學生占比高達82.4%?2。所以那些經常說學歷無用論的不要在自欺欺人了。

互聯網大廠在招聘時傾向于選擇985和211高校的畢業生，這可能與這些高校的教育質量和畢業生綜合素質較高有關。大廠通常要求應聘者具備較高的學歷背景和專業技能，因此985和211高校的畢業生更容易滿足這些要求。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第491題：非遞減子序列。

問題描述

來源：LeetCode第491題

難度：中等

給你一個整數數組 nums ，找出并返回所有該數組中不同的 遞增子序列 ，遞增子序列中至少有兩個元素 。你可以按任意順序返回答案。數組中可能含有重復元素，如出現兩個整數相等，也可以視作遞增序列的一種特殊情況。

示例1：

輸入：nums = [4,6,7,7] 輸出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例2：

輸入：nums = [4,4,3,2,1] 輸出：[[4,4]]

• 1 <= nums.length <= 15

• -100 <= nums[i] <= 100

問題分析

這題讓找出數組中所有的遞增子序列，和之前講的 非常類似，但這里數組中也有會有重復的元素。

因為這里求的是子序列，所以數組是不能排序的，我們可以使用集合set來剪枝。

子序列的選擇過程可以把它看作是一顆樹，比如第一層我們可以選擇任何數字，從第二層開始每次只能選擇當前數字后面的數字。

如下圖所示，對于每一顆子樹，如果有相同的子節點，我們只選擇一個，比如下圖中根節點為 7 的子樹，前面的會包含后面的，出現了重復，所以需要把后面的剪掉。

JAVA：

public List
         
 > findSubsequences( int[] nums) {     List > ans =  new ArrayList<>();     dfs(ans, nums,  new ArrayList<>(),  0);      return ans; } private void dfs(List > ans,  int[] nums, List  path,  int index)  {      if (path.size() >  1)         ans.add( new ArrayList<>(path));      // 記錄當前層并且具有共同父節點的所有節點，不能有重復的。     Set  set =  new HashSet<>();      for ( int i = index; i < nums.length; i++) {          if (!set.add(nums[i])) // 跳過重復的              continue;          // 必須是非遞減的才可以選擇          if (path.isEmpty() || nums[i] >= path.get(path.size() -  1)) {             path.add(nums[i]);             dfs(ans, nums, path, i +  1);             path.remove(path.size() -  1);         }     } }

C++：

public:     vector

 > findSubsequences(vector

  &nums) {         vector

 > ans;         vector

  path;         dfs(ans, nums, path, 0);         return ans;     }     void dfs(vector

 > &ans, vector

  &nums, vector

  &path, int index) {         if (path.size() > 1)             ans.emplace_back(path);         // 記錄當前層并且具有共同父節點的所有節點，不能有重復的。         set

  s;         for (int i = index; i < nums.size(); i++) {             if (s.find(nums[i]) != s.end()) // 跳過重復的                 continue;             s.insert(nums[i]);             // 必須是非遞減的才可以選擇             if (path.empty() || nums[i] >= path[path.size() - 1]) {                 path.push_back(nums[i]);                 dfs(ans, nums, path, i + 1);                 path.pop_back();             }         }     }

C：

void dfs(int **ans, int *path, int count, int *nums, int numsSize, int *returnSize,          int **returnColumnSizes, int index) {     if (count > 1) {         ans[*returnSize] = malloc(count * sizeof(int));         memcpy(ans[*returnSize], path, count * sizeof(int));         (*returnColumnSizes)[(*returnSize)++] = count;     }     // 記錄當前層并且具有共同父節點的所有節點，不能有重復的。     int *set = calloc(201, sizeof(int));     for (int i = index; i < numsSize; i++) {         int key = nums[i] + 100;         if (set[key]) // 跳過重復的             continue;         set[key] = 1;         // 必須是非遞減的才可以選擇         if (count == 0 || nums[i] >= path[count - 1]) {             path[count++] = nums[i];             dfs(ans, path, count, nums, numsSize, returnSize, returnColumnSizes, i + 1);             count--;         }     }     free(set); } int **findSubsequences(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {     int **ans = malloc(100000 * sizeof(int *));     int *path = malloc(15 * sizeof(int));     *returnSize = 0;     *returnColumnSizes = malloc(100000 * sizeof(int));     dfs(ans, path, 0, nums, numsSize, returnSize, returnColumnSizes, 0);     return ans; }

Python：

def findSubsequences(self, nums: List[int]) -> List[List[int]]:     def dfs(index):         if len(path) > 1:             ans.append(path[:])         # 記錄當前層并且具有共同父節點的所有節點，不能有重復的。         s = set()         for i in range(index, len(nums)):             if nums[i] in s:  # 跳過重復的                 continue             s.add(nums[i])             # 必須是非遞減的才可以選擇             if not path or nums[i] >= path[len(path) - 1]:                 path.append(nums[i])                 dfs(i + 1)                 path.pop()     ans = []     path = []     dfs(0)     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。