题目:给一个由数字组成的字符串。求出其可能恢复为的所有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;
}
网友评论