专栏：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算法文档 。
热门跟贴