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

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

简单题 求int型正整数在内存中存储时1的个数

一个 int 类型的变量有 32 位，想要取出第 i 位就是 n >> i & 1

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	ans := 0
	for i := 0; i < 32; i++ {
		if n>>i&1 == 1 {
			ans++
		}
	}
	fmt.Println(ans)
}

中等题 整数与IP地址间的转换

• IP 地址转整数
  • 使用strings.Split函数将IP地址按"."分割成四个部分。
  • 遍历分割后的每个部分，将其转换为整数，并将其转换为8位二进制字符串。
  • 将所有二进制字符串拼接在一起，形成一个完整的二进制字符串。
  • 使用strconv.ParseInt函数将二进制字符串转换为64位整数。
• 整数转 IP 地址
  • 初始化一个字符串切片，用于存储IP地址的每个部分。
  • 通过位移和按位与操作，提取整数的每8位，转换为十进制数。
  • 将每个提取的十进制数转换为字符串，并添加到字符串切片中。
  • 使用strings.Join函数将字符串切片按"."连接，形成完整的IP地址。

package main

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

func IpToInt64(ip string) int64 {
	ss := strings.Split(ip, ".")
	var bit string
	for _, v := range ss {
		n, _ := strconv.Atoi(v)
		bit += fmt.Sprintf("%08b", n)
	}
	res, _ := strconv.ParseInt(bit, 2, 64)
	return res
}

func Int64ToIp(ipInt int64) string {
	var ip []string
	for i := 3; i >= 0; i-- {
		shift := uint(i * 8)
		octet := (ipInt >> shift) & 0xFF
		ip = append(ip, fmt.Sprintf("%d", octet))
	}
	return strings.Join(ip, ".")
}

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

	var n int64
	fmt.Scan(&n)
	fmt.Println(Int64ToIp(n))
}

困难题 字符串通配符

dp[i][j] 表示 p 的前 i 个字符是否能匹配 s 的前 j 个字符

状态转移分三种情况：

• 第一种情况（处理 ? 通配符）：

if i >= 1 && s[j] == '?' && isAlphaNum(p[i]) {
    dp[i][j] = dp[i-1][j-1]
}

当模式串 s 中出现 ? 时，如果待匹配字符 p[i] 是字母或数字，就可以匹配。相当于 ? 可以匹配任意一个字母或数字。匹配成功与否取决于各自去掉一个字符后的匹配结果。

• 第二种情况（处理普通字符）：

else if i >= 1 && s[j] != '*' && unicode.ToLower(rune(p[i])) == unicode.ToLower(rune(s[j])) {
    dp[i][j] = dp[i-1][j-1]
}

当两个字符相同（忽略大小写）时，匹配成功与否取决于各自去掉一个字符后的匹配结果。这是最基本的字符匹配情况。

• 第三种情况（处理 * 通配符）：

else if s[j] == '*' {
    if j >= 1 && dp[i][j-1] {  // * 匹配空字符
        dp[i][j] = true
    } else if i >= 1 && dp[i-1][j] && isAlphaNum(p[i]) {  // * 匹配一个或多个字符
        dp[i][j] = true
    }
}

当遇到 * 时，有两种可能：

1. * 当作空字符处理：直接跳过 *，看前面是否匹配 (dp[i][j-1])
2. * 匹配当前字符：如果当前字符是字母或数字，可以继续用 * 匹配下一个字符 (dp[i-1][j])

最终的结果 dp[n][m] 就表示整个字符串是否匹配成功。

package main

import (
	"fmt"
	"unicode"
)

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

	n, m := len(p), len(s)
	dp := make([][]bool, n+1)
	for i := range dp {
		dp[i] = make([]bool, m+1)
	}

	s = " " + s
	p = " " + p
	dp[0][0] = true

	for i := 0; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if i >= 1 && s[j] == '?' && isAlphaNum(p[i]) {
				dp[i][j] = dp[i-1][j-1]
			} else if i >= 1 && s[j] != '*' && unicode.ToLower(rune(p[i])) == unicode.ToLower(rune(s[j])) {
				dp[i][j] = dp[i-1][j-1]
			} else if s[j] == '*' {
				if j >= 1 && dp[i][j-1] {
					dp[i][j] = true
				} else if i >= 1 && dp[i-1][j] && isAlphaNum(p[i]) {
					dp[i][j] = true
				}
			}
		}
	}
	if dp[n][m] {
		fmt.Println("true")
	} else {
		fmt.Println("false")
	}
}

func isAlphaNum(c byte) bool {
	if 'A' <= c && c <= 'Z' {
		return true
	}
	if 'a' <= c && c <= 'z' {
		return true
	}
	if '0' <= c && c <= '9' {
		return true
	}
	return false
}