米哈游9.14笔试第一题

找出字符串中存在k个“mihoyo”的最短子串,如果存在,则输出左下标 和右下标,不存在就输出-1, 卡了半个小时了,代码一直25%,求大佬指教指教
#include<iostream>
using namespace std;
#include<vector>
#include<string>
int main() {
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	string res = "mihoyo";
	int count = 0;
	int l = 0;
	int r = 0;
	vector<pair<int, int>>vec;
	int min_len = INT16_MAX;
	for (int left = 0; left < n - 5; left++) {
		string temp = s.substr(left, 6);
		if (temp == res) {
			vec.push_back({ left, left + 6 - 1 });
			left = left + 5;
		}
	}
	int size = vec.size();
	if (size < k) {
		cout << -1 << endl;
		return 0;
	}
	else {
		int len = 20000000;
		for (int i = 0; i < vec.size() - k + 1; i++) {
			if (vec[i + k - 1].second - vec[i].first < len) {
				l = vec[i].first;
				r = vec[i + k - 1].second;
			}
		}
		cout << l <<" "<< r << endl;
	}
	return 0;

}

#米哈游23秋招笔试心得体会#
全部评论
和你一样思路 过了33
1 回复 分享
发布于 2022-09-14 22:25 北京
找到的不一定是最短的 例: 20 2 mihoyomihoyoaamihoyo
1 回复 分享
发布于 2022-09-14 22:22 四川
#include <bits/stdc++.h> using namespace std; int n, k; string s; int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin >> n >> k;     cin >> s;     int idx = s.find("mihoyo");     int ans = 2 * n;     vector<int> a;     int pre = 0;     while (idx != -1) {         a.push_back(idx + pre);         pre = pre + idx + 6;         string tmp = s.substr(pre);         idx = tmp.find("mihoyo");     }     if (a.size() < k) {         cout << -1 << endl;         return 0;     }     int l = 0, r = 0;     int ll, rr;     while (r < a.size()) {         while (r < a.size() && (r - l) < k - 1) {             r++;         }         if (r == a.size()) break;         int end = a[r] + 5;         int begin = a[l];         if (end - begin + 1 < ans) {             ans = end - begin + 1;             ll = begin, rr = end;         }         l++;     }     cout << ll << " " << rr << endl;     return 0; }
1 回复 分享
发布于 2022-09-14 22:18 北京
先遍历一下找到所有米哈游的位置,然后在遍历一下这些位置,找到最短的
点赞 回复 分享
发布于 2022-09-15 15:53 上海
没有更新len
点赞 回复 分享
发布于 2022-09-15 09:26 上海
这代码好像是我写的一样哈哈哈 我开始也忘记更新最小长度了 在这卡了好久
点赞 回复 分享
发布于 2022-09-14 22:28 湖南
俺也25
点赞 回复 分享
发布于 2022-09-14 22:23 江苏
我也是,25我很难理解
点赞 回复 分享
发布于 2022-09-14 22:15 陕西

相关推荐

06-26 15:33
青岛工学院 Java
积极的秋田犬要冲国企:他现在邀请我明天面试
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司8个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 12:22
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务