美团3.23笔试(算法策略)求大佬指点

【回文字符串题】:
题干:删除最少的字符数,使得字符串中不包含长度为偶数的回文字符串。
输入:字符串S
输出:删除最少的字符数量

【排序题】:
题干:给定一个数组nums和一个字符串S,两者长度相同,S只包含'W'和'R','R'元素与'R'元素之间可以两两互换;'R'和'W'不可以互换;'W'和'W'也不可以互换。求问最少的交换次数使得nums非降序。
输入:数组长度、数组、字符串
输出:如果无法使得nums非降序,输出-1;否则,输出最小次数

【图论题】:
题干:现在有一颗迷宫树,每次小美随机选择一条边走路,求从a点成功走到b点的概率?
思路:深度优先遍历,a遍历到所有叶子节点的路径条数为sum,其中经过了b的路径数量num,因此,num/sum即为成功走到b点的概率

【字符串题】:
题干:给定一个字符串a(100)b(200)c(300),括号中的是该字符的数量;计算一个字符串权值的公式:weight = 字符种类*字符串长度。给定一个权值k,要求尽可能多的切分字符串,并且每个子串的权值>=k。求子串的最大数量。
输入:字符串、权值
输出:子串的最大数量

#美团暑期##美团2025实习生笔试##手撕题#
全部评论
回文串题 只要删除连续的相同字符就行 比如aa 删一个a abbc和abba删一个b abccba删一个c 因为偶数长度的回文子串中间两个字符必然连续相等 删掉连续重复就行
3 回复 分享
发布于 03-23 14:24 浙江
图论这题的话,因为是树所以无环,所以以a开始b结尾不走重复路径的路是唯一的。wfs找到这个路就行。 之后沿着这条路,a v1 v2 ... vn b,把a的度和vi度减一连乘,就是概率
点赞 回复 分享
发布于 04-01 21:23 浙江

相关推荐

09-29 17:39
已编辑
门头沟学院 Java
BG:双9,一段携程后端实习【流程】9.7笔试,9.26一面 9.29二面【一面】自我介绍实习项目介绍及问题延申:责任链设计模式;模版模式;模板方法为啥要抽象出来;redis库存管理decr和加锁;redis setnx用的k-v是啥;setnx会有并发效率很低的问题吗,有更好的改进效率的方案吗;redis 超时失败如何处理;redis中不知道是不是执行成功是抛异常还是继续流程;为什么用kafka不用其他的消息队列;kafka消息丢失怎么办;压测怎么测试流量;非科班一般遇到计算机领域的知识不懂怎么解决部分八股:threadlocal的原理,key和value是什么;hashmap的初始化大小,扩容机制是怎样的,为什么扩容得是原来的2倍;java集合;final,finally和finalize;操作数组时如何边遍历边移除;死锁的发生的必要条件和手段;手撕一道:重排链表,双指针做的,问有没有无需额外空间的做法(左右部分逆序 找中点)额外:为什么想做后端开发;抗压能力强的例子;付出了很多但是结果不符合预期怎么办是一位很温柔的小姐姐,体验感很好~【二面】自我介绍实习项目介绍 实习里遇到比较困难的点 主要是对具体所做一些业务的延伸 大概快半小时线程池的原理线程池核心线程数是5 任务执行完线程状态是什么 这个时候如果有新的任务提交应该怎么执行主线程提交任务整体流程手撕一道伪代码的题热点数据获取,10s内出现1000次的数据视为热点数据,如果缓存有数据直接读缓存,缓存没有直接读数据库应该是部门的负责人,感觉很多技术深度问的比较多,人很友善,一开始手撕思路写错了还提示了一下🥹
点赞 评论 收藏
分享
3 9 评论
分享
牛客网
牛客企业服务