本文主要是介绍[Algorithm][贪心][最长递增子序列][递增的三元子序列][最长连续递增序列][买卖股票的最佳时机][买卖股票的最佳时机Ⅱ]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 1.最长递增子序列
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 2.递增的三元子序列
- 1.题目链接
- 2.算法原理详解
- 3.题目链接
- 3.最长连续递增序列
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 4.买卖股票的最佳时机
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 5.买卖股票的最佳时机 II
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
1.最长递增子序列
1.题目链接
- 最长递增子序列
2.算法原理详解
-
基本思想:
- 动态规划
- 二分查找
-
动态规划思路:
- 状态表示:以
i
位置的元素为结尾的所有的子序列中,最长递增子序列的长度 - 状态转移方程:
dp[i] = max(dp[j] + 1) (j < i && nums[j] < nums[i])
- 该思路中,并不关心该序列长什么样子,只在乎”最后一个元素”是谁
- 状态表示:以
-
贪心优化:
- 存什么;所有长度为
x
的递增子序列中,最后一个元素的最小值 - 存哪里:所有大于等于
nums[i]
的最小值的位置
- 存什么;所有长度为
-
利用二分优化:时间复杂度: O ( N ) O(N) O(N) -> O ( l o g N ) O(log_N) O(logN)
3.代码实现
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 - left) / 2;if(ret[mid] < nums[i]){left = mid + 1;}else{right = mid;}}ret[left] = nums[i];}}return ret.size();
}
2.递增的三元子序列
1.题目链接
- 递增的三元子序列
2.算法原理详解
- 本题的贪心策略和最长递增子序列一样
- 但是本题只需两个变量即可完成贪心,无需数组
- 但是本题只需两个变量即可完成贪心,无需数组
3.题目链接
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;
}
3.最长连续递增序列
1.题目链接
- 最长连续递增序列
2.算法原理详解
- 思路;贪心 + 双指针
3.代码实现
int findLengthOfLCIS(vector<int>& nums)
{int n = nums.size(), ret = 0;for(int i = 0; i < n; ){int j = i + 1;while(j < n && nums[j - 1] < nums[j]){j++;}ret = max(ret, j - i);i = j; // 贪心}return ret;
}
4.买卖股票的最佳时机
1.题目链接
- 买卖股票的最佳时机
2.算法原理详解
- 思路:贪心 + 一个变量标记“前缀最小值”
3.代码实现
int maxProfit(vector<int>& prices)
{int ret = 0, prevMin = INT_MAX;for(int i = 0; i < prices.size(); i++){if(prices[i] > prevMin){ret = max(ret, prices[i] - prevMin);}prevMin = min(prices[i], prevMin); // 贪心}return ret;
}
5.买卖股票的最佳时机 II
1.题目链接
- 买卖股票的最佳时机 II
2.算法原理详解
-
贪心:只要能获得正收益,就交易
-
实现一:双指针
-
实现二:拆分交易,把交易拆成一天一天
3.代码实现
// v1.0 双指针
int maxProfit(vector<int>& p)
{int ret = 0, n = p.size();for(int i = 0; i < n; i++){int j = i;while(j + 1 < n && p[j + 1] > p[j]){j++;}ret += p[j] - p[i];i = j;}return ret;
}
---------------------------------------------------------
// v2.0 拆分成一天一天
int maxProfit(vector<int>& p)
{int ret = 0;for(int i = 1; i < p.size(); i++){if(p[i - 1] < p[i]){ret += p[i] - p[i - 1];}}return ret;
}
这篇关于[Algorithm][贪心][最长递增子序列][递增的三元子序列][最长连续递增序列][买卖股票的最佳时机][买卖股票的最佳时机Ⅱ]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!