牛客春招刷题训练营-2025.4.14题解
活动地址： 牛客春招刷题训练营 - 编程打卡活动
简单题 自守数
- 读入一个整数 n
- 遍历从 0 到 n 的每个数字 x
- 对于每个数字 x：
- 将 x 转换为字符串 sx
- 计算 x 的平方，并转换为字符串 sy
- 判断 sy 的末尾是否等于 sx（通过切片
sy[len(sy)-len(sx):]获取） - 如果相等，答案加 1
- 输出答案
package main
import (
"fmt"
"strconv"
)
func main() {
var n int
fmt.Scan(&n)
ans := 0
for x := 0; x <= n; x++ {
sx := strconv.Itoa(x)
sy := strconv.Itoa(x * x)
if sy[len(sy)-len(sx):] == sx {
ans++
}
}
fmt.Println(ans)
}
中等题 小红的双生串
- 将字符串 s 平分成两个等长子串 s1 和 s2
- 对于每个子串，找出出现次数最多的字符的频次
- 子串长度减去最大频次即为需要修改的最少字符数
- 两个子串需要修改的字符数之和即为答案
package main
import "fmt"
func main() {
var s string
fmt.Scan(&s)
s1, s2 := s[:len(s)/2], s[len(s)/2:]
f := func(str string) (ans int) {
m := make(map[rune]int)
for _, v := range str {
m[v]++
if m[v] > ans {
ans = m[v]
}
}
return
}
fmt.Println(len(s) - f(s1) - f(s2))
}
困难题 abb
-
使用前缀和思想，统计每个位置之后（包括当前位置）每个字母出现的次数：
- 建立二维数组
cnt[i][j]表示从位置 i 开始到末尾，字母 j 出现的次数 - 从后向前遍历，方便统计每个位置之后的字母出现次数
- 建立二维数组
-
遍历字符串的每个位置 i，对于每个字母 j：
- 如果等于当前位置的字母（aaa 型语句）不计数
- 如果不等于当前位置的字母，计算在位置 i 之后出现的字母 j 能形成的对数：
-
最终答案就是所有可能的字母对数之和
package main
import "fmt"
func main() {
var (
n int
s string
)
fmt.Scan(&n, &s)
cnt := make([][26]int64, n+1)
for i := n - 1; i >= 0; i-- {
for j := 0; j < 26; j++ {
cnt[i][j] = cnt[i+1][j]
}
cnt[i][s[i]-'a']++
}
ans := int64(0)
for i := 0; i < n; i++ {
for j := 0; j < 26; j++ {
if j == int(s[i]-'a') {
continue
}
ans += cnt[i+1][j] * (cnt[i+1][j] - 1) / 2
}
}
fmt.Println(ans)
}
牛客春招刷题训练营 文章被收录于专栏
爱丽姐真是太好了
滴滴公司福利 876人发布