【C++】 —— 笔试刷题day_12
一、删除公共字符
题目解析
题目给了两个字符串(其中包含空格),让我们在第一个字符串中删除第二个字符串中的字符。
我们要输出删除后的字符串。
算法思路
这道题,如果直接按照题目中的要求去第一个字符串中删除字符,那还是有一点难度的。
我们通过观察题目可以发现,第二个字符串
str2
中的所有字符,我们都要在str1
中删除;那我们不妨记录一下
str2
中出现的字符,这样再遍历str1
,再将str2
中出现的字符进行删除;这里还可以进行一下优化:我们知道在一个字符串中删除一个字符,代价是很大的,所以我们重新定义一个字符串
ret
,如果str1
中字符在str2
中没有出现,就放到ret
中去。
大致思路就如上所示,现在来梳理一下整个过程
遍历
str2
记录其中所有的字符: 首先要记录str2
中出现的所有字符,这里定义一个数组即可(大小200
左右应该就够用);遍历
str1
,将str2
中没有出现的字符放到新的字符串中: 这里也可以不定义新的字符串,直接输出字符即可。
代码实现
#include <iostream>
#include <string>
using namespace std;int main() {string s,t;getline(cin,s);getline(cin,t);bool hash[200] ={false};for(auto& e:t){hash[e] = true;}string ret;for(auto& e:s){if(hash[e] == false)ret+=e;}cout<<ret<<endl;return 0;
}
二、两个链表的第一个公共结点
题目解析
这两道题可以说
老朋友
了,在之前初学链表时,就做过这道题了;题目还是给了两个链表,让我们找出来它们相交的第一个节点并返回;如果不相交就返回
nullptr
算法思路
对于这道题,先来看思路一(也是之前做这道题的思路)
分别遍历两个链表,记录分别有多少个节点;
让指向长链表的指针先走(两个链表节点数的差值)
x
步。然后再同时遍历,直到两个指针相等(如果链表不相交,两个链表遍历到
nullptr
。返回当前两个指针相等的位置即可。
这里就不过多叙述了,现在来看思路二:
它们给了两个链表,我们将这两个链表分为以下三个部分
观察上图,我们可以得到一个等式关系:
x1 + x + x2 = x2 + x + x1
。(看到这,这不肯定相等吗,就换了一个位置)那我们如果这样来理解呢:
- 我们让
cur1
先遍历x1 + x
的部分,遍历完后再让cur1
去遍历x2
部分。- 同时让
cur2
遍历x2 + x
的部分,遍历完后再让cur2
去遍历x1
部分。- 因为
x1 + x + x2 = x2 + x + x1
,所以我们cur1
和cur2
会同时遍历到两个链表相交的第一个节点的位置。那如果两个链表不相交怎么办?
这个就很好说了,没有相交部分
x = 0
,那cur1
和cur2
就会同时遍历到nullptr
位置,最后返回即可。
代码实现
class Solution {public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {ListNode* cur1 = pHead1;ListNode* cur2 = pHead2;while (cur1 != cur2) {cur1 = cur1 == nullptr ? pHead2 : cur1->next;cur2 = cur2 == nullptr ? pHead1 : cur2->next;}return cur1;}
};
三、mari和shiny
题目解析
题目给了一个字符串,让我们找出这个字符串中一个有多少个
shy
子序列这里要注意,是子序列而不是子数组,这里子序列可以是不连续的;
通过示例一也可以看出来。
算法思路
这道题让我们找出shy
子序列,虽然说是不连续的,但是shy
相对位置是固定的;(也就是说hsy
、yhs
这些是不算shy
子序列的)
首先来看我们这道题暴力解法:
遍历字符串,遇到
s
就在s
后面找hy
;找
hy
是,遍历到h
再在后面找y
;
这要通过多层循环,可以说非常麻烦的。
现在来进行一下优化:
我们要找
shy
,那就要先找到sh
;找sh
就要先找到s
;(这里我们定义数组s,h,y
)
s[i]
:表示区间[0,i]
中s
的数量。h[i]
:表示区间[0,i]
中sh
的数量。y[i]
:表示区间[0,i]
中shy
的数量
现在我们来尝试去推到一下状态转移方程。
如果
i
位置是s
,那**s[i] = s[i-1]+1
;否则s[i] = s[i-1]
。**如果
i
位置是h
,那区间[0,i]
中sh
就可以分成两部分(一部分在区间[0,i-1]
中的sh
,另一部分就是区间[0,i-1]
中的s
和i
位置的h
组成的sh
)那我们的**h[i] = h[i-1] + s[i-1]
;否则h[i] = h[i-1]
(i
位置不是h
**)。如果
i
位置是y
,那区间[0,i]
中的shy
就可以分为两部分(一部分是区间[0,i-1]
中的shy
,另一部分是区间[0,i-1]
中的sh
和i
位置的y
组成的shy
)那我们的**y[i] = y[i-1] + h[i-1]
;否则y[i] = y[i-1]
(i
位置不是y
**)。
状态转移方程如上,现在来进行一下优化:
如果我们真的创建三个
dp
表s,h,y
;那未免一些太浪费空间了,我们可以使用三个变量来代替s,h,y
- 遍历字符串
str
:- 遇到
s
:s++;
(表示区间[0,i]
内s
的数量)- 遇到
h
:h+=s
(表示区间[0,i]
内sh
的数量)- 遇到
y
:y+=h
(表示区间[0,i]
内shy
的数量)最后我们输出
y
即可。
代码实现
这里要注意数据的范围,
1 <= n <= 300000
,我们如果使用int
来计数会超出范围的,要是有long long
。
#include<iostream>
#include<string>
using namespace std;int main()
{int n;string str;cin>>n>>str;long long s = 0,h = 0,y = 0;for(int i=0;i<n;i++){if(str[i] == 's') s++;else if(str[i] == 'h') h+=s;else if(str[i] == 'y') y+=h;}cout<<y<<endl;return 0;
}
到这里本篇博客就结束了,感谢支持
继续加油哇!!!
相关文章:
【C++】 —— 笔试刷题day_12
一、删除公共字符 题目解析 题目给了两个字符串(其中包含空格),让我们在第一个字符串中删除第二个字符串中的字符。 我们要输出删除后的字符串。 算法思路 这道题,如果直接按照题目中的要求去第一个字符串中删除字符,…...
家乡旅游景点小程序(源码+部署教程)
运行环境 家乡旅游景点小程序运行环境如下: • 前端:小程序 • 后端:无 • IDE工具:微信开发者工具 • 技术栈:小程序 注意:此项目为纯静态项目,无后端 主要功能 家乡旅游景点微信小程序主…...
SQL Server:当在删除数据库时因为存在触发器而无法删除
当在删除数据库时因为存在触发器而无法删除,你可以通过禁用触发器来解决这个问题。下面为你介绍在 SQL Server 里禁用和启用触发器的方法。 禁用数据库中所有表的触发器 你可以使用系统视图 sys.triggers 来查询数据库里所有的触发器,然后生成禁用这些…...
多人协同进行qt应用程序开发应该注意什么2?
在多人协同开发Qt应用程序时,为了确保高效协作、代码一致性和项目可维护性,需要特别注意以下关键点: 1. 版本控制与协作流程 统一版本控制工具:使用Git并规范分支策略(如Git Flow),通过.gitign…...
js关于for of 与for in
for…of for-of循环用于遍历可迭代对象,如数组、字符串、Map、Set等。它直接访问每个元素的值,而不是键名。 const arr [3,5,6,7,0] for(let item of arr){console.log(item); } // 3 // 5 // 6 // 7 // 0只有部署了Iterator接口的数据结构才能使用fo…...
Python Excel
一、Python读Excel——xlrd -*- coding: utf-8 -*- import xlrddef read_excel():打开文件workbook xlrd.open_workbook(rD:\demo1.xlsx)获取所有sheetprint(workbook.sheet_names()) 列表形式返回sheet1_name workbook.sheet_names()[0]根据sheet索引或者名称获取sheet内容…...
前端全局编程和模块化编程
1. 全局编程 <!DOCTYPE html> <html> <head><title>OpenLayers 示例</title><style>.map {width: 100%;height: 400px;}</style><script src"https://cdn.jsdelivr.net/npm/olv7.4.0/dist/ol.js"></script>&…...
随机2级域名引导页HTML源码
源码介绍 随机2级域名引导页HTML源码,每次点进去都随机一个域名前缀。 修改跳转域名在 350 行代码,源码由HTMLCSSJS组成,记事本打开源码文件可以进行内容文字之类的修改,双击html文件可以本地运行 效果预览 源码免费获取 随机2级域名引导页…...
Latex的各种数学公式
Latex的各种数学公式 简介公式1、 A 、 A ‾ \neg A\text{、}\overline{A} A、A2、 、 \text{、} 、3、 ⋅ 、 ∙ \cdot \text{、} \bullet ⋅、∙ 4、表格 简介 这里会随时更新我需要用到的数学公式,以csdn中写作格式为主,可能过时了,不适合…...
稻壳模板下载器(Windows):免费获取WPS稻壳模板的利器
稻壳模板下载器(Win) 稻壳模板下载器是一款功能强大的工具,能够帮助用户免费下载WPS稻壳儿中的各种模板,无需开通VIP会员。它支持多种模板类型,包括PPT、Word、Excel等,极大地提升了用户的办公效率。 依托…...
BeanDefinition和Beanfactory实现一个简单的bean容器
目录 什么是 Springbean 容器 设计思路 图解 参考文章 开源地址 BeanDefinition 类 BeanFactory 类 测试类 什么是 Springbean 容器 Spring 包含并管理应用对象的配置和生命周期,在这个意义上它是一种用于承载对象的容器,你可以配置你的每个 Bea…...
Mybatis的resultMap标签介绍
说明:在Mybatis中,resultMap 标签可以用于SQL查询后的封装数据,本文用两个场景介绍 resultMap 标签的使用。 搭建环境 先搭一个Demo,pom如下: <?xml version"1.0" encoding"UTF-8"?> &…...
jarvisoj API调用 [JSON格式变XXE]
http://web.jarvisoj.com:9882/ 题目要求:请设法获得目标机器 /home/ctf/flag.txt 中的flag值 抓包得到: POST /api/v1.0/try HTTP/1.1 Host: web.jarvisoj.com:9882 Content-Length: 36 Accept-Language: zh-CN,zh;q0.9 User-Agent: Mozilla/5.0 (W…...
论坛系统的测试
项目背景 论坛系统采用前后端分离的方式来实现,同时使用数据库 来处理相关的数据,同时将其部署到服务器上。前端主要有7个页面组成:登录页,列表页,论坛详情页,编辑页,个人信息页,我…...
RK3588使用笔记:纯linux系统下基础功能配置(不定期更新)
一、前言 用于记录使用RK3588这个平台在纯linux系统下的一些功能配置,RK3588只是一个芯片,linux只是一个系统,但是linux系统可以运行在无数的芯片上,也都大同小异,本编文章主要记录linux系统环境的一些常用的基础功能…...
yum install 报错(CentOS换源):
yum instally yum utils device mapper persistent-data lvm2 报错: 排查错误原因:centos7 系统停止维护了 解决方案:换源(更换操作系统) //1.备份 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-…...
HTTP常见状态码分析
当浏览者访问一个网页时,浏览者的浏览器会想网页所在的服务器发出请求,当浏览器接收并显示网页前,此网页所在的服务器会返回一个包含 HTTP 状态码的信息头(server header)用以响应浏览器的请求。 常见的状态码…...
Python与Web 3.0支付系统:技术融合与未来展望
Python与Web 3.0支付系统:技术融合与未来展望 随着区块链技术的不断发展,Web 3.0支付系统正逐步成为数字经济的重要组成部分。Python作为一种高效、易用的编程语言,在Web 3.0支付系统的开发中扮演着不可或缺的角色。本文将从技术背景、Python的应用、代码示例以及未来发展趋…...
Linux命令-sed指令
sed命令参数: 基本参数 -n:抑制默认输出,只显示匹配的行。 -e:指定 sed 脚本。 -i:直接修改文件内容。 -f:指定包含 sed 脚本的文件。 -r:启用扩展正则表达式。 常用操作 s:替换字符…...
Unbantu24.04配置-软件安装
Ubantu24.04配置—环境安装 最近在笔记本安装了双系统,这次在这里回顾一下,本章节主要是一些软件的注意点,大多数都是在网上有一定的教程的 1.搜狗输入法 1.1 删除其他框架 sudo apt purge ibus sudo apt remove fcitx5* sudo apt pur…...
八股总结(Java)实时更新!
八股总结(java) ArrayList和LinkedList有什么区别 ArrayList底层是动态数组,LinkedList底层是双向链表;前者利于随机访问,后者利于头尾插入;前者内存连续分配,后者通过指针连接多块不连续的内存…...
NVIDIA TensorRT 10 [TAR]安装教程
平台信息 操作系统:Ubuntu 20.04.6 LTSCPU架构:x86_64GPU:Tesla T4 x 2驱动信息: NVIDIA-SMI:535.104.05Driver Version: 535.104.05CUDA Version: 12.2 步骤 预备步骤 安装驱动和CUDA 假设已经成功安装好驱动&a…...
深入探索 iOS 卡顿优化
认识卡顿 一些概念 FPS:Frames Per Second,表示每秒渲染的帧数,通过用于衡量画面的流畅度,数值越高则表示画面越流畅。CPU:负责对象的创建和销毁、对象属性的调整、布局计算、文本的计算和排版、图片的格式转换和解码…...
【C/C++算法】从浅到深学习---分治算法之快排思想(图文兼备 + 源码详解)
绪论:冲击蓝桥杯一起加油!! 每日激励:“不设限和自我肯定的心态:I can do all things。 — Stephen Curry” 绪论:本章是针对快速排序进行的优化和再次理解快排思想,将会通过4道题目带你再次…...
精通React JS中的API调用:示例指南
精通React JS中的API调用:示例指南 推荐超级课程: 本地离线DeepSeek AI方案部署实战教程【完全版】Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战目录 精通React JS中的API调用:示例指南为什么在React JS中进行API调用?在React JS中制作API调用:…...
浅谈Thread类及常见方法与线程的状态(多线程编程篇2)
目录 前言 1.Thread类及常见方法 Thread类中常见的属性 1. getId() 2. getName() 3. getState() 4. getPriority() 5. isDaemon() 6. isAlive() 7. isInterrupted() 2.Thread类中常见的方法 Thread.interrupt() (中断线程) Thread.start()(启动线程) 1. 覆写 run…...
算法刷题记录——LeetCode篇(1.2) [第11~20题](持续更新)
更新时间:2025-03-29 LeetCode题解专栏:实战算法解题 (专栏)技术博客总目录:计算机技术系列目录页 优先整理热门100及面试150,不定期持续更新,欢迎关注! 17. 电话号码的字母组合 给定一个仅包含数字 2-9…...
基于HTML5和CSS3实现3D旋转相册效果
基于HTML5和CSS3实现3D旋转相册效果 这里写目录标题 基于HTML5和CSS3实现3D旋转相册效果项目介绍技术栈核心功能实现原理1. HTML结构2. CSS样式设计2.1 基础样式设置2.2 容器样式2.3 图片样式 3. JavaScript实现4. 交互功能实现4.1 触摸和鼠标拖拽4.2 播放控制 项目亮点技术难点…...
unity中Xcharts图表鼠标悬浮表现异常
鼠标悬浮在面板附近,只显示单独的一个项目 而且无论鼠标如何移动,根本没有效果。 解决方案: 需要在对应的Canvas上绑定主相机才可以 鼠标移动到项目上就有信息展示了...
Unity程序嵌入Qt后点击UI按钮Button没有反应
一、前言 在一次项目中,需要将Unity程序嵌入qt中,并在主界面显示,根据网络资料与相关代码,成功将unity程序嵌入,但是在点击Unity的Button按钮时却没有响应,在查找相关资料后,解决问题ÿ…...
Linux安装Cmake (Centos 7.9)
cmake安装 这个虽然已经更新到了4.0.0版本了,但是我们要用3.5版本的,因为这个比较稳定 官方地址:https://github.com/Kitware/CMake/releases/tag/v3.5.0,选择那个cmake-3.5.0-Linux-x86_64.tar.gz下载, 首先解压文…...
31天Python入门——第14天:异常处理
你好,我是安然无虞。 文章目录 异常处理1. Python异常2. 异常捕获try-except语句捕获所有的异常信息获取异常对象finally块 3. raise语句4. 自定义异常5. 函数调用里面产生的异常补充练习 异常处理 1. Python异常 Python异常指的是在程序执行过程中发生的错误或异…...
Linux使用集群服务器查看已安装conda环境,且环境名无显示、系统环境混乱等问题
一、问题 在使用集群服务器前可以查看导入,module load不需要安装。我都是自己重新下载Anaconda3-2024.10-1-Linux-x86_64.sh,然后安装,导致混乱。下面是情况 1.创建的环境名跑到目录下了 2.多个base,且有个base无显示 二、解决办法 1.删…...
【Linux】B站黑马程序视频学习笔记(一)
一、Linux内核与发行版 注意:下图程序指向内核的箭头用的是“调用”,内核指向硬件用的是“调度”。 Linux内核代码下载网站:https://www.kernel.org/ 二、虚拟机-VMware 学习Linux可以借助虚拟机(其使用到的CPU、内存、硬盘都是…...
HarmonyOS NEXT——【鸿蒙原生应用加载Web页面】
鸿蒙客户端加载Web页面: 在鸿蒙原生应用中,我们需要使用前端页面做混合开发,方法之一是使用Web组件直接加载前端页面,其中WebView提供了一系列相关的方法适配鸿蒙原生与web之间的使用。 效果 web页面展示: Column()…...
【软件工程】习题及答案
目录 第一章 习题第一章 习题答案第二章 习题第二章 习题答案第三章 习题第三章 习题答案第四章 习题第四章 习题答案第五章 习题第五章 习题答案第六章 习题第六章 习题答案第七章 习题第七章 习题答案 第一章 习题 一、选择题 1.关于引起软件危机的原因ÿ…...
css选择最后结尾的元素DOM
前言 选中最后一个元素,实际使用非常频繁。 解决方案 使用 CSS 提供的选择器,即可完成。 如下代码示例,两种选择器均可实现。 <p>...</p>p:last-child{ background:#ff0000; }p:nth-last-child(1){background:#ff0000; }p&…...
【AI论文】挑战推理的边界:大型语言模型的数学基准测试
摘要:近年来,大型推理模型的迅猛发展导致现有用于评估数学推理能力的基准测试趋于饱和,这凸显出迫切需要更具挑战性和严谨性的评估框架。为填补这一空白,我们推出了OlymMATH,这是一项全新的奥林匹克级数学基准测试&…...
使用 Python包管理工具 uv 完成 Open WebUI 的安装
uv 是一个极其快速的 Python 包安装器和解析器,用 Rust 编写,旨在作为 pip 和 pip-tools 工作流的替代品 使用 uv 安装(推荐) macOS/Linux: curl -LsSf https://astral.sh/uv/install.sh | shWindows: po…...
【区块链安全 | 第三篇】主流公链以太坊运行机制
文章目录 1. 以太坊账户类型2. 以太坊网络架构2.1 节点类型2.2 交易流程 3. 共识机制4. Gas 机制4.1 Gas 计算方式4.2 以太坊 EIP-1559 交易机制 5. EVM(以太坊虚拟机)5.1 EVM 结构5.2 EVM 指令5.3 EVM 运行机制 6. 智能合约7. ERC 代币标准7.1 ERC-207.…...
C# 字符串(String)
C# 字符串(String) 引言 在C#编程语言中,字符串(String)是处理文本数据的基础。字符串是字符的有序集合,用于存储和处理文本信息。C#的字符串类型是System.String,它是一个引用类型࿰…...
Unity Shader 学习18:Shader书写基本功整理
1. Drawer [HideInInspector]:面板上隐藏[NoScaleOffset]:隐藏该纹理贴图的TillingOffset[Normal]:检查该纹理是否设为法线贴图[HDR]:将颜色类型设为高动态范围颜色(摄像机也要开启HDR才有效果)[PowerSlid…...
构建第一个SpringBoot程序
第一种方式: 注,构建过程中一定要联网 new module -->选择spring Initializr 选择Web --> 勾选Spring Web --> create 构建好的项目如下 这里的 .mvn .git* HELP.md mvnw* 都可以删除 编辑好controller 之后 点击即可运行第一个springbo…...
Java高级JVM知识点记录,内存结构,垃圾回收,类文件结构,类加载器
JVM是Java高级部分,深入理解程序的运行及原理,面试中也问的比较多。 JVM是Java程序运行的虚拟机环境,实现了“一次编写,到处运行”。它负责将字节码解释或编译为机器码,管理内存和资源,并提供运行时环境&a…...
使用飞书API自动化更新共享表格数据
飞书API开发之自动更新共享表格 天马行空需求需求拆解1、网站数据爬取2、飞书API调用2.1 开发流程2.2 创建应用2.3 配置应用2.4 发布应用2.5 修改表格权限2.6 获取tenant_access_token2.7 调用API插入数据 总结 天马行空 之前一直都是更新的爬虫逆向内容,工作中基本…...
C++中ShellExecute函数使用方法说明,如果一开始参数为隐藏,后面还能再显示出来吗
文章目录 一、ShellExecute基础用法函数原型关键参数 nShowCmd示例代码:启动程序并隐藏窗口 二、隐藏后能否重新显示窗口直接答案 三、实现隐藏后显示窗口的步骤1. 获取目标窗口句柄2. 显示窗口 四、完整流程示例五、注意事项六、总结 在C中使用ShellExecute函数时&…...
MySQL的多表查询
我们之前在讲解SQL语句的时候,讲解了DQL语句,也就是数据查询语句,但是之前讲解的查询都是单表查询,而本章节我们要学习的则是多表查询操作,主要从以下几个方面进行讲解。 5.1 多表关系 项目开发中,在进行…...
(UI自动化测试web端)第二篇:元素定位的方法_css定位之层级选择器
看代码里的【find_element_by_css_selector( )】( )里的表达式怎么写? 文章介绍了第五种写法,层级选择器 ,你要根据网页中的实际情况来判断自己到底要用哪一种方法来进行元素定位。每种方法都要多练习,全都熟了之后你在工作当中使…...
《Python Web部署应知应会》No2:如何基于FastAPI 和 OLLAMA 架构实现高并发 AI 推理服务
《Python Web部署应知应会》No2:如何基于FastAPI 和 OLLAMA 架构实现高并发 AI 推理服务(上) 摘要: 在 FastAPI 和 OLLAMA 架构中实现高并发 AI 推理服务,并优化性能指标采集和缓存策略,可以充分利用 asy…...
【LeetCode 题解】算法:8.字符串转换整数(atoi)
一、问题描述 在 LeetCode 的算法题库里,有这样一道题目,要求我们实现一个名为 myAtoi(string s) 的函数,其功能是将给定的字符串转换为一个 32 位有符号整数。具体的转换规则如下: 处理步骤 剔除前导空格:读取字符串…...