这是美团2024届暑期实习后端岗位的第一轮笔试，总共有五道编程题，四道 情景算法题，一道 二叉树题目，时长两个小时，我用的是go语言，只AC了前两道，第三道死活通不过，第四道模拟情况太复杂，放弃了，第五道马上写完，可惜没时间了，还是得合理分配时间才行，哭死！！！
Coding 一
题目描述:
小美有一个由数字字符组成的字符串。现在她想对这个字符串进行一些修改。 具体地，她可以将文个字符串中任意位置字符修改为任意的数字字符。她想知道，至少进行多少次修改，可以使得“修改后的字符串不包含两个连续相同的字符?
例如，对于字符串”111222333", 她可以进行3次修改将其变为” 121212313"。
输入描述
一行，一个字符串s，保证s只包含数字字符。1<=|s|<= 100000
输出描述
一行，一个整数，表示修改的最少次数。
思路：
本题可以使用回溯，也可以使用动态规划解决，下面是动规的两种解决方法
func main() { var s string fmt.Scan(&s) length := len(s) dp := make([][10]int, length+1) for i := 1; i <= length; i++ { for j := 0; j < 10; j++ { dp[i][j] = length } for j := 0; j < 10; j++ { if int(s[i-1]) == '0'+j { for k := 0; k < 10; k++ { if j != k { dp[i][j] = min(dp[i][j], dp[i-1][k]) } } } else { for k := 0; k < 10; k++ { if j != k { dp[i][j] = min(dp[i][j], dp[i-1][k]+1) } } } } } res := length for i := 0; i < 10; i++ { res = min(res, dp[length][i]) } fmt.Println(res) } func main1() { scanner := bufio.NewScanner(os.Stdin) scanner.Scan() s := scanner.Text() n := len(s) dp := make([][2]int, n) // dp[i][0]表示s[i]不变的最小修改次数，dp[i][1]表示s[i]改为另一个数字的最小修改次数 for i := 0; i < n; i++ { if i == 0 { dp[i][0] = 0 dp[i][1] = 1 } else { if s[i] == s[i-1] { dp[i][0] = dp[i-1][1] // s[i]不变，必须将s[i-1]改为另一个数字 dp[i][1] = dp[i-1][0] + 1 // s[i]改为另一个数字，s[i-1]可以不变或改为另一个数字 } else { dp[i][0] = dp[i-1][0] // s[i]不变，s[i-1]不变或改为另一个数字都可以 dp[i][1] = dp[i-1][1] + 1 // s[i]改为另一个数字，s[i-1]不变或改为另一个数字都可以 } } } fmt.Println(min(dp[n-1][0], dp[n-1][1])) } func min(a, b int) int { if a > b { return b } return a }
Coding 二
题目描述:
小团在一个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列的数字表示地图上第行第j列的格子上的金币数量。保证所有数据中数字大小都是介于[0, 10]的整数。
1<=n,m<=200, 1<=k<=5。
输出描述
一行 一个整数， 表示小团能获得的最多 金币数量。
func main() { scanner := bufio.NewScanner(os.Stdin) scanner.Scan() line := strings.Split(scanner.Text(), " ") n, _ := strconv.Atoi(line[0]) m, _ := strconv.Atoi(line[1]) k, _ := strconv.Atoi(line[2]) grid := make([][]rune, n) for i := 0; i < n; i++ { scanner.Scan() grid[i] = []rune(scanner.Text()) } coins := make([][]int, n) for i := 0; i < n; i++ { coins[i] = make([]int, m) scanner.Scan() for j, v := range strings.Split(scanner.Text(), " ") { coins[i][j], _ = strconv.Atoi(v) } } // 初始化dp dp := make([][]int, n) for i := 0; i < n; i++ { dp[i] = make([]int, m) for j := 0; j < m; j++ { dp[i][j] = -1 } } dp[0][0] = 0 for i := 0; i < n; i++ { for j := 0; j < m; j++ { if dp[i][j] == -1 { continue } //右 if j+1 < m { c := 0 if grid[i][j] != grid[i][j+1] { c = k } dp[i][j+1] = max(dp[i][j+1], dp[i][j]+coins[i][j+1]-c) } //下 if i+1 < n { c := 0 if grid[i][j] != grid[i+1][j] { c = k } dp[i+1][j] = max(dp[i+1][j], dp[i][j]+coins[i+1][j]-c) } } } fmt.Println(dp[n-1][m-1]) } func max(a, b int) int { if a > b { return a } return b }
Coding 三
题目描述:
小美是位天文爱好者， 她收集了接下来段时间中所有 会划过她所在的观测地上空的流星信息。具体地，她收集了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表示可供她选择的最佳时刻数量。
算法思路：
首先，我们将每个流星的出现和消失时间转换为一系列时间事件，每个事件包括时间点和流星数量变化。然后，按时间点对这些事件进行排序。接下来，我们从左到右遍历这些事件，并统计当前观测地上空的流星数量。在遍历过程中，我们记录最大的流星数量以及达到最大数量的时间点个数。最终，输出最大数量和时间点个数即可。
时间复杂度：O ( n log n ) O(n\log n)O(nlogn)，其中 n nn 是流星的数量。我们需要对所有流星的出现和消失时间进行排序，时间复杂度为 O ( n log n ) O(n\log n)O(nlogn)。接下来，我们遍历这些事件，时间复杂度为 O ( n ) O(n)O(n)。因此，总时间复杂度为 O ( n log n ) O(n\log n)O(nlogn)。
空间复杂度：O ( n ) O(n)O(n)，我们需要保存每个流星的出现和消失时间，以及每个时间点的流星数量变化。
func main() { scanner := bufio.NewScanner(os.Stdin) // 读取流星数量 scanner.Scan() n := toInt(scanner.Bytes()) // 读取每个流星的出现和消失时间 starts := make([]int, n) ends := make([]int, n) for i := 0; i < n; i++ { scanner.Scan() starts[i] = toInt(scanner.Bytes()) } for i := 0; i < n; i++ { scanner.Scan() ends[i] = toInt(scanner.Bytes()) } // 将每个时间点的流星数量统计出来 events := make([][2]int, 2*n) for i := 0; i < n; i++ { events[2*i][0] = starts[i] events[2*i][1] = 1 events[2*i+1][0] = ends[i] + 1 events[2*i+1][1] = -1 } sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] }) // 找出最佳时刻 maxCount := 0 bestTimes := 0 count := 0 for i := 0; i < len(events); i++ { count += events[i][1] if count > maxCount { maxCount = count bestTimes = 1 } else if count == maxCount { bestTimes++ } } fmt.Printf("%d %d\n", maxCount, bestTimes) } func toInt(b []byte) int { n := 0 for _, c := range b { n = n*10 + int(c-'0') } return n }
Coding 四
题目描述:
小D和小W最近在玩坦克大战，双方操控自己的坦克在16*1 6的方格图上战斗，小D的坦克初始位置在地图的左上角，朝向为右，其坐标(0,0)， 小W的坦克初始位置在地图右下角，朝向为左，坐标为(15,15)。坦克不能移动到地图外，坦克会占领自己所在的格子，己方的坦克不可以进入对方占领过的格子。每一个回合双方必须对自己的坦克下达以下5种指令中的一种:
.移动指令U:回合结束后，使己方坦克朝向为上，若上方的格子未被对方占领，则向当前朝向移动一个单位(横坐标-1)，否则保持不动;
.移动指令D:回合结束后，使己方坦克朝向为下，若下方的格子未被对方占领，则向当前朝向移动一个单位(横坐标+1)，否则保持不动，
.移动指令L:回合结束后，使己方坦克朝向为左,若左侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标-1) ,否则保持不动;
.移动指令R:回合结束后，使己方坦克朝向为右，若右侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标+1)，否则保持不动;
. 开火指令F:己方坦克在当前回合立即向当前朝向开火;
己方坦克开火后，当前回合己方坦克的正前方若有对方的坦克，对方的坦克将被摧毁，游戏结束，己方获得胜利;若双方的坦克在同一-回合被摧毁，游戏结束，判定为平局;若双方的坦克在同一回合内进入到同一个未被占领的格子，则双方的坦克发生碰撞，游戏结束，判定为平局;当游戏进行到第256个回合后，游戏结束，若双方坦克均未被摧毁，则占领格子数多的一方获得胜利，若双方占领的格子数一样多，判定为平局。*注意， 若-方开火， 另-方移动，则认为是先开火，后移动。
现在小D和小W各自给出一串长度为256的指令字符串， 请你帮助他们计算出游戏将在多少个回合后结束，以及游戏的结果。
输入描述
输入共两行，每行为一串长度为256的指令宁符串，字符串中只包含“U”，“D"，“L" “R”，“F"这五个字符。第一行表示小D的指令，第工行表示小W的指令。
输出描述
输出一共两行，第一行一个整数k，表示游戏将在k个回合后结束。第二行为游戏的结 果，若小D获胜则输出“D"，若小W获胜则输出“W”若平局则输出“P”
思路：
本题模拟坦克即可，考虑的情况挺多的，当时没AC出来，后来也懒得做了
Coding 五
题目描述:
给一棵有n个点的有根树，点的编号为1到n，根为1。每个点的颜色是红色或者蓝色。对于树上的一个点，如果其子树中(不包括该点本身)红色点和蓝色点的数量相同，那么我们称该点是平衡的。
请你计算给定的树中有多少个点是平衡点。
输入描述
第一行是一个正整数n，表示有n个点。
接下来行一个长度为n的字符串，仅包含字符R’和’B’， 第i个字符表示编号为的节点的颜色，字符为’R’ 表示红色，’ B’ 表示蓝色。
接下来一行n-1个用空格隔开的整数，第1个整数表示编号为i+ 1的点的父亲节点编号。1<=n<=10000
输出描述
一行一个整数，表示树上平衡点的个数。
思路：
根据题意，我们可以使用深度优先搜索（DFS）来遍历树的每个节点，并计算出每个节点子树中红色和蓝色节点的数量。
对于每个节点，我们可以将其子树中红色和蓝色节点的数量保存在节点的 cnt 属性中。同时，我们也需要记录该节点的父节点，以便在遍历子树时跳过父节点。
在DFS的过程中，我们可以计算出子树中红色和蓝色节点的数量，并根据节点自身的颜色计算出该节点子树中红色和蓝色节点的数量。然后我们将该节点的子节点作为新的起点进行DFS，直到遍历完整棵树。
对于每个节点，如果其子树中红色和蓝色节点的数量相同，那么它就是一个平衡点。
最后，我们可以将平衡点的数量相加，得到最终的结果。
type Node struct { color string cnt [2]int child []*Node } func dfs(node *Node, parent *Node, cntRed int, cntBlue int) int { node.cnt[0] = cntRed node.cnt[1] = cntBlue res := 0 for _, child := range node.child { if child == parent { continue } childCntRed := 0 childCntBlue := 0 if node.color == "R" { childCntRed = cntRed + 1 childCntBlue = cntBlue } else { childCntRed = cntRed childCntBlue = cntBlue + 1 } res += dfs(child, node, childCntRed, childCntBlue) } if node.cnt[0] == node.cnt[1] { res += 1 } return res } func main() { scanner := bufio.NewScanner(os.Stdin) // 读取输入 scanner.Scan() n := parseNum(scanner.Text()) scanner.Scan() colors := strings.Split(scanner.Text(), "") nodes := make([]*Node, n+1) for i := 1; i <= n; i++ { nodes[i] = &Node{ color: colors[i-1], cnt: [2]int{}, child: []*Node{}, } } for i := 2; i <= n; i++ { scanner.Scan() parentIndex := parseNum(scanner.Text()) nodes[parentIndex].child = append(nodes[parentIndex].child, nodes[i]) nodes[i].child = append(nodes[i].child, nodes[parentIndex]) } // DFS计算平衡点数量 res := dfs(nodes[1], nil, 0, 0) // 输出结果 fmt.Println(res) } func parseNum(s string) int { var res int for _, c := range s { res = res*10 + int(c-'0') } return res }
