【模拟】算法实战
文章目录
- 一、算法原理
- 二、算法实战
- 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 什么是分支 分支就是便于多人在同一项目…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...




