栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java&C++题解与拓展——leetcode468.验证IP地址【么的新知识】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java&C++题解与拓展——leetcode468.验证IP地址【么的新知识】

每日一题做题记录,参考官方和三叶的题解

目录
  • 题目要求
  • 思路:双指针
    • Java
    • C++
    • Rust
  • 总结

题目要求

思路:双指针
  • 先根据分隔符判断是v4还是v6;
  • 根据不同协议特征分别遍历判断,判断被分隔符分开的每一段是否合法,左指针指段首,右指针向后移动直到遇到分隔符;
  • 最后判断分隔符数量。
Java
class Solution {
    int n;
    public String validIPAddress(String queryIP) {
        n = queryIP.length();
        if(queryIP.indexOf(".") >= 0 && ipv4(queryIP))
            return "IPv4";
        if(queryIP.indexOf(":") >= 0 && ipv6(queryIP))
            return "IPv6";
        return "Neither";
    }

    boolean ipv4(String ip) {
        int splitCnt = 0;
        for(int i = 0; i < n && splitCnt <= 3; ) {
            int j = i, cur = 0; // 被.分隔的段
            // 每一位合法,总数合法
            while(j < n && ip.charAt(j) >= '0' && ip.charAt(j) <= '9' && cur <= 255)
                cur = cur * 10 + (ip.charAt(j++) - '0');
            // ..
            if(i == j)
                return false;
            // 前导0
            if((j - i > 1 && ip.charAt(i) == '0') || (cur > 255))
                return false;
            i = j + 1; // 下一段
            if(j == n)
                continue;
            // 分隔符非法
            if(ip.charAt(j) != '.')
                return false;
            splitCnt++;
        }
        // 分隔符数量和位置都对
        return splitCnt == 3 && ip.charAt(0) != '.' && ip.charAt(n - 1) != '.';
    }
    boolean ipv6(String ip) {
        int splitCnt = 0;
        for(int i = 0; i < n && splitCnt <= 7; ) {
            int j = i;
            // 每一位合法
            while(j < n && ((ip.charAt(j) >= 'a' && ip.charAt(j) <= 'f') || (ip.charAt(j) >= 'A' && ip.charAt(j) <= 'F') || (ip.charAt(j) >= '0' && ip.charAt(j) <= '9')))
                j++;
            // ..或位数超了
            if(i == j || j - i > 4)
                return false;
            i = j + 1;
            if(j == n)
                continue;
            // 分隔符非法
            if(ip.charAt(j) != ':')
                return false;
            splitCnt++;
        }
        // 分隔符数量和位置都对
        return splitCnt == 7 && ip.charAt(0) != ':' && ip.charAt(n - 1) != ':';
    }
}
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)
C++
class Solution {
    int n;
public:
    string validIPAddress(string queryIP) {
        n = queryIP.size();
        if(queryIP.find(".") != string::npos && ipv4(queryIP))
            return "IPv4";
        if(queryIP.find(":") != string::npos && ipv6(queryIP))
            return "IPv6";
        return "Neither";
    }
    
    bool ipv4(string ip) {
        int splitCnt = 0;
        for(int i = 0; i < n && splitCnt <= 3; ) {
            int j = i, cur = 0; // 被.分隔的段
            // 每一位合法,总数合法
            while(j < n && ip[j] >= '0' && ip[j] <= '9' && cur <= 255)
                cur = cur * 10 + (ip[j++] - '0');
            // ..
            if(i == j)
                return false;
            // 前导0
            if((j - i > 1 && ip[i] == '0') || (cur > 255))
                return false;
            i = j + 1; // 下一段
            if(j == n)
                continue;
            // 分隔符非法
            if(ip[j] != '.')
                return false;
            splitCnt++;
        }
        // 分隔符数量和位置都对
        return splitCnt == 3 && ip[0] != '.' && ip[n - 1] != '.';
    }
    bool ipv6(string ip) {
        int splitCnt = 0;
        for(int i = 0; i < n && splitCnt <= 7; ) {
            int j = i;
            // 每一位合法
            while(j < n && ((ip[j] >= 'a' && ip[j] <= 'f') || (ip[j] >= 'A' && ip[j] <= 'F') || (ip[j] >= '0' && ip[j] <= '9')))
                j++;
            // ..或位数超了
            if(i == j || j - i > 4)
                return false;
            i = j + 1;
            if(j == n)
                continue;
            // 分隔符非法
            if(ip[j] != ':')
                return false;
            splitCnt++;
        }
        // 分隔符数量和位置都对
        return splitCnt == 7 && ip[0] != ':' && ip[n - 1] != ':';
    }
};
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)
Rust
  • 调用已有的库,然后对定义差异进行一定的修改
impl Solution {
    pub fn valid_ip_address(query_ip: String) -> String {
        use std::net::{Ipv4Addr, Ipv6Addr};
        query_ip
            .parse::()
            .map(|_| String::from("IPv4"))
            .or(query_ip
                .split(":")
                .map(|x| if x.is_empty() { "g" } else {x}) // 把空字符转为非法字符
                .collect::>()
                .join(":")
                .parse::()
                .map(|_| String::from("IPv6")))
            .unwrap_or_else(|_| String::from("Neither"))
    }
}
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)
总结

又是快乐的双指针,周末快乐~


欢迎指正与讨论!
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937365.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号