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

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

简单题 小红的顺子

1. 初始化变量：
   • 定义两个变量： 表示当前顺子的长度 l， 表示最长顺子的长度 ans。
   • 初始值： l = 1, ans = 1（因为单个元素本身可以看作长度为 1 的顺子）。
2. 遍历数组：
   • 遍历数组中的每个元素 （从第 2 个元素开始，因为需要比较前一个元素）。
   • 如果当前元素与前一个元素满足 ，说明当前顺子可以继续延伸，将 l 增加 1。
   • 如果不满足 ，说明当前顺子中断了，此时更新 ans 为当前的最大长度，并重置 l 为 1。
3. 结束时检查：
   • 遍历结束后，需要再次检查当前顺子的长度是否大于 ans，以确保最后一个顺子也被正确统计。
4. 输出结果：
   • 输出 ans，即最长顺子的长度。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	a[0] = -1
	l, ans := 1, 1
	for i := 1; i < n; i++ {
		fmt.Scan(&a[i])
		if a[i]-a[i-1] == 1 {
			l++
		} else {
			if l > ans {
				ans = l
			}
			l = 1
		}
	}
	if l > ans {
		ans = l
	}
	fmt.Println(ans)
}

中等题 小红的字符生成

通过观察可以发现：

1. 字符 'a' 本身不需要任何操作，直接贡献 1 个 'a'。
2. 字符 'b' 可以通过一次操作生成 2 个 'a'。
3. 字符 'c' 可以通过两次操作生成 个 'a'。
4. 字符 'd' 可以通过三次操作生成 个 'a'。
5. 以此类推，字符 'z' 可以通过 25 次操作生成 个 'a'。

为了使初始字符串的长度最短，我们可以采用贪心策略：

1. 优先选择贡献最大的字符：从 'z' 开始，依次尝试加入字符到初始字符串中。
2. 逐步减少目标数量 x：每次选择一个字符时，将其贡献从 x 中减去。
3. 重复上述过程，直到 x=0。

package main

import "fmt"

func main() {
	var x int
	fmt.Scan(&x)
	var s []byte
	for x > 0 {
		for i := 25; i >= 0; i-- {
			if 1<<i <= x {
				s = append(s, byte('a'+i))
				x -= 1 << i
				break
			}
		}
	}
	fmt.Println(string(s))
}

困难题 最少的完全平方数

动态规划数组定义：

• 我们定义一个数组 dp，其中 dp[i] 表示构成整数 i 所需的最少的完全平方数的数量。
• 初始状态：dp[0] = 0，因为0不需要任何完全平方数来表示。

状态转移方程：

对于每一个整数 i（1 <= i <= n），我们需要检查所有小于等于 i 的完全平方数 j*j。如果使用了这个完全平方数 j*j，那么剩下的部分就是 i - j*j，我们已经计算过它所需的最少完全平方数数量 dp[i-j*j]。因此，状态转移方程为：

dp[i] = min(dp[i], dp[i-j*j]+1)

这里 dp[i-j*j]+1 表示的是用了一个完全平方数 j*j 后，再加上构成剩余部分 i-j*j 所需的最少完全平方数数量。

初始化：

对于每个 i，在开始内部循环之前，我们可以先假设每个 i 都由 i 个1构成，即 dp[i] = i。这是因为最坏情况下，我们可以使用 i 个1来表示 i。

package main

import "fmt"

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

func main() {
	var n int
	fmt.Scan(&n)
	dp := make([]int, n+1)
	dp[0] = 0
	for i := 1; i <= n; i++ {
		dp[i] = i
		for j := 1; j*j <= i; j++ {
			dp[i] = min(dp[i], dp[i-j*j]+1)
		}
	}
	fmt.Println(dp[n])
}