美团笔试美团实习 0311

笔试时间：2023年3月11日

第一题

题目：小美的字符串

小美有一个由数字字符组成的字符串。现在她想对这个字符串进行一些修改。具体地，她可以将这个字符串中任意位置字符修改为任意的数字字符。她想知道至少进行多少次修改，可以使修改后的字符串不包含两个连续相同的字符？例如，对于字符串”111222333”，她可以进行3次修改将其变为”121212313"。

输入描述

一行，一个字符串s，保证s只包含数字字符。(1 <= |s| <= 100000)

输出描述

一行，一个整数，表示修改的最少次数。

示例输入

示例一：111222333

示例二：11551111

示例输出

示例一：3

示例二：4

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

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

int solution(vector<char>& s) {
    int cnt = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == s[i - 1]) {
            cnt++;
            if (i == s.size() - 1) {
                return cnt;
            }

            for (int nx = 0; nx < 10; nx++) {
                if (static_cast<char>('0' + nx) != s[i - 1] && static_cast<char>('0' + nx) != s[i + 1]) {
                    s[i] = static_cast<char>('0' + nx);
                    break;
                }
            }
        }
    }
    return cnt;
}

int main() {
    string input;
    cin >> input;
    vector<char> s(input.begin(), input.end());
    cout << solution(s) << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.nextLine().toCharArray();
        System.out.println(solution(s));
    }

    static int solution(char[] s) {
        int cnt = 0;
        for (int i = 1; i < s.length; i++) {
            if (s[i] == s[i - 1]) {
                cnt++;
                if (i == s.length - 1) {
                    return cnt;
                }

                for (int nx = 0; nx < 10; nx++) {
                    if (Character.forDigit(nx, 10) != s[i - 1] && Character.forDigit(nx, 10) != s[i + 1]) {
                        s[i] = Character.forDigit(nx, 10);
                        break;
                    }
                }
            }
        }
        return cnt;
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solution(s):
    cnt = 0
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            cnt += 1
            if i == len(s) - 1:
                return cnt

            for nx in range(10):
                if str(nx) != s[i - 1] and str(nx) != s[i + 1]:
                    s[i] = str(nx)
                    break
    return cnt

print(solution([c for c in input()]))

第二题

题目：流星

小美是一位天文爱好者，她收集了接下来一段时间中所有会划过她所在的观测地上空的流星信息。具体地,她收集了n个流星在她所在观测地上空的出现时刻和消失时刻。对于一个流星，若其的出现时刻为s,消失时刻为t,那么小美在时间段[s,t]都能够观测到它。对于一个时刻，观测地上空出现的流星数量越多，则小美认为该时刻越好。小美希望能够选择一个最佳的时刻进行观测和摄影，使她能观测到最多数量的流星。现在小美想知道，在这个最佳时刻，她最多能观测到多少个流星以及一共有多少个最佳时刻可供她选择。

输入描述

第一行是一个正整数n,表示流星的数量。

第二行是n个用空格隔开的正整数,第i个数si表示第i个流星的出现时间。

第三行是n个用空格隔开的正整数,第i个数ti表示第i个流星的消失时间。

1<=n<=100000, 1<=si<=ti<=10^9

输出描述

输出一行用空格隔开的两个数x和y，其中x表示小美能观测到的最多的流行数，y表示可供她选择的最佳时刻数量。

示例输入

3

2 1 5

6 3 7

示例输出

2 4

参考题解

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] intervals = new int[n][2];

        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            ends[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            intervals[i][0] = starts[i];
            intervals[i][1] = ends[i];
        }

        maxCoveredPoint(intervals);
    }

    static void maxCoveredPoint(int[][] intervals) {
        List<int[]> points = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[0] == interval[1]) {
                points.add(new int[]{interval[0], 3});
            }
            points.add(new int[]{interval[0], 1});
            points.add(new int[]{interval[1], 2});
        }
        Collections.sort(points, (a, b) -> a[0] - b[0]);

        int maxCoverage = 0;
        int coveredPoint = 0;
        int count = 0;
        for (int[] point : points) {
            if (point[1] == 1) coveredPoint += point[1];
            if (coveredPoint > maxCoverage) {
                maxCoverage = coveredPoint;
                count = 1;
            } else if (coveredPoint == maxCoverage) {
                count++;
            }
            if (point[1] == 2 || point[1] == 3) coveredPoint -= 1;
        }

        System.out.print(maxCoverage + " ");
        System.out.println(count);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def max_covered_point(intervals):
    points = []
    for interval in intervals:
        if interval[0] == intervals[1]:
            points.append(interval[0], 3)
        points.append((interval[0], 1))
        points.append((interval[1], 2))
    points.sort()
    max_ = 0
    cov_point = 0
    cnt = 0
    for point in points:
        if point[1] == 1: cov_point += point[1]
        if cov_point > max_:
            max_ = cov_point
            cnt = 1
        elif cov_point == max_:
            cnt += 1
        if point[1] == 2 or points[1] == 3: cov_point -= 1


    print(max_, end=" ")
    print(cnt)

n = int(input())
intevals = [[0, 0] for _ in range(n)]

sts = [int(c) for c in input().split(" ")]
ends = [int(c) for c in input().split(" ")]
for i in range(n):
    intevals[i][0] = sts[i]
    intevals[i][1] = ends[i]

max_covered_point(intevals)

第三题

题目：最佳规划

小团在一个n *m的网格地图上探索。网格地图上第i行第j列的格子用坐标(i,j)简记。初始时,小团的位置在地图的左上角。即坐标(1,1),地图上的每一个格子上都有一定的金币，特别地,小团位于的初始位置(1,1)上的金币为0。小团在进行探索移动时,可以选择向右移动一格(即从(x,y)到达(x,y+1))或向下移动一格(即从(x,y)到达(x+1,y))。地图上的每个格子都有一个颜色，红色或蓝色。如果小团一次移动前后的两个格子颜色不同，那么他需要支付k个金币才能够完成这一次移动;如果移动前后的两个格子颜色相同,则不需要支付金币。小团可以在任意格子选择结束探索。现在给你网格地图上每个格子的颜色与金币数量,假设小团初始时的金币数量为0，请你帮助小团计算出最优规划，使他能获得最多的金币,输出能获得的最多金币数量即可。

注意:要求保证小团任意时刻金币数量不小于零。