代码随想录算法训练营第36期DAY35

news/2024/7/25 3:40:51/文章来源:https://blog.csdn.net/illuosion7/article/details/139105113

DAY35

122买卖股票的最佳时机ii

很巧妙,也很难想到:计算每天的利润(今天卖出,昨天买入的利润),只取正数相加。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int diif=0,res=0;
  5.         for(int i=0;i<prices.size()-1;i++){
  6.             diif=prices[i+1]-prices[i];
  7.             if(diif<0) diif=0;
  8.             res+=diif;
  9.         }
  10.         return res;
  11.     }
  12. };

55跳跃游戏

把可选的(每次可选跳几步)复杂问题转化为覆盖单位问题(能覆盖到哪)。

自己还是写不出覆盖的代码。多学一下;

关键在于 i<=cover; i要在覆盖范围内移动;

取max也是关键

  1. class Solution {
  2. public:
  3.     bool canJump(vector<int>& nums) {
  4.         int cover=0;
  5.         if(nums.size()==1return true;
  6.         //关键在于 i<=cover; i要在覆盖范围内移动
  7.         for(int i=0;i<=cover;i++){
  8.             cover=max(nums[i]+i,cover);//也是关键
  9.             if(cover>=nums.size()-1return true;
  10.         }
  11.         return false;
  12.     }
  13. };

45跳跃游戏ii

难呀。复杂。

方法一:

用最少的步数,尽可能覆盖最多的范围。

当前覆盖范围用完,但是仍然没有覆盖到终点,就启动下一步覆盖范围(nextcover)

  1. class Solution {
  2. public:
  3.     int jump(vector<int>& nums) {
  4.         int cur=0,next=0,res=0;
  5.         if(nums.size()==1return 0;
  6.         for(int i=0;i<nums.size();i++){
  7.             next=max(next,i+nums[i]);
  8.             if(i==cur){
  9.                 res++;
  10.                 cur=next;
  11.                 if(cur>=nums.size()-1break;
  12.             }
  13.         }
  14.         return res;
  15.     }
  16. };

442数组中重复的数据,中等

学习参考:b站up主,老汤讲底层基础。

(高频算法面试题:找出数组中的重复元素)

[https://www.bilibili.com/video/BV1hG411q7q6/?spm_id_from=333.788&vd_source=baa5f3043be10f96febc0c68c5983df5]

注意要找到所有出现两次的整数,这样的整数可能不只有一个。        

  1. 暴力线性查找
  1. vector<int> res;
  2. for(int i=0;i<nums.size();i++){
  3.    for(int j=i+1;j<nums.size();j++){
  4.        if(nums[i]==nums[j]) res.push_back(nums[i]);
  5.     }
  6. }

  1. 排序+二分查找

二分怎么用?学一学:

首先对数组排序,然后使用二分查找来查找后面的元素中是否有和当前元素相同的元素,如果找到,就添加到结果中。

  1. class Solution {
  2. public:
  3.     int EFfind(int l,int r,vector<int>&nums,int target){
  4.         while(l<r){
  5.             int mid=(l+r+1)/2;
  6.             if(nums[mid]<=target) l=mid;
  7.             else r=mid-1;
  8.         }
  9.         if(nums[l]!=target) return -1;
  10.         return l;
  11.     }
  12.     vector<intfindDuplicates(vector<int>& nums) {
  13.         sort(nums.begin(),nums.end());
  14.         vector<int> res;
  15.         for(int i=0;i<nums.size()-1;i++){
  16.             if(EFfind(i+1,nums.size()-1,nums,nums[i])!=-1) res.push_back(nums[i]);
  17.         }
  18.         return res;
  19.     }
  20. };

  1. 排序+双指针

法2没有用到相邻这一特性,这里用到了:

  1. class Solution {
  2. public:
  3.     vector<intfindDuplicates(vector<int>& nums) {
  4.         sort(nums.begin(),nums.end());
  5.         vector<int>res;
  6.         for(int i=0;i<nums.size();i++){
  7.             int j=i+1;
  8.             if(j<nums.size()&&nums[i]==nums[j]) res.push_back(nums[i]);
  9.         }
  10.         return res;
  11.     }
  12. };

  1. 哈希查找
  1. unordered_set<intset;
  2. vector<int>res;
  3. for(int i=0;i<nums.size();i++){
  4.     if(set.count(nums[i])) res.push_back(nums[i]);
  5.     set.insert(nums[i]);
  6. }

  1. 数组代替哈希表
  1. class Solution {
  2. public:
  3.     vector<intfindDuplicates(vector<int>& nums) {
  4.         vector<int>res;
  5.         int cnt[100010]={0};
  6.         for(int i=0;i<nums.size();i++){
  7.             if(cnt[nums[i]]) res.push_back(nums[i]);
  8.             cnt[nums[i]]++;
  9.         }
  10.         return res;
  11.     }
  12. };

  1. 最佳解决方案,符合题目要求:时间复杂度O(n),常量级的空间复杂度。

没必要了。。

复习一下树的对称的判断

101对称二叉树

还是不会呀,每天抽时间来复习做过的题吧。

这个题还是有很多细节,比如:什么时候才能继续往下递归;虽然是遍历树,但是仍然要接住他。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool isres(TreeNodeleft,TreeNoderight){
  15.         //排除空节点,避免空指针报错。且只有值相等时,才能往下递归
  16.         if(left==nullptr&&right==nullptr) return true;
  17.         else if(left==nullptr&&right!=nullptr) return false;
  18.         else if(left!=nullptr&&right==nullptr) return false;
  19.         else if(left->val!=right->val) return false;
  20.         bool inside=isres(left->right,right->left);
  21.         bool outside=isres(left->left,right->right);
  22.         return inside&&outside;
  23.     }
  24.     bool isSymmetric(TreeNode* root) {
  25.         if(root==nullptr) return true;
  26.         return isres(root->left,root->right);
  27.     }
  28. };

100相同的树

注意方向就好。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     bool findres(TreeNode*p,TreeNode*q){
  15.         if(p==nullptr&&q==nullptrreturn true;
  16.         else if(p!=nullptr&&q==nullptrreturn false;
  17.         else if(p==nullptr&&q!=nullptrreturn false;
  18.         else if(p->val!=q->val) return false;
  19.         bool in=findres(p->left,q->left);
  20.         bool out=findres(p->right,q->right);
  21.         return in&&out;
  22.     }
  23. public:
  24.     bool isSameTree(TreeNode* p, TreeNode* q) {
  25.     return findres(p,q);
  26.     }
  27. };

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JAVA云HIS医院系统源码 云HIS运维平台源码 融合B/S版电子病历系统,支持电子病历四级,saas模式

JAVA云HIS医院系统源码 云HIS运维平台源码 融合B/S版电子病历系统&#xff0c;支持电子病历四级&#xff0c;saas模式 HIS系统就是医院信息管理系统&#xff0c;HIS系统是整个医院信息化的核心&#xff0c;门诊、住院、药房、药库等都是由HIS系统来承载起来的&#xff0c;所以…

【MATLAB源码-第215期】基于matlab的8PSK调制CMA均衡和RLS-CMA均衡对比仿真,对比星座图和ISI。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 CMA算法&#xff08;恒模算法&#xff09; CMA&#xff08;Constant Modulus Algorithm&#xff0c;恒模算法&#xff09;是一种自适应盲均衡算法&#xff0c;主要用于消除信道对信号的码间干扰&#xff08;ISI&#xff09;…

package.json中peerDependencies的使用场景

文章目录 peerDependencies 的使用场景peerDependencies 的使用案例为什么使用 peerDependencies需要注意的事项主要作用 ✍创作者&#xff1a;全栈弄潮儿 &#x1f3e1; 个人主页&#xff1a; 全栈弄潮儿的个人主页 &#x1f3d9;️ 个人社区&#xff0c;欢迎你的加入&#xf…

python中的空语句以及对于条件语句的总结

if条件&#xff1a; 代码块 if条件&#xff1a; 代码块1 else&#xff1a; 代码块2 if条件1&#xff1a; 代码块1 elif条件2&#xff1a; 代码块2 else&#xff1a; 代码块3

【class18】人工智能初步----语音识别(4)

【class17】 上节课&#xff0c;我们学习了: 语音端点检测的相关概念&#xff0c;并通过代码切分和保存了音频。 本节课&#xff0c;我们将学习这些知识点&#xff1a;1. 序列到序列模型2. 循环神经网络3. 调用短语音识别接口 知其然&#xff0c;知其所以然 在调用语…

【最新更新】上市公司-全要素生产率(1999-2023年)(数据+5种方法测算)

上市公司的全要素生产率是指在一定时期内&#xff0c;上市公司通过使用各种生产要素(包括资本、劳动力、技术等)所创造的价值。它是衡量上市公司经营绩效的重要指标之一&#xff0c;可以反映出公司的生产效率和创新能力。全要素生产率的计算方法有很多种&#xff0c;其中最常见…

Springboot项目——博客平台

前言&#xff1a;为巩固之前学习的知识&#xff0c;同时锻炼自己的代码能力&#xff0c;项目经验&#xff0c;熟悉前后端交互方式等&#xff0c;特此完成一个博客平台系统。&#xff08;总之&#xff0c;为了学习&#xff0c;为了进步&#xff09; 博客平台&#xff1a;本项目…

鸿蒙开发接口UI界面:【@ohos.mediaquery (媒体查询)】

媒体查询 说明&#xff1a; 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 &#xff1a; gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 导入模块 import mediaquery from ohos.media…

Python图像处理库全面详细解析

目录 引言 PIL和Pillow&#xff1a;基础但强大的图像处理 PIL到Pillow的演变 功能亮点 实际应用案例 Pillow的适用场景 结论 ​编辑 OpenCV&#xff1a;计算机视觉的瑞士军刀 OpenCV的核心特点 功能亮点 实际应用案例 OpenCV的适用场景 结论 ​编辑 Scikit-Imag…

AI预测福彩3D采取888=3策略+和值012路一缩定乾坤测试5月28日预测第4弹

昨天的第二套方案已命中&#xff0c;第一套方案由于杀了对子&#xff0c;导致最终出错。 今天继续基于8883的大底&#xff0c;使用尽可能少的条件进行缩号&#xff0c;同时&#xff0c;同样准备两套方案&#xff0c;一套是我自己的条件进行缩号&#xff0c;另外一套是8883的大底…

WordPress国外超人气主题Vikinger汉化版

WordPress国外超人气主题Vikinger汉化版 前言效果图安装教程领取主题下期更新预报 前言 我们在上一个教程已经学过如何安装WordPress&#xff0c;所以现在不用多说。 效果图 安装教程 下载后先本地解压&#xff0c;找到vikinger.zip文件&#xff0c;上传安装并启用主题。 访…

LeetCode题练习与总结:有序链表转换二叉搜索树--109

一、题目描述 给定一个单链表的头节点 head &#xff0c;其中的元素 按升序排序 &#xff0c;将其转换为平衡二叉搜索树。 示例 1: 输入: head [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0&#xff0c;-3,9&#xff0c;-10,null,5]&#xff0c;它表…

区块链钱包如果丢失了私钥或助记词,资产还能恢复吗?

如果你丢失了区块链钱包的私钥或助记词&#xff08;通常是用于恢复钱包的短语或种子&#xff09;&#xff0c;那么你的资产在大多数情况下是无法恢复的。私钥是访问和控制你在区块链上资产的唯一凭证&#xff0c;而助记词&#xff08;如BIP39标准中的12、18、24个单词的短语&am…

MySQL中Undo-log是什么?有什么作用?

2.6.1. Undo-log撤销日志 Undo即撤销的意思&#xff0c;通常也称为回滚日志&#xff0c;用来给MySQL撤销SQL操作的。 当一条写入类型的SQL执行时&#xff0c;都会记录Undo-log日志&#xff0c;Undo-log并不存在单独的日志文件&#xff0c;InnoDB默认是将Undo-log存储在xx.ibd…

java项目——图书管理系统

文章目录 前言图书管理系统整体框架&#xff1a;book包user包Main包&#xff1a;iooperation包总结&#xff1a; 前言 针对这些天所学的javaSE的知识&#xff0c;用一个小项目来实践一下。 图书管理系统 整体框架&#xff1a; 采取面向对象的思想实现此项目&#xff0c;首先…

企业如何正确地利用LLM大模型?

大型语言模型 (LLM) 不值得信任。就是这样。 考虑到它们先进的 AI 能力以及当今强大的基础模型的普遍知识&#xff0c;这似乎是一件令人惊讶的事情。然而&#xff0c;问题的关键在于 LLM 无法解释其输出。你不能信任 LLM 的结果&#xff0c;不是因为它不准确&#xff0c;而是因…

超市进销存|基于SprinBoot+vue的超市进销存系统(源码+数据库+文档)

超市进销存系统 目录 基于SprinBootvue的超市进销存系统 一、前言 二、系统设计 三、系统功能设计 1 登录注册 2 管理员功能模块 3员工功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#x…

golang中的md5、sha256数据加密文件md5/sha256值计算步骤和运行内存图解

在go语言中对数据计算一个md5&#xff0c;或sha256和其他语言 如java, php中的使用方式稍有不同&#xff0c; 那就是要加密的数据必须通过流的形式写入到你创建的Hash对象中。 Hash数据加密步骤 1. 先使用对应的加密算法包中的New函数创建一个Hash对象&#xff0c;(这个也就是…

手搓单链表(无哨兵位)(C语言)

目录 SLT.h SLT.c SLTtest.c 测试示例 单链表优劣分析 SLT.h #pragma once#include <stdio.h> #include <assert.h> #include <stdlib.h>typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next; }SLTNode;//打印…

Hololens 2 新建自定义按钮

官方链接地址 1、创建Cube 2、添加PressableButton脚本&#xff0c;并点击AddNearin… 3、把Cube拖入到MovingButtonVisuals变量中 4、点击NearInteractionTouchable组件&#xff08;这个组件是添加和上一个脚本绑定的&#xff0c;自动添加上来的&#xff09;上的Fix… 5、…