美团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实习生笔试##手撕题#
题干:删除最少的字符数,使得字符串中不包含长度为偶数的回文字符串。
输入:字符串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
因为偶数长度的回文子串中间两个字符必然连续相等 删掉连续重复就行
图论这题的话,因为是树所以无环,所以以a开始b结尾不走重复路径的路是唯一的。wfs找到这个路就行。
之后沿着这条路,a v1 v2 ... vn b,把a的度和vi度减一连乘,就是概率
相关推荐
点赞 评论 收藏
分享