【算法专场】模拟(上)

2024-09-04 01:52
文章标签 算法 模拟 专场

本文主要是介绍【算法专场】模拟(上),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

​前言

模拟算法

1576. 替换所有的问号 

495. 提莫攻击

 1688. 比赛中的配对次数

 6. Z 字形变换


前言

我们在有时候会看到刷题网站上面看到一些已经把题意讲的很明确的题目,并且一般这种不怎么需要利用那些复杂的算法,只需要我们按照着题目的意思就能够写出来,这种就是---模拟算法

模拟算法

模拟算法本质上就是比葫芦画瓢

我们只需要根据题目要求即可解答,但需要注意细节。

一般模拟的过程,我们需要在草稿纸上进行模拟,考虑某些细节问题,在模拟完之后根据演算的过程将代码一步步写出来。

接下来我们来练习一下

1576. 替换所有的问号 

通过上面的板书,那么我们就可以将演算的过程转化为以下代码:

class Solution {public String modifyString(String ss) {// 将字符串转为字符数组char[] s = ss.toCharArray();// 获取zifushuint n = s.length;for (int i = 0; i < n; i++) {// 判断字符是否是问号if (s[i] == '?') {// 遍历字符,判断是否有满足条件的for (char ch = 'a'; ch <= 'z'; ch++) {// 如果是在第一个字符或者最后一个字符,特殊处理if ((i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch)) {s[i] = ch;// 替换完毕,停止循环break;}}}}// 返回字符串return String.valueOf(s);}
}

 时空复杂度为O(n),n为字符串长度。

495. 提莫攻击

将图中的演算过程转化为代码:

class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {//用来存储最终结果int ans=0;//遍历,从1开始for(int i=1;i<timeSeries.length;i++){int x=timeSeries[i]-timeSeries[i-1];if(x>=duration) ans+=duration;else ans+=x;}return ans+duration;}
}

 1688. 比赛中的配对次数

将上述转换为代码:

class Solution {public int numberOfMatches(int n) {int ans=0;while(n!=1){if(n%2==1){//奇数,比赛次数为(n-1)/2sum+=(n-1)/2;n=(n-1)/2+1;}else{//偶数,比赛次数为n/2sum+=n/2;n/=2;}}return ans;}
}

 6. Z 字形变换

将上述转换为代码:

/*** 将给定的字符串按照Z字形排列后,按行读取并返回结果字符串* Z字形排列是指字符串在numRows行中按顺序排列,第一行和最后一行除外,其它行在两端对齐* 例如,"PAYPALISHIRING"在3行中按Z字形排列后,按行读取的结果是"PAHNAPLSIIGYIR"** @param s 输入的字符串* @param numRows 字符串排列的行数* @return 按Z字形排列后按行读取的字符串*/
public String convert(String s, int numRows) {// 判断特殊情况,如果行数为1,直接返回原字符串if (numRows == 1) return s;// 创建一个字符串StringBuffer sb = new StringBuffer();// 获取输入字符串的长度int n = s.length();// 公差,用于计算每个字符在字符串中的位置增量int d = numRows * 2 - 2;// 处理第一行for (int i = 0; i < n; i += d) {sb.append(s.charAt(i));}// 处理中间行for (int k = 1; k < numRows - 1; k++) {for (int i = k, j = d - k; i < n; i += d, j += d) {sb.append(s.charAt(i));if (j < n) {sb.append(s.charAt(j));}}}// 处理最后一行for (int i = numRows - 1; i < n; i += d) {sb.append(s.charAt(i));}// 将字符串缓冲区转换为字符串并返回return sb.toString();
}

以上就是模拟上篇的全部内容咯~

若有不足,欢迎指正~ 

 

这篇关于【算法专场】模拟(上)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1134667

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int