百度2024届暑期实习后端算法题详解

这是百度2024届暑期实习后端岗位的第一轮笔试，总共有十五道单选题，五道多选题，三道编程题，选择题涉及数据库、计算机网络、操作系统、语言基础、补充代码、哈希算法、linux、数据结构、数学等等；时长两个小时，我用的是go语言，编程题前两题挺简单的，最后一题体感虽然很简短，其实很有深度。话不多说，开冲！

一 Coding1

题目描述

小红拿到了一个字符串，她想知道这个字符串能否通过重新排列 组成"Baidu"字符串?

注:必须大小写完全相同。

共有t组询问。

输入描述

第一行输入一个正整数t，代表询问次数。

接下来的t行，每行输入一个仅包含英文字母的字符串。

所有字符串的长度之和保证不超过200000。

输出描述

对于每次询问，输出一行答案。如果可以通过重新排列组成"Baidu",则输出"Yes"， 否则输出"No"。

解题思路

在主函数中，我们首先读取询问次数t。然后对于每个询问，我们读取一个字符串并调用Form函数来检查是否可以通过重新排列组成"Baidu"字符串。如果返回true，则输出"Yes"，否则输出"No"。

在Form函数中，我们使用一个Map：freq来统计输入字符串中每个字符出现的次数。然后检查是否有足够的字符可以组成"Baidu"。具体来说，我们将需要的字符存储在一个Map中，并遍历该Map，检查每个字符是否在Map中出现过。如果有任何一个字符没有出现，则说明无法组成"Baidu"，返回false。否则返回true。

详细代码

package main
​
import (
   "bufio"
   "fmt"
   "os"
   "strconv"
)
​
func main() {
   scanner := bufio.NewScanner(os.Stdin)
   scanner.Scan()
   t,_:=strconv.Atoi(scanner.Text())
   for i:=0;i<t;i++{
      scanner.Scan()
      s := scanner.Text()
      if Form(s){
         fmt.Println("Yes")
      }else {
         fmt.Println("No")
      }
   }
}
func Form(s string)bool{
   freq :=make(map[rune]int)
   for _,c := range s{
      freq[c]++
   }
   if freq['B']==1 && freq['a']==1 && freq['i']==1 && freq['d']==1 && freq['u']==1{
      return true
   }
   return false
}

二 Coding2

题目描述

给定一个整数x， 请你构造一个仅由了‘r’、'e'、'd'三种字符组成的 字符串，其中回文子串的数量恰好为x。

字符串的长度不得超过10的5次方。

输入描述

一个正整数x。

1<x<10的9次方

输出描述

输出一个仅由'r'、'e'、'd'三种字符组成的字符串，长度不得超过10的五次方。有多解时输出任意即可。

解题思路

首先，我们读入整数 x。

如果 x 等于 1，那么可以直接输出 "r"，因为 "r" 是一个回文字符串。

否则，我们需要构造一个由 "r"、"e"、"d" 三种字符组成的字符串，使得该字符串中恰好有 x 个回文子串。

我们可以观察到，由 "r"、"e"、"d" 三种字符组成的回文子串只有 "r"、"e"、"d"、"ee"、"rr"、"dd"、"redd"、"drrd" 和 "erede" 这九种。

假设我们需要构造 k 个回文子串，那么我们可以构造一个由 k/2 个 "redd" 和 (k+1)/2 个 "red" 组成的字符串，其中 "/" 表示整除符号。

例如，如果 x 等于 3，那么我们需要构造一个由三个回文子串组成的字符串，可以先计算出需要两个回文子串，然后构造一个由一个 "redd" 和一个 "red" 组成的字符串，即 "reddred"，然后去掉多余的字符，得到 "red"。

最后，我们可以通过 Go 标准库中的 strings.Repeat 函数来构造由 "redd" 组成的子串，然后通过字符串切片的方式去掉多余的字符，得到长度为 x 的字符串。

详细代码

package main
​
import (
    "fmt"
    "strings"
)
​
func main() {
    var x int
    fmt.Scan(&x)
    if x == 1 {
        fmt.Println("r")
        return
    }
    palindromeCount := (x + 1) / 2
    palindrome := strings.Repeat("red", palindromeCount)[:x]
    fmt.Println(palindrome)
}

三 Coding3

题目描述

小红拿到了棵树，每个节点被染成 了红色或者蓝色。

小红定义每条边的权值为:删除这条边时，形成的两个子树的同色连通块数量之差的绝对值。

小红想知道，所有边的权值之和是多少?

输入描述

第一行输入一个正整数n,代表节点的数量。

第二行输入一个长度为n且仅由'R"和B，两种字符组成的字符串。

第i个字符为'R"代表i号节点被染成红色，为'B'则被染成蓝色。

接下来的n-1行，每行输入两个正整数u和U，代表节点么和节 点U有一条边相连

1≤n≤200000

输出描述

一个正整数，代表所有节点的权值之和。

解题思路

代码思路：

定义一个 node 结构体，每个节点包括颜色和邻接表。

读入节点信息和颜色，构造邻接表。

采用 DFS 的方式遍历整个树，对于每个节点，分别统计其子树中红色节点和蓝色节点的数量，最终求出所有节点的权值之和。

具体地，对于每个节点 u，先将其本身的颜色统计一下，再遍历其邻接表，如果邻接点 v 不是 u 的父节点，则递归遍历以 v 为根的子树，并将其子树中红色节点和蓝色节点的数量累加到 u 节点的计数器 red[u] 和 blue[u] 上，最后将 red[u] 和 blue[u] 的差的绝对值累加到答案中即可。

最终输出所有节点的权值之和。

详细代码

package main
​
import (
   "bufio"
   "fmt"
   "os"
)
​
type node struct {
   color byte
   edges []int
}
func abs(x int) int {
   if x < 0 {
      return -x
   }
   return x
}
​
func dfs(u int, parent int, nodes []node, red, blue []int, ans *int) {
   if nodes[u].color == 'R' {
      red[u]++
   } else {
      blue[u]++
   }
   for _, v := range nodes[u].edges {
      if v != parent {
         dfs(v, u, nodes, red, blue, ans)
         red[u] += red[v]
         blue[u] += blue[v]
      }
   }
   *ans += abs(red[u] - blue[u])
}
​
func main() {
   var n int
   fmt.Scanln(&n)
​
   nodes := make([]node, n)
   colors := make([]byte, n)
   for i := 0; i < n; i++ {
      fmt.Scanf("%c", &colors[i])
      nodes[i].color = colors[i]
   }
   scanner := bufio.NewScanner(os.Stdin)
   scanner.Split(bufio.ScanWords)
   for i := 0; i < n-1; i++ {
      var u, v int
      scanner.Scan()
      fmt.Sscan(scanner.Text(), &u)
      scanner.Scan()
      fmt.Sscan(scanner.Text(), &v)
      u--
      v--
      nodes[u].edges = append(nodes[u].edges, v)
      nodes[v].edges = append(nodes[v].edges, u)
   }
​
   red := make([]int, n)
   blue := make([]int, n)
   ans := 0
   dfs(0, -1, nodes, red, blue, &ans)
   fmt.Println(ans)
}

测试：

输入：

4

BBRR

1 2

3 2

4 1

输出

2