05-17 09:37 门头沟学院 前端工程师 发布于广东
关注
5.16美团笔试
#笔试##面试之前应该如何准备？#
一、选择题：略。
二、编程题：
(1) 给定一个数字n（n <= 5e6），求有多少美丽数x <= n, 美丽数x的定义是：是一个正整数且存在一个质数p，使得x % p = 0且x <= p * p。
先用线性筛筛一遍素数，然后枚举每一个质数的倍数（时间复杂度是一个调和级数，约为log），时间复杂度O(N + n loglog(n))。
(2) 给定一个长度为n的且只有小写字母构成的字符串s，可以选择两个不同的索引x, y, 交换s[x] 和 s[y]，问恰好一次操作使得s[0] <= s[1] <= ... <= s[n - 1]可不可以，可以输出YES, 不可以输出NO，多组测试数据，长度和不超过1e5。
预处理每个位置往前最多有序多少位，记为dp[i], 举个例子，如果dp[i]=2, s[i]>=s[i-1]。
预处理前缀的索引最小值mx[26],每次记录每种字母s[i]-'a'的索引最小值。
枚举s，对于每个位置，枚举s[i]-'a'+1到25中的最小值，为什么是最左边的值，因为如果交换的不是最左边，那么左边还存在比它大的，肯定不行，因为操作恰好一次，最优方案一定是最左边的那个比它大的字符。假设找到了这个索引是l, 那么就是l和i交换，
判断：dp[l - 1] == l;dp[r-1] >= len(l+1,r-1);dp[n]>=len(r+1,n)，此时交换完是i, l, 要满足s[i]>=s[l-1], s[i]<=s[l+1], s[l]>=s[i-1], s[l]<=s[i+1]。
注意一下边界，如果一开始就是有序的，看有没有相等的，有就是YES。
一、选择题：略。
二、编程题：
(1) 给定一个数字n（n <= 5e6），求有多少美丽数x <= n, 美丽数x的定义是：是一个正整数且存在一个质数p，使得x % p = 0且x <= p * p。
先用线性筛筛一遍素数，然后枚举每一个质数的倍数（时间复杂度是一个调和级数，约为log），时间复杂度O(N + n loglog(n))。
(2) 给定一个长度为n的且只有小写字母构成的字符串s，可以选择两个不同的索引x, y, 交换s[x] 和 s[y]，问恰好一次操作使得s[0] <= s[1] <= ... <= s[n - 1]可不可以，可以输出YES, 不可以输出NO，多组测试数据，长度和不超过1e5。
预处理每个位置往前最多有序多少位，记为dp[i], 举个例子，如果dp[i]=2, s[i]>=s[i-1]。
预处理前缀的索引最小值mx[26],每次记录每种字母s[i]-'a'的索引最小值。
枚举s，对于每个位置，枚举s[i]-'a'+1到25中的最小值，为什么是最左边的值，因为如果交换的不是最左边，那么左边还存在比它大的，肯定不行，因为操作恰好一次，最优方案一定是最左边的那个比它大的字符。假设找到了这个索引是l, 那么就是l和i交换，
判断：dp[l - 1] == l;dp[r-1] >= len(l+1,r-1);dp[n]>=len(r+1,n)，此时交换完是i, l, 要满足s[i]>=s[l-1], s[i]<=s[l+1], s[l]>=s[i-1], s[l]<=s[i+1]。
注意一下边界，如果一开始就是有序的，看有没有相等的，有就是YES。
全部评论
170zhiyixi
广东金融学院 算法工程师
大佬带带我
小猫咪帮我找工作吧
门头沟学院 Java
老哥是一个小时吗？就两道编程题吗？
相关推荐
投递美团等公司7个岗位 点赞 评论 收藏
分享
美团开奖1032人在聊
查看18道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
