数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：查找恢复后所有可能的IP地址
假设我们有一个只包含数字的字符串，我们需要通过形成所有可能的有效IP地址组合来恢复它。我们知道有效的IP地址由四个整数（每个整数的范围是0到255）组成，并用单个句点符号分隔。
因此，如果输入类似于ip = "25525511136"，则输出将为["254.25.40.123", "254.254.0.123"]
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数convertToNum()，它将接收s、start、end作为参数。
- num := 0
- for i := start to end do −
- num := (num * 10) + (s[i] - '0'的ASCII码)
- if num > 255 then −
- return 10000
- return num
- 定义一个函数addDots()，它将接收positions作为参数。
- res := 空字符串
- x := 0, posIndex := 0
- for i := 0 to positions的长度-1 do −
- num := positions[i]
- 创建一个字符串str1
- temp := num转换为字符串
- res := res + temp
- if i < positions的长度-1 then −
- res := res + "."
- return res
- 定义一个函数solve()，它将接收s、一个字符串数组result、一个数组positions、dotCount（初始化为3）、startIndex（初始化为0）作为参数。
- if dotCount != 0 and ((s的长度 - 1) - startIndex + 1) >= 4 then −
- temp := convertToNum(s, startIndex, s的长度 -1)
- if temp >= 0 and temp <= 255 then −
- 将temp添加到positions数组的末尾
- res := addDots(positions)
- if res的长度等于s的长度 then −
- 将res添加到result数组的末尾
- return
- for i := startIndex to s的长度 -1 do −
- temp := convertToNum(s, startIndex, i)
- if temp >= 0 and temp <= 255 then −
- 将temp添加到positions数组的末尾
- solve(s, result, positions, dotCount - 1, i + 1)
- 从positions数组中删除最后一个元素
- 定义一个函数genIp()，它将接收一个字符串s作为参数
- 定义一个数组result
- 定义一个数组position
- solve(s, result, position)
- return result
- 在主方法中调用genIp(A)
示例 (C++)
让我们看看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
lli convertToNum(string s,int start, int end){
lli num = 0;
for (int i = start; i <= end; i++) {
num = (num * 10) + (s[i] - '0');
if (num > 255)
return 10000;
}
return num;
}
string addDots(vector <int> positions){
string res = "";
int x = 0;
int posIndex = 0;
for (int i = 0; i < positions.size(); i++) {
int num = positions[i];
ostringstream str1;
str1 << num;
string temp = str1.str();
res += temp;
if (i < positions.size() - 1)
res += ".";
}
return res;
}
void solve(string s, vector <string> &result,vector <int> positions, int dotCount = 3, int startIndex = 0){
if (!dotCount && ((s.size() - 1) - startIndex + 1) >= 1) {
int temp = convertToNum(s, startIndex, s.size() - 1);
if (temp >= 0 && temp <= 255) {
positions.push_back(temp);
string res = addDots(positions);
if (res.size() - 3 == s.size()) {
result.push_back(res);
}
}
return;
}
for (int i = startIndex; i < s.size(); i++) {
int temp = convertToNum(s, startIndex, i);
if (temp >= 0 && temp <= 255) {
positions.push_back(temp);
solve(s, result, positions, dotCount - 1, i + 1);
positions.pop_back();
}
}
}
vector<string> genIp(string s){
vector<string> result;
vector<int> position;
solve(s, result, position);
return result;
}
vector<string> get_ip(string A) {
return genIp(A);
}};
main(){
Solution ob;
string ip = "25525511136";
print_vector(ob.get_ip(ip));
}输入
25525511136
输出
[255.255.11.136, 255.255.111.36, ]
更新于：2020年12月12日
285 次浏览
广告