牛客春招刷题训练营-2025.3.17题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 数字颠倒

1. 定义一个字符串变量 s 来存储输入的字符串。
2. 使用 fmt.Scan(&s) 从标准输入读取字符串并存储到变量 s 中。
3. 使用一个 for 循环从字符串的最后一个字符开始遍历，直到第一个字符。
4. 在循环中使用 fmt.Printf("%c", s[i]) 输出每个字符。

package main

import "fmt"

func main() {
	var s string
	for {
		n, _ := fmt.Scan(&s)
		if n == 0 {
			break
		}
	}
	fmt.Println(len(s))
}

中等题 密码截取

题意：最长回文子串

方案一：动态规划

dp[i][j]：字符串 s 的第 i 个字符到第 j 个字符是否为回文子串（不是为0，是为它的长度 j-i） dp[i][j] 是回文子串的条件为 s[i] == s[j]，且 dp[i+1][j-1] 回文

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	n := len(s)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = 1
		if i < n-1 && s[i] == s[i+1] {
			dp[i][i+1] = 1
		}
	}

	for l := 3; l <= n; l++ { // 长度
		for i := 0; i+l-1 < n; i++ { // 起点
			j := i + l - 1 // 终点
			if s[i] == s[j] && dp[i+1][j-1] > 0 {
				dp[i][j] = l
			}
		}
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			if dp[i][j] > ans {
				ans = dp[i][j]
			}
		}
	}
	fmt.Println(ans)
}

方案二：马拉车算法（Manacher）

算法讲解：https://oi-wiki.org/string/manacher/

mx 表示某个回文串延伸在最右端半径的下标 id 表示这个回文子串最中间位置下标 reslen 表示对应在s中的最大子回文串的半径 rescenter 表示最大子回文串的中间位置

package main

import "fmt"

func Manacher(s string) int {
	str := "@#"
	for i := 0; i < len(s); i++ {
		str += string(s[i]) + "#"
	}

	p := make([]int, len(str))
	mx, id, resLen := 0, 0, 0

	for i := 1; i < len(str); i++ {
		if mx > i {
			p[i] = min(p[2*id-i], mx-i)
		} else {
			p[i] = 1
		}

		for i+p[i] < len(str) && i-p[i] >= 0 && str[i+p[i]] == str[i-p[i]] {
			p[i]++
		}

		if i+p[i] > mx {
			mx = i + p[i]
			id = i
		}

		if resLen < p[i] {
			resLen = p[i]
		}
	}

	return resLen - 1
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var s string
	fmt.Scan(&s)
	fmt.Println(Manacher(s))
}

困难题 计算字符串的编辑距离

dp[i][j]：将 s1[1:i] 变成 s2[1:j] 的最小操作次数

• 删除一个字符：dp[i-1][j]+1
• 插入一个字符：dp[i][j-1]+1
• 将一个字符替换成另一个字符：
  • a[i] == b[j]：dp[i-1][j-1]
  • a[i] != b[j]：dp[i-1][j-1]+1

package main

import "fmt"

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var s1, s2 string
	fmt.Scan(&s1, &s2)
	n := len(s1)
	m := len(s2)

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m+1)
		for j := range dp[i] {
			dp[i][j] = 1e9
		}
	}

	s1 = " " + s1
	s2 = " " + s2
	dp[0][0] = 0

	for j := 1; j <= m; j++ {
		dp[0][j] = j
	}
	for i := 1; i <= n; i++ {
		dp[i][0] = i
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			replace := dp[i-1][j-1]
			if s1[i] != s2[j] {
				replace++
			}
			dp[i][j] = min(replace, min(dp[i-1][j]+1, dp[i][j-1]+1))
		}
	}

	fmt.Println(dp[n][m])
}