当前位置: 首页> 财经> 金融 > 中国肩章大全图解_外贸进出口代理公司_网页制作接单平台_培训学校机构有哪些

中国肩章大全图解_外贸进出口代理公司_网页制作接单平台_培训学校机构有哪些

时间:2025/7/12 2:17:59来源:https://blog.csdn.net/weixin_49332521/article/details/145912440 浏览次数:0次
中国肩章大全图解_外贸进出口代理公司_网页制作接单平台_培训学校机构有哪些

题目链接:

链接

题目描述:

在这里插入图片描述

思路:

思路一:动态规划

类似于“单词拆分”,需要遍历之前的元素 对应的最大长度,然后找到最大的
设第 i i i个元素对应的最长递增序列长度是 d p ( i ) dp(i) dp(i),每一个 d p ( i ) dp(i) dp(i)最初都是1

则:当 n u m s [ i ] > n u m s [ j ] nums[i] > nums[j] nums[i]>nums[j] 时,有
d p ( i ) = m a x { d p ( i ) , d p ( j ) + 1 } dp(i) = max\{ dp(i) ,dp(j) + 1 \} dp(i)=max{dp(i)dp(j)+1}
返回dp中的最大值就行

思路二

贪心 + 二分查找

要找最长的递增序列,就期望递增的幅度最小,相同长度下,递增的幅度越小,后面可以满足递增的元素就越多(不一定),按照这种思路写代码会存在一个问题:我们并不知道后面是否会有更多的满足递增的元素,如:0 2 6 7 4,最长的是0 2 6 7,但是按照上面的思路我们会选择0 2 4,

所以,我们也需要记录下已经遍历到的最长的递增序列及长度,我们可以使用一个数组d记录“已经遍历到的最长的递增序列”,如 0 2 6 7 len = 4,

如果有更长的递增序列,d里面的元素就应该被覆盖掉

怎么覆盖呢?当我们遇到更小的元素后,就可以把更小的元素放进d里面合适的位置使d继续满足递增,如0 2 4 7

  • 如果后面有 相对于4 递增的数据(假设原数组是:0 2 6 7 4 5 6):则d变成 0 2 4 5 6,len=5
  • 如果后面是 相对于7 递增的数据(假设原数组是:0 2 6 7 4 8):则d变成 0 2 4 7 8

(这里d从索引1开始存放元素)
总结:

  • 如果 d [ j ] < n u m [ i ] < d [ l e n ] d[j]<num[i] < d[len] d[j]<num[i]<d[len],就把 n u m [ i ] num[i] num[i]放入d数组中间
  • 如果 n u m [ i ] > d [ l e n ] num[i] > d[len] num[i]>d[len],就把 n u m [ i ] num[i] num[i]放入d数组末尾,同时len++

这里 “把 n u m [ i ] num[i] num[i]放入d数组中间”,可以用二分法

注意:最后得到的d数组不一定是最长递增序列,实际上d只能记录某个最长序列的最后一个元素d[len]

实现代码:

class Solution {public int lengthOfLIS(int[] nums) {if(nums.length == 0) return 0;int[] dp = new int[nums.length];//这里直接用 当前元素的位置 存放 最大长度就行dp[0] = 1;int ans = 1;for(int i = 1; i < nums.length; i++){dp[i] = 1;for(int j = 0; j < i; j++){if(nums[i]>nums[j]){dp[i] = Math.max(dp[i],dp[j]+1);}}ans = Math.max(ans,dp[i]);}return ans;}
}
class Solution {public int lengthOfLIS(int[] nums) {int len = 1, n = nums.length;if(n ==0) {return 0;}int[] d = new int[n+1];d[len] = nums[0];//的d[1] = nums[0]for(int i = 1; i < n; i++){if(nums[i]>d[len]){d[++len] = nums[i];}else{int left = 1, right = len, pos = 0;//pos表示d里面小于nums[i]的数的索引while(left <= right){int mid = (right -left) / 2 + left;if(d[mid] < nums[i]){pos = mid;left = mid + 1;}else{right = mid - 1;}}d[pos + 1] = nums[i];}}return len;}
}
关键字:中国肩章大全图解_外贸进出口代理公司_网页制作接单平台_培训学校机构有哪些

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: