[LeetCode] 491. Increasing Subsequences

wupengyu 發(fā)布于2019-08-16 13:50 / 1846人閱讀

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

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/72406.html

leetcode115. Distinct Subsequences

摘要：題目要求判斷字符串中通過刪減單詞含有幾個字符串。例如中含有個字符串，通過分別刪除第，，個。也就是說，我們需要通過一個數(shù)據(jù)結構來記錄臨時結果從而支持我們在已知前面幾個情況的場景下對后續(xù)情況進行計算。題目要求 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]

摘要：用動規(guī)方法做建立長度為和的二維數(shù)組，表示的第到位子串包含不同的的第到位子串的個數(shù)。初始化當?shù)淖哟L度為時，當?shù)淖哟L度為時，當和子串都為時，包含，故。 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 不同順序字串

摘要：計算元素值時，當末尾字母一樣，實際上是左方數(shù)字加左上方數(shù)字，當不一樣時，就是左方的數(shù)字。示意圖代碼如果這個字符串有個怎么辦用暴力法，對每一位開始向后檢查是否是。 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

摘要：題目要求思路和代碼這里采用廣度優(yōu)先算法加上緩存的方式來實現(xiàn)。我們可以看到，以一個節(jié)點作為開始構成的最長路徑長度是確定的。因此我們可以充分利用之前得到的結論來減少重復遍歷的次數(shù)。題目要求 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