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

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

简单题 小红的多彩糖葫芦

1. 输入处理：

   • 读取一个字符串 s，每个字符代表一个糖葫芦的颜色

2. 核心算法：

   • 从第一个糖葫芦开始遍历 (i 从 0 开始)
   • 对于每个位置 i，检查当前糖葫芦的颜色是否和前一个相同
   • 如果发现相同颜色（s[i] == s[i-1]），则停止吃糖葫芦

3. 结果输出：

   • 如果找到相同颜色的相邻糖葫芦，输出此时的位置 i（表示吃了多少个糖葫芦）
   • 如果遍历完整串都没有找到相同颜色，输出字符串长度（表示可以把整串都吃完）

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	for i := 0; i < len(s); i++ {
		if i != 0 && s[i] == s[i-1] {
			fmt.Println(i)
			return
		}
	}
    fmt.Println(len(s))
}

中等题 小红的好数

1. 输入整数 k
2. 定义了一个 check 函数来判断一个字符串是否每个字符都不重复：
   • 使用 map 记录已出现的字符
   • 如果发现重复字符返回 false，否则返回 true
3. 主要逻辑：
   • 从 98765 到 1234 递减遍历所有 5 位数
   • 将每个数字格式化为 5 位字符串（不足位补 0）
   • 使用 check 函数检查是否每位数字都不同
   • 如果是不重复的数字，k 减 1
   • 当 k 变为 0 时，输出当前数字并结束程序

package main

import "fmt"

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

func main() {
	var n int
	fmt.Scan(&n)
	mp := make(map[int]int)
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		mp[a]++
	}
	var ans int
	for _, v := range mp {
		ans = max(ans, v)
	}
	if ans == n {
		fmt.Println(n)
	} else {
		fmt.Println(ans + 1)
	}
}

困难题 滑雪

1. 状态定义：
   • 定义一个二维数组dp，其中dp[x][y]表示从位置(x, y)出发，能够走的最长递减路径长度。
   • 初始时，所有dp[x][y]的值为0，表示尚未计算。
2. 转移方程：
   • 对于当前位置(x, y)，可以向四个方向移动：上、下、左、右。
   • 如果从(x, y)移动到(xx, yy)满足a[x][y] > a[xx][yy]（即目标位置的值更小），则更新dp[x][y]为：
   • 这意味着当前路径长度等于目标路径长度加1。
3. 边界条件：
   • 如果越界（即xx < 0、xx >= n、yy < 0或yy >= m），则跳过该方向。
   • 如果dp[x][y]已经计算过（即dp[x][y] != 0），直接返回结果，避免重复计算（记忆化搜索）。
4. DFS与记忆化搜索：
   • 使用深度优先搜索（DFS）递归地计算每个位置的最长路径长度。
   • 在递归过程中，通过dp数组记录已经计算过的结果，避免重复计算，从而提高效率。
5. 主逻辑：
   • 遍历矩阵中的每一个点(i, j)，调用dfs(i, j)计算从该点出发的最长路径。
   • 记录全局最大值ans，即所有起点中最长路径的长度。

package main

import (
	"fmt"
)

var (
	n, m int
	a    [][]int
	dp   [][]int
	dx   = []int{0, 0, 1, -1}
	dy   = []int{1, -1, 0, 0}
)

func dfs(x, y int) int {
	if dp[x][y] != 0 {
		return dp[x][y]
	}
	dp[x][y] = 1
	for i := 0; i < 4; i++ {
		xx, yy := x+dx[i], y+dy[i]
		if xx < 0 || xx >= n || yy < 0 || yy >= m {
			continue
		}
		if a[x][y] > a[xx][yy] {
			dp[x][y] = max(dp[x][y], dfs(xx, yy)+1)
		}
	}
	return dp[x][y]
}

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

func main() {
	fmt.Scan(&n, &m)
	a = make([][]int, n)
	dp = make([][]int, n)
	for i := range a {
		a[i] = make([]int, m)
		dp[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Scan(&a[i][j])
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			ans = max(ans, dfs(i, j))
		}
	}
	fmt.Println(ans)
}