美团软件算法笔试3-18

公号：嵌入式未来

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《嵌入式软件笔试-2023年真题汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

题型：5道编程题

题目1：

题目描述:

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。

敌人的位置将被一个二维坐标(x,y)所描述。

小美有一个全屏技能,该技能能一次性将若干敌人一次性捕获。

捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B。

现在给出所有敌人的坐标,你的任务是计算小美一次性最多能使用技能捕获多少敌人。

输入描述

第一行三个整数N,A,B,表示共有N个敌人,小美的全屏技能的参数A和参数B.接下来N行,每行两个数字xy,描述一个敌人所在的坐标。

1≤N≤500,1≤A,B≤1000,1≤x,y≤1000.

输出描述

一行,一个整数表示小美使用技能单次所可以捕获的最多数量。

样例输入

3 1 1

1 1

1 2

1 3

样例输出

2

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

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	vector<pair<int, int> > enemies(n);
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		enemies[i] = {x, y};
	}
	int max_count = 1;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			int x_diff = abs(enemies[i].first - enemies[j].first);
			int y_diff = abs(enemies[i].second - enemies[j].second);
			if (x_diff <= a && y_diff <= b) {
				int count = j - i + 1;
				max_count = max(max_count, count);
			}
		}
	}
	cout << max_count << endl;
	return 0;
}

题目2：

题目描述:

小美现在有一串彩带,假定每一厘米的彩带上都是一种色彩。

因为任务的需要,小美希望从彩带上截取一段,使得彩带中的颜色数量不超过K种。显然,这样的截取方法可能非常多。于是小美决定尽量长地截取一段。

你的任务是帮助小美截取尽量长的一段,使得这段彩带上不同的色彩数量不超过K种。

输入描述

第一行两个整数N,K,以空格分开,分别表示彩带有N厘米长,你截取的一段连续的彩带不能超过K种颜色。

接下来一行N个整数,每个整数表示一种色彩,相同的整数表示相同的色彩。1≤N,K≤5000,彩带上的颜色数字介于[1,2000]之间。

输出描述

一行,一个整数,表示选取的彩带的最大长度。

样例输入

8 3

1 2 3 2 1 4 5 1

样例输出

5

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

int main() {
    int n, k;
    cin >> n >> k;
    int* arr = new int[n];
    map<int, int> color_cnt;
    int left = 0, right = 0, max_len = 0, color_num = 0;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        color_cnt[arr[i]]++;
        if (color_cnt[arr[i]] == 1) {
            color_num++;
        }
        while (color_num > k) {
            color_cnt[arr[left]]--;
            if (color_cnt[arr[left]] == 0) {
                color_num--;
            }
            left++;
        }
        max_len = max(max_len, i - left + 1);
    }

    cout << max_len << endl;
    delete[] arr;
    return 0;
}

题目3：

题目描述:

现在小美获得了一个字符串。小美想要使得这个字符串是回文串。

小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符’a’-‘z’。

你的任务是帮助小美在当前制约下,获得字典序最小的回文字符串。

数据保证能在题目限制下形成回文字符串。

输入描述

一行,一个字符串。字符串中仅由小写英文字符构成。保证字符串不会是空字符串。

字符串长度介于[1,100000]之间。

输出描述

一行,一个在题目条件限制下所可以获得的字典序最小的回文字符串。

样例1输入

acca

样例1输出

aaaa

样例2输入

abcde

样例1输出

abcba

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    bool flag = true;
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            flag = false;
            break;
        }
    }
    if (flag) {