Massive Algorithms: LeetCode 491 - Increasing Subsequences

LeetCode 491 - Increasing Subsequences

https://leetcode.com/problems/increasing-subsequences/

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.

X. DFS
http://www.cnblogs.com/grandyang/p/6388103.html

这道题让我们找出所有的递增子序列，那么我们应该不难想到，这题肯定是要先找出所有的子序列，从中找出递增的。找出所有的子序列的题我们之前也接触过Subsets和Subsets II，那两题不同之处在于数组中有没有重复项。而这道题明显是有重复项的，所以需要用到Subsets II中的解法。我们首先来看一种迭代的解法，对于重复项的处理，最偷懒的方法是使用set，利用其自动去处重复项的机制，然后最后返回时再转回vector即可。由于是找递增序列，所以我们需要对递归函数做一些修改，首先题目中说明了递归序列数字至少两个，所以只有当当前子序列个数大于等于2时，才加入结果。然后就是要递增，如果之前的数字大于当前的数字，那么跳过这种情况，继续循环，

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> res;
        vector<int> out;
        helper(nums, 0, out, res);
        return vector<vector<int>>(res.begin(), res.end());
    }
    void helper(vector<int>& nums, int start, vector<int>& out, set<vector<int>>& res) {
        if (out.size() >= 2) res.insert(out);
        for (int i = start; i < nums.size(); ++i) {
            if (!out.empty() && out.back() > nums[i]) continue;
            out.push_back(nums[i]);
            helper(nums, i + 1, out, res);
            out.pop_back();
        }
    }

我们也可以在递归中进行去重复处理，方法是用一个set保存中间过程的数字，如果当前的数字在之前出现过了，就直接跳过这种情况即可

https://blog.csdn.net/magicbean2/article/details/78708889
1、DFS+backtracking：这是稍微有点变形的DFS题目：对于nums中的每个整数，如果符合条件，我们有两种选择：1）将它加入到结果中，然后进行DFS并且回溯；2）忽略它，直接进行DFS。为此我们在dfs的内部设立一个哈希表，表示已经尝试过的整数。这样对于具有重复整数的情况，比如例子中给出的[4, 6, 7, 7]，当我们遇到第一个7之后，则包含7的所有升序组合都已经被输出了，那么当遇到第二个7的时候，我们就可以忽略。否则就生成重复结果了。

我发现DFS + BackTracking的题目往往有两种模板，一种是dfs中没有for循环的，也就是只调用DFS的下一层（有点像在dfs内部再进行dfs）；另一种是dfs内含有从当前位置到末尾的for循环的，也就是在dfs内，平行的调用dfs（有点像dfs内部再进行一个bfs）。前一种模板适合无局部状态的情况，而后一种模板则比较适合需要记录局部状态的情况，例如本题目中我们需要记录已经采用过的整数。

https://leetcode.com/problems/increasing-subsequences/discuss/97147/Java-solution-beats-100

                // used只用于每一层递归，每次只添加一次，遇到重复的就自动跳过
                // 下一层会重新申请数组，所以并不会影响到下一层加新的重复的元素

while nums is not necessarily sorted but we have to skip duplicates in each recursion, so we use a hash set to record what we have used in this particular recursion

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        helper(new LinkedList<Integer>(), 0, nums, res);
        return res; 
    }
    private void helper(LinkedList<Integer> list, int index, int[] nums, List<List<Integer>> res){
        if(list.size()>1) res.add(new LinkedList<Integer>(list));
        Set<Integer> used = new HashSet<>();
        for(int i = index; i<nums.length; i++){
            if(used.contains(nums[i])) continue;
            if(list.size()==0 || nums[i]>=list.peekLast()){
                used.add(nums[i]);
                list.add(nums[i]); 
                helper(list, i+1, nums, res);
                list.remove(list.size()-1);
            }
        }
    }

https://discuss.leetcode.com/topic/76249/java-20-lines-backtracking-solution-using-set-beats-100

If you use LinkedList instead of ArrayList, you could use its getLast, removeLast methods

     public List<List<Integer>> findSubsequences(int[] nums) {
         Set<List<Integer>> res= new HashSet<List<Integer>>();
         List<Integer> holder = new ArrayList<Integer>();
         findSequence(res, holder, 0, nums);
         List result = new ArrayList(res);
         return result;
     }

    public void findSequence(Set<List<Integer>> res, List<Integer> holder, int index, int[] nums) {
        if (holder.size() >= 2) {
            res.add(new ArrayList(holder));
        }
        for (int i = index; i < nums.length; i++) {
            if(holder.size() == 0 || holder.get(holder.size() - 1) <= nums[i]) {
                holder.add(nums[i]);
                findSequence(res, holder, i + 1, nums);
                holder.remove(holder.size() - 1);
            }
        }
    }

https://discuss.leetcode.com/topic/76211/clean-20ms-solution
http://blog.csdn.net/alwaystry/article/details/54692902

public List<List<Integer>> findSubsequences(int[] nums) {
Set<List<Integer>> list = new HashSet<List<Integer>>();
backtrack(list,new ArrayList<>(),nums,0);
return new ArrayList(list);
}
private void backtrack(Set<List<Integer>> list, List<Integer> tempList, int[] nums,int start){
if (tempList.size()>1) list.add(new ArrayList<>(tempList));
for(int i=start;i<nums.length;i++){
if(tempList.size()==0||tempList.get(tempList.size()-1)<=nums[i]){
tempList.add(nums[i]);
backtrack(list,tempList,nums,i+1);
tempList.remove(tempList.size()-1);
}
}
}

https://leetcode.com/problems/increasing-subsequences/discuss/97127/Simple-Python

First build all increasing subsequences regardless of length, then filter out the too short ones.

def findSubsequences(self, nums):
    subs = {()}
    for num in nums:
        subs |= {sub + (num,)
                 for sub in subs
                 if not sub or sub[-1] <= num}
    return [sub for sub in subs if len(sub) >= 2]

X. BFS
https://leetcode.com/problems/increasing-subsequences/discuss/97134/Evolve-from-intuitive-solution-to-optimal

We can also generate all increasing subsequences by adding each number to the current sequencies iteratively and use set to remove duplicates.

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> seq(1);
        set<vector<int>> bst;
        for(int i=0;i<nums.size();i++) {
            int n = seq.size();
            for(int j=0;j<n;j++)
                if(seq[j].empty() || seq[j].back()<=nums[i]) {
                    seq.push_back(seq[j]);
                    seq.back().push_back(nums[i]);
                    if(seq.back().size()>1) bst.insert(seq.back());
                }  
        }
        return vector<vector<int>>(bst.begin(),bst.end());
    }

We can do better by not generating duplicates. When adding a duplicate number to existing sequences, we don't need to add to all sequences because that will create duplicate sequence. We only need to add to the sequences created since adding this number last time.

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res(1);
        unordered_map<int,int> ht;
        for(int i=0;i<nums.size();i++) {
            int n = res.size();
            int start = ht[nums[i]];
            ht[nums[i]] = n;
            for(int j=start;j<n;j++)
                if(res[j].empty() || res[j].back()<=nums[i]) {
                    res.push_back(res[j]);
                    res.back().push_back(nums[i]);
                }  
        }
        for(int i=res.size()-1;i>=0;i--) 
            if(res[i].size()<2) {
                swap(res[i],res.back());
                res.pop_back();
            }
        return res;
    }

https://blog.csdn.net/magicbean2/article/details/78708889
2、前缀生成法：注意到一个升序序列总是可以由升序的前缀加上当前整数组成，所以我们可以采用递推的方式由升序的前缀生成所有的结果。例如对于本题目，我们初始的升序前缀是{}，那么随着扫描的进行，结果的变化依次是：

当扫描到4之后，由升序前缀{{}}生成{4}，然后升序前缀更新为{{}, {4}}；

当扫描到6之后，由升序前缀{{}, {4}}生成{{6}, {4, 6}}，然后升序前缀更新为{{}, {4}, {6}, {4, 6}}；

当扫描到7之后，由升序前缀{{}, {4}, {6}, {4, 6}}生成{{7}, {4, 7}, {6, 7}, {4, 6, 7}}，然后升序前缀更新为{{}, {4}, {6}, {4, 6}, {7}, {4, 7}, {6, 7}, {4, 6, 7}}；

当再次扫描到7之后，由升序前缀{{}, {4}, {6}, {4, 6}, {7}, {4, 7}, {6, 7}, {4, 6, 7}}可以生成{{7}, {4, 7}, {6, 7}, {4, 6, 7}, {7, 7}, {4, 7, 7}, {6, 7, 7}, {4, 6, 7, 7}}，然后升序前缀更新为{{}, {4}, {6}, {4, 6}, {7}, {4, 7}, {6, 7}, {4, 6, 7}, {7}, {4, 7}, {6, 7}, {4, 6, 7}, {7, 7}, {4, 7, 7}, {6, 7, 7}, {4, 6, 7, 7}}。注意到背景为灰色的部分是重复元素，它们在set中将会被去重。最后再筛选出长度大于等于2的升序序列即可。

vector<vector<int>> findSubsequences(vector<int>& nums) {
set<vector<int>> seqs = {vector<int>(0)}; // increasing prefix
for (int i = 0; i < nums.size(); i++) {
vector<vector<int>> built(seqs.size()); // get a copy of seqs
std::copy(seqs.begin(), seqs.end(), built.begin());
for (auto seq : built) {
if (seq.empty() || nums[i] >= seq.back()) {
seq.push_back(nums[i]);
seqs.insert(seq);
}
}
}
vector<vector<int>> res;
for (auto seq : seqs)
if (seq.size() > 1) {
res.push_back(seq);
}
return res;
}

下面我们来看迭代的解法，还是老套路，先看偷懒的方法，用set来去处重复。对于递归的处理方法跟之前相同

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> res;
        vector<vector<int>> cur(1);
        for (int i = 0; i < nums.size(); ++i) {
            int n = cur.size();
            for (int j = 0; j < n; ++j) {
                if (!cur[j].empty() && cur[j].back() > nums[i]) continue;
                cur.push_back(cur[j]);
                cur.back().push_back(nums[i]);
                if (cur.back().size() >= 2) res.insert(cur.back());
            }
        }
        return vector<vector<int>>(res.begin(), res.end());
    }

我们来看不用set的方法，使用一个哈希表来建立每个数字对应的遍历起始位置，默认都是0，然后在遍历的时候先取出原有值当作遍历起始点，然后更新为当前位置，如果某个数字之前出现过，那么取出的原有值就不是0，而是之前那个数的出现位置，这样就就不会产生重复了，如果不太好理解的话就带个简单的实例去试试吧

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res, cur(1);
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            int n = cur.size();
            int start = m[nums[i]];
            m[nums[i]] = n;
            for (int j = start; j < n; ++j) {
                if (!cur[j].empty() && cur[j].back() > nums[i]) continue;
                cur.push_back(cur[j]);
                cur.back().push_back(nums[i]);
                if (cur.back().size() >= 2) res.push_back(cur.back());
            }
        }
        return res;
    }

https://blog.csdn.net/fuxuemingzhu/article/details/79827505
http://bookshadow.com/weblog/2017/01/22/leetcode-increasing-subsequences/
下面是动态规划的代码，使用了一个set来保证不会有重复，然后由于set之中只能放不可变的对象，所以放进去的是元组对象。当我们遍历到nums的每个数字的时候，对set中的所有的元素进行遍历，看每个tuple元素的最后一个数字是否是小于等于当前的num的，如果是的话就把当前的元素添加到原来的tuple的后面。这样的循环虽说稍显复杂，但是竟然也能通过了。。
def findSubsequences(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ dp = set() for n in nums: for y in list(dp): if n >= y[-1]: dp.add(y + (n,)) dp.add((n,)) return list(e for e in dp if len(e) > 1)
https://leetcode.com/problems/increasing-subsequences/discuss/97157/DP-solution%3A-not-as-clean-as-other-Python-solutions-but-beats-99-in-speed
X. DP
https://buptwc.com/2018/07/03/Leetcode-491-Increasing-Subsequences/

我们可以先思考一下LIS问题是怎么处理的，我们使用dp[i]表示前i个数字组成的序列中以nums[i]结尾的最长上升子序列的长度，dp[i] = max([dp[j]+1 for j in range(i) if nums[j] < nums[i]])
根据这个思路我们可以想到这道题其实也可以用一样的方法，我们使用一个字典d，d[i]表示以nums[i]结尾的上升子序列，初始化所有的d[i] = [[nums[i]]]
则可获得递推式 d[i].append(l+nums[i]) for j in range(i) if nums[j] <= nums[i] for l in d[j]
当然严格来说上式不能算是递推式，我们直接用给出的具体实例来看一下是怎么运作的，初始化d = {0:[[4]],1:[[6]],2:[[7]],3:[[7]]}，我们从1开始分析，nums[1] > nums[0]，所以d[1] = [[6],[4,6]]，依次类推d[2] = [[4,7],[6,7],[4,6,7]]，d[3] = …

递推式如分析中所示，但考虑到4,6,7,7,7这种情况，计算第三个7的时候会出现重复情况，所以用一个集合来确保答案中没有重复元素，然后又因为list本身不可hash，所以转化成元祖来进行hash即可

    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 初始化字典
        d = {i:[[nums[i]]] for i in range(len(nums))}
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[i] >= nums[j]:
                    for l in d[j]:
                        d[i].append(l+[nums[i]])
        
        s = set()
        res = []
        for i in range(len(nums)):
            for l in d[i]:
             # 因为字典中本身存在长度为1的list，需要我们排除
                if len(l) < 2: continue
                if tuple(l) in s: continue
                s.add(tuple(l))
                res.append(l)
        return res

http://bgmeow.xyz/2017/02/24/LeetCode-491/

动态规划解法。遍历数组 nums 。用一个 map 来存储已经出现过的值及其上次出现的位置。

nums[i] 的结果集等于之前所有结果集 res[i - 1] 加上 res[i - 1] 中所有 List 加上 nums[i] （如果 nums[i] 大于最后的数）再加上:

若 nums[i] 第一次出现，nums[i] 与 map 中所有 key 的对子。
若 map 中已存在 nums[i] ，遍历上次位置 last 到这次位置 curr，若某个值 nums[j] 首次出现的位置 i 比 last 小，说明这个值在上次 nums[i] 以后才有，应该将 (nums[j], nums[i]) 加入集合 res 。
最后将 (nums[i], i) 存入 map

本来是用一个 List<List<List<Integer>>> 作为 dp 来做，写完之后发现只要记录一下上一次加的最后一个就好了。

用 List 超时了，应该是中间判断的时间花了太久，干脆先用 set 存，最后转到 List 里，过了。以为考的就是重复时候的条件，辣鸡。


public List<List<Integer>> findSubsequences(int[] nums) {

List<List<Integer>> res = new ArrayList<>();

if (nums == null || nums.length <= 1) {

return res;

}        



int length = nums.length;



Set<List<Integer>> tempRes = new HashSet<>();



Set<Integer> numSet = new HashSet<>();



for (int i = 0; i < length; i++) {



// for list whose last num is smaller than nums[i], add nums[i] to get a new list.

for (List<Integer> subset: tempRes) {

if (subset.get(subset.size() - 1) <= nums[i]) {

List<Integer> newSet = new ArrayList<>(subset);

newSet.add(nums[i]);

res.add(newSet);

}   

}

tempRes.addAll(res);

res.clear();



// for single num, combine num[i] to get a new list

for (Integer num: numSet) {

if (nums[i] >= num) {

List<Integer> newSet = new ArrayList<>();

newSet.add(num);

newSet.add(nums[i]);

tempRes.add(newSet);

}

}

numSet.add(nums[i]);



}

res.addAll(tempRes);

return res;

}

LeetCode 491 - Increasing Subsequences

Labels

Popular Posts