Html5移动网站,帮别人做网站赚钱吗,环球军事网,建设 网站给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 输入#xff1… 给你一个整数数组 nums 找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4 。 由上图我们可以很容易直到该数组中的最长递增子序列的长度为4可是计算机可不知道这么算所以我们要告诉它得这么算我们仔细找找规律 这种的分析是不是能让你看出一点点规律如果当前值i比i-1前的最长自序列的最后一个值大时将当前这个值加入这个递增子序列中是不是我们就比较容易得到 for (int i 1; i nums.length; i) {for (int j 0; j i; j) {if(nums[j]nums[i]){dp[i]Math.max(dp[j]1,dp[i]); }}} 那么我们动态规划中最难的一步已经写出来了状态转移方程接下来就是动规的一般解题步骤入参判断维护一个dp数组对其进行初始化具体的看下面的源代码 public int lengthOfLIS(int[] nums) {if(numsnull||nums.length0){return 0;}int[] dpnew int[nums.length];Arrays.fill(dp,1);for (int i 1; i nums.length; i) {for (int j 0; j i; j) {if(nums[j]nums[i]){dp[i]Math.max(dp[j]1,dp[i]); }}}return Arrays.stream(dp).max().getAsInt();} 在大家再给大家介绍一种解法面试时两种解法任选一种即可我认为还是动态规划这种比较容易好记
堆纸牌方法
这种方法一般人还真想不到可能那种久经牌场的人说不定可以想到 类似于蜘蛛纸牌一样的游戏规则每次找到最左边的适合当前牌的牌堆如果没有就直接新创一个牌堆 没堆牌出一张组成子序列牌堆的堆数越多最长子序列的长度也就越大
【567J】、【578J】...
所以我们应该怎么样去模拟这个算法呢
由于我们要时刻的知道每堆牌的顶牌所以我们可以维护一个数组去记录每个堆的牌顶
int[] topnew int[nums.length];
int count0;//一开始未进行发牌牌堆数为0 如果有这么sexy的荷官给你发牌你做题怎么可能会错比如邱淑贞姐姐给你发牌哒哒哒... 因为数组中的索引是从0开始的但是牌堆数确实从1开始的所以当我们查找可以放当前牌的最左牌堆的索引等于牌堆数的时候就应该重新创建一个牌堆如果不太了解二分搜索最左侧搜索请看二分搜索篇 public int lengthOfLIS(int[] nums) {if(numsnull||nums.length0){return 0;}int[] topnew int[nums.length];int count0;//进行发牌for(int num:nums){int left0;int rightcount;//这里给大家说明以下这种二分查找区间的时候区间是左闭右开的//因为count代表的是堆数(从1开始)但是right指针代表的是数组的索引(从0开始)指针永远不可能到达堆数的数量while(leftright){int midleft(right-left)/2;if(top[mid]num){rightmid;//不断的去优先收缩右区间}else{leftmid1;//收缩左区间}}//找到最小的大于等于num的索引大小if(leftcount){count;}//更新牌顶元素top[left]num;}return count;}
