【模拟】算法实战
文章目录
- 一、算法原理
- 二、算法实战
- 1. leetcode1576 替换所有的问号
- 2. leetcode495 提莫攻击
- 3. leetcode6 N字形变换
- 4. leetcode38 外观数列
- 5. leetcode1419 数青蛙
- 三、总结
一、算法原理
模拟就是用计算机来模拟题目中要求的操作,模拟题目通常具有代码量大、操作多、思路繁琐的特点。所谓的"模拟题",用一句老话所就是"照着葫芦画瓢",根据题目的表述进行筛选提取关键要素,按需求书写代码解决实际问题。
二、算法实战
1. leetcode1576 替换所有的问号
替换所有的问号
解题思路:
这是一道简单的模拟题,意思是一个字符串中有 '?' 字符,将些字符替换为'a' ~ 'z'中的任意一个字符后,使得这个字符串中不会出现连续两个以上的连续字符。首先我们遍历这个字符串,先找到字符 '?' 的位置,然后从'a' ~ 'z'中从左往右开始遍历,将该问号替换为其某个字符后看该位置左右是否一样,如果不一样,继续往后遍历寻找符合要求的字符。这里注意处理边界情况。
代码实现:
class Solution {
public:string modifyString(string s) {for(int i = 0; i < s.size(); i++){if(s[i] == '?'){for(char ch = 'a'; ch <= 'z'; ch++){if((i == 0 || ch != s[i-1]) && (i == s.size()-1 || ch != s[i+1])){s[i] = ch;break;} }}}return s;}
};
2. leetcode495 提莫攻击
提莫攻击
解题思路:
首先扫描这个数组,使用cnt统计答案,timeSeries[i]表示此时攻击的开始点,timeSeries[i+1]表示下一次攻击的开始点。
- timeSeries[i + 1] - timeSeries[i] < duration,表示两次攻击重叠。cnt+=
timeSeries[i + 1] - timeSeries[i]。 - timeSeries[i + 1] - timeSeries[i] >= duration,表示两次攻击不重叠, cnt+=duration。
因为最后一次攻击是肯定会持续完的,所以我们扫描数组的时候只需要扫描前n-1个元素。但是最后返回结果时候需要返回cnt+duration。
代码实现:
class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int cnt = 0;for(int i = 0; i < timeSeries.size() - 1; i++){int tmp = timeSeries[i + 1] - timeSeries[i];if(tmp < duration)cnt += tmp;elsecnt += duration;}return cnt + duration;}
};
3. leetcode6 N字形变换
N字形变换
解题思路:
首先我们应该先搞清楚从原字符串到目标字符串是如何变换而来的。

我们可以看到这个过程:先将该字符串以'N'字形的顺序依次填入一个二维数组中,然后将该二维数组中的内容从上到下一行一行拼接起来即可。这里我们可以从中找一些规律出来:

代码实现:
class Solution {
public:string convert(string s, int numRows) {string ret = "";if(numRows == 1)return s;int sub = 2*numRows - 2;for(int i = 0; i < numRows; i++){// 处理第一行和最后一行if(i == 0 || i == numRows-1){for(int j = i; j < s.size(); j += sub){ret += s[j];}}else{// 处理中间行for(int k = i, p = sub - k; k < s.size() || p < s.size(); k += sub, p += sub){if(k < s.size()) ret += s[k];if(p < s.size()) ret += s[p];}}}return ret;}
};
4. leetcode38 外观数列
外观数列
解题思路:
题目告诉了我们数列的每一项的变换过程是通过上一项推导出来的,因此我们可以根据上一项模拟数列每一项的形成过程。在数列每一项的模拟过程中,我们依然使用滑动窗口的算法原理来实现。
代码实现:
class Solution {
public:string countAndSay(int n) {// 使用双指针算法进行模拟string start = "1";while(--n){string tmp;for(int left = 0, right = 0; left < start.size(); right++){if(start[left] != start[right]){tmp += to_string(right - left);tmp += start[left];left = right;}}start = tmp;}return start;}
};
5. leetcode1419 数青蛙
数青蛙
解题思路:
这道题目属于典型的比较难的模拟题,先开一个哈希表,然后将"croak"按照<char, int>的方式映射进哈希表,这里的int指的是"croak"中字符的下标。开一个cnt来计数,统计每一个字符出现的次数。
从前向后遍历字符串,如果ch=='c',说明需要一只青蛙开始发出蛙鸣,如果前面统计cnt[n - 1],这里的n-1表示"croak"字符串的最后一个’k’的下标,意思是如果cnt[n - 1]已经出现过了,说明前面有一只青蛙已经将"croak",这个字符串全部叫了一遍,那么我们让前面的青蛙继续从头开始叫就可以了,不需要增加青蛙的数量,因此让cnt[n - 1]--,cnt[0]++,如果cnt[n - 1] == 0, 则直接让cnt[0]++。
如果ch!='c',则说明一只青蛙正在发出蛙鸣的过程中,此时我们让此时青蛙发出蛙鸣的字符的前一个字符的下标cnt[c前面的字符]- -,然后让正在遍历的字符数量cnt[c]++,如果中途发现cnt[c前面的字符] == 0, 说明该字符连续出现了两次以上,或者字幕出现的顺序有问题。直接返回-1即可。
最后我们统计的时候只需要关心"croak"中最后一个’k’出现了几次即可,同时,我们还需要遍历cnt中除最后一个元素外,看前面的字母出现的次数是否为0,若不为0,说明字幕出现的顺序不符合要求,直接返回-1。
代码实现:
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();vector<int> cnt(n);unordered_map<char, int> hash;for(int i = 0; i < n; i++) hash[t[i]] = i;for(char ch : croakOfFrogs){if(ch == 'c'){if(cnt[n - 1]) cnt[n - 1]--;cnt[0]++;}else{int i = hash[ch];if(cnt[i - 1])cnt[i - 1]--, cnt[i]++;else return -1;}}for(int i = 0; i < n - 1; i++)if(cnt[i] != 0) return -1;return cnt[n - 1];}
};
三、总结
模拟的过程就是对真实场景尽可能的模拟,但我们需要注意的是:模拟题并没有我们所想象的那么简单,它的代码中可能会有很多的'坑',我们在写模拟算法的过程中需要谨慎。
相关文章:
【模拟】算法实战
文章目录 一、算法原理二、算法实战1. leetcode1576 替换所有的问号2. leetcode495 提莫攻击3. leetcode6 N字形变换4. leetcode38 外观数列5. leetcode1419 数青蛙 三、总结 一、算法原理 模拟就是用计算机来模拟题目中要求的操作,模拟题目通常具有代码量大、操作…...
各个微服务模块之间互相依赖调用的问题
首先是模块之间不能够循环引用,否则会报循环依赖引入的错误。 没有了模块之间的相互依赖,在项目中这两个模块是相互调用的,分别各自定义相应的Feign接口,如下: 最开始写的运行报错的代码如下: FeignCli…...
理论转换实践之keepalived+nginx实现HA
背景: keepalivednginx实现ha是网站和应用服务器常用的方法,之前项目中单独用nginx实现过负载均衡和服务转发,keepalived一直停留在理论节点,加之最近工作编写的一个技术文档用到keepalived,于是便有了下文。 服务组件…...
华为OD七日集训第1期复盘 - 按算法分类,由易到难,循序渐进,玩转OD(文末送书)
目录 一、活动内容如下第1天、逻辑分析第2天、字符串处理第3天、数据结构第4天、双指针第5天、递归回溯第6天、二分查找第7天、贪心算法 && 二叉树 二、可观测性工程1、简介2、主要内容 大家好,我是哪吒。 最近一直在刷华为OD机试的算法题,坚持…...
MPI之持久化通信句柄与非持久化通信句柄
MPI_Isend & MPI_Send 创建临时通信句柄 在前面的文章中举了例子,我们使用MPI_Isend接口发送数据时,有个传出参数request,该参数是创建的通信句柄, 实际上该句柄是一个临时句柄,即只用于一次性发送数据的场景&…...
搭建个人备忘录中心服务memos、轻量级笔记服务
目录 一、源码 二、官网 三、搭建 四、使用 一、源码 GitHub - usememos/memos: A privacy-first, lightweight note-taking service. Easily capture and share your great thoughts. 二、官网 memos - Easily capture and share your great thoughts 三、搭建 docke…...
探究代理技术在网络安全、爬虫与HTTP通信中的多重应用
在当今高度互联的世界中,代理技术在网络安全、爬虫开发以及HTTP通信中扮演着举足轻重的角色。本文将深入探讨Socks5代理、IP代理以及HTTP代理在这些领域中的多重应用,探索其如何为我们创造更安全、高效的网络环境。 1. Socks5代理:构建安全通…...
vue左侧漏斗切换 echart图表动态更新
这个需求是根据点击左侧的箭头部分,右侧图表切换,左侧选中数据高亮(图片用的svg) 一、效果图 二、vue组件 <template><div class"funnel_wrap"><div class"flex_between"><div class&q…...
Centos7安装ZK-UI管理界面安装|Maven|Git|
一: JDK1.8安装 参考: Centos7卸载|安装JDK1.8|Xshell7批量控制多个终端 二:Maven安装 2.1:下载maven安装包 maven 下载地址:https://mirror.bit.edu.cn/apache/maven/maven-3/ [rootwww ~]# mkdir -p /usr/local/maven [rootwww ~]# …...
C语言日常刷题7
文章目录 题目答案与解析1234567 题目 1、如下程序的运行结果是( ) char c[5]{a, b, \0, c, \0}; printf("%s", c)A: ‘a’ ‘b’ B: ab\0c\0 C: ab c D: ab 2、若有定义: int a[2][3]; ,以下选项中对 a 数组元素正确…...
037 - 有关时间和日期的函数方法
文档:MySQL :: MySQL 5.7 Reference Manual :: 12.7 Date and Time Functions 以下为案例,更多内容可查看文档 返回当前日期: CURDATE() 返回当前时间: CURTIME() 返回当前日期和时间: NOW() 返回年份&a…...
(JAVA)树——tree
...
js判断对象是否为空对象的方法总结
js判断对象是否为空对象的方法总结 方法1:JSON.stringify()方法方法2:for in方法方法3:Object.keys()方法方法4:Object.getOwnPropertyNames()方法方法5:jquery 的 isEmptyObject()方法 在面试或者开发过程中ÿ…...
LeetCode1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II 文章目录 [1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)一、题目二、题解方法一:01背包二维数组算法思路具体实现 方法二:01背包一维数组 一、题目 有一堆石头,用整数数…...
universal robot 机械臂 官方基本教程
https://academy.universal-robots.cn/modules/e-Series-core-track/Chinese/module3/story_html5.html?courseId2166&languageChinese 教程1 控制箱内部 包含: 主机板,SD卡,和安全控制板 安全控制板负责所有控制信息,包括…...
网络常见安全漏洞
引言 随着互联网的迅猛发展,网络安全问题日益严重。在网络世界中,各种常见的安全漏洞给人们的通信和数据安全带来了巨大的威胁。本文将介绍一些常见的网络安全漏洞,并提供一些防范措施。 1. XSS(跨站脚本攻击) 跨站…...
【JS案例】JS实现图片放大镜功能
JS案例图片放大镜 🌟效果展示 🌟HTML结构 🌟CSS样式 🌟实现思路 🌟具体实现 1.初始化数据图片 2.获取所需DOM元素 3.初始化页面 初始化缩略图 绑定事件 🌟完整代码 🌟写在最后 &…...
linux centos7 bash中字符串反向输出
给定一个字符串,如何反向(倒序)输出? 字符串反转的方法:a.对各个字符位置进行循环调换(从原字符串左边取出放在新字符串的右边;从原字符串右边取出放在新字符串的左边)。b.对各个字符由水平排列转为垂直排…...
git rebase和merge区别
一、概述 merge和rebase 标题上的两个命令:merge和rebase都是用来合并分支的。 这里不解释rebase命令,以及两个命令的原理,详细解释参考这里。 下面的内容主要说的是两者在实际操作中的区别。 1.1 什么是分支 分支就是便于多人在同一项目…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?
在现代前端开发中,Utility-First (功能优先) CSS 框架已经成为主流。其中,Tailwind CSS 无疑是市场的领导者和标杆。然而,一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...




