庆阳亚衡设计,优化网络推广外包,织梦网络公司网站源码,小程序代理加盟政策“星辰野草#xff0c;造出无边的天地~” 最⻓递增⼦序列
(1) 题目解析 (2) 算法原理 class Solution {
public:int lengthOfLIS(vectorint nums) {// 使用dp int n nums.size(), ret 1;// 初始化为1vectorint dp(n1,1);// 从第二个位置…
“星辰野草造出无边的天地~” 最⻓递增⼦序列
(1) 题目解析 (2) 算法原理 class Solution {
public:int lengthOfLIS(vectorint nums) {// 使用dp int n nums.size(), ret 1;// 初始化为1vectorint dp(n1,1);// 从第二个位置开始for(int i1;in;i){// 子序列搜索for(int j0;ji;j){// 可以进行拼接if(nums[j] nums[i]) dp[i] max(dp[i],dp[j] 1);}ret max(ret,dp[i]);}return ret;}
};class Solution {
public:int lengthOfLIS(vectorint nums) {// 使用贪心vectorint vec; // 记录子序列长度vec.push_back(nums[0]); // 初始化for(int i1;inums.size();i){// 如果是最大的直接插入即可if(vec.back() nums[i]) vec.push_back(nums[i]);else{// 二分查找int left 0,right vec.size() - 1;while(left right){int mid (left right) 1;// 哪个分支暗含“相等” 不能跳过midif(nums[i] vec[mid]) left mid1;else rightmid;}// 更新较小值vec[left] nums[i];}}return vec.size();}
}; 递增的三元⼦序列
(1) 题目解析 这题同上一道题相差无几甚至更为简单因为我们只需要判断这个子序列长度是否超过3。
(2) 算法原理
class Solution {
public:bool increasingTriplet(vectorint nums) {// 这里默认给b一个无穷大的值// 由nums中的小数来替换int a nums[0],b INT_MAX;for(int i1;inums.size();i){if(b nums[i]) return true; // 找打了else if(a nums[i]) b nums[i]; // 替换belse a nums[i];}return false;}
}; 最⻓连续递增序列
(1) 题目解析 (2) 算法原理 class Solution {
public:int findLengthOfLCIS(vectorint nums) {int n nums.size();int left 0,right 1,ret 0;while(left n){while(right n nums[right] nums[right-1]) right;ret max(ret,right - left);left right;}return ret;}
}; 买卖股票的最佳时机
(1) 题目解析
(2) 算法原理 class Solution {
public:int maxProfit(vectorint prices) {int prevMin prices[0], n prices.size();int ret 0;for(int i1;in;i){ret max(ret,prices[i] - prevMin);prevMin min(prevMin,prices[i]); // 更新}return ret;}
}; 买卖股票的最佳时机 Ⅱ
(1) 题目解析 (2) 算法原理 class Solution {
public:int maxProfit(vectorint prices) {// 方法1双指针贪心int n prices.size();int left 0,right left 1;int ret 0;while(left n){while(right n prices[right] prices[right - 1]) right;ret prices[right - 1] - prices[left];left right;}return ret;}
};class Solution {
public:int maxProfit(vectorint prices) {// 方法2拆分交易int ret 0;for(int i0;iprices.size()-1;i){if(prices[i] prices[i1]) ret prices[i1] - prices[i];}return ret;}
}; 本篇到此结束感谢你的阅读。
祝你好运向阳而生~
