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

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

简单题 查找输入整数二进制中1的个数

方案一：使用 bits.OnesCount 函数

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	var n, m uint
	fmt.Scan(&n, &m)
	fmt.Println(bits.OnesCount(n))
	fmt.Println(bits.OnesCount(m))
}

方案二：手动实现 countBits 函数

其中 n &= n - 1 用来清除最右边的 1

package main

import (
	"fmt"
)

func countBits(n uint) int {
	count := 0
	for n > 0 {
		n &= n - 1
		count++
	}
	return count
}

func main() {
	var n, m uint
	fmt.Scan(&n, &m)
	fmt.Println(countBits(n))
	fmt.Println(countBits(m))
}

中等题 宝石手串

• 将原字符串 s 复制一份并拼接（s += s），这样可以处理环形的情况
• 用哈希表 mp 记录每个字符最后一次出现的位置
• 对于每个字符，查看它上一次出现的位置，计算中间需要移动的最小距离
• 最终答案就是所有相同字符对之间最小的移动距离

package main

import "fmt"

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

func solve(t int) {
	var (
		n int
		s string
	)
	fmt.Scan(&n, &s)
	s += s
	mp := make(map[rune]int)
	ans := n - 1
	for i, c := range s {
		if _, ok := mp[c]; ok {
			ans = min(ans, i-mp[c]-1)
		}
		mp[c] = i
	}
	if ans == n-1 {
		ans = -1
	}
	fmt.Println(ans)
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve(i)
	}
}

困难题 最长上升子序列(一)

方案一：线性DP 时间复杂度：

dp[i] 表示以第 i 个数结尾的最长递增子序列长度

• 对于每个位置 i，初始化 dp[i] = 1（最短的递增子序列就是数字本身）
• 遍历 i 前面的所有位置 j
• 如果 a[i] > a[j]，说明可以将第 i 个数接在以 j 结尾的递增子序列后面
• 此时可以更新 dp[i] = max(dp[i], dp[j] + 1)

package main

import "fmt"

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

func main() {
	var n int
	fmt.Scanf("%d", &n)
	a := make([]int, n)
	for i := range a {
		fmt.Scanf("%d", &a[i])
	}
	dp := make([]int, n)
	dp[0] = 1
	for i := 1; i < n; i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if a[i] > a[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
	}
	ans := 0
	for _, v := range dp {
		ans = max(ans, v)
	}
	fmt.Println(ans)
}

方案二：贪心 + 二分查找 时间复杂度：

我们可以维护一个子序列 dp，其中 dp[i] 表示长度为 i+1 的上升子序列的最小结尾值，保证 dp 子序列一定是递增的

遍历所有的元素，如果当前元素比子序列中的最后一个元素还大，就将其添加到子序列的末尾

否则，我们可以用二分查找找到子序列中第一个大于等于当前元素的位置，将该位置上的元素替换为当前元素，从而保证子序列仍然是上升的。

最终，子序列的长度就是最长上升子序列的长度。

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)
	a := make([]int, n)
	for i := range a {
		fmt.Scanf("%d", &a[i])
	}
	var dp []int
	for _, x := range a {
		idx := sort.SearchInts(dp, x)
		if idx == len(dp) {
			dp = append(dp, x)
		} else {
			dp[idx] = x
		}
	}
	fmt.Println(len(dp))
}