恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经，目前已更新至美团、微软…
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡?

第一题：最短子串

题目描述

米小游拿到了一个字符串，她想截取一个连续子串，使得该子串中包含至少k个连续的“mihoyo”。

你可以帮米小游求出最短的子串长度，以及对应的子串位置吗？

输入描述

第一行输入两个正整数n和k，用空格隔开。

第二行输入一个长度为n的、仅由小写字母组成的字符串。1≤k≤n≤200000

22 2

mihoyoyomihoyomimihoyo

输出描述

如果不存在这样一个连续子串，请输出-1。

否则输出两个正整数l，r，代表选取的子串的左下标和右下标(整个字符串左下标为0，右下标为n-1）。

请务必保证选择的连续子串包含至少k个"mihoyo"，且长度是最短的。有多解时输出任意即可。

0 13

代码

Java版本

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();
        String tmp = "mihoyo";
        List<Integer> l = new ArrayList<>();
        // 先尝试获取 mihoyo 的位置，这里用list存储m的索引
        for(int i = 0; i < n - 5; i++){
            boolean ok = true;
            for(int j = 0; j < 6; j++){
                if(s.charAt(i+j) != tmp.charAt(j)){
                    ok = false;
                }
            }
            if(ok){
                l.add(i);
                i += 5;
            }
        }
        // 不够 k 个
        if(l.size() < k){
            System.out.println(-1);
            return;
        }
        // 判断比较
        int retIdx = 0;
        int len = l.get(k-1) - l.get(0);
        for(int i = k; i < l.size(); i++){
            int tmplen = l.get(i) - l.get(i-k+1);
            if(tmplen <= len){
                retIdx = i-k+1;
                len = tmplen;
            }
        }
        System.out.println(l.get(retIdx)+" "+(l.get(retIdx+k-1)+5));
    }
// vx公众号关注TechGuide 实时题库 闪电速递

Python版本

n, k = map(int, input().split())
s = input()
a = []
start = 0
t = 'mihoyo'
while True:
    i = s.find(t, start)
    if i == -1: break
    a.append(i)
    start = i + 1
ans = float('inf')
ansl, ansr = 0, 0

if len(a) >= k:
    for i in range(len(a) - k + 1):
        l = a[i]
        r = a[i + k - 1] + 5
        if r - l + 1 < ans:
            ans = r - l + 1
            ansl, ansr = l, r

if ans == float('inf'): print(-1)
else: print(ansl, ansr)
# vx公众号关注TechGuide 实时题库 闪电速递

CPP版本

#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;
}
// vx公众号关注TechGuide 实时题库 闪电速递

第二题：猜数字

题目描述

米小游心中想了一个正整数，她邀请了n个人来猜这个数。每个人会猜一个数ai，然后米小游会告诉对方猜的结果：大于等于米小游想的数（≥）或者小于米小游想的数（<）。

猜谜结束后，米小游统计了共有x个≥和y个<。请你判断米小游初始想的数有多少种不同的可能？

输入描述：

输出描述：

input:

output:

输入描述

第一行输入一个正整数n，代表猜谜的人数。

第二行输入n个正整数ai，代表每个人猜的数字。

第三行输入两个整数x和y，用空格隔开。

1≤x+y=n≤1e5，1 ≤ ai ≤ 1e9

3
1 5 3
0 3

输出描述

如果有无穷多种可能，输出"infinity"

否则输出一个整数，代表米小游心中想的数的不同可能数量。

infinity

代码

Java版本

    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
        int a = sc.nextInt(), b = sc.nextInt();
        Arrays.sort(arr);
        if(b == 0){ // 全部是小于等于的
            System.out.println(arr[0]);
            return;
        }
        if(a == 0) { // 全部是大于的
            System.out.println("infinity");
            return;
        }
        int left = arr[b-1], right = arr[b];
        if(left == right){ // left < x <= right 不成立
            System.out.println(-1);
            return;
        }else{
            System.out.println(right-left);
        }

    }
// vx公众号关注TechGuide 实时题库 闪电速递

Python版本

n = int(input())
*a, = map(int, input().split())
x, y = map(int, input().split())
a.sort()

if x == 0:
    print('infinity')
else:
    if y:
        l = a[y - 1]
    else:
        l = 1
    r = a[y]
    print(r - l)
# vx公众号关注TechGuide 实时题库 闪电速递

第三题：树的连通块

题目描述

米小游有一棵有根树，树上共有n个节点。

米小游指定了一个节点x为根，然后定义所有相邻的、编号奇偶性相同的节点为一个连通块。

米小游想知道，所有子树（共有n个子树）的连通块数量之和是多少？

举个例子：

如上图，3号节点被指定为根

然后3-1-5作为一个连通块，4号节点和2号节点为单独的连通块。

那么1号节点到5号节点，每个节点的子树连通块数量分别为：2、1、3、1、1，总连通块数量是8。

输入描述

5 3
1 2
1 3
3 4
5 1

输出描述

8

代码

Java版本

    static Map<Integer, Integer> map;
    static long ret;
    static List<List<Integer>> l;
    static boolean vis[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();

        vis = new boolean[n+1];
        map = new HashMap<>();
        ret = 0;

        l = new ArrayList<>();
        for(int i = 0; i <= n; i++){
            l.add(new ArrayList<>());
        }
        for(int i = 0; i < n-1; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            l.get(a).add(b);
            l.get(b).add(a);
        }

        dfs(root);
        System.out.println(ret);
    }

    public static int dfs(int pos) {
        List<Integer> childs = l.get(pos);
        vis[pos] = true;
        // 当前节点是一个连通分量
        int tmp = 1;
        for(int child: childs){
            if(!vis[child]){
                // 获取 child 的连通分量
                tmp += dfs(child);
                // 如果同奇偶，则连通分量个数-1
                if(child % 2 == pos%2) {
                    tmp -=1;
                }
            }
        }
        ret += tmp;
        return tmp;
    }

// vx公众号关注TechGuide 实时题库 闪电速递

Python版本

import sys

sys.setrecursionlimit(int(2e5))

n, x = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)


def solve():
    ret = 0

    def dfs(cnt, pre):
        ans = 1
        for nxt in g[cnt]:
            if nxt == pre: continue
            ans += dfs(nxt, cnt)
            if (cnt & 1) == (nxt & 1): ans -= 1
        nonlocal ret
        ret += ans
        return ans

    dfs(x, -1)
    return ret
    
print(solve())
# vx公众号关注TechGuide 实时题库 闪电速递