模拟算法专题——算法介绍算法讲解力扣实战应用

目录

1、模拟算法介绍

2、算法应用【leetcode】

2.1 替换所有的问号

2.1.1 算法思想

 2.1.2 算法代码

 2.2 提莫攻击

2.2.1 算法思想

2.2.2 算法代码

2.3 Z字形变换

2.3.1 算法思想

2.3.2 算法代码

2.4 外观数列

2.4.1 算法思想

2.4.2 算法代码

2.5 数青蛙

2.5.1 算法思想

2.5.2 算法代码


1、模拟算法介绍

模拟算法其实就是——比葫芦画瓢。

模拟算法的思想很简单,解题思路一般在题目上就给了,我们只需用代码将题目的要求模拟出来就可以了,所以模拟算法对代码能力要求较强,模拟算法并没有固定的模版,我们只需将题目要求用代码模拟出来即可。

 模拟算法是一种计算机算法,用于模拟或仿真现实世界中的某个过程、系统或现象。它通过运行一系列的步骤或规则来模拟目标对象的行为,并生成与真实情况相似的结果。


2、算法应用【leetcode】

2.1 替换所有的问号

. - 力扣(LeetCode)

2.1.1 算法思想

本题为简单模拟题,只需将字符'?'替换为前后不连续的字符即可。

  1. 从'a'~'z'中寻找字符,与i-1位置和i+1位置比较,判断是否出现连续的字符(字符重复)
  2. 注意:0下标处和n-1下标处要额外处理,避免越界访问

 2.1.2 算法代码

class Solution {public String modifyString(String s) {char[] ss = s.toCharArray();int len = ss.length;for (int i = 0; i < len; i++) {//替换字符if (ss[i] == '?') {for (char j = 'a'; j < 'z'; j++) {if ((i == 0 || ss[i - 1] != j) && (i == len - 1 || ss[i + 1] != j) ) {ss[i] = j;break;}}}}return String.valueOf(ss);}
}

 2.2 提莫攻击

. - 力扣(LeetCode)

2.2.1 算法思想

计算出每两次发动攻击之间的时间差x,判断是否 >= 持续时间d秒:

  1. 若x >= d,则说明时间充裕,d秒时间内会一直中毒,中毒时间ret += d
  2. 若x < d,则说明时间不够,中毒时间会重复,中毒时间ret += 时间差x
  3. 最后一次攻击,时间必然充裕,必然中毒d秒,中毒时间ret += d

2.2.2 算法代码

class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int ret = 0;for(int i = 0; i < timeSeries.length - 1; i++) {int x = timeSeries[i + 1] - timeSeries[i];if(x < duration) ret += x;else ret += duration;}//最后一次攻击,必然中毒d秒ret += duration;return ret;}
}

2.3 Z字形变换

. - 力扣(LeetCode)

2.3.1 算法思想

在模拟算法中,若想要寻得时空效率高的算法,只能通过找规律来做优化。

我们将字符的下标放在矩阵中,求得公差d = 2*n - 2,且发现字符在矩阵中和下标有以下规律:

  • ①:当k==0时(第一行),k += d,拿到下一个要打印的字符的下标,直到k >= 字符串.len
  • ②:当k == n-1时(最后一行),k += d,拿到下一个要打印的字符的下标,直到k >= 字符串.len
  • ③:当k为中间行时,k和d-k为一组,(k,d-k)-->(k+d,d-k+d)-->...,直到k >= 字符串.len

2.3.2 算法代码

class Solution {public String convert(String s, int numRows) {if (numRows == 1) return s;char[] ss = s.toCharArray();int len = ss.length;StringBuilder stringBuilder = new StringBuilder();int d = 2 * numRows - 2;//公差for (int i = 0; i < numRows; i++) {int k = i;if (k == 0) {while (k < len) {stringBuilder.append(ss[k]);k += d;}} else if (k == numRows - 1) {while (k < len) {stringBuilder.append(ss[k]);k += d;}} else {int k2 = d - k;while (k < len || k2 < len) {if (k < len) stringBuilder.append(ss[k]);if (k2 < len) stringBuilder.append(ss[k2]);k += d;k2 += d;}}}return stringBuilder.toString();}
}

2.4 外观数列

. - 力扣(LeetCode)

2.4.1 算法思想

外观数列其实就是从2开始(1的外观数列就是1)用口头的语言将前一个数的表述出来,比如:

1 --> 1
2 --> 11(1个1)
3 --> 21(2个1)
4 --> 1211(1个2、1个1)
5 --> 111221(1个1、1个2、2个1)
....

使用双指针法求解:

  1. 从数字以1开始
  2. 定义left和right指针,起始位置均为0下标
  3. 当ret[right] != ret[left]时,记录长度(相同元素的个数),且更新left = right,继续向后遍历,直至遍历完成当前字符串
  4. 更新ret字符串,更新数字,直至数字n,返回数字n的外观数列

2.4.2 算法代码

class Solution {public String countAndSay(int n) {String ret = "1";for(int i = 0; i < n - 1; i++) {StringBuilder sb = new StringBuilder();int left = 0, right = 0;int len = ret.length();while(right < len) {while(right < len && ret.charAt(right) == ret.charAt(left)) right++;sb.append(right - left);sb.append(ret.charAt(left));left = right;}ret = sb.toString();}return ret;}
}

2.5 数青蛙

. - 力扣(LeetCode)

2.5.1 算法思想

  • 若下标为1~4的字符(r、o、a、k),则去哈希表中查看其前驱字符,若存在则:前驱个数--,当前字符个数++;若不存在:返回-1
  • 若下标为0的字符(c),说明蛙叫刚刚开始,查看最后一个字符的个数,若存在则:最后一个字符个数--,当前字符个数++;  若不存在则:当前字符++
  • 注意:当遍历完成后,除最后一个字符外,哈希表中仍有其他字符存在个数,则不成立,返回-1

2.5.2 算法代码

class Solution {public int minNumberOfFrogs(String croakOfFrogs) {char[] s = croakOfFrogs.toCharArray();int n = "croak".length();int[] hash = new int[n];// 绑定字符和其下标Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < n; i++)map.put("croak".charAt(i), i);for (char ch : s) {int index = map.get(ch);if (index == 0) {if (hash[n - 1] != 0)hash[n - 1]--;hash[0]++;} else {if (hash[index - 1]-- == 0)return -1;hash[index]++;}}//除最后一个字符外,哈希表中仍有其他字符存在个数for (int i = 0; i < n - 1; i++) {if (hash[i] != 0)return -1;}return hash[n - 1];}
}

END

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

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

相关文章

计算机毕业设计选题推荐-博客平台-博客系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

【NLP自然语言处理】文本处理的基本方法

目录 &#x1f354;什么是分词 &#x1f354;中文分词工具jieba 2.1 jieba的基本特点 2.2 jieba的功能 2.3 jieba的安装及使用 &#x1f354;什么是命名实体识别 &#x1f354;什么是词性标注 &#x1f354;小结 学习目标 &#x1f340; 了解什么是分词, 词性标注, 命名…

解锁高效项目管理:精选软件项目管理工具与技术实战

在当今快节奏的商业环境中&#xff0c;项目管理不仅是确保任务按时完成的手段&#xff0c;更是企业战略规划与执行的核心。面对日益复杂的项目需求和不断变化的市场环境&#xff0c;传统的手工管理方式已难以满足高效协同的要求。此时&#xff0c;项目管理软件作为数字化时代的…

10款主流图纸加密软件大盘点|2024企业常用图纸加密软件分享(赶快码住!)

某天早上&#xff0c;小李&#xff0c;作为一家大型制造企业的设计工程师&#xff0c;正准备提交他耗时数月设计的一份机密产品图纸。就在点击发送的那一刻&#xff0c;突然发现网络异常。他的心猛地一沉&#xff0c;联想到前段时间公司内部的泄密事件&#xff0c;他不由得心跳…

yolov8目标检测pyside6可视化图形界面+检测源码ui文件——用于计数统计

项目结构 YOLOv8模型加载&#xff1a;加载预训练的YOLOv8模型。PySide6 GUI&#xff1a;设计图形用户界面&#xff0c;用于显示检测结果和控制选项。摄像头/视频输入&#xff1a;从摄像头或视频文件读取图像帧。目标检测&#xff1a;使用YOLOv8模型对输入图像进行实时目标检测…

中国水资源用水紧张程度数据(栅格/0.5度)

2010-2020年中国用水紧张程度栅格数据集 数据介绍 用水紧张程度被定义为淡水汲取量占可用淡水资源的比例&#xff0c;又称取水强度&#xff0c;是衡量可持续发展目标具体目标6.4进展状况的重要指标。本数据集为2010年至2020年中国用水紧张程度逐年数据&#xff0c;格式为Geoti…

Anylogic制作界面元素tips

点击元素后跳转至其他视图&#xff0c;且能够把某个共同元素移植过去 navigate( viewStatistics2 ); groupControls.setX( groupControls.getX() 1200 );

互联网全景消息(2)之RabbitMq高阶使用

一、RabbitMQ消息可靠性保障 消息的可靠性投递是使用消息中间件不可避免的问题&#xff0c;不管是Kafka、rocketMQ或者是rabbitMQ&#xff0c;那么在RabbitMQ中如何保障消息的可靠性呢&#xff1f; 首先来看一下rabbitMQ的 架构图&#xff1a; 首先从图里我们可以看到&#xff…

脑机接口定义及相关概念

1 什么是脑机接口 脑机接口(Brain-Computer Interface,简称,BCI)是指一种系统或设备,它通过解码大脑的电生理信号来与外部计算机或设备进行直接的通讯。BCI的目的是在不依赖身体运动的情况下实现大脑与计算机之间的信息交换。 2 相关概念 2.1 脑电图(EEG) 最常用的脑机接口技…

C# 窗口页面布局

1.Groupbox 单机鼠标右键&#xff0c;置于底层 2.Label 在右方属性中修改名称 3.ComboBox 点击属性中的集合&#xff0c;可以添加选择项 4.CheckBox 在属性中修改名称 5.RichTextBox 富文本 在属性中修改名称与区域 6.StatusStrip 状态栏 将AutoSize改成false就可以修改…

深入探索MySQL数据库结构设计:实战案例解析,打造高效、可扩展的数据存储方案

作者简介&#xff1a;我是团团儿&#xff0c;是一名专注于云计算领域的专业创作者&#xff0c;感谢大家的关注 座右铭&#xff1a; 云端筑梦&#xff0c;数据为翼&#xff0c;探索无限可能&#xff0c;引领云计算新纪元 个人主页&#xff1a;团儿.-CSDN博客 前言&#xff1a;…

vue-echarts :知识图谱可视化,动态更新 动态赋值series,更新options

<template><div style="display: flex;align-items: center;justify-content: space-between;"><

【大模型llms本质,并分析未来发展反向】

大模型的本质: 是有损压缩后的概率模型 2024年2月28日&#xff0c;OpenAI 的核心研发人员 Jack Rae 在参加 Stanford MLSys Seminar 的访谈时进行了一个名为 Compression for AGI 的主题分享&#xff0c;其核心观点为&#xff1a;AGI的一个关键目标是通过最小描述长度&#xf…

苹果11月推出新款M4 Mac:Mac mini设计焕新 MacBook Pro仅例行更新

据外媒 MacRumors 报道&#xff0c;苹果公司计划在 11 月推出首批 M4 Mac&#xff0c;这一时间表与去年相似&#xff0c;当时苹果公司在同样的时间点中宣布推出搭载 M3 芯片的 MacBook Pro。 ▲ 苹果公司在 2023 年 10 月 31 日推出的 M3 MacBook Pro 同时根据古尔曼爆料称苹果…

安宝特科技 | AR眼镜在安保与安防领域的创新应用及前景

随着科技的不断进步&#xff0c;增强现实&#xff08;AR&#xff09;技术逐渐在多个领域展现出其独特的优势&#xff0c;尤其是在安保和安防方面。AR眼镜凭借其先进的功能&#xff0c;在机场、车站、海关、港口、工厂、园区、消防局和警察局等行业中为安保人员提供了更为高效、…

Tableau 社区项目 | 参与 Data+TV 挑战,洞悉全球电视剧集数据的精彩故事!

如果你钟爱某部电视剧集&#xff0c;正苦于没有数据练手&#xff0c;就快来参与 DataTV 挑战吧~ 去年&#xff0c;Tableau 和 IMDb 携手发起 DataMovies 挑战&#xff0c;吸引了全球各地的数据爱好者与影迷参与。今年&#xff0c;TC24 Viz 竞赛也以此为主题&#xff0c;让我们领…

SprinBoot+Vue问卷调查微信小程序的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue3.6 uniapp代码 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍&#xff1a;CSDN认证博客专家&#xff0c;CSDN平…

vsCode多文件标签栏换行显示

1.文件——首选项——点‘设置’ 2.输入 wrap tabs 并勾选Workbench › Editor: Wrap Tabs

Spring Boot源码阅读——spring.factories的加载机制

Spring Boot源码阅读——spring.factories的加载 提到 SpringBoot 的自动装配&#xff0c;不管是文章还是视频&#xff0c;都会提到 spring.factories 这个文件&#xff0c;这篇文章就来简单讲讲 spring.factories 的作用&#xff0c;以及它是怎么被加载的 简介 位置 以 Sprin…

Opencv中的直方图(3)直方图比较函数compareHist()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 比较两个直方图。 函数 cv::compareHist 使用指定的方法比较两个密集或两个稀疏直方图。 该函数返回 d ( H 1 , H 2 ) d(H_1, H_2) d(H1​,H2​…