c++贪心
本篇文章，我将同大家一起学习c++的贪心！！！
目录
第一题
题目链接
题目解析
代码原理
代码编写
第二题
题目链接
题目解析
代码原理
代码编写
第三题
题目链接
题目解析
代码原理
代码编写
第四题
题目链接
题目解析
代码原理
代码编写
第五题
题目链接
题目解析
代码原理
代码编写
思路拓展
第六题
题目链接
题目解析
代码原理
代码编写
第一题
题目链接
300. 最长递增子序列 - 力扣（LeetCode）
题目解析
代码原理
代码编写
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(ret.back() < nums[i]) 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];
}
}
return ret.size();
}
};
第二题
题目链接
334. 递增的三元子序列 - 力扣（LeetCode）
题目解析
解释：三元子序列:条件：1.i - 1 < i < i + 1 2.nums[i - 1] < nums[i] < nums[i + 1]
代码原理
代码编写
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
int a = nums[0], b = INT_MAX;
for(int i = 1; i < n; i++)
{
if(nums[i] > b) return true;
else if( nums[i] > a) b = nums[i];
else a = nums[i];
}
return false;
}
};
第三题
题目链接
674. 最长连续递增序列 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
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] > nums[j - 1]) j++;
ret = max(ret, j - i);
i = j;
}
return ret;
}
};
第四题
题目链接
121. 买卖股票的最佳时机 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size(), ret = 0;
int min_prices = INT_MAX, max_prices = 0;
for(int i = 0; i < n; i++)
{
min_prices = min(min_prices, prices[i]);
max_prices = max(max_prices, prices[i] - min_prices);
}
return max_prices;
}
};
第五题
题目链接
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ret = 0;
for(int i = 0; i < prices.size(); i++)
{
if(i + 1 < prices.size() && prices[i] < prices[i + 1]) ret += prices[i + 1] - prices[i];
}
return ret;
}
};
思路拓展
第一种思路：找到上升段，然后末减初
第二种思路：找到每一上升小段，就进行一次末减初，然后移动右指针，持续计算，求出最大结果
代码
int n = prices.size();
int ret = 0;
// for(int left = 0; left < n; left++)
// {
// int right = left;
// while(right + 1 < n && prices[right + 1] > prices[right])
// {
// right++;
// }
// ret += prices[right] - prices[left];
// left = right;
// }第六题
题目链接
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int n = nums.size(), m = 0, min_nums = INT_MAX,ret = 0;
for(int i = 0; i < n; i++)
{
if(nums[i] < 0)
m++;
min_nums = min(min_nums, abs(nums[i]));
}
if(m > k)
{
sort(nums.begin(),nums.end());
for(int i = 0; i < k; i++)
{
ret += -nums[i];
}
for(int i = k; i < n; i++)
{
ret += nums[i];
}
}
else
{
for(auto cur: nums)
{
ret += abs(cur);
}
if((k - m) % 2)
ret -= min_nums * 2;
}
return ret;
}
};
注意：这里的最小值一定要记得加绝对值。
本篇文章的内容就先到这里，最后也祝大家除夕快乐，春节快乐！！！
记得一键三连哦！！！
