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

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

简单题 【模板】栈

1. 使用切片 stk []int 来模拟栈
2. 首先输入操作次数 n
3. 循环 n 次，每次读入一个操作命令 op
4. 根据不同的操作命令执行相应的操作：
   • push：额外读入一个整数 x，使用 append 将其加入栈中
   • pop：判断栈是否为空，空则输出 "error"，否则输出并删除栈顶元素
   • top：判断栈是否为空，空则输出 "error"，否则只输出栈顶元素

代码使用 Go 语言的切片特性来实现栈的功能，通过 stk[len(stk)-1] 访问栈顶元素，通过 stk = stk[:len(stk)-1] 来模拟出栈操作。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	var stk []int
	for i := 0; i < n; i++ {
		var op string
		fmt.Scan(&op)
		switch op {
		case "push":
			var x int
			fmt.Scan(&x)
			stk = append(stk, x)
		case "pop":
			if len(stk) == 0 {
				fmt.Println("error")
			} else {
				fmt.Println(stk[len(stk)-1])
				stk = stk[:len(stk)-1]
			}
		case "top":
			if len(stk) == 0 {
				fmt.Println("error")
			} else {
				fmt.Println(stk[len(stk)-1])
			}
		}
	}
}

中等题 点击消除

1. 扫描输入一个字符串 s
2. 使用一个数组（切片）t 作为栈来存储字符
3. 遍历输入字符串的每个字符：
   • 如果栈为空，直接将当前字符入栈
   • 如果栈不为空，比较栈顶字符与当前字符：
     • 如果相同，则将栈顶字符弹出（相当于两个字符消除）
     • 如果不同，则将当前字符入栈
4. 最后：
   • 如果栈为空（所有字符都被消除），输出 0
   • 如果栈不为空，将栈中剩余字符转换为字符串并输出

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	var t []rune
	for _, c := range s {
		if len(t) == 0 {
			t = append(t, c)
		} else {
			if t[len(t)-1] == c {
				t = t[:len(t)-1]
			} else {
				t = append(t, c)
			}
		}
	}
	if len(t) == 0 {
		fmt.Println(0)
	} else {
		fmt.Println(string(t))
	}
}

困难题 小红取数

• 状态定义：dp[i][j] 表示考虑前 i 个数字，当前和除以 k 的余数为 j 时能够获得的最大和

• 初始化：

  • dp[0][0] = 0（一个数都不选时，和为0，余数为0）
  • 其他位置初始化为 MinInt64（表示不可能的状态）

• 状态转移：

  • 对于每个数字 x，有两种选择：
    • 不选 x：dp[i][j] = dp[i-1][j]
    • 选 x：dp[i][(j+mod)%k] = max(dp[i][(j+mod)%k], dp[i-1][j]+x) 其中 mod 是 x 除以 k 的余数

• 最终答案：

  • 如果 dp[n][0] == 0，说明没有找到符合条件的方案，输出 -1
  • 否则输出 dp[n][0]（表示和能被 k 整除的最大值）

package main

import (
	"fmt"
	"math"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	dp := make([][]int64, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int64, k)
		for j := 0; j < k; j++ {
			dp[i][j] = math.MinInt64
		}
	}
	dp[0][0] = 0
	for i := 1; i <= n; i++ {
		var x int64
		fmt.Scan(&x)
		mod := int(x % int64(k))
		// 不选 x
		for j := 0; j < k; j++ {
			dp[i][j] = dp[i-1][j]
		}
		// 选 x
		for j := 0; j < k; j++ {
			newMod := (j + mod) % k
			dp[i][newMod] = max(dp[i][newMod], dp[i-1][j]+x)
		}
	}

	if dp[n][0] == 0 {
		fmt.Println(-1)
	} else {
		fmt.Println(dp[n][0])
	}
}

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