java怎么还原IP地址

这篇文章主要讲解了“java怎么还原IP地址”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“java怎么还原IP地址”吧!

成都一家集口碑和实力的网站建设服务商,拥有专业的企业建站团队和靠谱的建站技术,10多年企业及个人网站建设经验 ,为成都数千家客户提供网页设计制作,网站开发,企业网站制作建设等服务,包括成都营销型网站建设,成都品牌网站建设,同时也为不同行业的客户提供成都网站设计、成都做网站的服务,包括成都电商型网站制作建设,装修行业网站制作建设,传统机械行业网站建设,传统农业行业网站制作建设。在成都做网站,选网站制作建设服务商就选成都创新互联公司

Example 1:

Input: s = "25525511135"Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"Output: ["0.0.0.0"]

Example 3:

Input: s = "1111"Output: ["1.1.1.1"]

Example 4:

Input: s = "010010"Output: ["0.10.0.10","0.100.1.0"]

Example 5:

Input: s = "101023"Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

  • 0 <= s.length <= 3000

  • s consists of digits only.

解题思路

首先既然要验证的是一个IP地址,那就意味着这个给定的字符串一定不能超过12个字符,因为如果超过12个字符就不可能是IP地址。在此基础上,这个给定的字符串最多只有12个字符,要让一个字符串对应的可能的IP地址,就要穷举出所有的情况,然后逐个验证。穷举的方式相当于往字符之间的(顶多)11个空位中添加3个点,一共有C^3_11种加点的方式。例如,25525511135的所有可能情况如下所示,只要剔除不可能的情况即可:

2.5.5.25511135
2.5.52.5511135
2.5.525.511135
2.5.5255.11135
2.5.52551.1135
2.5.525511.135
2.5.5255111.35
2.5.52551113.5
2.55.2.5511135
2.55.25.511135
2.55.255.11135
2.55.2551.1135
2.55.25511.135
2.55.255111.35
2.55.2551113.5
2.552.5.511135
2.552.55.11135
2.552.551.1135
2.552.5511.135
2.552.55111.35
2.552.551113.5
2.5525.5.11135
2.5525.51.1135
2.5525.511.135
2.5525.5111.35
2.5525.51113.5
2.55255.1.1135
2.55255.11.135
2.55255.111.35
2.55255.1113.5
2.552551.1.135
2.552551.11.35
2.552551.113.5
2.5525511.1.35
2.5525511.13.5
2.55255111.3.5
25.5.2.5511135
25.5.25.511135
25.5.255.11135
25.5.2551.1135
25.5.25511.135
25.5.255111.35
25.5.2551113.5
25.52.5.511135
25.52.55.11135
25.52.551.1135
25.52.5511.135
25.52.55111.35
25.52.551113.5
25.525.5.11135
25.525.51.1135
25.525.511.135
25.525.5111.35
25.525.51113.5
25.5255.1.1135
25.5255.11.135
25.5255.111.35
25.5255.1113.5
25.52551.1.135
25.52551.11.35
25.52551.113.5
25.525511.1.35
25.525511.13.5
25.5255111.3.5
255.2.5.511135
255.2.55.11135
255.2.551.1135
255.2.5511.135
255.2.55111.35
255.2.551113.5
255.25.5.11135
255.25.51.1135
255.25.511.135
255.25.5111.35
255.25.51113.5
255.255.1.1135
255.255.11.135
255.255.111.35
255.255.1113.5
255.2551.1.135
255.2551.11.35
255.2551.113.5
255.25511.1.35
255.25511.13.5
255.255111.3.5
2552.5.5.11135
2552.5.51.1135
2552.5.511.135
2552.5.5111.35
2552.5.51113.5
2552.55.1.1135
2552.55.11.135
2552.55.111.35
2552.55.1113.5
2552.551.1.135
2552.551.11.35
2552.551.113.5
2552.5511.1.35
2552.5511.13.5
2552.55111.3.5
25525.5.1.1135
25525.5.11.135
25525.5.111.35
25525.5.1113.5
25525.51.1.135
25525.51.11.35
25525.51.113.5
25525.511.1.35
25525.511.13.5
25525.5111.3.5
255255.1.1.135
255255.1.11.35
255255.1.113.5
255255.11.1.35
255255.11.13.5
255255.111.3.5
2552551.1.1.35
2552551.1.13.5
2552551.11.3.5
25525511.1.3.5

针对每种情况c,将它分割为4个部分,比如2.5.5.25511135被分割为2、5、5、25511135,接下来对每个部分做判断。设其中一个部分的字符串为x,则只需要判断它是否满足以下两个条件,如果不满足则c这种情况就不是合法IP地址(在这个例子中是2.5.5.25511135):

1)x不能大于255;

2)x如果不等于0的话,它的第一个字符不能为0,比如02这种就是不满足的。

只有4个部分(2、5、5、25511135)都满足了上述两个条件,才算是合法的IP地址。对于上面的例子而言,所有情况里面就只有以下两个才是合法的IP地址:

255.255.11.135
255.255.111.35

时间复杂度

无论初始给定的字符串长度是多少,一共最多只有C^3_11=165种加点的方式,所以时间复杂度为O(165)=O(1)

最终实现

Java实现
class Solution {
        public List restoreIpAddresses(String s) {
        if (s.length() > 12) {
            return new ArrayList<>();
        }
        List candidates = new ArrayList<>();
        // Step 1. Select all probable slots
        List positions = new ArrayList<>();
        for (int i = 1; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                for (int k = j + 1; k < s.length(); k++) {
                    Position pos = new Position(i, j, k);
                    positions.add(pos);
                }
            }
        }
        // Step 2. Add dot to the given string
        for (Position pos : positions) {
            StringBuffer buffer = new StringBuffer(s);
            buffer.insert(pos.getZ(), ".");
            buffer.insert(pos.getY(), ".");
            buffer.insert(pos.getX(), ".");
            String candidate = buffer.toString();
            if (isValidIpAddress(candidate)) {
                candidates.add(candidate);
            }
        }
        return candidates;
    }

        private boolean isValidIpAddress(String ipAddress) {
        String[] blocks = ipAddress.split("\\.");
        for (String block : blocks) {
            if (Integer.valueOf(block) > 255) {
                return false;
            }
            if (block.startsWith("0") && block.length() != 1) {
                return false;
            }
        }
        return true;
    }

    static class Position {

        private int x;

        private int y;

        private int z;

        public Position(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public int getZ() {
            return z;
        }

        public void setZ(int z) {
            this.z = z;
        }
    }
}

感谢各位的阅读,以上就是“java怎么还原IP地址”的内容了,经过本文的学习后,相信大家对java怎么还原IP地址这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!


网页题目:java怎么还原IP地址
网址分享:http://myzitong.com/article/pghehj.html