2023美团春招实习笔试算法题解析_美团 算法 笔试

来源：投稿 作者：LSC
编辑：学姐

第一题：小美的字符串

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

例如，对于字符串”111222333”，她可以进行3次修改将其变为”121212313"。

输入描述
一行， 一个字符串s，保证s只包含数字字符。 1 <= |s| <= 100000

输出描述
一行，一个整数，表示修改的最少次数。

示例1
输入 111222333
输出 3
 

示例2
输入 11551111
输出 4

思路和代码

【此代码未通过大量数据的测试，仅供参考，有疑问欢迎讨论】

直接模拟即可。遇到一个字符与前一个字符相同则变换，但是注意不要变成与后一个字符相同

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()]))

第二题：流星

时间限制:3000MS
内存限制:589824KB

题目描述:

小美是一位天文爱好者，她收集了接下来一段时间中所有会划过她所在的观测地上空的流星信息。具体地,她收集了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表示可供她选择的最佳时刻数量。

示例1
输入 3
2 1 5
6 3 7
输出 2 4

思路与代码

此代码未通过大量数据的测试，仅供参考，有疑问欢迎讨论】

我们将区间inteval[l,r]拆分成 p[l,1] p[r,2] 这样的点，然后把所有的点排序。

如果遇到的p[1] == 1的话就说明进入了一个新区间，此时覆盖的次数 + 1，

如果p[1]==2的话说明走出了一个区间，此时覆盖点 - 1。

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)

第三题：最佳规划

时间限制:3000MS
内存限制:589824KB

题目描述:
小团在一个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。

输出描述
一个正整数，表示能获得最多金币的数量。

示例1
输入
3 3 2
BBB
RBR
RBR
0 2 3
2 4 1
3 2 2
输出 8

思路与代码

【此代码未通过大量数据的测试，仅供参考，有疑问欢迎讨论】 经典的DP思路。

dp[i,j]表示走到[i,j]可以获取的最多金币数。

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)

第四题：坦克大战

时间限制:3000MS
内存限制:589824KB

题目描述:
小D和小W最近在玩坦克大战,双方操控自己的坦克在16*16的方格图上战斗,小D的坦克初始位置在地图的左上角,朝向为右,其坐标(0,0),小W的坦克初始位置在地图右下角，朝向为左，坐标为(15,15)。坦克不能移动到地图外，天坦克会占领自己所在的格子，己方坦克不可以进入对方占领过的格子。每一个回合双方必须对自己的坦克下达以下五种指令中的一种：

• 移动指令U：回合结束后，使已方坦克朝向为上，若上方的格子未被对方占领，则向当前朝向移动一个单位(横坐标-1)，否则保持不动;
• 移动指令D：回合结束后，使己方坦克朝向为下，若下方的格子未被对方占领，则向当前朝向移动一个单位(横坐标+1)，否则保持不动;
• 移动指令L：回合结束后，使己方坦克朝向为左，若左侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标-1)，否则保持不动;
• 移动指令R：回合结束后，使己方坦克朝向为右，若右侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标+1)，否则保特不动;
• 开火指令F：已方坦克在当前回合立即向当前朝向开火； 己方坦克开火后，当前回合己方坦克的正前方若有对方的坦克，对方的坦克将被摧毁，游戏结束，己方获得胜利；

若双方的坦克在同一回合被摧毁，游戏结束，判定为平局；若双方的坦克在同一回合内进入到同一个未被占领的格子，则双方的坦克发生碰撞，游戏结束，判定为平局；当游戏进行到第256个回合后，游戏结束，若双方坦克均未被摧毁,则占领格子数多的一方获得胜利，若双方占领的格子数一样多，判定为平局。*注意，若一方开火，另一方移动，则认为是先开火，后移动。

现在小D和小W各自给出一串长度为256的指令字符串，请你帮助他们计算出游戏将在多少个回合后结束,以及游戏的结果。

示例1
输入
DDDDDDDRF
UUUUUUUUU
输出 9 D

思路和代码

【此代码未通过大量数据的测试，仅供参考，有疑问欢迎讨论】 没什么可说的，模拟题，尽量设计好结构。【这种题遇到对于大部分同学来说是要放弃的，因为没时间写】

instru1 = 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()

关注下方《学姐带你玩AI》