美团笔试 美团实习 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，请你帮助小团计算出最优规划，使他能获得最多的金币,输出能获得的最多金币数量即可。
注意:要求保证小团任意时刻金币数量不小于零。
输入描述
第一行是三个用空格隔开的整数n,m和k，表示网格地图的行数为n，列数为m，在不同颜色的两个格子间移动需要支付k个金币。
接下来n行，每行是一个长度为m的字符串，字符串仅包含字符'R'或'B'。第i行字符串的第j个字符表示地图上第i行第j列的格子颜色。如果字符为'R'，则表示格子颜色为红色，为'B'表示格子颜色为蓝色。
接下来是一个n行m列的非负整数矩阵，第i行第j列的数字表示地图上第i行第j列的格子上的金币数量。保证所有数据中数字大小都是介于[0,10]的整数。
1<=n, m <= 200, 1 <= k <= 5。
输出描述
一个正整数，表示能获得最多金币的数量。
示例输入
3 3 2
BBB
RBR
RBR
0 2 3
2 4 1
3 2 2
示例输出
8
说明：第一个使用原价卖，第二个物品使用原价买，第三个物品使用半价买，不买第四个物品，这样是最优的。
请注意，如果第二个物品使用了半价，那么第三个物品则不能使用半价。
参考题解
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> colors(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> colors[i][j];
}
}
vector<vector<int>> coins(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> coins[i][j];
}
}
vector<vector<int>> dp(n, vector<int>(m, 0));
for (int i = 1; i < n; i++) {
if (colors[i][0] == colors[i - 1][0]) {
dp[i][0] = coins[i][0] + dp[i - 1][0];
} else {
if (dp[i - 1][0] < k) break;
dp[i][0] = dp[i - 1][0] - k + coins[i][0];
}
}
for (int j = 1; j < m; j++) {
if (colors[0][j] == colors[0][j - 1]) {
dp[0][j] = coins[0][j] + dp[0][j - 1];
} else {
if (dp[0][j - 1] < k) break;
dp[0][j] = dp[0][j - 1] - k + coins[0][j];
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (colors[i][j] == colors[i - 1][j]) {
dp[i][j] = dp[i - 1][j] + coins[i][j];
} else {
if (dp[i - 1][j] >= k) {
dp[i][j] = dp[i - 1][j] - k + coins[i][j];
}
}
if (colors[i][j] == colors[i][j - 1]) {
dp[i][j] = max(dp[i][j], dp[i][j - 1] + coins[i][j]);
} else {
if (dp[i][j - 1] >= k) {
dp[i][j] = max(dp[i][j], dp[i][j - 1] - k + coins[i][j]);
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans = max(ans, dp[i][j]);
}
}
cout << ans << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
sc.nextLine();
char[][] colors = new char[n][m];
for (int i = 0; i < n; i++) {
colors[i] = sc.nextLine().toCharArray();
}
int[][] coins = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
coins[i][j] = sc.nextInt();
}
}
int[][] dp = new int[n][m];
for (int i = 1; i < n; i++) {
if (colors[i][0] == colors[i - 1][0]) {
dp[i][0] = coins[i][0] + dp[i - 1][0];
} else {
if (dp[i - 1][0] < k) break;
dp[i][0] = dp[i - 1][0] - k + coins[i][0];
}
}
for (int j = 1; j < m; j++) {
if (colors[0][j] == colors[0][j - 1]) {
dp[0][j] = coins[0][j] + dp[0][j - 1];
} else {
if (dp[0][j - 1] < k) break;
dp[0][j] = dp[0][j - 1] - k + coins[0][j];
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (colors[i][j] == colors[i - 1][j]) {
dp[i][j] = dp[i - 1][j] + coins[i][j];
} else {
if (dp[i - 1][j] >= k) {
dp[i][j] = dp[i - 1][j] - k + coins[i][j];
}
}
if (colors[i][j] == colors[i][j - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + coins[i][j]);
} else {
if (dp[i][j - 1] >= k) {
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] - k + coins[i][j]);
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans = Math.max(ans, dp[i][j]);
}
}
System.out.println(ans);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
n,m,k = map(int, input().split(" "))
colors = []
for i in range(n):
colors.append([c for c in input()])
coins = []
for i in range(n):
coins.append([int(c) for c in input().split(" ")])
dp = [[0 for _ in range(m)] for _ in range(n)]
for i in range(1, n):
if colors[i][0] == colors[i - 1][0]:
dp[i][0] = coins[i][0] + dp[i - 1][0]
else:
if dp[i - 1][0] < k: break
dp[i][0] = dp[i-1][0] - k + coins[i][0]
for j in range(1, m):
if colors[0][j] == colors[0][j-1]:
dp[0][j] = coins[0][j] + dp[0][j-1]
else:
if dp[0][j-1] < k: break
dp[0][j] = dp[0][j-1] - k + coins[0][k]
for i in range(1, n):
for j in range(1, m):
if colors[i][j] == colors[i-1][j]:
dp[i][j] = dp[i-1][j] + coins[i][j]
else:
if dp[i-1][j] >= k:
dp[i][j] = dp[i-1][j]-k + coins[i][j]
if colors[i][j] == colors[i][j-1]:
dp[i][j] = max(dp[i][j], dp[i][j-1] + coins[i][j])
else:
if dp[i][j-1] >= k:
dp[i][j] = max(dp[i][j], dp[i][j-1]-k+coins[i][j])
ans = 0
for i in range(n):
ans = max(ans, max(dp[i]))
print(ans)
第四题
题目：坦克大战
小D和小W最近在玩坦克大战,双方操控自己的坦克在16*16的方格图上战斗,小D的坦克初始位置在地图的左上角,朝向为右,其坐标(0,0),小W的坦克初始位置在地图右下角，朝向为左，坐标为(15,15)。坦克不能移动到地图外，天坦克会占领自己所在的格子，己方坦克不可以进入对方占领过的格子。每一个回合双方必须对自己的坦克下达以下五种指令中的一种：
- 移动指令U：回合结束后，使已方坦克朝向为上，若上方的格子未被对方占领，则向当前朝向移动一个单位(横坐标-1)，否则保持不动;
- 移动指令D：回合结束后，使己方坦克朝向为下，若下方的格子未被对方占领，则向当前朝向移动一个单位(横坐标+1)，否则保持不动;
- 移动指令L：回合结束后，使己方坦克朝向为左，若左侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标-1)，否则保持不动;
- 移动指令R：回合结束后，使己方坦克朝向为右，若右侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标+1)，否则保特不动;
- 开火指令F：已方坦克在当前回合立即向当前朝向开火；
己方坦克开火后，当前回合己方坦克的正前方若有对方的坦克，对方的坦克将被摧毁，游戏结束，己方获得胜利；
若双方的坦克在同一回合被摧毁，游戏结束，判定为平局；若双方的坦克在同一回合内进入到同一个未被占领的格子，则双方的坦克发生碰撞，游戏结束，判定为平局；当游戏进行到第256个回合后，游戏结束，若双方坦克均未被摧毁,则占领格子数多的一方获得胜利，若双方占领的格子数一样多，判定为平局。*注意，若一方开火，另一方移动，则认为是先开火，后移动。
现在小D和小W各自给出一串长度为256的指令字符串，请你帮助他们计算出游戏将在多少个回合后结束,以及游戏的结果。
示例输入
DDDDDDDRF
UUUUUUUUU
示例输出
9 D
说明：第一个使用原价卖，第二个物品使用原价买，第三个物品使用半价买，不买第四个物品，这样是最优的。
请注意，如果第二个物品使用了半价，那么第三个物品则不能使用半价。
参考题解
直接模拟即可
Python：[此代码未进行大量数据的测试，仅供参考]
nstru1 = input()
instru2 = input()
grid = [[0 for _ in range(16)] for _ in range(16)] # 1小D占领 2小W占领
grid[0][0] = 1
grid[-1][-1] = 2
poss = [[], [0,0], [15,15]]
dirs = {'U':[-1,0], 'D':[1,0], 'L':[0,-1], 'R':[0,1]}
ds= [[],[0,1],[0,-1]] #初始方向
cnts = [0, 1, 1] #占领数量
'''移动指令 instruc指令， pos位置 w 1小D，2小W'''
def move(instruc, w):
pos = poss[w]
dir = dirs[instruc]
ds[w] = dir
if grid[pos[0]][pos[1]] == 0 or grid[pos[0]][pos[1]] == w:
pos[0]+= dir[0]
pos[1] += dir[1]
if grid[pos[0]][pos[1]] == 0:
grid[pos[0]][pos[1]] = w
cnts[w] += 1
'''开火指令'''
def fire(w, ot):
if ds[w][0] == 0 and ds[w][1] == 1 :
#右边开火，检查是否在右边即可。
return poss[ot][1] > poss[w][1]
if ds[w][0] == 0 and ds[w][1] == -1:
return poss[ot][1] < poss[w][1]
if ds[w][0] == 1 and ds[w][1] == 0:
return poss[ot][0] > poss[w][0]
if ds[w][0] == -1 and ds[w][1] == 0:
return poss[ot][0] < poss[w][0]
def main():
for i in range(len(instru1)):
i1, i2 = instru1[i], instru2[i]
if i1 == 'F' and i2 == 'F' and fire(1, 2) and fire(2, 1):
print(i + 1, end=" ")
print("平局")
return
if i1 == 'F':
if fire(1, 2):
print(i + 1, end=" ")
print("D")
return
if i2 == 'F':
if fire(2, 1):
print(i + 1, end=" ")
print('W')
return
if i1 != 'F' and i2 != 'F':
move(i1, 1)
move(i2, 2)
if poss[1][0] == poss[2][0] and poss[1][1] == poss[2][1]:
print(i + 1, end=" ")
print("平局")
return
if cnts[1] == cnts[2]:
print(256, end=" ")
print("平局")
return
if cnts[1] > cnts[2]:
print(256, end=" ")
print("D")
return
if cnts[1] < cnts[2]:
print(256, end=" ")
print("W")
return
if __name__ == '__main__':
main()
#美团笔试##美团实习#
投递京东等公司10个岗位
