目录
最⻓递增⼦序列(medium)
题目解析
1.题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/description/
2.题目描述
给你⼀个整数数组 nums ,找到其中最⻓严格递增⼦序列的⻓度。⼦序列是由数组派⽣⽽来的序列,删除(或不删除)数组中的元素⽽不改变其余元素的顺序。例
如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的⼦序列。
⽰例1:
输⼊:nums=[10,9,2,5,3,7,101,18]
输出:4
解释:最⻓递增⼦序列是[2,3,7,101],因此⻓度为4。⽰例2:
输⼊:nums=[0,1,0,3,2,3]
输出:4
⽰例3:
输⼊:nums=[7,7,7,7,7,7,7]
输出:1
提⽰:
◦ 1 <= nums.length <= 2500
◦ -10(4) <= nums[i] <= 10(4)
讲解算法原理
解法(贪⼼):
贪⼼策略:
我们在考虑最⻓递增⼦序列的⻓度的时候,其实并不关⼼这个序列⻓什么样⼦,我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后,我们就可以判断是否可以拼接到它的后⾯。
因此,我们可以创建⼀个数组,统计⻓度为 x 的递增⼦序列中,最后⼀个元素是谁。为了尽可能的让这个序列更⻓,我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
统计的过程中发现,数组中的数呈现「递增」趋势,因此可以使⽤「⼆分」来查找插⼊位置。
编写代码
cc++算法代码:
class Solution
{
public:
int lengthOfLIS(vector<int>& nums)
{
int n = nums.size();
vector<int> ret;
ret.push_back(nums[0]);
for(int i = 1; i < n; i++)
{
if(nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯,直接放 {
ret.push_back(nums[i]);
}
else
{
// ⼆分插⼊位置
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = (left + right) >> 1;
if(ret[mid] < nums[i]) left = mid + 1;
else right = mid;
}
ret[left] = nums[i]; // 放在 left 位置上 }
}
return ret.size();
}
};
java算法代码:
class Solution
{
public int lengthOfLIS(int[] nums)
{
ArrayList<Integer> ret = new ArrayList<>();
int n = nums.length;
ret.add(nums[0]);
for(int i = 1; i < n; i++)
{
if(nums[i] > ret.get(ret.size() - 1)) // 如果能接在最后⼀个元素后⾯,直接放
{
ret.add(nums[i]);
}
else
{
// ⼆分插⼊位置
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = (left + right) / 2;
if(ret.get(mid) < nums[i]) left = mid + 1;
else right = mid;
}
ret.set(left, nums[i]); // 放在 left 位置上
}
}
return ret.size();
}
}
递增的三元⼦序列(medium)
题目解析
1.题目链接:. - 力扣(LeetCode)
2.题目描述
给你⼀个整数数组 nums ,判断这个数组中是否存在⻓度为 3 的递增⼦序列。
如果存在这样的三元组下标 (i, j, k) 且满⾜ i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。
⽰例1:
输⼊:nums=[1,2,3,4,5]
输出:true
解释:任何i<j<k的三元组都满⾜题意
⽰例2:
输⼊:nums=[5,4,3,2,1]
输出:false
解释:不存在满⾜题意的三元组
⽰例3:
输⼊:nums=[2,1,5,0,4,6]
输出:true
解释:三元组(3,4,5)满⾜题意,因为nums[3]==0<nums[4]==4<nums[5]==6
提⽰:
◦ 1 <= nums.length <= 5 * 10(5)
◦ -2(31) <= nums[i] <= 2(31) - 1
讲解算法原理
解法(贪⼼):
贪⼼策略:
最⻓递增⼦序列的简化版。
不⽤⼀个数组存数据,仅需两个变量即可。也不⽤⼆分插⼊位置,仅需两次⽐较就可以找到插⼊位置。
编写代码
c++算法代码:
class Solution
{
public:
bool increasingTriplet(vector<int>& nums)
{
int a = nums[0], b = INT_MAX;
for(int i = 1; i < nums.size(); i++)
{
if(nums[i] > b) return true;
else if(nums[i] > a) b = nums[i];
else a = nums[i];
}
return false;
}
};
java算法代码:
class Solution
{
public boolean increasingTriplet(int[] nums)
{
int a = nums[0], b = Integer.MAX_VALUE;
for(int i = 1; i < nums.length; i++)
{
if(nums[i] > b) return true;
else if(nums[i] > a) b = nums[i];
else a = nums[i];
}
return false;
}
}
标签:第三篇,nums,int,递增,ret,算法,序列,left,贪心
From: https://blog.csdn.net/weixin_73861555/article/details/143050789