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

最后一次更新,之后去复习专业课和简历

583两个字符串的删除操作

自己做出来了:

Code:

  1. class Solution {
  2. public:
  3. //找到公共子序列的最大长度dp 最小步数=串1.size-dp+串2.size-dp
  4.     int minDistance(string word1, string word2) {
  5.         vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
  6.         dp[0][0]=0;
  7.         for(int i=1;i<=word1.size();i++){
  8.             for(int j=1;j<=word2.size();j++){
  9.                 if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
  10.                 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  11.             }
  12.         }
  13.         return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
  14.     }
  15. };

72编辑距离

没思路,明天学。积累经验

拓展思维:word2转变到word1也可以。

别人的删,就相当于我的增。Dp[i][j]=dp[i][j-1]+1

  1. class Solution {
  2. public:
  3.     int minDistance(string word1, string word2) {
  4.         vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
  5.         for(int i=0;i<=word1.size();i++) dp[i][0]=i;
  6.         for(int i=0;i<=word2.size();i++) dp[0][i]=i;
  7.         for(int i=1;i<=word1.size();i++){
  8.             for(int j=1;j<=word2.size();j++)
  9.             {
  10.                 if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
  11.                 else dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));
  12.             }
  13.         }
  14.         return dp[word1.size()][word2.size()];
  15.     }
  16. };

647回文子串

写的很好,我想不到用i j的距离(而不是索引字符)来做单字符与双字符的回文。

Code:

注意都是在s[i]==s[j]时候改值

  1. class Solution {
  2. public:
  3.     int countSubstrings(string s) {
  4.         int res = 0;
  5.         vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
  6.         for (int i = s.size() - 1; i >= 0; i--) {
  7.             for (int j = i; j < s.size(); j++) {
  8.                 if (s[j] == s[i]) {
  9.                     if (j - i <= 1) {
  10.                         res++;
  11.                         dp[i][j] = true;
  12.                     } else if (dp[i + 1][j - 1]) {
  13.                         res++;
  14.                         dp[i][j] = true;
  15.                     }
  16.                 }
  17.             }
  18.         }
  19.         return res;
  20.     }
  21. };

516最长回文子序列

经验题,继续学:

注意里面的加减符号别弄错,理解题意是关键。

  1. class Solution {
  2. public:
  3.     int longestPalindromeSubseq(string s) {
  4.         vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));
  5.         for(int i=0;i<s.size();i++) dp[i][i]=1;
  6.         for(int i=s.size()-1;i>=0;i--){
  7.             for(int j=i+1;j<s.size();j++){
  8.                 if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
  9.                 else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
  10.             }
  11.         }
  12.         return dp[0][s.size()-1];
  13.     }
  14. };

单调栈

整半天才发现自己把栈顶(top), 栈底给弄反了,要重做之前的题目。

739每日温度

朴素法,超时:

  1. class Solution {
  2. public:
  3. //朴素法
  4.     vector<intdailyTemperatures(vector<int>& temperatures) {
  5.         vector<intres(temperatures.size(),0);
  6.         for(int i=0;i<temperatures.size();i++){
  7.             int idx=temperatures[i];
  8.             for(int j=i+1;j<temperatures.size();j++){
  9.                 if(idx<temperatures[j]){
  10.                     res[i]=j-i;
  11.                     break;
  12.                 }
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. };

注意!

单调栈里存的是下标。

未精简的代码:

  1. class Solution {
  2. public:
  3.     vector<intdailyTemperatures(vector<int>& temperatures) {
  4.         vector<intres(temperatures.size(),0);
  5.         stack<int> s;
  6.         s.push(0);
  7.         for(int i=1;i<temperatures.size();i++){
  8.             if(temperatures[i]<temperatures[s.top()]) s.push(i);
  9.             else if(temperatures[i]==temperatures[s.top()]) s.push(i);
  10.             else{
  11.                 while(!s.empty()&&temperatures[i]>temperatures[s.top()]){
  12.                     res[s.top()]=i-s.top();
  13.                     s.pop();
  14.                 }
  15.                 s.push(i);
  16.             }
  17.         }
  18.         return res;
  19.     }
  20. };

精简后的代码:

  1. class Solution {
  2. public:
  3.     vector<intdailyTemperatures(vector<int>& temperatures) {
  4.         vector<intres(temperatures.size(),0);
  5.         stack<int> s;
  6.         for(int i=0;i<temperatures.size();i++){
  7.             while(!s.empty()&&temperatures[i]>temperatures[s.top()]){
  8.                 res[s.top()]=i-s.top();
  9.                 s.pop();
  10.             }
  11.             s.push(i);
  12.         }
  13.         return res;
  14.     }
  15. };

496下一个更大元素i

没想到:“数组中没有重复数字,用map做两个数组的映射。

根据数值快速找到下标,还可判断nums2[i]是否在nums1中出现过。

当使用集合来解决哈希问题的时候,优先使用unordered_set,因为他的查询和增删效率是最优的。”

注意注释上的东西:

  1. class Solution {
  2. public:
  3.     vector<intnextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
  4.         unordered_map<int,intmap;
  5.         vector<intres(nums1.size(),-1);
  6.         for(int i=0;i<nums1.size();i++) map[nums1[i]]=i;
  7.         stack<int> s;
  8.         s.push(0);
  9.         for(int i=1;i<nums2.size();i++){
  10.             while(!s.empty()&&nums2[i]>nums2[s.top()]){
  11.                 if(map.count(nums2[s.top()])>0){
  12.                     //idx注意怎么求,别弄错
  13.                     int idx=map[nums2[s.top()]];
  14.                     res[idx]=nums2[i];
  15.                 }
  16.                 //这句话不要写在if里面
  17.                 s.pop();
  18.             }
  19.             s.push(i);
  20.         }
  21.         return res;
  22.     }
  23. };

待理清思路,二刷:

  1. class Solution {
  2. public:
  3.     vector<intnextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
  4.         unordered_map<int,intmap;
  5.         vector<intres(nums1.size(),-1);
  6.         for(int i=0;i<nums1.size();i++) map[nums1[i]]=i;
  7.         stack<int> s;
  8.         s.push(0);
  9.         for(int i=1;i<nums2.size();i++){
  10.             while(!s.empty()&&nums2[i]>nums2[s.top()]){
  11.                 if(map.count(nums2[s.top()])>0){
  12.                     res[map[nums2[s.top()]]]=nums2[i];
  13.                 }
  14.                 s.pop();
  15.             }
  16.             s.push(i);
  17.         }
  18.         return res;
  19.     }
  20. };

503下一个更大元素ii

1 很妙的想法:数组拼接,取res.size()/2

注意insert的写法:

  1. class Solution {
  2. public:
  3.     vector<intnextGreaterElements(vector<int>& nums) {
  4.         vector<intnewnums(nums.begin(),nums.end());
  5.         nums.insert(nums.end(),newnums.begin(),newnums.end());
  6.         vector<intres(nums.size(),-1);
  7.         stack<int> s;
  8.         s.push(0);
  9.         for(int i=1;i<nums.size();i++){
  10.             while(!s.empty()&&nums[i]>nums[s.top()]){
  11.                 res[s.top()]=nums[i];
  12.                 s.pop();
  13.             }
  14.             s.push(i);
  15.         }
  16.         res.resize(res.size()/2);
  17.         return res;
  18.     }
  19. };

2 对于“循环”,要想到:用mod (%)来操作。

要注意的是 ,res[idx];; idx=s.top()相关的。

  1. class Solution {
  2. public:
  3.     vector<intnextGreaterElements(vector<int>& nums) {
  4.         vector<intres(nums.size(),-1);
  5.         stack<int> s;
  6.         s.push(0);
  7.         for(int i=1;i<2*nums.size();i++){
  8.             while(!s.empty()&&nums[i%nums.size()]>nums[s.top()]){
  9.                 res[s.top()]=nums[i%nums.size()];
  10.                 s.pop();
  11.             }
  12.             s.push(i%nums.size());
  13.         }
  14.         return res;
  15.     }
  16. };

42接雨水,困难

对于不规则的阴影面积(由单位面积组成)求解,应当明确:按行计算还是按列计算。

按列计算,朴素法:一次性写对了,真的进步了很多,坚持每天复现+做复试真题来加强吧。

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         int sum=0;
  5.         for(int i=0;i<height.size();i++){
  6.             if(i==0||i==height.size()-1continue;
  7.             int maxleft=height[0];
  8.             int maxright=height[height.size()-1];
  9.             for(int j=0;j<=i;j++) maxleft=max(maxleft,height[j]);
  10.             for(int j=height.size()-1;j>=i;j--) maxright=max(maxright,height[j]);
  11.             int mywater=min(maxleft,maxright)-height[i];
  12.             if(mywater>0) sum+=mywater;
  13.         }
  14.         return sum;
  15.     }
  16. };

按列计算,双指针优化:

双指针优化 求左右最大的语句写错了。在纸上写一下就写对了,不要空想:

求右边的最大:如果当前自己的高度是最大的,那么自己就是最大height[i],;

反正,我们需要继承之前的maxright结果。即:maxright[i+1];

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         int sum=0;
  5.         vector<intmaxleft(height.size(),height[0]);
  6.         vector<intmaxright(height.size(),height[height.size()-1]);
  7.         for(int j=1;j<height.size();j++) maxleft[j]=max(maxleft[j-1],height[j]);
  8.         for(int j=height.size()-2;j>=0;j--) maxright[j]=max(maxright[j+1],height[j]);
  9.         for(int i=0;i<height.size();i++){
  10.             if(i==0||i==height.size()-1continue;
  11.             int mywater=min(maxleft[i],maxright[i])-height[i];
  12.             if(mywater>0) sum+=mywater;
  13.         }
  14.         return sum;
  15.     }
  16. };

单调栈:

一旦形成槽,就要计算接水量,所以从栈顶部到栈底,应当是维护递增。

注意是按行计算。

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         int sum=0;
  5.         stack<int> s;
  6.         s.push(0);
  7.         for(int i=1;i<height.size();i++){
  8.             if(height[i]<height[s.top()]) s.push(i);
  9.             else if(height[i]==height[s.top()]){
  10.                 s.pop();
  11.                 s.push(i);
  12.             }
  13.             else{
  14.                 while(!s.empty()&&height[i]>height[s.top()]){
  15.                     int mid=s.top();
  16.                     s.pop();
  17.                     if(!s.empty()){
  18.                         int h=min(height[i],height[s.top()])-height[mid];
  19.                         int w=i-s.top()-1;
  20.                         int mywater=h*w;
  21.                         if(mywater>0) sum+=mywater;
  22.                         //按行计算,所以下一句还不能做pop();
  23.                     }
  24.                 }
  25.                 //记得入栈
  26.                 s.push(i);
  27.             }
  28.         }
  29.         return sum;
  30.     }
  31. };

正好二刷,单调栈写法:

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         int sum=0;
  5.         stack<int> s;
  6.         s.push(0);
  7.         for(int i=1;i<height.size();i++){
  8.             while(!s.empty()&&height[i]>height[s.top()]){
  9.                 int mid=s.top();
  10.                 s.pop();
  11.                 if(!s.empty()){
  12.                     int h=min(height[i],height[s.top()])-height[mid];
  13.                     int w=i-s.top()-1;
  14.                     if(w*h>0) sum+=(w*h);
  15.                 }
  16.             }
  17.             s.push(i);
  18.         }
  19.         return sum;
  20.     }
  21. };

你可能会好奇:为什么while 里面的if要去计算宽度呢?不是按行计算吗?

因为外层是while,i不更新,却一直在弹出并计算水量。所以宽度不一定是1,宽度是动态变化的(根据栈的弹出。)

84柱状图中最大的矩形,困难

最后一题了,以后都是二刷或者做类似的题型。

因为每次只在一个柱子上搜结果,不累加,期望尽量搜到最大结果。

那么应当:往i的左边找最矮在哪,往i的右边找最矮的在哪(这些都要高于或等于i)。若左右有矮于i的,就不往那边搜(因为这样搜到的结果必定小于等于其他矮柱子搜到的结果,画图就知道了)。跨度*高度就是i搜到的矩形结果。

知道上述思路,就可以写算法去实现了。

朴素(超时):

  1. class Solution {
  2. public:
  3.     int largestRectangleArea(vector<int>& heights) {
  4.         int res=0;
  5.         for(int i=0;i<heights.size();i++){
  6.             int left=i,right=i;
  7.             for(;left>=0;left--){
  8.                 if(heights[left]<heights[i]) break;
  9.             }
  10.             for(;right<heights.size();right++){
  11.                 if(heights[right]<heights[i]) break;
  12.             }
  13.             int w=right-left-1;
  14.             int h=heights[i];
  15.             res=max(res,h*w);
  16.         }
  17.         return res;
  18.     }
  19. };

双指针写法比较复杂,不管了。

单调栈:与“接雨水”不一样的是,这题最左边和最右边柱子都有相应的结果,在接雨水里不是这样。为了普适性,我们需要把heights数组开头及末尾加入元素0.

你可能会好奇:为什么while 里面的if要去计算宽度呢?并且能实现题意呢?

因为外层是while,i不更新,却一直在弹出并计算面积。所以间距不一定是1,间距是动态变化的(根据栈的弹出。)

  1. class Solution {
  2. public:
  3.     int largestRectangleArea(vector<int>& heights) {
  4.         int res=0;
  5.         stack<int> s;
  6.         s.push(0);
  7.         heights.insert(heights.begin()+0,0);
  8.         heights.push_back(0);
  9.         for(int i=1;i<heights.size();i++){
  10.             while(!s.empty()&&heights[i]<heights[s.top()]){
  11.                 int mid=s.top();
  12.                 s.pop();
  13.                 if(!s.empty()){
  14.                     int left=s.top();
  15.                     int right=i;
  16.                     int w=right-left-1;
  17.                     int h=heights[mid];
  18.                     res=max(res,h*w);
  19.                 }
  20.             }
  21.             s.push(i);
  22.         }
  23.         return res;
  24.     }
  25. };

感谢支持,之后会写的其他的东西。

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

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

相关文章

用智能插件(Fitten Code: Faster and Better AI Assistant)再次修改vue3 <script setup>留言板

<template><div><button class"openForm" click"openForm" v-if"!formVisible">编辑</button><button click"closeForm" v-if"formVisible">取消编辑</button><hr /><formv-i…

基于梯度下降的多元线性回归原理

为了展示多元线性回归的迭代过程&#xff0c;我们可以使用梯度下降算法手动实现多元线性回归。梯度下降是一种迭代优化算法&#xff0c;用于最小化损失函数。 我们将以下步骤进行手动实现&#xff1a; 初始化回归系数。计算预测值和损失函数。计算梯度。更新回归系数。重复步…

高分论文密码---大尺度空间模拟预测与数字制图

大尺度空间模拟预测和数字制图技术和不确定性分析广泛应用于高分SCI论文之中&#xff0c;号称高分论文密码。大尺度模拟技术可以从不同时空尺度阐明农业生态环境领域的内在机理和时空变化规律&#xff0c;又可以为复杂的机理过程模型大尺度模拟提供技术基础。我们将结合一些经典…

制造业几大系统(MES/WMS/QMS/ERP)的集成

制造业的几大系统包括MES&#xff08;制造执行系统&#xff09;、WMS&#xff08;仓库管理系统&#xff09;、QMS&#xff08;质量管理系统&#xff09;和ERP&#xff08;企业资源计划&#xff09;系统。这些系统在制造业中扮演着不同的角色&#xff0c;可以通过集成实现更高效…

Kafka高频面试题整理

文章目录 1、什么是Kafka?2、kafka基本概念3、工作流程4、Kafka的数据模型与消息存储机制1)索引文件2)数据文件 5、ACKS 机制6、生产者重试机制:7、kafka是pull还是push8、kafka高性能高吞吐的原因1&#xff09;磁盘顺序读写&#xff1a;保证了消息的堆积2&#xff09;零拷贝机…

SqlSugar有实体CURD应用-C#

本文所述开发环境&#xff1a;.C#、NET8、Visual Studio2022 SqlSugar有实体查询数据表 首先根据《SqlSugar使用DbFirst对象根据数据库表结构创建实体类-C#》中的描述的表结构创建所有表的实体类如下&#xff1a; 表名创建的实体类名tb_studentStudenttb_teacherTeachertb_c…

linux的UDP广播测试:C语言代码

测试代码 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #include <netdb.h>#…

MyEclipse新手使用介绍

目录 1.MyEclipse诞生背景 2.作用 3.版本历史 4.优缺点 5.应用场景 6.如何使用 6.1.下载与安装 6.2.MyEclipse 菜单及其菜单项 7.创建和发布一个 Java 程序 7.1.创建 Java 程序 7.2.发布 Java 程序 8.示例 8.1. Hello World 示例 8.2. 简单Spring Boot 应用 8.3…

kettle从入门到精通 第六十九课 ETL之kettle kettle cdc mysql,轻松实现增量同步

1、之前kettle cdc mysql的时候使用的方案是canalkafkakettle&#xff0c;今天我们一起学习下使用kettle的插件Debezium直接cdc mysql。 注&#xff1a;CDC (Change Data Capture) 是一种技术&#xff0c;用于捕获和同步数据库中的更改。 1&#xff09;Debezium步骤解析mysql b…

鸿蒙轻内核Kconfig使用笔记

鸿蒙轻内核使用Kconfig进行图形化配置&#xff0c;本文专门讲解下鸿蒙轻内核LiteOS-M和LiteOS-A的图形化配置方法。本文中所涉及的源码&#xff0c;均可以在开源站点 https://gitee.com/openharmony/kernel_liteos_a 、 https://gitee.com/openharmony/kernel_liteos_m 获取。本…

Spring AI 接入OpenAI实现文字生成图片功能

Spring AI 框架集成的图片大模型 2022年出现的三款文生图的现象级产品&#xff0c;DALL-E、Stable Diffusion、Midjourney。 OpenAI dall-e-3dall-e-2 Auzre OpenAI dall-e-3dall-e-2 Stability stable-diffusion-v1-6 ZhiPuAI cogview-3 OpenAI 与 Auzer OpenAI 使用的图片…

【FreeRTOS】创建任务-声光色影

参考《FreeRTOS入门与工程实践(基于DshanMCU-103).pdf》 目录 1 基本概念2 任务创建与删除2.1 什么是任务2.2 创建分配内存2.2.1 动态任务2.2.1 静态分配内存 2.3 示例1: 创建任务2.3.1 声2.3.1.1 music.c2.3.1.2 music.h2.3.1.4 硬件接线 2.3.2 光2.3.3 色2.3.4 影 在本章中&a…

DC12V升压24V/5A电流 布控球产品应用 升压恒压SL4010耐压40V芯片

随着科技的不断发展&#xff0c;布控球作为一种高效、精准的安全监控设备&#xff0c;被广泛应用于公安、消防、交通等多个领域。然而&#xff0c;布控球在工作过程中需要稳定的电源供应&#xff0c;以保证其正常运行和长期稳定性。因此&#xff0c;一款性能优良的升压恒压芯片…

WindTerm使用SSH密钥连接阿里云实例,服务器设置SSH密钥登录

安装Windterm 地址https://github.com/kingToolbox/WindTerm/releases 下载完放到文件夹就可以打开 阿里云开启密钥对 打开阿里云ecs控制台 https://ecs.console.aliyun.com/keyPair/region/cn-wulanchabu 网络与安全->密钥对&#xff0c;创建密钥对&#xff0c;创建成…

《现代通信原理与技术》--数字信号的最佳接收实验报告

《现代通信原理与技术》 数字信号的最佳接收实验报告 实 验&#xff1a;数字信号的最佳接收实验报告 目录 摘要......................................................................................................3 引言........................................…

R语言绘制三变量分区地图

参考资料&#xff1a; https://mp.weixin.qq.com/s/5c7gpO2mJ2BqJevePJz3CQ tricolore包教程&#xff1a;https://github.com/jschoeley/tricolore 学习笔记&#xff1a;Ternary choropleth maps 1、测试实例 代码&#xff1a; library(ggplot2) library(rnaturalearthdata) …

探索AI视频生成技术的原理

探索AI视频生成技术的原理 随着人工智能技术的迅猛发展&#xff0c;AI在视频生成领域的应用已经引起了广泛关注。从娱乐、广告到教育和科学研究&#xff0c;AI视频生成技术正在彻底改变我们制作和消费视频内容的方式。本文将深入探讨AI视频生成技术的原理&#xff0c;解析其背…

【Kadane】Leetcode 918. 环形子数组的最大和【中等】

环形子数组的最大和 给定一个长度为 n 的环形整数数组 nums &#xff0c;返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上&#xff0c; nums[i] 的下一个元素是 nums[(i 1) % n] &#xff0c;nums[i] 的前一个元素是 nums…

安鸾学院靶场——安全基础

文章目录 1、Burp抓包2、指纹识别3、压缩包解密4、Nginx整数溢出漏洞5、PHP代码基础6、linux基础命令7、Mysql数据库基础8、目录扫描9、端口扫描10、docker容器基础11、文件类型 1、Burp抓包 抓取http://47.100.220.113:8007/的返回包&#xff0c;可以拿到包含flag的txt文件。…

【车载音视频电脑】嵌入式AI分析车载DVR,支持8路1080P

产品特点 采用H.265 & H.264编解码&#xff0c;节约存储空间、传输流量&#xff1b; 高分辨率&#xff1a;支持8路1080P*15FPS/4路1080P*30FPS、720P、D1等编解码&#xff1b; 支持1张SATA硬盘&#xff0c;取用方便&#xff0c;满足大容量存储要求&#xff1b; 支持1个…