README.md

comments	difficulty	edit_url	tags
true	困难	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3451.Find%20Invalid%20IP%20Addresses/README.md	数据库

3451. 查找无效的 IP 地址

English Version

题目描述

表：logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| log_id      | int     |
| ip          | varchar |
| status_code | int     |
+-------------+---------+
log_id 是这张表的唯一主键。
每一行包含服务器访问日志信息，包括 IP 地址和 HTTP 状态码。

编写一个解决方案来查找 无效的 IP 地址。一个 IPv4 地址如果满足以下任何条件之一，则无效：

• 任何 8 位字节中包含大于 255 的数字
• 任何 8 位字节中含有 前导零（如 01.02.03.04）
• 少于或多于 4 个 8 位字节

返回结果表分别以 invalid_count，ip 降序 排序。

结果格式如下所示。

 

示例：

输入：

logs 表：

+--------+---------------+-------------+
| log_id | ip            | status_code | 
+--------+---------------+-------------+
| 1      | 192.168.1.1   | 200         | 
| 2      | 256.1.2.3     | 404         | 
| 3      | 192.168.001.1 | 200         | 
| 4      | 192.168.1.1   | 200         | 
| 5      | 192.168.1     | 500         | 
| 6      | 256.1.2.3     | 404         | 
| 7      | 192.168.001.1 | 200         | 
+--------+---------------+-------------+

输出：

+---------------+--------------+
| ip            | invalid_count|
+---------------+--------------+
| 256.1.2.3     | 2            |
| 192.168.001.1 | 2            |
| 192.168.1     | 1            |
+---------------+--------------+

解释：

• 256.1.2.3 是无效的，因为 256 > 255
• 192.168.001.1 是无效的，因为有前导零
• 192.168.1 是非法的，因为只有 3 个 8 位字节

输出表分别以 invalid_count，ip 降序排序。

解法

方法一：模拟

我们可以根据题意，判断 IP 地址是否不合法，判断的条件有：

1. IP 地址中的 . 的个数不等于 $3$；
2. IP 地址中的某个 octet 以 0 开头；
3. IP 地址中的某个 octet 大于 $255$。

然后我们将不合法的 IP 地址进行分组，并统计每个不合法的 IP 地址的个数 invalid_count，最后按照 invalid_count 和 ip 降序排序。

MySQL

SELECT
    ip,
    COUNT(*) AS invalid_count
FROM logs
WHERE
    LENGTH(ip) - LENGTH(REPLACE(ip, '.', '')) != 3
    OR SUBSTRING_INDEX(ip, '.', 1) REGEXP '^0[0-9]'
    OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 2), '.', -1) REGEXP '^0[0-9]'
    OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 3), '.', -1) REGEXP '^0[0-9]'
    OR SUBSTRING_INDEX(ip, '.', -1) REGEXP '^0[0-9]'
    OR SUBSTRING_INDEX(ip, '.', 1) > 255
    OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 2), '.', -1) > 255
    OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 3), '.', -1) > 255
    OR SUBSTRING_INDEX(ip, '.', -1) > 255
GROUP BY 1
ORDER BY 2 DESC, 1 DESC;

Pandas

import pandas as pd


def find_invalid_ips(logs: pd.DataFrame) -> pd.DataFrame:
    def is_valid_ip(ip: str) -> bool:
        octets = ip.split(".")
        if len(octets) != 4:
            return False
        for octet in octets:
            if not octet.isdigit():
                return False
            value = int(octet)
            if not 0 <= value <= 255 or octet != str(value):
                return False
        return True

    logs["is_valid"] = logs["ip"].apply(is_valid_ip)
    invalid_ips = logs[~logs["is_valid"]]
    invalid_count = invalid_ips["ip"].value_counts().reset_index()
    invalid_count.columns = ["ip", "invalid_count"]
    result = invalid_count.sort_values(
        by=["invalid_count", "ip"], ascending=[False, False]
    )
    return result