首页 > 其他 > 详细

复原IP地址

时间:2021-06-03 16:04:31      阅读:21      评论:0      收藏:0      [点我收藏+]

复原IP地址

题目描述

给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.‘ 分隔。

例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

输入输出样例

//样例一
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
//样例二
输入:s = "0000"
输出:["0.0.0.0"]
//样例三
输入:s = "1111"
输出:["1.1.1.1"]    
//样例四
输入:s = "010010"
输出:["0.10.0.10","0.100.1.0"]
//样例五
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

题目分析

采用dfs回溯算法,每次dfs只分析IP地址中的其中一段,这样就会有函数dfs(string s, int id, int start)。其中id是当前分析的段数,start是此段从哪开始分析。

但是会有三个条件判断

  • 已经分析出来了:id=4且strat=s.length。那么就直接把结果存放到res这个结果字符串数组中。
  • 分析到尾但是没有四段:s.length=strat。那么就直接返回。
  • 当前分析的第一个数字是0:s[start]=‘0‘。那么只能作为单独一段,因为不允许有前导0。

接下来就是函数分析主体

会从start开始每次取一个数字分析下一段(for循环),也就是分析当前IP地址的第Id段为1、2、3位数字的情况。如果分析不成功,根据递归调用会回溯到上一个分析的状态

代码实现

#include <iostream>
#include<string>
#include<vector>
using namespace std;

vector<string> res;
int num[4];


void dfs(string s, int id, int start) {
    if (id == 4) {
        if (start == s.length()){
            string str;
            str = str + to_string(num[0]) + ‘.‘ + to_string(num[1]) + ‘.‘ + to_string(num[2]) + ‘.‘ + 		             to_string(num[3]);
            res.push_back(str);
        }
        return;
    }//已经分析出来了

    if (start == s.length())
        return;
    //分析到尾但是没有四段

    if (s[start] == ‘0‘) {
        num[id] = 0;
        dfs(s, id + 1, start + 1);
    }
    //当前分析的第一个数字是0

    int addr = 0;//存放当前第id段的地址
    for (int i = start; i < s.length(); i++) {
        addr = addr * 10 + s[i] - ‘0‘;
        if (addr > 0 && addr < 256) {
            num[id] = addr;
            dfs(s, id + 1, i + 1);
        }
        else break;
    }

}


int main()
{
    string s;
    cin >> s;
    dfs(s, 0, 0);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i]<<endl;
    }
    return 0;
}

复原IP地址

原文:https://www.cnblogs.com/MrDaddy/p/14845117.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!