精品推薦：

《征服數(shù)據(jù)結構》專欄：50多種數(shù)據(jù)結構徹底征服

《經(jīng)典圖論算法》專欄：50多種經(jīng)典圖論算法全部掌握

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

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

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

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

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

輸入：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]]

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

輸出：[[4,4]]

public List<List<Integer>> findSubsequences(int[] nums) {
 List<List<Integer>> ans = new ArrayList<>();
 dfs(ans, nums, new ArrayList<>(), 0);
 return ans;
}

private void dfs(List<List<Integer>> ans, int[] nums, List<Integer> path, int index) {
 if (path.size() > 1)
  ans.add(new ArrayList<>(path));
 // 記錄當前層并且具有共同父節(jié)點的所有節(jié)點，不能有重復的。
 Set<Integer> 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);
  }
 }
}

public:
 vector<vector<int>> findSubsequences(vector<int> &nums) {
  vector<vector<int>> ans;
  vector<int> path;
  dfs(ans, nums, path, 0);
  return ans;
 }

 void dfs(vector<vector<int>> &ans, vector<int> &nums, vector<int> &path, int index) {
  if (path.size() > 1)
   ans.emplace_back(path);
  // 記錄當前層并且具有共同父節(jié)點的所有節(jié)點，不能有重復的。
  set<int> 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();
   }
  }
 }

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;
 }
 // 記錄當前層并且具有共同父節(jié)點的所有節(jié)點，不能有重復的。
 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;
}

def findSubsequences(self, nums: List[int]) -> List[List[int]]:
 def dfs(index):
  if len(path) > 1:
   ans.append(path[:])
  # 記錄當前層并且具有共同父節(jié)點的所有節(jié)點，不能有重復的。
  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