溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

java怎么還原IP地址

發(fā)布時(shí)間：2022-01-04 10:39:30 來(lái)源：億速云 閱讀：368 作者：iii 欄目：大數(shù)據(jù)

這篇文章主要講解了“java怎么還原IP地址”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“java怎么還原IP地址”吧！

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.

解題思路

首先既然要驗(yàn)證的是一個(gè)IP地址，那就意味著這個(gè)給定的字符串一定不能超過(guò)12個(gè)字符，因?yàn)槿绻^(guò)12個(gè)字符就不可能是IP地址。在此基礎(chǔ)上，這個(gè)給定的字符串最多只有12個(gè)字符，要讓一個(gè)字符串對(duì)應(yīng)的可能的IP地址，就要窮舉出所有的情況，然后逐個(gè)驗(yàn)證。窮舉的方式相當(dāng)于往字符之間的（頂多）11個(gè)空位中添加3個(gè)點(diǎn)，一共有C^3_11種加點(diǎn)的方式。例如，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

針對(duì)每種情況c，將它分割為4個(gè)部分，比如2.5.5.25511135被分割為2、5、5、25511135，接下來(lái)對(duì)每個(gè)部分做判斷。設(shè)其中一個(gè)部分的字符串為x，則只需要判斷它是否滿足以下兩個(gè)條件，如果不滿足則c這種情況就不是合法IP地址（在這個(gè)例子中是2.5.5.25511135）：

1）x不能大于255；

2）x如果不等于0的話，它的第一個(gè)字符不能為0，比如02這種就是不滿足的。

只有4個(gè)部分（2、5、5、25511135）都滿足了上述兩個(gè)條件，才算是合法的IP地址。對(duì)于上面的例子而言，所有情況里面就只有以下兩個(gè)才是合法的IP地址：

255.255.11.135
255.255.111.35

時(shí)間復(fù)雜度

無(wú)論初始給定的字符串長(zhǎng)度是多少，一共最多只有C^3_11=165種加點(diǎn)的方式，所以時(shí)間復(fù)雜度為O(165)=O(1)

最終實(shí)現(xiàn)

Java實(shí)現(xiàn)
class Solution {
        public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) {
            return new ArrayList<>();
        }
        List<String> candidates = new ArrayList<>();
        // Step 1. Select all probable slots
        List<Position> 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地址”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)java怎么還原IP地址這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手