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

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

简单题 字符个数统计

利用 map/set 去重的性质可以来求不同字符的个数

因为Go 语言 没有内置的 Set 数据结构，但可以使用 map（哈希表）来实现类似 Set 的功能。

1. map[rune]struct{} （ struct{} 不占额外空间）
2. map[rune]bool

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	set := make(map[rune]bool, len(s))
	for _, c := range s {
		set[c] = true
	}
	fmt.Println(len(set))
}

中等题 删除字符串中出现次数最少的字符

1. 利用 map 来统计字符串中国所有字符出现的字数
2. 找出最小出现的次数
3. 构建结果字符串，不包含出现次数最少的字符

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	mp := make(map[rune]int, len(s))
	for _, c := range s {
		mp[c]++
	}
	
	minFreq := len(s)
	for _, freq := range mp {
		if freq < minFreq {
			minFreq = freq
		}
	}

	var result []rune
	for _, c := range s {
		if mp[c] != minFreq {
			result = append(result, c)
		}
	}

	fmt.Println(string(result))
}

困难题 四则运算

https://oi-wiki.org/misc/expression/

思路：将中缀表达式转化为后缀表达式

从左到右扫描该中缀表达式：

1. 如果遇到数字，直接输出该数字。
2. 如果遇到左括号，那么将其放在运算符栈上。
3. 如果遇到右括号，不断输出栈顶元素，直至遇到左括号，左括号出栈。换句话说，执行一对括号内的所有运算符。
4. 如果遇到其他运算符，不断输出所有运算优先级大于等于当前运算符的运算符。最后，新的运算符入运算符栈。
5. 在处理完整个字符串之后，一些运算符可能仍然在堆栈中，因此把栈中剩下的符号依次输出，表达式转换结束。

注意：这题会出现正负号，需要前面加一个 0 来特殊处理

package main

import (
	"fmt"
)

func calc(a, b int, op byte) (result int) {
	switch op {
	case '+':
		result = a + b
	case '-':
		result = a - b
	case '*':
		result = a * b
	case '/':
		result = a / b
	}
	return
}

// 优先级
func precedence(op byte) int {
	switch op {
	case '+', '-':
		return 1
	case '*', '/':
		return 2
	}
	return 0
}

func isLeftBracket(c byte) bool {
	return c == '(' || c == '[' || c == '{'
}

func isRightBracket(c byte) bool {
	return c == ')' || c == ']' || c == '}'
}

func main() {
	var s string
	fmt.Scan(&s)

	nums := make([]int, 0)
	ops := make([]byte, 0)

	eval := func() {
		num1 := nums[len(nums)-1]
		num2 := nums[len(nums)-2]
		nums = nums[:len(nums)-2]
		op := ops[len(ops)-1]
		ops = ops[:len(ops)-1]
		nums = append(nums, calc(num2, num1, op)) // num1, num2 注意顺序
	}

	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= '0' && c <= '9' {
			j := i
			num := 0
			for j < len(s) && s[j] >= '0' && s[j] <= '9' {
				num = num*10 + int(s[j]-'0')
				j++
			}
			i = j - 1
			nums = append(nums, num)
		} else if isLeftBracket(c) {
			ops = append(ops, c)
		} else if isRightBracket(c) {
			for !isLeftBracket(ops[len(ops)-1]) {
				eval()
			}
			ops = ops[:len(ops)-1] // 弹出左括号
		} else {
			// 判断是不是正负号
			if (c == '+' || c == '-') && (i == 0 || isLeftBracket(s[i-1])) {
				nums = append(nums, 0)
			}
			// 如果栈顶运算符优先级较高，先操作栈顶元素再入栈
			for len(ops) > 0 && precedence(ops[len(ops)-1]) >= precedence(c) {
				eval()
			}
			// 如果栈顶运算符优先级较低，直接入栈
			ops = append(ops, c)
		}
	}

	// 把没有操作完的运算符从右往左操作一遍
	for len(ops) > 0 {
		eval()
	}
	fmt.Println(nums[0])
}