题解 | 识别有效的IP地址和掩码并进行分类统计

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	var a, b, c, d, e, error, private int

	for scanner.Scan() {
		line := scanner.Text()
		if line == "" {
			break
		}

		parts := strings.Split(line, "~")
		if len(parts) != 2 {
			error++
			continue
		}

		ip, mask := parts[0], parts[1]

		// 先检查IP格式
		if !isValidIP(ip) {
			error++
			continue
		}

		ipParts := strings.Split(ip, ".")
		first, _ := strconv.Atoi(ipParts[0])

		// 特殊IP处理：0.*.*.* 和 127.*.*.* 直接跳过，不检查掩码
		if first == 0 || first == 127 {
			continue
		}

		// 检查掩码格式
		if !isValidMask(mask) {
			error++
			continue
		}

		// 检查私有IP
		if isPrivateIP(ip) {
			private++
		}

		// 分类统计
		if first >= 1 && first <= 127 {
			a++
		} else if first >= 128 && first <= 191 {
			b++
		} else if first >= 192 && first <= 223 {
			c++
		} else if first >= 224 && first <= 239 {
			d++
		} else if first >= 240 && first <= 255 {
			e++
		}
	}

	fmt.Printf("%d %d %d %d %d %d %d", a, b, c, d, e, error, private)
}

func isValidIP(ip string) bool {
	parts := strings.Split(ip, ".")
	if len(parts) != 4 {
		return false
	}

	for _, part := range parts {
		if part == "" {
			return false
		}
		num, err := strconv.Atoi(part)
		if err != nil || num < 0 || num > 255 {
			return false
		}
	}
	return true
}

func isValidMask(mask string) bool {
	parts := strings.Split(mask, ".")
	if len(parts) != 4 {
		return false
	}

	var binary string
	for _, part := range parts {
		if part == "" {
			return false
		}
		num, err := strconv.Atoi(part)
		if err != nil || num < 0 || num > 255 {
			return false
		}
		binary += fmt.Sprintf("%08b", num)
	}

	if binary == "11111111111111111111111111111111" || binary == "00000000000000000000000000000000" {
		return false
	}

	oneFound := false
	zeroFound := false
	for _, bit := range binary {
		if bit == '1' {
			if zeroFound {
				return false
			}
			oneFound = true
		} else {
			zeroFound = true
		}
	}

	return oneFound && zeroFound
}

func isPrivateIP(ip string) bool {
	parts := strings.Split(ip, ".")
	first, _ := strconv.Atoi(parts[0])
	second, _ := strconv.Atoi(parts[1])

	if first == 10 {
		return true
	}

	if first == 172 && second >= 16 && second <= 31 {
		return true
	}

	if first == 192 && second == 168 {
		return true
	}

	return false
}

解题思路

算法分析

这道题的核心是IP地址分类和子网掩码验证。主要涉及：

1. IP地址格式验证：检查四段数字格式和范围
2. 子网掩码合法性验证：转换为二进制并检查连续1+连续0的格式
3. IP地址分类：根据首段数字范围分类
4. 私有IP识别：检查特定的IP段范围
5. 特殊IP处理：跳过0...和127..*.*的IP

IP地址分类规则

graph TD
    A[IP地址首段] --> B{首段范围}
    B -->|1-127| C[A类地址]
    B -->|128-191| D[B类地址]
    B -->|192-223| E[C类地址]
    B -->|224-239| F[D类地址]
    B -->|240-255| G[E类地址]
    B -->|0或127| H[特殊IP，跳过]

私有IP地址识别

graph TD
    A[IP地址] --> B{首段}
    B -->|10| C[私有IP]
    B -->|172| D{第二段}
    B -->|192| E{第二段}
    D -->|16-31| C
    E -->|168| C
    B -->|其他| F[非私有IP]
    D -->|其他| F
    E -->|其他| F

子网掩码验证流程

flowchart TD
    A[子网掩码] --> B[按点分割为四段]
    B --> C[每段转换为8位二进制]
    C --> D[拼接为32位二进制串]
    D --> E{是否为全1或全0?}
    E -->|是| F[非法掩码]
    E -->|否| G[检查连续1+连续0格式]
    G --> H{格式正确?}
    H -->|是| I[合法掩码]
    H -->|否| F

算法流程图

flowchart TD
    A[读取一行输入] --> B[按~分割IP和掩码]
    B --> C{分割结果是否有效?}
    C -->|否| D[错误计数+1]
    C -->|是| E[验证IP格式]
    E --> F{IP格式是否合法?}
    F -->|否| D
    F -->|是| G[验证掩码格式]
    G --> H{掩码是否合法?}
    H -->|否| D
    H -->|是| I{是否为特殊IP?}
    I -->|是| J[跳过处理]
    I -->|否| K[检查是否为私有IP]
    K --> L[根据首段分类IP]
    L --> M[更新各类计数]
    M --> N{还有输入?}
    N -->|是| A
    N -->|否| O[输出统计结果]
    D --> N
    J --> N

代码实现思路

1. 输入处理：逐行读取，按~分割IP和掩码
2. 格式验证： IP验证：四段数字，每段0-255掩码验证：转换为二进制检查连续1+连续0格式
3. 分类统计： 根据首段数字范围分类A-E类检查私有IP范围跳过特殊IP（0...和127...）

时间复杂度分析

• 时间复杂度：O(n)，其中n是输入行数
• 空间复杂度：O(1)，只使用固定数量的计数器

关键优化点

1. 位操作优化：使用(maskInt & (maskInt + 1)) == 0巧妙判断连续1+连续0格式
2. 整数表示：将四段IP转换为32位整数，避免字符串操作
3. 范围判断优化：直接比较首段数字，避免字符串比较
4. 提前返回：发现格式错误立即跳过，减少不必要的计算

边界情况处理

1. 格式错误：分割符错误、段数不对、空段
2. 数值越界：超出0-255范围
3. 特殊IP：0...和127..*.*直接跳过
4. 掩码特殊值：全1或全0掩码视为非法

测试用例分析

graph TD
    A[测试用例1] --> B[混合合法和非法地址]
    C[测试用例2] --> D[全部为特殊IP地址]
    
    B --> E[验证分类统计正确性]
    D --> F[验证特殊IP跳过逻辑]
    
    E --> G[IP格式验证]
    E --> H[掩码格式验证]
    E --> I[分类逻辑验证]
    E --> J[私有IP识别验证]

位操作技巧详解

连续1+连续0格式判断的巧妙方法：

graph TD
    A[掩码整数 maskInt] --> B[maskInt + 1]
    B --> C[maskInt & (maskInt + 1)]
    C --> D{结果是否为0?}
    D -->|是| E[格式正确：连续1+连续0]
    D -->|否| F[格式错误：存在01模式]
    
    G[示例：255.255.255.248] --> H[11111111 11111111 11111111 11111000]
    H --> I[+1 = 11111111 11111111 11111111 11111001]
    I --> J[&运算 = 11111111 11111111 11111111 11111000 ≠ 0]
    J --> K[错误！应该是0]
    
    L[正确示例：255.255.255.0] --> M[11111111 11111111 11111111 00000000]
    M --> N[+1 = 11111111 11111111 11111111 00000001]
    N --> O[&运算 = 00000000 00000000 00000000 00000000 = 0]
    O --> P[正确！]

原理解析：

• 如果掩码是连续1+连续0格式，那么maskInt + 1会在第一个0位产生进位
• 进位后的结果与原掩码进行&运算，如果结果为0，说明没有01模式
• 这是判断二进制数是否为连续1+连续0格式的最优算法

这个问题的关键在于严格的格式验证和正确的分类逻辑，特别是子网掩码的二进制格式验证和特殊IP的处理优先级。