华为机试 - 完美走位

news/2024/3/29 22:39:14/文章来源:https://blog.csdn.net/qfc_128220/article/details/128062246

目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码


题目描述

输入一个长度为4的倍数的字符串,字符串中仅包含WASD四个字母。

将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换,如果替换后整个字符串中WASD四个字母出现的频数相同,那么我们称替换后的字符串是“完美走位”。

求子串的最小长度。

如果输入字符串已经平衡则输出0。

输入描述

一行字符表示给定的字符串s

数据范围:1<=n<=10^5且n是4的倍数,字符串中仅包含WASD四个字母。

输出描述

一个整数表示答案

用例

输入WASDAASD
输出1
说明将第二个A替换为W,即可得到完美走位
输入AAAA
输出3
说明将其中三个连续的A替换为WSD,即可得到完美走位

题目解析

题目要求,保持W,A,S,D字母个数平衡,即相等,如果不相等,可以从字符串中选取一段连续子串替换,来让字符串平衡。

比如:WWWWAAAASSSS

字符串长度12,W,A,S,D平衡的话,则每个字母个数应该是3个,而现在W,A,S各有4个,也就是说各超了1个。

因此我们应该从字符串中,选取一段包含1个W,1个A,1个S的子串,来替换为S。

WWWWAAAASSSS

WWWWAAAASSSS

WWWWAAAASSSS

........

WWWWAAAASSSS

而符合这种要求的子串可能很多,我们需要找出其中最短的,即WAAAAS

本题其实就是求最小覆盖子串,同LeetCode - 76 最小覆盖子串_伏城之外的博客-CSDN博客

题目解析请看上面链接博客。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {console.log(getResult(line));
});function getResult(str) {// 此时count记录统计W,A,S,D字母的数量const count = {W: 0,A: 0,S: 0,D: 0,};for (let c of str) count[c]++;// 平衡状态时,W,A,S,D应该都是avg数量const avg = str.length / 4;let total = 0; // total用于记录多余字母个数let flag = true; // flag表示当前是否为平衡状态,默认是for (let c in count) {if (count[c] > avg) {flag = false; // 如果有一个字母数量超标,则平衡打破count[c] -= avg; // 此时count记录每个字母超过avg的数量total += count[c];} else {delete count[c];}}if (flag) return 0; // 如果平衡,则输出0let i = 0;let j = 0;let minLen = str.length + 1;while (j < str.length) {const jc = str[j];if (count[jc]-- > 0) {total--;}while (total === 0) {minLen = Math.min(minLen, j - i + 1);const ic = str[i];if (count[ic]++ >= 0) {total++;}i++;}j++;}return minLen;
}

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

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

相关文章

Python学习:json对象与string相互转换教程

首先要明确&#xff0c;python里有json这个库&#xff0c;但并没有json这个类&#xff0c;所以所谓的json对象本质上就是一个dict&#xff1b;而json这个库&#xff0c;用于实现dict到string、string到dict的互转。 更具体一点&#xff0c;json对象&#xff08;dict&#xff0…

Linux网络编程——IO多路复用

文章目录1&#xff0c;I/O模型2&#xff0c;阻塞I/O 模式2.1&#xff0c;读阻塞&#xff08;以read函数为例&#xff09;2.2&#xff0c;写阻塞3&#xff0c;非阻塞I/O模式3.1&#xff0c;非阻塞I/O模式的实现&#xff08;fcntl()函数、ioctl() 函数&#xff09;3.1.1&#xff…

leetcode 343. 整数拆分(动态规划)

题目链接&#xff1a;343. 整数拆分 动态规划 (1) 确定 dpdpdp 数组下标含义&#xff1a; dp[i]dp[i]dp[i]: 将 iii 拆分为至少两个正整数之后的最大乘积&#xff1b; (2) 确定递推公式&#xff1a; 当 i≥2i \ge 2i≥2 时, 设 jjj 是 iii 拆分出来的第一个正整数&#xff0c…

关于uni-app小程序接入微信登录

https://uniapp.dcloud.net.cn/api/plugins/login.html#login 官网上有关于uni.login()的说明&#xff0c;如果是要微信登录&#xff0c;则需要wx.login()。 小程序登录 | 微信开放文档 如下图&#xff0c;在小程序管理平台生成AppSecret&#xff0c;同时将AppId在HubilderX中…

swift @State @Published @ObservedObject sink

State struct ContentView: View {State private var isRain truevar body: some View {VStack {Image(systemName: isRain ? "cloud.rain.fill" : "sun.max.fill").resizable().frame(width: 100, height: 100)Text(isRain ? "我們淋著大雨不知何…

【PS-7】移动工具

目录 移动工具快捷键【v】&#xff08;英文状态&#xff09; 多文件间拖拽图层对象 快捷键【ALT】复制图层 【ALTSHIFT】只能垂直/水平/45角地去复制图层 4个方向键可以微调图层的位置 变换控件 对齐分布 【题外话】设置参考线颜色 【题外话】快捷键【F12】让已经动过…

实验三-----数据库

一、实验目的 1.掌握SQL Server Management Studio中SQL 查询操作&#xff1b; 2.掌握SQL 的单表查询命令&#xff1b; 3.掌握SQL 的连接查询操作&#xff1b; 4.掌握SQL 的嵌套查询操作&#xff1b; 5.掌握SQL 的集合查询操作。 二、实验环境 1&#xff0e;实验室名称&…

[附源码]计算机毕业设计springboot海南琼旅旅游网

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; SSM mybatis Maven Vue 等等组成&#xff0c;B/S模式 M…

前端单元测试,更进一步

前端测试2022 如果从 2014 年 Jest 的第一个版本发布开始计算&#xff0c;前端开发领域工程化的单元测试能力已经发展了八年有余。Jest 集成了 Jasmine 等以往各种被证明有效的单元测试框架和断言等工具&#xff0c;也可以用来完成包含外部接口服务的集成测试等。最近几年热门的…

xxl-job安装部署

一、简介 XXL-JOB是一个分布式任务调度平台&#xff0c;其核心设计目标是开发迅速、学习简单、轻量级、易扩展。现已开放源代码并接入多家公司线上产品线&#xff0c;开箱即用。 中文文档English Documentation 二、安装 xxl-job需要的提前安装好以下环境&#xff1a;jdk、m…

INTERSPEECH 2022|CALM: 基于对比学习的表现力语音合成跨模态说话风格建模【语音之家】

本文由清华大学与腾讯科技有限公司和香港中文大学合作&#xff0c;并 在腾讯公司落地应用 。 说话风格建模对于表现力语音合成具有重要作用。 现有基于参考音频提取风格表征的方法通常利用文本的语义相似度进行参考音频选择&#xff0c;忽略了语义信息和说话风格的差异性。 本文…

大厂都在用MyBatis,跳槽的时候MyBatis更是面试必问的内容,那你对于MyBatis又掌握了多少呢?这份MyBatis源码解析值得拥有!

MyBatis作为一个流行的半自动ORM框架&#xff0c;里面融合了许多优秀的设计理念&#xff0c;分析其源码骨架能够帮你建立良好的项目设计经验。由于其比较复杂&#xff0c;我会分成几篇来讲&#xff0c;一起踏上征服的旅程吧&#xff01; 首先把MyBatis源码包导入到idea&#x…

python+django汽车租赁系统pycharm项目

目录 1 绪论 1 1.1课题背景 1 1.2课题研究现状 1 1.3初步设计方法与实施方案 2 1.4本文研究内容 2 4 2.3 B/S结构简介 4 2.4MySQL数据库 5 3 系统分析 6 3.1系统可行性分析 6 3.1.1经济可行性 6 3.1.2技术可行性 6 3.1.3运行可行性 6 3.2系统现状分析 6 3.3功能需求分析 7 …

Apollo 应用与源码分析:Monitor监控-软件监控-时间延迟监控

目录 代码 分析 RunOnce 函数分析 UpdateState函数分析 发送时间延迟报告函数分析 备注 代码 class LatencyMonitor : public RecurrentRunner {public:LatencyMonitor();void RunOnce(const double current_time) override;bool GetFrequency(const std::string& ch…

Git---idea中git的基本操作

idea中使用git仓库 idea中配置git仓库&#xff1a; 首先idea配置git仓库的位置 配置完成之后&#xff0c;有两种创建仓库的方式 从本地配置git仓库&#xff1a; idea本身设置好的&#xff0c;直接下一步就好 从远程克隆仓库&#xff1a; 如果远程仓库没有的话可以绑定完…

CDMP考试时间与报名方式

CDMP“数据管理专业人士认证”证书国际通用&#xff0c;行业认可度极高&#xff0c;是一项涵盖学历教育、工作经验和专业知识考试在内的综合资格认证&#xff0c;也是 目前全球唯一数据管理方面权威性认证 。CDMP考试时间是什么时候&#xff1f;怎样报名&#xff1f;今天小编来…

从ChargePoint到能链智电,充电服务商的价值创新

近日&#xff0c;吉林长春出租车雨雪之中排队换电艰难的视频引起热议。 新能源汽车充换电困难&#xff0c;一方面说明电池在寒冷天气下的性能有优化空间&#xff0c;另一方面也反映出国内新能源汽车配套基础设施仍然存在较大需求缺口。 充电基础设施建设对新能源汽车推广意义…

使用Spark的foreach算子及UDTF函数实现MySQL数据的一对多【Java】

使用Spark的foreach算子及UDTF函数实现MySQL数据的一对多【Java】 背景 我们的数仓项目中遇到了这样一种场景&#xff0c;脱敏后内容大致如下&#xff1a; col1col2time1time2a1b12022-01-01 00:00:002022-01-05 00:00:00a2b22022-01-28 00:00:002022-02-03 00:00:00a3b3202…

设计模式——模板方法模式

模板方法模式 一、基本思想 定义一个操作中的算法骨架&#xff0c;而将算法的一些步骤延迟到子类中&#xff0c;使得子类可以不改变该算法结构的情况下重定义该算法的某些特定步骤。 二、应用场景 算法的整体步骤很固定&#xff0c;但其中个别部分易变时&#xff0c;这时候…

数据结构学习:Trie树

Trie一、概念二、代码实现三、Tire树的时间复杂度和空间复杂度四、Tire树的优势一、概念 Trie树,也叫"字典树",顾名思义,是一种专门处理字符串匹配的树形结构,用来解决在一组字符串集合中快速找到某个字符串类似于这种字符串匹配问题,可以使用RF暴力匹配、RK哈希匹配…