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

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

简单题 23年OPPO-a的翻转

这道题目是一个简单的数字翻转求和问题。

首先读取一个整数 a
将整数转为字符串，然后翻转，再转回整数得到 b
最后输出 a + b

代码中的关键部分是 ReverseString 函数，它通过以下步骤实现字符串翻转：

将字符串转换为 rune 切片，这样可以正确处理字符
使用双指针法，从两端向中间遍历，交换对应位置的字符
最后将 rune 切片转回字符串

runes[i], runes[j] = runes[j], runes[i] 实现了两个字符的交换。

package main

import (
	"fmt"
	"strconv"
)

func ReverseString(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func main() {
	var a int
	fmt.Scan(&a)
	b, _ := strconv.Atoi(ReverseString(strconv.Itoa(a)))
	fmt.Println(a + b)
}

中等题斐波那契数列

和昨天的跳台阶做法完全一致

我们可以根据 f(n) = f(n-1) + f(n-2) 优化这个递推公式的空间

使用两个变量 a 和 b 来保存当前状态和前一个状态
通过循环来累积计算每一步的结果
使用并行赋值来优化空间复杂度

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a, b := 1, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	fmt.Println(a)
}

困难题括号区间匹配

状态定义：

dp[i][j] 表示将区间 [i,j] 的子串分割成有效括号序列所需的最小分割数

初始化：

当 i==j 时，单个字符需要1个分割
其他情况初始化为最大值n（最差情况每个字符都需要单独分割）

状态转移：有两种情况需要考虑：

如果 s[i] 和 s[j] 能配对（即是匹配的括号对），则可以直接继承 dp[i+1][j-1] 的值
考虑在区间 [i,j] 中的任意位置k进行分割，取所有可能的 dp[i][k] + dp[k+1][j] 的最小值

匹配函数：

match 函数用于判断两个括号是否匹配
支持圆括号 () 和方括号 [] 的匹配

最终答案：

dp[0][n-1] 就是整个字符串需要的最小分割数

package main

import "fmt"

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

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)
		for j := i; j < n; j++ {
			if i == j {
				dp[i][j] = 1
			} else {
				dp[i][j] = n
			}
		}
	}

	match := func(a, b byte) bool {
		if a == '(' && b == ')' {
			return true
		}
		if a == '[' && b == ']' {
			return true
		}
		return false
	}

	for l := 2; l <= n; l++ {
		for i := 0; i < n-l+1; i++ {
			j := i + l - 1
			if match(s[i], s[j]) {
				dp[i][j] = dp[i+1][j-1]
			}
			for k := i; k < j; k++ {
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
			}
		}
	}
	fmt.Println(dp[0][n-1])
}

#牛客春招刷题训练营#

牛客春招刷题训练营文章被收录于专栏

爱丽姐真是太好了