精华内容
下载资源
问答
  • 抽取所有递增子序列
    2020-11-10 10:16:49

    题目

    链接:https://leetcode-cn.com/problems/increasing-subsequences

    给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。

    示例:
    
    输入: [4, 6, 7, 7]
    输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
    说明:
    
    给定数组的长度不会超过15。
    数组中的整数范围是 [-100,100]。
    给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。
    

    回溯

    这题也是使用回溯法求解,相比第90题.子集II,这题需要得到所有的递增子集,而第90题中是将数组排序后达到对树同一层元素去重的目的,本题中不能使用这种方法,而应使用Set容器。当当前元素小于路径path集合中最后一个元素是说明子集不是递增的,所以也应该跳过选取:

    class Solution {
    
        private List<List<Integer>> result = new ArrayList<>();
        private List<Integer> path = new ArrayList<>();
    
        public List<List<Integer>> findSubsequences(int[] nums) {
            if (nums.length == 0) return result;
            backTracking(nums, 0);
            return result;
        }
    
        private void backTracking(int[] nums, int startIndex) {
            if (path.size() > 1) { // 递增子序列长度至少为2
                result.add(new ArrayList<>(path));
            }
            Set<Integer> set = new HashSet<>(); // 对本层元素去重
            for (int i = startIndex; i < nums.length; i++) {
                if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) 
                || set.contains(nums[i])) continue;
                set.add(nums[i]);
                path.add(nums[i]);
                backTracking(nums, i+1);
                path.remove(path.size() - 1);
            }
        }
    }
    
    更多相关内容
  • 文章目录Leetcode--寻找递增子序列获取list中所有元素的子列(寻找集合子集)寻找所有递增子列 Leetcode–寻找递增子序列 每日一题里面先随到了股票…好家伙直接跳过,这难度好像对新手不太友好。于是第二题就是它啦...

    Leetcode–寻找递增子序列

    每日一题里面先随到了股票…好家伙直接跳过,这难度好像对新手不太友好。于是第二题就是它啦!
    题目描述:
    在这里插入图片描述
    看到这个题目不知道大家第一想法是啥(我看好多大佬们都是直接dfs,俺还不知道这是个啥东东,于是就直接上最笨的方法来了),反正俺第一想法就是找到所有子列,然后看其是否递增,从题目原意来理解我想还是很直接的(毕竟人家说数组长度不大于15哈哈哈哈哈,不然这暴力解法必然Timeout)。那么就一步步来做吧!

    获取list中所有元素的子列(寻找集合子集)

    学过小学(中学)数学的大家应该都知道,集合子集的个数为 2 n 2^n 2n,那么在程序中如何找到这么多个组合来作为集合子集呢,这里提供两种思路,这两种思路基本涵盖了所有寻找子集的方法。

    1. 利用数组下标做文章
      这一方法主要利用数组的下标来构建子集集合,具体的思想是:子集的个数 2 n 2^n 2n可以被视为一个二进制选通开关。举个栗子,一个长度为4的list,它的子集个数为24共计16个,那么对应的就是二进制0000~1111,不知道大家有没有看出点端倪。其实根据二进制位是否为1,我们就可以构建出原数组的下标组合,将对应的下标组合生成新的sublist,组合在一起就是全部的子集啦!代码实现见下文:
      def subsets(nums: List[int]) -> List[List[int]]:
          answer = []
          # length of list
          N = len(nums)
          # 2^N: number of subsets
          for i in range(2 ** N):
          	# traverse all binary value from 0000 - 1111
              subset = []
              # find bits which is 1
              for j in range(0, N):
                  if (i >> j) % 2:
                      subset.append(nums[j])
                  else:
                      continue
              answer.append(subset)
          return answer
      >>> subset([1,2,3,4])
      [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], 
      [2, 3, 4], [1, 2, 3, 4]]
      
      可以看到,上述方法构建出了完整的集合的子集
    2. 采用动态生成的方法构建子集集合
      这种方法是一种直观上最容易理解的方法,我们从头开始遍历数组,每遇到一个新的元素就将其加入到我们原来子集中的每一个元素中去,最后就可以生成一个完整的子集集合,上菜:
      def subset(nums: list) -> list:
          answer = [[]]
          last_sublist = [[]]
          for num in nums:
              for ans in last_sublist:
                  answer.append(ans + [num])
              # the `copy` function here does matter, since the `=` can lead to the same
              # memory space for both `answer` and `last_sublist`, which is unwanted
              last_sublist = answer.copy()
          return answer
      
      应该说这种方法的实现相较于上面方法更加直观一些,但是从leetcode提交的结果来看,前者的效率更高。至此,找寻List子集的两种方法介绍完毕。

    寻找所有递增子列

    通过上述方法获取到子列之后,我们还需要判断每个子列是否为递增的情况,这一步就很好办了,遍历每个子列,只要后面一个元素比前一个大,就认为是递增子列,这一条件在整个子列中满足即可。值得注意的是,上面获取到的子集中存在空集以及元素个数为一的集合,因此需要剔除这些子列,对剩下的子列进行研究。具体代码实现如下:

    class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
    	    answer = []
    	    # length of list
    	    N = len(nums)
    	    # 2^N: number of subsets
    	    for i in range(2 ** N):
    	    	# traverse all binary value from 0000 - 1111
    	        subset = []
    	        # find bits which is 1
    	        for j in range(0, N):
    	            if (i >> j) % 2:
    	                subset.append(nums[j])
    	            else:
    	                continue
    	        answer.append(subset)
    	    return answer
    
        def findSubsequences(self, nums: list) -> list:
            result = []
            subsets = self.subset(nums)
            # remove subsets with length < 2
            sublists_condition = [subset for subset in subsets if len(subset) >= 2]
            # traverse all subsets, find those with increase order
            for subset in sublists_condition:
                for i in range(1, len(subset)):
                    if subset[i - 1] <= subset[i]:
                        continue
                    else:
                        i = 0
                        break
                if i == len(subset) - 1 and subset not in result:
                    result.append(subset)
                else:
                    continue
            return result
    

    上面方法的执行效率可以说是非常低,给大家看一个非常羞耻的图叭:
    在这里插入图片描述
    就是这么差劲。作为优秀的代码搬运工,我把leetcode上一个优质答案给搬了过来

    def findSubsequences(self, nums: list) -> list:
        """
        491. 递增子序列
        :see https://leetcode-cn.com/problems/increasing-subsequences/
        """
        # 用字典存以数字key结尾的所有递增子序列
        all_list = {}
        
        for i in nums:
            # 把单个数字也当做一个递增子序列,以便后续计算
            new_list = [[i]]
            # 遍历字典中所有结尾数字key小于等于当前数字的情况,将其所有递增子序列加上当前数字
            for j in all_list:
                if j <= i:
                    for k in all_list[j]:
                        new_list.append(k + [i])
            # 此时的new_list,就是遍历到i时,以数字i结尾的所有递增子序列
            all_list[i] = new_list
    
        result = []
        for i in all_list:
            # 从下标1开始的原因是,去掉由单个数字组成的递增子序列
            for j in range(1, len(all_list[i])):
                result.append(all_list[i][j])
    
        return result
    

    根据作者@Wu-GQ口述,该实现方法在时间上和空间上都秒杀几乎所有提交者,我愿称之为绝杀。作者的实现方法非常巧妙,充分利用了字典的动态生成特性,记录以列表中每个元素结尾的所有递增子列,这样最后遍历整个字典找出长度满足条件的递增子列即可。

    展开全文
  • 最长递增子序列前言问题描述解法一分析代码解法二分析代码总结 前言 ok,这两天又研究了关于最长递增子序列相关的一些内容。记录在此,希望便人便己 问题描述 求一个序列的最长递增子序列,这样的子序列是允许中间...


    前言

    ok,这两天又研究了关于最长递增子序列相关的一些内容。记录在此,希望便人便己


    问题描述

    求一个序列的最长递增子序列,这样的子序列是允许中间越过一些字符的,即留“空”。
    例如:序列A: 4 2 3 1 5 的最长递增子序列为 2 3 5,长度为 3 。

    在这里插入图片描述


    解法一

    分析

    这题其实和上次那个最大连续子序列和有点像,解法一的思路也和最大连续子序列和问题有些许联系。可以采用类似的解空间的思路。
    对于给定的一个求解序列来说,假定其最终的答案是b0,b1,b2…bj(这里的b0,b1,b2…都是从原序列中抽取的递增值,其中bj是最后一个元素,也是最大的一个),那么可以肯定bj要么是a0,要么是a1,…要么是a(n-1).也就是说,最终求解的序列的最大值,要么是以a0为结尾的序列,要么是a1结尾的序列…

    举个栗子,还是题目中的那个序列:最终的答案可以是以下几种:
    (1)、以4为结尾的序列,只有一种:就是4
    (2)、以2为结尾的序列,一种:2 (注意(4 2)不是递增的)
    (3)、以3为结尾的序列,两种:3 或者(2 3)

    所以我们可以确定一个条件,然后所有的条件都组合起来。还是一句话,这里并不是说要用暴力解法,全部都列举出来,只是用这种思路(先确定解空间的一个条件)来构造符合动态规划的性质和特点,也就是重复子问题和最优子结构。

    经过上述的分析,我们可以用lcs[i] 表示 以第i个结点为递增序列的最后一个结点的所有序列中最长的序列长度。

    说的有点拗口哦,以题目所给的序列作为例子,比如说lcs[2]就是以3为结尾的递增序列中长度最长的那个,以3位结尾的递增序列有两种3 和 2 3 ,最长的长度肯定就是2了。所以lcs[2] = 2.

    构造了lcs[ ]之后,我们可以得到动态规划的很重要的一个属性,就是最优子结构性质。具体一点就是说,lcs[i] 的求解可以从lcs[j],(0<=j <= i-1) 得到,说的在透明些,也就是说,lcs[i]的求解不需要重复i元素之前的所有序列情况,只要用到前面记录的所有lcs[j] 就可以(0<=j <= i-1) ),这也是动态规划思想的一个精髓,用记表的方式避免了重复计算相同的单元

    最终我们可以得到这样一个递推式:
    在这里插入图片描述

    好了递推式出来了,代码就不成问题了。

    代码

    //利用动态规划求解最长递增子序列
    int LongIncSeq(int data[],int n)
    {
        int lis[n] = {0};
        int longest = 0;
    
        for(int i = 0;i<n;++i)
        {
            int tmpLon = 0;         //记录以i为结束结点的,最长递增子序列
            for(int j = i-1;j>=0;--j)       //判断data[0]-data[i-1]所有比data[i]小的元素
            {
                if(data[i] > data[j])
                {
                    if(lis[j] >tmpLon)      //取较大的值
                        tmpLon = lis[j];
                }
            }
            lis[i] = tmpLon+1;          //记录以i为尾部的最长的递增子序列
            if(lis[i]>longest)      //记录整体最长的
                longest = lis[i];
        }
        return longest;
    }
    

    注:以上算法的复杂度很容易看出来是O(N2)级别的


    解法二

    分析

    解法二比较巧妙,照我看来,还是从某种程度上用了解空间的这种思维方式。它是这样分解解空间的:

    假设递增子序列B是一个解,那么B长度可能的取值是
    0,1,2,3,…, n-1. 这个挺容易理解的。
    那么我可以在遍历元素的过程中,记录着长度为i的递增子序列最大元素的最小值。用maxElem[i]表示。

    具体来说:
    (1)、长度为1的递增子序列最大元素的最小值为maxElem[1]
    (2)、长度为2的递增子序列最大元素的最小值为maxElem[2]
    (3)、长度为2的递增子序列最大元素的最小值为maxElem[3]
    … … …
    比如说对于序列A = {1,-1,2,-3,4,-5,6,-7}
    当i为4时,
    长度为1的递增序列有:1,-1,2,-3 这四个,其中的最小值为-1
    长度为2的递增序列有:(1,2),(-1,2),其中的最小值为2
    长度为3的递增序列没有。

    与此同时,还要记录一个遍历到当前位置时,产生的最大的递增子序列,也就是随时更新maxElem[]数组的大小,假设用变量longIncSeq表示。

    在遍历的时候主要的操作是用当前元素A[i] 和maxElem[j](j>=0 && j<=longIncSeq ),进行比较 (当然是从后往前比较)。
    如果A[i]大于某个maxElem[j],就说明可以形成一个以A[i]为最大元素的子序列。如果这个新形成的子序列长度大于longIncSeq,就更新longIncSeq的值。同时要更新对应长度子序列最大元素(也就是末尾元素)的最小值。

    我知道,看起来写的有些复杂,真正动动你的小手指,模拟一下就基本清楚了。

    代码

    //另一种动态规划的解法:最长递增子序列
    int LongIncseq(int data[],int n)
    {
        int longIncSeq = 0;         //记录最长的递增子序列的长度
        int maxElem[n] = {0};       //记录长度为i的递增子序列最大元素(也就是序列的末尾元素)的最小值
    
        maxElem[0] = (*min_element(data,data+n))-1;  //最小元素减1
        for(int i = 0;i<n;++i)
        {
            int j;
    
            for( j= longIncSeq;j>=0;--j)        //寻找所有序列长度在longIncSeq—0之间
            {
                if(data[i] > maxElem[j])       //data[i]大于序列长度为j的最大元素
                {
                    break;
                }
            }
    
            if(j == longIncSeq)
            {
                ++longIncSeq;
    
                maxElem[longIncSeq] = data[i];          //最新的序列长度
            }
            else if(maxElem[j]<data[i] && maxElem[j+1] > data[i])    //新长度为j+1的序列,其最大值小于原来的那个就更换
            {
                maxElem[j+1] = data[i];
            }
        }
    
        return longIncSeq;
    }
    

    总结

    稍稍总结一下吧,两点内容:
    (1)、动态规划算法针对的是问题的求解过程,而不是针对问题本身。我们在有了一个思路之后,可以按照这个思路,探究是否可以使用动态规划的思想,就我来看就是记表、以空间换时间。
    (2)、分解解空间,先假设确定一个条件,或许可以作为上面的一种探究思路。

    展开全文
  • 如果了解动态规划经典题目LIS(最长递增子序列)问题,那么读完这个题应该就能知道这个题其实质是让我们找信封长宽数组对的最长递增子序列。不过还有一点不同的是,LIS问题中,子序列是选取一些元素后按其原有的相对...

    题目

    在这里插入图片描述
    如果了解动态规划经典题目LIS(最长递增子序列)问题,那么读完这个题应该就能知道这个题其实质是让我们找信封长宽数组对的最长递增子序列。不过还有一点不同的是,LIS问题中,子序列是选取一些元素后按其原有的相对序列排列的。而这个问题中,“子序列”在选取部分元素后,并不是按其原来的相对顺序排列的,而是按照大小排列。所以,我们可以先把这个二维数组转化一下,对它排个序,它的宽由小到大排列。那长应该如何排列呢?
    我们看一下对[(5, 4), (6, 4), (6, 7), (2, 3)]
    长由大到小排列: (2, 3), (5, 4), (6, 7), (6,4)
    抽取宽的一维数组得到: 3, 4, 7, 4
    我们可以发现,当对这个二维数组的长由大到小排列时,我们可以直接将问题转换为LIS问题。因为这种排列将(6, 7)排在(6,4)的前面,(6, 7)不能套(6,4),而LIS也不会出现7,4这样的子序列。这样的排列方式保证了相同宽的信封至多只有1个被计入LIS中。

    朴素dp

    class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            int dp[];
            int N = envelopes.length;
            dp = new int[N];
            Arrays.sort(envelopes, (int[] o1, int[] o2) -> {
                if(o1[0] == o2[0])
                    return o2[1] - o1[1];
                return o1[0] - o2[0];
            });
            int ans = 1;
            for(int i = 0; i < N; i++)
            {
                dp[i] = 1;
                for(int  j = 0; j < i; j++)
                {
                    if(envelopes[j][1] < envelopes[i][1])
                    {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                    ans = Math.max(ans, dp[i]);
                }
            }
            return ans;
        }
    }
    

    二分

    和LIS一样,本题也可用此方法

    class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            int N = envelopes.length;
            int d[][] = new int[N + 1][2];
            int len = 1;
            Arrays.sort(envelopes, (int[] o1, int[] o2) -> {
                 if(o1[0] == o2[0])
                     return o2[1] - o1[1];
                 return o1[0] - o2[0];
             });
            d[len] = envelopes[0];
            //找位置的思想
            for(int i = 1;  i < N; i++)
            {
                if(d[len][1] < envelopes[i][1])
                {
                    d[++len] = envelopes[i];
                }
                else {
                    int le = 1;
                    int ri = len + 1;
                    //左闭右开 找位置
                    int mid = (le + ri) / 2;
                    int pos = 0;
                    while(le < ri)
                    {
                        mid = (le + ri) / 2;
                        //符合条件 则尝试再向后面找找
                        if(d[mid][1] < envelopes[i][1])
                        {
                            pos = mid;
                            le = mid + 1;
                        }
                        else {
                            ri = mid;
                        }
                    }
                    d[pos + 1] = envelopes[i]; 
                }
            }
            return len;
    
        }
    }
    
    
    展开全文
  • 递增顺序的最小子序列给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。示例 1:输出:[10,
  • 300. 最长上升子序列 解法一:DP(C++) 我们记状态 dp[i]dp[i]dp[i] 表示以第 iii 个元素结尾的最长上升子序列的长度,那么专一方程就可以定义为 dp[i]=max(dp[j])+1 (0≤j<i and nums[j]<...
  • 最长递增子序列
  • 最长递增子序列

    千次阅读 2013-07-08 19:40:07
    最长递增子序列(Longest Increasing Subsequence)长度有很多种解决方法,这里介绍两种,一种是动态规划的实现,一种是O(NlogN)的解决方法(参考编程之美) 动态规划 我们假定w1,w2,...,wn为一串正整数序列,前i个数...
  • 1.分割平衡字符串 //在一个「平衡字符串」中,'L' 和 'R' 字符的数量是相同的。...//解释:s 可以分割为 "RL", "RRLL", "RL", "RL", 每个字符串中都包含相同数量的 'L' 和 'R'。 // // // 示例 2:
  • 给你一个数组nums,请你从中抽取一个子序列,满足该子序列的元素之和严格大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回长度最小的子序列。如果仍然有多个解决方案,则返回元素之和最大的...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 题目描述:给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 ...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • ​力扣解法汇总1403-非递增顺序的最小子序列
  • 给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和...
  • 给你一个数组nums,请你从中抽取一个子序列,满足该子序列的元素之和严格大于未包含在该子序列中的各元素之和。 如果存在多个解决方案,只需返回长度最小的子序列。如果仍然有多个解决方案,则返回元素之和最大的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,527
精华内容 1,410
关键字:

抽取所有递增子序列