美团2024届暑期实习第一轮后端笔试详解-六虎

这是美团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(nlog⁡n)O(n\log n)$ ，其间 $n$ 是流星的数量。咱们需求对一切流星的呈现和消失时刻进行排序，时刻杂乱度为 $O(nlog⁡n)O(n\log n)$ 。接下来，咱们遍历这些事情，时刻杂乱度为 $O (n)$ 。因此，总时刻杂乱度为 $O(nlog⁡n)O(n\log 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
}

本文正在参加「金石方案」

美团2024届暑期实习第一轮后端笔试详解

Coding 一

Coding 二

Coding 三

Coding 四

Coding 五

相关文章

Spring Security + JWT + Swagger2 登录验证小结

AI – stable-diffusion(AI绘画)的搭建与使用

提升运维效率三倍以上 深度揭秘蚂蚁业务智能可观测平台

公司应该如何招人？

作者信息

提升运维效率三倍以上深度揭秘蚂蚁业务智能可观测平台