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

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

简单题 输入n个整数，输出其中最小的k个

使用 sort.Ints() 对整个数组进行升序排序

遍历前 k 个元素并输出

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}
	sort.Ints(a)
	for i := 0; i < k; i++ {
		fmt.Printf("%d ", a[i])
	}
}

中等题 记票统计

1. 输入处理：

   • 读入整数 n，表示候选字符串的数量
   • 创建一个 map 和一个切片来存储候选字符串及其出现次数
   • 读入 n 个候选字符串，初始化它们在 map 中的计数为 0

2. 统计处理：

   • 读入整数 m，表示需要统计的字符串数量
   • 创建一个计数器 invalid 统计无效字符串的数量
   • 读入 m 个字符串：
     • 如果字符串在候选集合中，对应计数加一
     • 如果不在候选集合中，增加无效计数

3. 输出结果：

   • 按照输入的候选字符串顺序输出每个字符串及其出现次数
   • 最后输出无效字符串的数量

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	mp := make(map[string]int)
	ss := make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&ss[i])
		mp[ss[i]] = 0
	}

	var m int
	fmt.Scan(&m)
	invalid := 0
	for i := 0; i < m; i++ {
		var s string
		fmt.Scan(&s)
		if _, ok := mp[s]; ok {
			mp[s]++
		} else {
			invalid++
		}
	}

	for _, s := range ss {
		fmt.Printf("%s : %d\n", s, mp[s])
	}
	fmt.Printf("Invalid : %d\n", invalid)
}

困难题 【模板】哈夫曼编码

贪心策略来求解最小合并代价

1. 核心思想：

• 每次选择两个最小的频率值进行合并
• 合并后的新频率重新加入堆中
• 重复这个过程直到只剩一个节点
• 所有合并操作的代价之和就是最终结果

2. 具体实现：

• 使用最小堆（优先队列）维护所有频率
• 每次从堆顶取出两个最小值进行合并
• 合并结果再次入堆
• 累加每次合并的代价

package main

import (
	"container/heap"
	"fmt"
)

// MinHeap 实现最小堆
type MinHeap []int64

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int64)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	var n int
	fmt.Scan(&n)

	// 创建并初始化最小堆
	h := &MinHeap{}
	heap.Init(h)

	// 读取频率并放入最小堆
	for i := 0; i < n; i++ {
		var freq int64
		fmt.Scan(&freq)
		heap.Push(h, freq)
	}

	// 计算合并代价
	total := int64(0)
	for h.Len() > 1 {
		freq := heap.Pop(h).(int64) + heap.Pop(h).(int64)
		total += freq
		heap.Push(h, freq)
	}

	fmt.Println(total)
}