网站模板 wordpress,wordpress书单,只做自己网站,做创新方法工作的网站#x1f4dd;前言说明#xff1a;
本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录#xff0c;按专题划分每题主要记录#xff1a;#xff08;1#xff09;本人解法 本人屎山代码#xff1b;#xff08;2#xff09;优质解法 优质代码#xff1b;#xff…前言说明
本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录按专题划分每题主要记录1本人解法 本人屎山代码2优质解法 优质代码3精益求精更好的解法和独特的思想如果有的话4贪心策略正确性的 “证明”文章中的理解仅为个人理解。如有错误感谢纠错 个人简介努力学习ing 本专栏C刷题专栏 其他专栏C语言入门基础python入门基础C学习笔记Linux CSDN主页 愚润泽 你可以点击下方链接进行其他贪心算法题目的学习
点击链接开始学习贪心day1贪心day2贪心day3贪心day4贪心day5贪心day6贪心day7贪心day8贪心day9贪心day10
也可以点击下面连接学习其他算法
点击链接开始学习优选专题动态规划递归、搜索与回溯贪心算法题目122. 买卖股票的最佳时机 II个人解1005. K 次取反后最大化的数组和个人解2418. 按身高排序个人解122. 买卖股票的最佳时机 II
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
个人解
思路
拆分成一天一天进行无限次交易 后一天比当前股票便宜就重新买入比当前股票贵就直接卖出 (贪心策略) 细节: 因为可能出现连续递增所以在卖出后直接将当天价格作为买入的价格继续贪心其他解法也可以用一个双指针去找每个上升区间的开始和结束位置然后添加利润
屎山代码
class Solution {
public:int maxProfit(vectorint prices) {int PreMIN INT_MAX;int ans 0;for(auto x: prices){if(x PreMIN)PreMIN x;else{ans x - PreMIN;PreMIN x; // 代表未买入状态同时避免连续递增的股票}}return ans;}
};时间复杂度O(n)O(n)O(n) 空间复杂度O(1)O(1)O(1) 1005. K 次取反后最大化的数组和
题目链接https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
个人解
思路
有点数学题的感觉 先将数组排序贪心策略: 从小到大现将负数取反如果没有负数了, 则 k % 2 。如果结果为 1 则将绝对值最小的数取反)
屎山代码
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {ranges::sort(nums);int sum 0;int Min INT_MAX;for(auto num: nums){Min min(Min, abs(num));if(num 0 k 0){sum - num;k--;}elsesum num;}if(k % 2) // 如果还有取反次数则剩下的一定为非负数了sum - 2 * Min; // 把之前加上的减掉return sum;}
};时间复杂度O(nlogn)O(nlogn)O(nlogn) 空间复杂度O(1)O(1)O(1) 2418. 按身高排序
题目链接https://leetcode.cn/problems/sort-the-people/description/
个人解
屎山代码
class Solution {
public:vectorstring sortPeople(vectorstring names, vectorint heights) {int n names.size();vectorpairint, int hash; // 身高, 下标, 存在vector中便于后续排序for(int i 0; i n; i)hash.emplace_back(heights[i], i);ranges::sort(hash.begin(), hash.end(), [](const auto a, const auto b){return a.first b.first; // 大的优先级高});vectorstring ans;for(auto [h, index]: hash)ans.emplace_back(names[index]);return ans;}
};时间复杂度O(nlogn)O(nlogn)O(nlogn) 空间复杂度O(n)O(n)O(n) 我的分享也就到此结束啦 要是我的分享也能对你的学习起到帮助那简直是太酷啦 若有不足还请大家多多指正我们一起学习交流 公主王子点赞→收藏⭐→关注 感谢大家的观看和支持祝大家都能得偿所愿天天开心
