程序员基德

01-31 17:36 中国科学技术大学 C++ 发布于浙江

关注

【笔试题解】2024-08-31-美团秋招

大家好这里是程序员基德，今天给大家带来的是美团笔试题(改编题面)的题目解析。

感兴趣的朋友可以来订阅基德的笔试专栏，感谢大家的支持。

互联网刷题必备宝典🔗

第一题：名字统计

题目内容

小基在整理同学名单时，发现混入了一些非人名的单词。已知人名单词必须以大写字母开头，请统计有效人名的数量。

输入描述

输入一个由大小写字母和空格组成的字符串 $s$ （ $1 \leq |s| \leq 10^5$ ），单词间用空格分隔，且字符串首尾不含空格。

输出描述

输出有效人名的数量。

样例1

输入：

ABC abc Abc

输出：

样例2

输入：

A A c

输出：

题解

这道题的关键是判断每个单词的首字母是否为大写。将输入字符串按空格分割后，遍历每个单词检查首字母即可。

时间复杂度： $O(n)$ ，其中 $n$ 是字符串长度。分割字符串和遍历单词的时间复杂度都是线性的。空间复杂度： $O(n)$ ，存储分割后的单词数组。

三语言参考代码

#include <iostream>
#include <sstream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    istringstream iss(s);
    string word;
    int count = 0;
    
    while(iss >> word) {
        if(word[0] >= 'A' && word[0] <= 'Z') {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Python

s = input().split()
count = sum(1 for word in s if word and word[0].isupper())
print(count)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] words = sc.nextLine().split(" ");
        int count = 0;
        
        for(String word : words) {
            if(!word.isEmpty() && Character.isUpperCase(word.charAt(0))) {
                count++;
            }
        }
        System.out.println(count);
    }
}

第二题：最短种树区间

题目内容

小柯需要安排 $n$ 位工人在无限长的公路上种树。每位工人从自己的位置开始向右种树，要求所有工人种树区间长度相同。求满足至少 $k$ 棵树的情况下，最短的种树区间长度。

输入描述

第一行输入两个整数 $n$ 和 $k$ （ $1 \leq n,k \leq 2 \times 10^5$ ）。第二行输入 $n$ 个整数 $a_1,a_2,...,a_n$ （ $1 \leq a_i \leq 2 \times 10^5$ ），表示工人位置。

输出描述

输出满足条件的最小区间长度。

样例1

输入：

3 6
1 2 5

输出：

题解

使用二分法确定最小种树长度。对于每个候选长度，计算总种树数是否满足要求。

时间复杂度： $O(n \log k)$ ，二分次数为 $\log k$ ，每次检查需要 $O(n)$ 时间。空间复杂度： $O(n)$ ，存储工人位置。

三语言参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> pos(n);
    for(int i=0; i<n; i++) cin >> pos[i];
    sort(pos.begin(), pos.end());
    
    int l=1, r=2e9;
    while(l < r) {
        int mid = l + (r-l)/2;
        long long cnt=0, last=-1e18;
        for(int p : pos) {
            long long start = max(last+1, (long long)p);
            long long end = p + mid -1;
            if(start > end) continue;
            cnt += end - start +1;
            last = end;
        }
        if(cnt >= k) r=mid;
        else l=mid+1;
    }
    cout << l << endl;
}

Python

n, k = map(int, input().split())
pos = sorted(list(map(int, input().split())))

def check(m):
    cnt = last = 0
    for p in pos:
        start = max(last +1, p)
        end = p + m -1
        if start > end: continue
        cnt += end - start +1
        last = end
    return cnt >=k

l, r = 1, 2*10**18
while l < r:
    mid = (l + r) //2
    if check(mid): r=mid
    else: l=mid+1
print(l)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] pos = new int[n];
        for(int i=0; i<n; i++) pos[i] = sc.nextInt();
        Arrays.sort(pos);
        
        long l=1, r=(long)2e18;
        while(l < r) {
            long mid = (l + r)/2;
            long cnt=0, last=Long.MIN_VALUE;
            for(int p : pos) {
                long start = Math.max(last+1, p);
                long end = p + mid -1;
                if(start > end) continue;
                cnt += end - start +1;
                last = end;
            }
            if(cnt >= k) r=mid;
            else l=mid+1;
        }
        System.out.println(l);
    }
}

第三题：区间博弈

题目内容

小兰和小柯在数组上进行博弈。每轮给定区间 $[l,r]$ ，小柯先选一个数，小兰扩展区间后选另一个数，较大者胜。求每轮结果及最小扩展长度。

输入描述

第一行输入 $n$ 和 $q$ （ $2 \leq n,q \leq 2 \times 10^5$ ）。第二行输入数组 $a$ 。接下来 $q$ 行每行两个整数 $l,r$ 。

输出描述

每轮输出结果（win/draw/lose）及最小扩展长度。

样例1

输入：

6 2
1 1 4 5 1 4
1 3
4 4

输出：

win
4
lose
2

题解

预处理区间最大值及其位置
使用单调栈预处理每个元素左右第一个更大值的位置
根据最大值出现次数判断胜负
计算最小扩展长度

时间复杂度： $O(n \log n + q)$ 空间复杂度： $O(n)$

三语言参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5+5;
int a[MAXN], lg[MAXN], st[MAXN][20], L[MAXN], R[MAXN];
vector<int> max_pos;

void build_st(int n) {
    for(int i=2; i<=n; i++) lg[i] = lg[i/2]+1;
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++) {
            int x = st[i][j-1], y = st[i+(1<<(j-1))][j-1];
            st[i][j] = a[x]>=a[y] ? x : y;
        }
}

int query_max(int l, int r) {
    int k = lg[r-l+1];
    int x = st[l][k], y = st[r-(1<<k)+1][k];
    return a[x]>=a[y] ? x : y;
}

void preprocess(int n) {
    stack<int> s;
    for(int i=1; i<=n; i++) {
        while(!s.empty() && a[s.top()] < a[i]) s.pop();
        L[i] = s.empty() ? 0 : s.top();
        s.push(i);
    }
    s = stack<int>();
    for(int i=n; i>=1; i--) {
        while(!s.empty() && a[s.top()] <= a[i]) s.pop();
        R[i] = s.empty() ? n+1 : s.top();
        s.push(i);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, q;
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        st[i][0] = i;
    }
    
    build_st(n);
    preprocess(n);
    
    int global_max = *max_element(a+1, a+n+1);
    for(int i=1; i<=n; i++)
        if(a[i] == global_max)
            max_pos.push_back(i);
    
    while(q--) {
        int l, r;
        cin >> l >> r;
        int pos = query_max(l, r);
        int val = a[pos];
        
        if(val == global_max) {
            int cnt = upper_bound(max_pos.begin(), max_pos.end(), r) 
                    - lower_bound(max_pos.begin(), max_pos.end(), l);
            if(cnt >= 2) {
                cout << "draw\n" << r-l+1 << "\n";
            } else {
                cout << "lose\n";
                int min_len = INT_MAX;
                if(pos > 1) min_len = min(min_len, pos - l);
                if(pos < n) min_len = min(min_len, r - pos);
                cout << (min_len == INT_MAX ? r-l+1 : r-l+1 + min_len) << "\n";
            }
        } else {
            int left = L[pos] >= l ? L[pos] : -1e9;
            int right = R[pos] <= r ? R[pos] : 1e9;
            if(left == -1e9 && right == 1e9) {
                cout << "lose\n" << r-l+1 << "\n";
            } else {
                int extend = min(pos - left, right - pos);
                cout << "win\n" << (r-l+1 + extend) << "\n";
            }
        }
    }
    return 0;
}

Python

import bisect

n, q = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a  # 1-based index
max_val = max(a)
max_pos = [i for i in range(len(a)) if a[i] == max_val]

# Preprocess ST table
LOG = 20
st = [[0]*(n+1) for _ in range(LOG)]
for i in range(1, n+1):
    st[0][i] = i
for k in range(1, LOG):
    for i in range(1, n+1 - (1<<k) +1):
        x = st[k-1][i]
        y = st[k-1][i + (1<<(k-1))]
        st[k][i] = x if a[x] >= a[y] else y

# Preprocess L and R
L = [0]*(n+2)
R = [n+1]*(n+2)
stack = []
for i in range(1, n+1):
    while stack and a[stack[-1]] < a[i]:
        stack.pop()
    L[i] = stack[-1] if stack else 0
    stack.append(i)
stack = []
for i in range(n, 0, -1):
    while stack and a[stack[-1]] <= a[i]:
        stack.pop()
    R[i] = stack[-1] if stack else n+1
    stack.append(i)

for _ in range(q):
    l, r = map(int, input().split())
    k = (r - l + 1).bit_length() -1
    x = st[k][l]
    y = st[k][r - (1<<k) +1]
    pos = x if a[x] >= a[y] else y
    val = a[pos]
    
    if val == max_val:
        left_idx = bisect.bisect_left(max_pos, l)
        right_idx = bisect.bisect_right(max_pos, r)
        cnt = right_idx - left_idx
        if cnt >= 2:
            print("draw")
            print(r - l +1)
        else:
            print("lose")
            min_len = float('inf')
            if pos > 1:
                min_len = min(min_len, pos - l)
            if pos < n:
                min_len = min(min_len, r - pos)
            print(r - l +1 + (0 if min_len == float('inf') else min_len))
    else:
        left = L[pos] if L[pos] >= l else -1e9
        right = R[pos] if R[pos] <= r else 1e9
        if left == -1e9 and right == 1e9:
            print("lose")
            print(r - l +1)
        else:
            extend = min(pos - left, right - pos)
            print("win")
            print(r - l +1 + extend)

Java

import java.util.*;
import java.io.*;

public class Main {
    static int[][] st;
    static int[] a, L, R;
    static List<Integer> maxPos = new ArrayList<>();
    static int n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);
        int q = Integer.parseInt(first[1]);
        a = new int[n+1];
        st = new int[20][n+1];
        
        String[] arr = br.readLine().split(" ");
        for(int i=1; i<=n; i++) {
            a[i] = Integer.parseInt(arr[i-1]);
            st[0][i] = i;
        }
        
        // Build ST table
        for(int j=1; j<20; j++) 
            for(int i=1; i+(1<<j)-1<=n; i++) {
                int x = st[j-1][i];
                int y = st[j-1][i + (1<<(j-1))];
                st[j][i] = a[x] >= a[y] ? x : y;
            }
        
        // Preprocess L and R
        L = new int[n+2];
        R = new int[n+2];
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i=1; i<=n; i++) {
            while(!stack.isEmpty() && a[stack.peek()] < a[i]) stack.pop();
            L[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for(int i=n; i>=1; i--) {
            while(!stack.isEmpty() && a[stack.peek()] <= a[i]) stack.pop();
            R[i] = stack.isEmpty() ? n+1 : stack.peek();
            stack.push(i);
        }
        
        int globalMax = Arrays.stream(a).max().getAsInt();
        for(int i=1; i<=n; i++) 
            if(a[i] == globalMax) maxPos.add(i);
        
        while(q-- >0) {
            StringTokenizer stk = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(stk.nextToken());
            int r = Integer.parseInt(stk.nextToken());
            int k = 31 - Integer.numberOfLeadingZeros(r - l +1);
            int x = st[k][l];
            int y = st[k][r - (1<<k) +1];
            int pos = a[x] >= a[y] ? x : y;
            int val = a[pos];
            
            if(val == globalMax) {
                int leftIdx = Collections.binarySearch(maxPos, l);
                if(leftIdx <0) leftIdx = -leftIdx -1;
                int rightIdx = Collections.binarySearch(maxPos, r);
                if(rightIdx <0) rightIdx = -rightIdx -2;
                int cnt = rightIdx - leftIdx +1;
                if(cnt >=2) {
                    System.out.println("draw");
                    System.out.println(r - l +1);
                } else {
                    System.out.println("lose");
                    int minLen = Integer.MAX_VALUE;
                    if(pos >1) minLen = Math.min(minLen, pos - l);
                    if(pos <n) minLen = Math.min(minLen, r - pos);
                    System.out.println(r - l +1 + (minLen == Integer.MAX_VALUE ? 0 : minLen));
                }
            } else {
                int left = L[pos] >= l ? L[pos] : -1_000_000_000;
                int right = R[pos] <= r ? R[pos] : 1_000_000_000;
                if(left == -1_000_000_000 && right == 1_000_000_000) {
                    System.out.println("lose");
                    System.out.println(r - l +1);
                } else {
                    int extend = Math.min(pos - left, right - pos);
                    System.out.println("win");
                    System.out.println(r - l +1 + extend);
                }
            }
        }
    }
}

#美团##秋招##春招提前批，你开始投了吗##春招#

互联网刷题笔试宝典文章被收录于专栏

互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力