分享一道字节跳动后端面试算法题

这篇具有很好参考价值的文章主要介绍了分享一道字节跳动后端面试算法题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

给你一个字符串s,可以将任意一个字符转为任意一个小写字符,这个操作可有m次,问转化后的字符串中最长的相等子串长度。

案例:

s="abcdac" ,m=2,2次操作,可以转化为"abcccc" ,最长是4,返回4。

分析:

题目很好理解,但是如果对算法掌握不是很透彻或者是对滑动窗口、双指针算法学的不是很明白的同学还是有点难度的。字符串的任意字符都可以改变成其他的字符。我们优先考虑滑动窗口双指针来写

定义left和right为左右指针,定义一个字典mp来记录字符串中每个字符出现的次数。遍历一次字符串s,每次循环执行如下,将该下标元素对应的字符+1,如果right-left+1(现在窗口的长度)- mp字典中最大的数(max_value)> m ,说明不可能完成这样的操作,减去当前mp下标元素对应的字符,left+1。再一次执行right-left+1(现在窗口的长度)- mp字典中最大的数(max_value)> m的操作,直接此判断语句不符合。结束后说明right-left+1的字符串满足操作m次将任意一个字符转为任意一个小写字符。与max_length比较取最大值。

mp:保证是字符串s滑动窗口 [left,right] 中字符对应的字符数量

max_value:滑动窗口中字符数量的最大值

max_length:m次操作后最长的相等子串长度

题目代码:文章来源地址https://www.toymoban.com/news/detail-567438.html

#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
	string s;
	int m;
	cin>>s;
	cin>>m;
	unordered_map<char,int>mp;
	int left=0;
	int max_lenth=0;
	for(int right=0;right<s.size();right++)
	{
		mp[s[right]]++;
		int max_value=0;
		for(int i=0;i<26;i++)
		{
			char ch='a'+i;
			max_value=max(max_value,mp[ch]);
		}
		while(right-left+1-max_value>m)
		{
			mp[s[left]]--;
			left++;
		}
		max_lenth=max(max_lenth,right-left+1);
	}
	cout<<max_lenth<<endl;
}

到了这里,关于分享一道字节跳动后端面试算法题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • HTTPS是如何保证安全的(1),字节跳动+腾讯+华为+小米+阿里面试题分享

    服务端发送给浏览器 加密方法以及公钥 之后浏览器通过公钥将数据加密传输给服务端,服务端收到数据使用私钥进行解密。服务端给浏览器发送数据,则使用私钥进行加密,浏览器收到服务端发送过来的数据,使用公钥进行解密。 存在的问题: 非对称加密效率太低 , 这会

    2024年04月10日
    浏览(49)
  • cocos creator上架字节跳动(抖音)小游戏注意事项(匿名登录、录屏、分享等踩坑记录)

    常见拒绝原因1:小游戏无录屏功能,不符合平台要求 2:小游戏录屏时间小于3S,分享按钮点击无反应或提示错误文案,不符合平台要求 3:小游戏录屏时间大于300S,分享按钮点击无反应或无法正常分享录屏,不符合平台要求 不久前写了款小游戏,最近上架了字节跳动小游戏平

    2024年01月16日
    浏览(50)
  • 字节跳动大数据容器化构建与落地实践

    动手点关注 干货不迷路 随着字节跳动旗下业务的快速发展,数据急剧膨胀,原有的大数据架构在面临日趋复杂的业务需求时逐渐显现疲态。而伴随着大数据架构向云原生演进的行业趋势,字节跳动也对大数据体系进行了云原生改造。本文将详细介绍字节跳动大数据容器化的

    2024年02月13日
    浏览(37)
  • 字节跳动开源其云原生数据仓库 ByConity

    动手点关注 干货不迷路 ‍ ByConity 是字节跳动开源的云原生数据仓库,它采用计算-存储分离的架构,支持多个关键功能特性,如计算存储分离、弹性扩缩容、租户资源隔离和数据读写的强一致性等。通过利用主流的 OLAP 引擎优化,如列存储、向量化执行、MPP 执行、查询优化

    2024年02月10日
    浏览(35)
  • 字节跳动云原生大数据平台运维管理实践

    云原生大数据是大数据平台新一代架构和运行形态。随着字节跳动内部业务的快速增长,传统大数据运维平台的劣势开始逐渐暴露,如组件繁多,安装运维复杂,与底层环境过度耦合;对业务方来说缺少开箱即用的日志、监控、告警功能等。在此背景下,我们进行了一系列云

    2024年02月11日
    浏览(37)
  • 火山引擎 DataLeap:揭秘字节跳动业务背后的分布式数据治理思路

    动手点关注 干货不迷路 导读:经过十多年的发展, 数据治理 在传统行业以及新兴互联网公司都已经产生落地实践。字节跳动也在探索一种分布式的数据治理方式。本篇内容来源于 火山引擎 超话数据直播活动的回顾,将从以下四个部分展开分享: 字节的挑战与实践 数据治

    2023年04月10日
    浏览(47)
  • 字节跳动 EB 级 Iceberg 数据湖的机器学习应用与优化

    深度学习的模型规模越来越庞大,其训练数据量级也成倍增长,这对海量训练数据的存储方案也提出了更高的要求:怎样更高性能地读取训练样本、不使数据读取成为模型训练的瓶颈,怎样更高效地支持特征工程、更便捷地增删和回填特征。本文将介绍字节跳动如何通过 Ic

    2024年02月15日
    浏览(50)
  • 演讲预告|字节跳动云原生大数据发展、AIGC 新引擎、运维管理实践

    出品人:李亚坤|火山引擎云原生计算技术负责人 专题简介: 大数据已成为企业数字化转型中, 支撑企业经营和业绩增长的主要手段之一。通过升级云原生架构,可以为大数据在弹性、多租户、敏捷开发、降本增效、安全合规、容灾和资源调度等方向上带来优势。传统的大数

    2024年02月11日
    浏览(38)
  • 字节跳动面试题目大数据计算引擎:impala对比hive,Python开发自学技巧

    数据流: 内存使用: 调度: 容错: 适用面: Impala相对于Hive所使用的优化技术 Impala的优缺点 Impala****与Hive的异同 ====================== 数据存储 使用相同的存储数据池都支持把数据储于HDFS, HBase。 元数据 两者使用相同的元数据。 SQL解释处理 比较相似都是通过词法分析生成执

    2024年04月10日
    浏览(49)
  • Unity游戏开发客户端面经——数据结构(初级)

    前言:记录了总6w字的面经知识点,文章中的知识点若想深入了解,可以点击链接学习。由于文本太多,按类型分开。这一篇是数据结构常问问题总结,有帮助的可以收藏。 GC方面:栈保持着先进后出的原则,是一片连续的内存域,有系统自动分配和维护,产生的垃圾系统自

    2024年02月06日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包