(关注数据结构和算法，了解更多新知识)
一网友在网上吐槽说自己被邀请过来做架构师，来团队一年多，没从头到尾负责过一个完整的项目，每次把事情做起来的时候就会被转到别的方向。
后来之前的项目出现了问题，又想让他回去顶着，他希望这种事适可而止，结果被领导说：我就是这种管理风格，不爱干走吧。网友评论说：多埋点坑跑路，你跑他也待不住。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是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来剪枝，如下图所示，对于每一颗子树，如果有相同的子节点，我们只选择一个。
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算法文档 。
热门跟贴