[LeetCode] 491. Increasing Subsequences

wupengyu 发布于2019-08-16 13:50 / 1790人阅读

Problem

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

Solution

class Solution {
    public List> findSubsequences(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        dfs(nums, 0, new ArrayList(), res);
        return res;
    }
    private void dfs(int[] nums, int start, List temp, List> res) {
        if (temp.size() > 1) {
            res.add(new ArrayList<>(temp));
        }
        Set used = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (used.contains(nums[i])) continue;
            if (temp.size() == 0 || nums[i] >= temp.get(temp.size()-1)) {
                temp.add(nums[i]);
                used.add(nums[i]);
                dfs(nums, i+1, temp, res); //next dfs doesn"t have used, yeah
                temp.remove(temp.size()-1);
            }
        }
    }
}

云服务器 GPU云服务器 Increasing Subsequences LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72406.html

leetcode115. Distinct Subsequences

摘要：题目要求判断字符串中通过删减单词含有几个字符串。例如中含有个字符串，通过分别删除第，，个。也就是说，我们需要通过一个数据结构来记录临时结果从而支持我们在已知前面几个情况的场景下对后续情况进行计算。题目要求 Given a string S and a string T, count the number of distinct subsequences of S which equa...

NSFish 2019-08-16 10:44 评论0 收藏0
[LintCode/LeetCode] Distinct Subsequences [一维DP]

摘要：用动规方法做建立长度为和的二维数组，表示的第到位子串包含不同的的第到位子串的个数。初始化当的子串长度为时，当的子串长度为时，当和子串都为时，包含，故。 Problem Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a strin...

dailybird 2019-08-14 15:29 评论0 收藏0
[Leetcode] Distinct Subsequences 不同顺序字串

摘要：计算元素值时，当末尾字母一样，实际上是左方数字加左上方数字，当不一样时，就是左方的数字。示意图代码如果这个字符串有个怎么办用暴力法，对每一位开始向后检查是否是。 Distinct Subsequences Given a string S and a string T, count the number of distinct subsequences of T in S. A su...

SnaiLiu 2019-08-14 16:11 评论0 收藏0
leetcode 329. Longest Increasing Path in a Matrix

摘要：题目要求思路和代码这里采用广度优先算法加上缓存的方式来实现。我们可以看到，以一个节点作为开始构成的最长路径长度是确定的。因此我们可以充分利用之前得到的结论来减少重复遍历的次数。题目要求 Given an integer matrix, find the length of the longest increasing path. From each cell, you can ei...

heartFollower 2019-08-16 11:09 评论0 收藏0
[LeetCode] 329. Longest Increasing Path in a Matri

Problem Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move ou...

hss01248 2019-08-16 13:25 评论0 收藏0