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

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

简单题 找出字符串中第一个只出现一次的字符

• 使用map[rune]int作为哈希表来统计字符频率
• 使用两次遍历：第一次统计频率，第二次查找第一个频率为1的字符

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	mp := make(map[rune]int)
	for _, c := range s {
		mp[c]++
	}
	for _, c := range s {
		if mp[c] == 1 {
			fmt.Println(string(c))
			return
		}
	}
	fmt.Println(-1)
}

中等题 字符统计

1. 读取输入字符串：使用fmt.Scan(&s)读取用户输入的字符串s。
2. 统计字符频率：使用一个map（mp）来统计每个字符在字符串中出现的次数。map的键是字符（rune类型），值是该字符出现的次数（int类型）。
3. 收集字符：遍历map，将所有字符收集到一个切片（ans）中。
4. 排序：使用sort.Slice对字符切片进行排序。排序规则是：
   • 如果两个字符的出现次数相同，则按字符的字典序排序。
   • 否则，按字符的出现次数从高到低排序。
5. 输出结果：将排序后的字符切片转换为字符串并输出。

package main

import (
	"fmt"
	"sort"
)

func main() {
	var s string
	fmt.Scan(&s)
	mp := make(map[rune]int)
	for _, c := range s {
		mp[c]++
	}
	ans := make([]rune, 0, len(mp))
	for k := range mp {
		ans = append(ans, k)
	}
	sort.Slice(ans, func(i, j int) bool {
		if mp[ans[i]] == mp[ans[j]] {
			return ans[i] < ans[j]
		}
		return mp[ans[i]] > mp[ans[j]]
	})
	fmt.Println(string(ans))
}

困难题 相差不超过k的最多数

核心思想是：

1. 排序数组：使得差值最大的一定是两端的差。
2. 滑动窗口双指针：从左往右找出每个区间中满足条件的最长子段。
   • j用于表示当前窗口的右边界，ans用于存储最长子序列的长度。
   • 外层循环遍历数组a，i表示当前窗口的左边界。
   • 内层循环不断移动右边界j，直到a[j] - a[i] > k为止。
     • 每次内层循环结束后，检查当前窗口的长度j - i是否大于ans，如果是，则更新ans。
3. 记录最大长度：输出满足条件的最大选择数。

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	sort.Ints(a)
	j, ans := 0, 0
	for i := 0; i < n; i++ {
		for j < n && a[j]-a[i] <= k {
			j++
		}
		if j-i > ans {
			ans = j - i
		}
	}
	fmt.Println(ans)
}