当前位置: 首页 > news >正文

【代码随想录day28】【C++复健】122.买卖股票的最佳时机II ;376. 摆动序列;53. 最大子序和

122.买卖股票的最佳时机II

一周目做dp的时候也遇到过这个题,也知道这个题怎么不用递归做。这种题其实在知道怎么做了以后就会变得很简单,所以做出来也是洒洒水啦。

class Solution {
public:int maxProfit(vector<int>& prices) {int pro = 0;for(int i=1; i<prices.size(); i++){if(prices[i] > prices[i-1]){pro += prices[i] - prices[i-1];}}return pro;}
};

55. 跳跃游戏

也是一遍做出来了,不过做完之后看解析,写法和卡哥不太一样,卡哥是直接看最大下表覆盖能到哪里,我的这个写法相当于是一个汽车从nums的头开到尾,每个地方都有加油站,那每个nums[i]代表在这里加完油以后,最多能开再开几个地方。

那我这种想法我觉得还是比较形象的,必过相比卡哥的做法很显然还是麻烦了一点。(主要还是不知道一个for循环,如果我们给终止条件里面的值取一个变量,比如卡哥代码里代表最大覆盖范围的cover,那这个cover是会随着循环进行不断变化,还是固定成最开始传入的值,卡哥的代码告诉我是前者。)

除此之外,还漏掉了nums.size()==1时的情况。

class Solution {
public:bool canJump(vector<int>& nums) {int gas = nums[0];int i = 0;if(nums.size()==1){return true;}while(gas > 0){gas--;i++;if(nums[i] > gas){gas = nums[i];}if(i + gas >= nums.size()-1){return true;}}return false;}
};

45.跳跃游戏 II

一开始的想法把这题的思路想出来了八成左右,没做出来的主要原因是没做到变量的干湿分离:

第一遍写的时候我以为maxidex是固定的,但其实在不断地动态更新,导致盯着看了半天看似没啥问题,实则问题很大。

除此之外,判断条件也写成了<maxidx,实则应该是<=才对,边界处理也需要再斟酌。

class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1){return 0;}int step = 0;int maxidx = nums[0];int previdx = 0;while(maxidx < nums.size()-1){int endturn = maxidx;for(int i=previdx; i<=maxidx; i++){if(i+nums[i]>endturn){endturn = i+nums[i];}}previdx = maxidx+1;maxidx = endturn;step++;}return step+1;}
};

1005.K次取反后最大化的数组和

本题也是,思路上能想明白,但实现总是差点意思,导致做不出来。不过也是学到了不少。

关键问题1:如何找到最小的元素

我的做法是找到第一个非负数的下标i,将其与前一个下标的数的绝对值进行比较。但这样显然是麻烦了,让我们看看卡哥和GPT都是怎么做的:
卡哥:在sort的时候直接传入参数cmp,按绝对值大小排列,这样最右边的元素就是绝对值最小的

GPT:用了一个叫做min_element的函数,返回值指向nums中的最小值的位置,也就是一个迭代器。如果我们想要访问值,需要再前方加入一个*。这里*是解引用符,隐约好像听过又好像没听过的,还是学的不够扎实。

 
关键问题2:如何求和

使用accumulate(nums.begin(), nums.end(), 0),要传三个参数,第三个是和的初始值。要调用的库是<numeric>。其实和直接一个for循环是一样的。

关键问题3:循环终止条件

应该是i < nums.size() && k > 0,我只写了后面那个,会导致越界问题。

关键问题4:对于翻转操作的处理

因为前面我的做法是找到第一个非负数的下标i并且与前一个元素比较来决出最小,其实并不知道还剩多少次,单纯写了个i-k次for循环的nums[i] = -nums[i],这样其实是很不严谨的,因为如果最小的元素是i-1,那应该nums[i-1]翻转i-k+1次,如果是对nums[i]翻转才是i-k次。所以实际上这么搞是自找麻烦的,不如每次遇到一个负数就k--,这样才是好想的思路。

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int i=0;for(i=0; i < nums.size() && k > 0; i++){if (nums[i] < 0) {nums[i] = -nums[i];k--;} else {break; }}int min = *std::min_element(nums.begin(), nums.end());if(k%2 == 1){return accumulate(nums.begin(), nums.end(), 0) - min*2;}else{return accumulate(nums.begin(), nums.end(), 0);}}
};


http://www.mrgr.cn/news/71989.html

相关文章:

  • 万字长文解读深度学习——ViT、ViLT、DiT
  • 生成式模型api国际选择
  • 世界坐标系、相机坐标系、图像物理坐标系、像素平面坐标系
  • 自动化运维:提升效率与可靠性的关键
  • golang分布式缓存项目 Day2 单机并发缓存
  • c语言中孤立位(loner)的使用
  • (67)RLS滤波器用于信道均衡时的判决引导(Decision-Directed)自适应模式的MATLAB仿真
  • rust高级特征
  • 基于微信小程序的养老院管理系统的设计与实现,LW+源码+讲解
  • Qt---双缓冲绘图
  • 【bat】自动生成指定层级文件夹
  • pytorch奇怪错误
  • 数字信号处理Python示例(12)生成Chirp(线性调频)信号
  • 实验27:lcd12864液晶显示实验
  • CAN总线位同步的使用以及总线仲裁规则详解
  • 基于YOLOv5的人群密度检测系统设计与实现
  • 跟着尚硅谷学vue2—进阶版2.0—使用 Vue 脚手架2.0
  • 常用数字器件的描述-时序逻辑器件的描述
  • 类似keepalived的软件还有哪些
  • Docker部署Redis哨兵
  • 在 Service Worker 中caches.put() 和 caches.add()/caches.addAll() 方法他们之间的区别
  • 【知识科普】ARM架构和x86架构
  • CustomersettleController
  • 大循环引起CPU负载过高
  • Android命令行启动SoftAP功能
  • golang项目三层依赖架构,自底向上;依赖注入trpc\grpc