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

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

简单题 截取字符串

字符串切片的一些常见用法

• s[start:end]：从 start 到 end-1 的子串（左闭右开）
• s[:end]：从 0 开始到 end-1
• s[start:]：从 start 到末尾
• s[:]：整个字符串的副本

package main

import "fmt"

func main() {
	var (
		s string
		k int
	)
	fmt.Scan(&s, &k)
	fmt.Println(s[:k])
}

中等题 矩阵乘法

1. 输入和初始化：

• 输入三个整数 x, y, z，分别表示第一个矩阵的行数、列数（同时也是第二个矩阵的行数）和第二个矩阵的列数
• 创建两个矩阵 和 ，并读入数据
• 创建结果矩阵

2. 对于 的计算： ，其中 k 从 0 到 y-1

package main

import "fmt"

func main() {
	var x, y, z int
	fmt.Scan(&x, &y, &z)
	a := make([][]int, x)
	for i := 0; i < x; i++ {
		a[i] = make([]int, y)
		for j := 0; j < y; j++ {
			fmt.Scan(&a[i][j])
		}
	}
	b := make([][]int, y)
	for i := 0; i < y; i++ {
		b[i] = make([]int, z)
		for j := 0; j < z; j++ {
			fmt.Scan(&b[i][j])
		}
	}
	c := make([][]int, x)
	for i := 0; i < x; i++ {
		c[i] = make([]int, z)
		for j := 0; j < z; j++ {
			for k := 0; k < y; k++ {
				c[i][j] += a[i][k] * b[k][j]
			}
		}
	}
	for i := 0; i < x; i++ {
		for j := 0; j < z; j++ {
			fmt.Printf("%d ", c[i][j])
		}
		fmt.Println()
	}
}

困难题 小红的01子序列构造（easy）

做法：双指针

1. 解题思路：

• 使用滑动窗口的方法求解
• 维护一个窗口 [l, r]，使用双指针 l 和 r
• zero 记录窗口内 '0' 的数量
• one 记录窗口内 '1' 的数量
• cnt 记录当前窗口内 '01' 子序列数量

2. 具体实现：

• 当遇到 '0' 时：

  • zero++（增加 0 的计数）

• 当遇到 '1' 时：

  • one++（增加 1 的计数）
  • cnt += zero（该位置的 1 会跨越它之前的所有 0）

• 当 cnt > k 时：

  • 需要收缩左边界，直到 cnt <= k
  • 如果移除的是 '0'：zero-- 且 cnt 需要减去当前窗口内的 one
  • 如果移除的是 '1'：one--

• 当 cnt == k 时：

  • 找到了符合条件的子串，输出位置并返回

3. 时间复杂度：

• ，其中 n 为字符串长度
• 每个字符最多被右指针和左指针各遍历一次

package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	var s string
	fmt.Scan(&s)

	zero, one, cnt := 0, 0, 0
	for l, r := 0, 0; r < n; r++ {
		if s[r] == '0' {
			zero++
		} else {
			one++
			cnt += zero
		}
		for l < r && cnt > k {
			if s[l] == '0' {
				zero--
				cnt -= one
			} else {
				one--
			}
			l++
		}
		if cnt == k {
			fmt.Println(l+1, r+1)
			return
		}
	}
	fmt.Println(-1)
}