【算法训练记录——Day32】

news/2024/7/14 7:10:57

Day32——贪心算法Ⅱ

  • 1.leetcode122买卖股票的最佳时机II
  • 2.leetcode55跳跃游戏
  • 3.leetcode45跳跃游戏II
  • 4.eetcode1005K次取反后最大化的数组和

目标:

  1. leetcode122买卖股票的最佳时机II
  2. leetcode55跳跃游戏
  3. leetcode45跳跃游戏II
  4. leetcode1005K次取反后最大化的数组和

1.leetcode122买卖股票的最佳时机II

在这里插入图片描述
思路:贪心没理解,这个题毫无头绪。感觉就是求递增子序列是吧。
贪心需要把问题分解为若干个子问题的集合,子问题是什么呢???想不到,看题解
优秀,其实就是每天的正利润之和,把一段时间分解为若干天,只要为正就买入
第一天没有利润,利润的序列比股票序列少一天
知道了这层关系,那这道题就很简单了

贪心:int maxProfit(vector<int>& prices) {int max = 0;for(int i = 1; i < prices.size(); i++) {int lirun = prices[i] - prices[i-1];if(lirun > 0)max += lirun;}return max;}

思路二:动态规划
待补充

2.leetcode55跳跃游戏

在这里插入图片描述
思路:直接就是忘了,看了一眼题解
怎么跳不重要,关键是覆盖范围,于是想到用一个变量记录当前能到达的最远点,遍历数组,更新最远点,最后只要最远点>size,那么就可以到达

	bool canJump(vector<int>& nums) {int maxSize = nums.size();int nowSize = 0;for(int i = 0; i < maxSize-1; i++) {// 如果当前范围不能再更新了,那就要退出// if(nowSize < i || nums[0] == 0) break;// 当前位置能到达的最远点如果小于等于当前位置,那就退出if(nowSize + nums[i] <= i) break;nowSize = max(nowSize, nums[i] + i);// 提前退出if(nowSize >= maxSize - 1) return true;}return nowSize >= maxSize-1;}

3.leetcode45跳跃游戏II

在这里插入图片描述
思路:

	int jump(vector<int>& nums) {if(nums.size() <= 1) return 0;int curDistance = 0; // 当前覆盖最远距离下标int nextDistance = 0; // 下一步覆盖的最远距离int res = 0;for(int i = 0; i < nums.size(); i++) {nextDistance = max(nums[i] + i, nextDistance);if(curDistance == i) {++res;curDistance = nextDistance;if(nextDistance >= nums.size() - 1) break;}}return res;}

4.eetcode1005K次取反后最大化的数组和

在这里插入图片描述

	static bool cmp(int a, int b) {return abs(a) > abs(b);}
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), cmp);       // 第一步for (int i = 0; i < nums.size(); i++) { // 第二步if (nums[i] < 0 && k > 0) {nums[i] *= -1;k--;}}if (k % 2 == 1) nums[nums.size() - 1] *= -1; // 第三步int result = 0;for (int a : nums) result += a;        // 第四步return result;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.cpky.cn/p/13258.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

高效、智能、安全:小型机房EasyCVR+AI视频综合监控解决方案

一、背景需求分析 随着信息技术的迅猛发展&#xff0c;小型机房在企事业单位中扮演着越来越重要的角色。为了确保机房的安全稳定运行&#xff0c;远程监控成为了必不可少的手段。 二、视频监控 视频监控是机房远程监控的重要组成部分。通过安装IP摄像机及部署视频监控系统Ea…

Unity3d 游戏暂停(timeScale=0)引起的deltaTime关联的系列问题解决

问题描述 游戏暂停的功能是通过设置timeScale0实现的&#xff0c;不过在暂停游戏的时候&#xff0c;需要对角色进行预览和设置&#xff0c;为了实现这个功能&#xff0c;是通过鼠标控制相机的操作&#xff0c;为了使相机的操作丝滑&#xff0c;获取鼠标操作系数乘以Time.delta…

人工智能--搭建人工神经网络

欢迎来到 Papicatch的博客 文章目录 &#x1f349;引言 &#x1f349;神经元与感知器 &#x1f348;神经元&#xff08;Neuron&#xff09; &#x1f348;感知器 &#x1f349;损失函数与梯度下降算法 &#x1f348;损失函数 &#x1f348;梯度下降算法 &#x1f349;…

小熊文件工具箱免费版

小熊文件工具箱是一款基于本地离线操作的一系列工具的合集&#xff0c;最大特点是各种批量任务的执行&#xff0c;包含了智能证件照&#xff0c;自动抠图&#xff0c;直播录制&#xff0c;九宫格切图&#xff0c;拼图&#xff0c;视频格式转换及压缩&#xff0c;zip压缩解压缩&…

PPT: Pre-trained Prompt Tuning for Few-shot Learning

文章汇总 当前的问题 当前的学者(a)、(b)、©都是通过微调模型(encoder/decoder)来适应下游任务。尽管效果很好&#xff0c;但是一方面代价很大&#xff0c;一方面在小样本设置下&#xff0c;微调模型这种做法性能差得多。本文的想法&#xff1a;通过一些预训练任务仅冻结…

湖南科技大学24计算机考研情况,软工学硕考数二,分数线290分,录取均分321分!

湖南科技大学&#xff08;Hunan University of Science and Technology&#xff09;坐落在伟人故里、人文圣地湘潭&#xff0c;处于长株潭核心区域&#xff0c;比邻湘潭九华经济技术开发区&#xff08;国家级&#xff09;&#xff0c;是应急管理部、国家国防科技工业局与湖南省…