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

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

简单题 简单密码

1. 读取输入字符串：

   • 使用 fmt.Scan(&s) 读取用户输入的字符串 s。

2. 定义转换函数：

   • 定义一个匿名函数 convert，用于将小写字母转换为对应的数字键盘上的数字。

3. 遍历输入字符串的每个字符：

   • 使用 for _, c := range s 遍历字符串 s 中的每个字符 c。

4. 字符转换逻辑：

   • 小写字母：如果字符 c 是小写字母（'a' 到 'z'），调用 convert(c) 函数将其转换为对应的数字，并打印出来。
   • 大写字母：如果字符 c 是大写字母（'A' 到 'Z'），先将其转换为小写字母，然后进行一个简单的加密操作（将字母循环右移一位），最后打印出来。
   • 其他字符：如果字符 c 不是字母，直接打印出来。

package main

import (
	"fmt"
)

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

	convert := func(c rune) int {
		switch c {
		case 'a', 'b', 'c':
			return 2
		case 'd', 'e', 'f':
			return 3
		case 'g', 'h', 'i':
			return 4
		case 'j', 'k', 'l':
			return 5
		case 'm', 'n', 'o':
			return 6
		case 'p', 'q', 'r', 's':
			return 7
		case 't', 'u', 'v':
			return 8
		case 'w', 'x', 'y', 'z':
			return 9
		}
		return 0
	}

	for _, c := range s {
		if c >= 'a' && c <= 'z' {
			fmt.Print(convert(c))
		} else if c >= 'A' && c <= 'Z' {
			c += 'a' - 'A'
			c = (c-'a'+1)%26 + 'a'
			fmt.Printf("%c", c)
		} else {
			fmt.Printf("%c", c)
		}
	}
}

中等题 蛇形矩阵

根据样例说明可以很容易发现

1. 同一步中下标和相同，即 是个固定值
2. 每一步的 下标和依次递增
3. 同一步中 坐标依次从 0 开始递增

按照上述特征进行模拟填充矩阵

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, n-i)
	}
	x := 1
	for s := 0; s < n; s++ {
		for i := s; i >= 0; i-- {
			j := s - i
			a[i][j] = x
			x++
		}
	}
	for i := range a {
		for j := range a[i] {
			fmt.Printf("%d ", a[i][j])
		}
		fmt.Println()
	}
}

困难题 火车进站

该题的思路是使用深度优先搜索（DFS）来枚举所有可能的栈操作序列，从而获得所有可能的出栈结果。具体做法如下：

1. 输入与初始化 从输入中读取数字个数和数字序列，初始化用于模拟栈操作的两个数组：一个用于模拟栈（临时保存还未出栈的数字），另一个用于存储最终出栈的顺序。
2. 递归 DFS 遍历 定义一个递归函数，参数为当前处理到输入序列的位置。在每次调用中，将当前数字压入栈中，然后尝试从栈中弹出 0 到栈中所有数字的所有情况。每种弹出情况都会把弹出的数字附加到结果数组中。
3. 分情况尝试弹出操作 对于当前栈状态，遍历可能的弹出数量；每次循环中，通过循环将栈顶一定数量的数字（注意顺序需要翻转）一次性弹出，并添加到结果数组中。接着，递归处理下一个数字。
4. 回溯恢复状态 递归返回后，通过相应的操作将之前弹出且加入结果数组的数字恢复回栈中，然后将结果数组恢复，确保可以尝试其他的弹出方案。
5. 终止条件与结果收集 当已经处理完所有输入数字时，如果最终结果数组的长度与输入数量相同，则说明得到了一种完整的出栈结果，将该结果保存到答案集合中。
6. 排序输出 最后对所有得到的出栈序列按照字典序排序，并逐行输出。

注意点：ans = append(ans, append([]int(nil), b...))是将当前的切片 b 进行深拷贝，然后把拷贝后的副本追加到 ans 中，以确保后续对 b 的修改不会影响已经保存到 ans 中的结果。

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}
	var stack, b []int
	ans := make([][]int, 0)
	var dfs func(int)
	dfs = func(u int) {
		if u == n {
			if len(b) == n {
				ans = append(ans, append([]int(nil), b...))
			}
			return
		}
		stack = append(stack, a[u])
		for i := 0; i <= len(stack); i++ {
			for j := len(stack) - 1; j >= len(stack)-i; j-- {
				b = append(b, stack[j])
			}
			stack = stack[:len(stack)-i]
			dfs(u + 1)
			// 回溯
			for j := len(b) - 1; j >= len(b)-i; j-- {
				stack = append(stack, b[j])
			}
			b = b[:len(b)-i]
		}
		stack = stack[:len(stack)-1]
	}

	dfs(0)

	sort.Slice(ans, func(i, j int) bool {
		for k := 0; k < n; k++ {
			if ans[i][k] != ans[j][k] {
				return ans[i][k] < ans[j][k]
			}
		}
		return false
	})

	for i := range ans {
		for j := range ans[i] {
			fmt.Printf("%d ", ans[i][j])
		}
		fmt.Println()
	}
}