被leader公开要求滚了。。。

(关注数据结构和算法，了解更多新知识)

一网友在网上吐槽说自己被邀请过来做架构师，来团队一年多，没从头到尾负责过一个完整的项目，每次把事情做起来的时候就会被转到别的方向。

后来之前的项目出现了问题，又想让他回去顶着，他希望这种事适可而止，结果被领导说：我就是这种管理风格，不爱干走吧。网友评论说：多埋点坑跑路，你跑他也待不住。

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

来看下今天的算法题，这题是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算法文档 。