美文网首页
从字符串恢复IP地址

从字符串恢复IP地址

作者: 鬼谷神奇 | 来源:发表于2016-03-14 17:15 被阅读2790次

题目:给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。
给出字符串 "25525511135",
所有可能的IP地址为:
[ "255.255.11.135", "255.255.111.35"]
(顺序无关紧要)

算法分析:

  • 众所周知,IP地址分为4段,每段的位数范围是1,2,3,所以看到题目第一个想法是从1,2,3三个数中挑选4个数,使4个数的和等于字符串的长度,题目转换为k数和为定值的问题。
  • 利用递归求得和为字符串长度的所有序列,然后利用STL next_permutation函数全排列,依次按照位数从字符串中截取,这里需要注意01、001等这种首位数字为0的情况,需排除。
  • 删除重复的IP地址

算法实现:(有点儿麻烦,虽然题目规定顺序无关,但提交lintcode不能通过,其中答案正确,只是顺序有误)

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <sstream>

using namespace std;

int buf[3] = {1, 2, 3};
vector<int> tmp;

void get4Num(int buf[], int index, int k, int sum, vector<vector<int> > &result)
{
    if(k > 3)
        return;
    if(index == 3 || sum <= 0)
        return;
            
    if(sum == buf[index] && k == 3)
    {
        tmp.push_back(buf[index]);
        result.push_back(tmp);
        tmp.pop_back();
    }
         
    tmp.push_back(buf[index]);
    get4Num(buf, index, k+1, sum-buf[index], result);
    tmp.pop_back();
         
    get4Num(buf, index+1, k, sum, result);
}
     
vector<vector<int> > getAllPermutation(vector<vector<int> > &result)
{
    vector<vector<int> > ans;

    for(int i = 0; i < result.size(); ++i)
    {
        sort(result[i].begin(), result[i].end());

        do
        {
            ans.push_back(result[i]);
        }while(next_permutation(result[i].begin(), result[i].end()));
    }

    return ans;
}

int main()
{
    ifstream cin("in.txt");
    string s;
    while(cin >> s)
    {
        vector<vector<int> > result;    

        if(s.size() < 4 || s.size() > 12)
            return result;
        
        get4Num(buf, 0, 0, s.size(), result);

        result = getAllPermutation(result);

        vector<vector<int> > ip;

        for(int i = 0; i < result.size(); ++i)
        {
            int index = 0;
            bool flag = true;
            vector<int> tmp;
            for(int j = 0; j < result[i].size(); ++j)
            {
                /* 010010 
                0 1 0 010
                0 1 001 0
                0 100 1 0
                010 0 1 0
                0 1 00 00
                0 10 0 10
                0 10 01 0
                01 0 0 10
                01 0 01 0
                01 00 0 0
                */
                string subs = s.substr(index, result[i][j]);
                if(subs.size() > 1 && subs[0] == '0')  
                {
                    flag = false;
                    continue;
                }

                int fragment = atoi(subs.c_str());

                index += result[i][j];

                if(fragment < 0 || fragment > 255)
                {
                    flag = false;
                    continue;
                }

                tmp.push_back(fragment);            
            }

            if(flag == true)
                ip.push_back(tmp);
        }

        /*
        for(int i = 0; i < ip.size(); ++i)
        {
            for(int j = 0; j < ip[i].size(); ++j)
                cout << ip[i][j] << " ";
            cout << endl;
        }
        */

        stringstream stream;

        vector<string> res;
        for(int i = 0; i < ip.size(); ++i)
        {
            string ss = "";
            for(int j = 0; j < ip[i].size(); ++j)
            {
                string s;
                stream << ip[i][j];
                stream >> s;
                ss += s;
                if(j < ip[i].size() - 1)
                    ss += ".";
                stream.clear();
            }

            res.push_back(ss);
        }

        sort(res.begin(), res.end());
        for(int i = 0; i < res.size(); ++i)
            res.erase(unique(res.begin(), res.end()), res.end());

        for(int i = 0; i < res.size(); ++i)
        {
            cout << res[i] << endl;
        }
    }

    


    return 0;
}

深搜法求解:

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <sstream>

using namespace std;

bool isValid(string s)
{
    if(s.size() > 1 && s[0] == '0')
        return false;
    int res = atoi(s.c_str());

    return res <= 255 && res >= 0;
}

void DFS(string s, string tmp, int count, vector<string> &result)
{
    if(count == 3 && isValid(s))
    {
        result.push_back(tmp+s);
        return;
    }

    //可以取1-3个字符
    for(int i = 1; i <= 3 && i < s.size(); ++i) //特别需要注意i<s.size()
    {
        string subs = s.substr(0, i);
        if(isValid(subs))
            DFS(s.substr(i), tmp+subs+".", count+1, result);        
    }
}

int main()
{
    ifstream cin("in.txt");

    string s;

    while(cin >> s)
    {
        vector<string> result;

        if(s.size() < 4 || s.size() > 12)
            return 0;

        DFS(s, "", 0, result);
        
        for(int i = 0; i < result.size(); ++i)
        {
            cout << result[i] << endl;
        }
        
    }


    return 0;
}

相关文章

  • 从字符串恢复IP地址

    题目:给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。给出字符串 "25525511135",所有可能的...

  • 算法(2)重构IP地址

    LeetCode算法题,重构IP地址 参考DFS-lintcode恢复ip地址(Restore IP Addres...

  • 答案

    字符串: 英语: IP地址: 黑洞数

  • LintCode:恢复IP地址【DFS】

    描述 给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。(你的任务就是往这段字符串中添加三个点, 使它成为...

  • Java正则表达式

    正则表达式一般用于字符串匹配、查找、替换、分割。例如: 从网页中找出email地址,IP地址是否正确,从网页中找出...

  • 93. Restore IP Addresses 恢复IP地址

    题目链接tag: Medium; question:  Given a string containing onl...

  • Long.ValueOf("String") Long.pars

    IP地址类型转换原理: 将一个点分十进制IP地址字符串转换成32位数字表示的IP地址(网络字节顺序)。 将一个32...

  • leetcode刷题记录 js算法与数据结构 基础篇(中)

    1: #### 复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。示例:输入: "2...

  • 递归与回溯:93.复原IP地址

    /** 题目 给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址 正好由四个...

  • LeetCode-093-复原 IP 地址

    复原 IP 地址 题目描述:给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效...

网友评论

      本文标题:从字符串恢复IP地址

      本文链接:https://www.haomeiwen.com/subject/hjpflttx.html