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

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

简单题 查找组成一个偶数最接近的两个素数

1. 定义一个函数 isPrime 来判断一个数是否为质数。
2. 在 main 函数中读取用户输入的整数 n。
3. 从 n/2 开始（保证了刚开始差值最小，逐步增大）向下遍历，寻找两个质数 i 和 n-i，使得它们的和等于 n。
4. 找到符合条件的两个质数后，输出它们并结束循环。

package main

import "fmt"

func isPrime(n int) bool {
	if n <= 1 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func main() {
	var n int
	fmt.Scan(&n)
	for i := n / 2; i >= 2; i-- {
		if isPrime(i) && isPrime(n-i) {
			fmt.Println(i)
			fmt.Println(n - i)
			break
		}
	}
}

中等题 最小循环节

因为题目说的是可以无限制的添加任意字符，最小循环节必由初始字符串原有的那些字符组成（因为如果我们再加入新的字符，会将循环节扩大），又要确保循环节覆盖到每一个已有字符，所以最小循环节的长度就等于已有字符串去重之后的长度。

package main

import (
	"fmt"
	"sort"
)

func main() {
	var s string
	fmt.Scan(&s)
	mp := make(map[rune]int)
	for _, c := range s {
		mp[c]++
	}
	ans := make([]rune, 0, len(mp))
	for k := range mp {
		ans = append(ans, k)
	}
	sort.Slice(ans, func(i, j int) bool {
		if mp[ans[i]] == mp[ans[j]] {
			return ans[i] < ans[j]
		}
		return mp[ans[i]] > mp[ans[j]]
	})
	fmt.Println(string(ans))
}

困难题 连续子数组最大和

1. 读取输入：从标准输入读取一个整数 n，表示数组的长度，然后读取 n 个整数，存储在数组 a 中。

2. 初始化动态规划数组：创建一个长度为 n 的数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最大连续子数组和。初始化 dp[0] 为 a[0]。

3. 动态规划递推：从 1 到 n-1 遍历数组，对于每个位置 i，可以选择：

   • 将当前数加入前面的子数组：dp[i-1] + a[i]

   • 重新开始一个子数组：a[i]

4. 求解结果：遍历 dp 数组，找到其中的最大值，即为所求的最大子数组和。

package main

import (
	"fmt"
	"math"
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	dp := make([]int, n)
	dp[0] = a[0]
	for i := 1; i < n; i++ {
		dp[i] = max(dp[i-1]+a[i], a[i])
	}
	ans := math.MinInt
	for i := 0; i < n; i++ {
		ans = max(ans, dp[i])
	}
	fmt.Println(ans)
}