​LeetCode刷题实战491:递增子序列

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 递增子序列,我们先来看题面:
https://leetcode-cn.com/problems/increasing-subsequences/

Given an integer array nums, return all the different possible increasing subsequences of the given array with at least two elements. You may return the answer in any order.
The given array may contain duplicates, and two equal integers should also be considered a special case of increasing sequence.

给你一个整数数组 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]]


解题

https://www.cnblogs.com/kexinxin/p/10372504.html

利用递归的思想,维护一个栈,将每次找到的比当前栈顶大的数,然后入栈,将更新过后的栈扔进递归函数,然后更新查找的初始位置即从当前的位置后一个位置开始查找。递归函数结束后,取出栈顶,进入下个循环,这样将所有元素都作为栈底元素遍历一遍。

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

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


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-480题汇总,希望对你有点帮助!

LeetCode刷题实战481:神奇字符串

LeetCode刷题实战482:密钥格式化

LeetCode刷题实战483:最小好进制

LeetCode刷题实战484:寻找排列

LeetCode刷题实战485:最大连续 1 的个数

LeetCode刷题实战486:预测赢家

LeetCode刷题实战487:最大连续1的个数 II

LeetCode刷题实战488:祖玛游戏

LeetCode刷题实战489:扫地机器人

LeetCode刷题实战490:迷宫


​LeetCode刷题实战491:递增子序列

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/17964.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息