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

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

简单题 单词倒排

1. 读取输入

   因为句子中可能包含空格，所以需要从标准输入读取一整行字符串。

2. 分词处理

   • 创建一个空的字符串切片来存储单词
   • 遍历输入的每个字符
   • 如果是字母，就追加到当前单词
   • 如果不是字母且当前单词不为空，就把当前单词加入切片，并重置当前单词

3. 处理最后一个单词

   如果循环结束后还有未处理的单词，将其加入切片。

4. 逆序打印

   从后向前遍历单词切片，打印每个单词并用空格分隔。

package main

import (
	"bufio"
	"fmt"
	"os"
	"unicode"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	s, _ := r.ReadString('\n')

	words := make([]string, 0)
	word := ""
	for _, c := range s {
		if unicode.IsLetter(c) {
			word += string(c)
		} else if word != "" {
			words = append(words, word)
			word = ""
		}
	}
	if word != "" {
		words = append(words, word)
	}
	
	for i := len(words) - 1; i >= 0; i-- {
		fmt.Printf("%s ", words[i])
	}
}

中等题 判断两个IP是否属于同一子网

1. 主要功能分为三个部分：

   • IP 地址解析
   • 子网掩码验证
   • 判断两个 IP 是否在同一子网

2. 具体实现分析：

• IP 地址解析函数 (parseIP)：

  • 使用 strings.Split 分割 IP 地址字符串
  • 验证是否为 4 段数字
  • 每段数字需在 0-255 范围内
  • 返回整数数组表示的 IP 地址

• 子网掩码验证函数 (isValidSubnetMask)：

  • 将子网掩码转换为 32 位整数
  • 验证二进制格式是否符合规则（连续的 1 后跟连续的 0）
  • 用位运算检查是否合法

package main

import (
	"fmt"
	"strconv"
	"strings"
)

func parseIP(ip string) ([]int, error) {
	parts := strings.Split(ip, ".")
	if len(parts) != 4 {
		return nil, fmt.Errorf("invalid IP address format")
	}

	ipParts := make([]int, 4)
	for i, part := range parts {
		num, err := strconv.Atoi(part)
		if err != nil || num < 0 || num > 255 {
			return nil, fmt.Errorf("invalid IP address format")
		}
		ipParts[i] = num
	}
	return ipParts, nil
}

func isValidSubnetMask(maskIP []int) bool {
	// 转换为32位整数
	maskBinary := (uint32(maskIP[0]) << 24) | (uint32(maskIP[1]) << 16) | (uint32(maskIP[2]) << 8) | uint32(maskIP[3])

	// 判断连续性：从最高位开始，一旦遇到 0 后续不应再出现 1
	encounteredZero := false
	for i := 0; i < 32; i++ {
		if (maskBinary & (1 << (31 - i))) == 0 {
			encounteredZero = true
		} else if encounteredZero {
			return false
		}
	}
	return true
}

func main() {
	var mask string
	fmt.Scanln(&mask)

	var ip1, ip2 string
	fmt.Scanln(&ip1)
	fmt.Scanln(&ip2)

	// 解析子网掩码和IP地址
	maskIP, err1 := parseIP(mask)
	ip1Net, err2 := parseIP(ip1)
	ip2Net, err3 := parseIP(ip2)

	if err1 != nil || err2 != nil || err3 != nil {
		fmt.Println("1")
		return
	}

	// 检查子网掩码是否有效
	if !isValidSubnetMask(maskIP) {
		fmt.Println("1")
		return
	}

	// 检查IP是否属于同一子网
	for i := 0; i < 4; i++ {
		if (ip1Net[i] & maskIP[i]) != (ip2Net[i] & maskIP[i]) {
			fmt.Println("2")
			return
		}
	}
	fmt.Println("0")
}

困难题 将真分数分解为埃及分数

方法：贪心算法

证明：https://www.zhihu.com/question/569413113

1. 取分母最大但小于等于当前分数的单位分数

   • 选取 最小的单位分数 ，其中 是比当前分数 的倒数大的最小整数，即 。

2. 将该单位分数从当前分数中减去

   • 计算新的剩余分数，并对其重复步骤 1，直到剩余部分变为 0。

感谢评论区指出代码中的不足之处，严谨考虑应该将 int 类型修改成 int64 类型。

package main

import (
	"fmt"
)

func ceil(a, b int) int {
	return (a + b - 1) / b
}

func main() {
	var a, b int
	fmt.Scanf("%d/%d", &a, &b)
	d := make([]int, 0)
	for a != 0 {
		x := ceil(b, a)
		d = append(d, x)
		// 计算剩余的分数 a/b - 1/x
		a = a*x - b
		b = b * x
	}
	for i, x := range d {
		if i > 0 {
			fmt.Print("+")
		}
		fmt.Printf("1/%d", x)
	}
}