我要招人

去企业版

首页 > 试题广场 >

数字字符串转化成IP地址

[编程题]数字字符串转化成IP地址

热度指数：79678 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525522135",

返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围：字符串长度 $0 \leq n \leq 12$

要求：空间复杂度 $O(n!)$ ,时间复杂度 $O(n!)$

注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。

示例1

输入

"25525522135"

输出

["255.255.22.135","255.255.221.35"]

示例2

输入

"1111"

输出

["1.1.1.1"]

示例3

输入

"000256"

输出

[]

算法知识视频讲解

湫湫宁

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param s string字符串

* @return string字符串一维数组

* @return int* returnSize 返回数组行数

// 全局数组用于存储合法的 IP 地址

char** results;

int result_count;

// 检查IP段是否有效

int is_valid_segment(const char* segment)

{

int len = strlen(segment);

if (len == 0 || len > 3) return 0; // 长度为0或大于3无效

if (segment[0] == '0' && len > 1) return 0; // 不能以0开头而长度大于1

int num = atoi(segment);

return num >= 0 && num <= 255; // 数字在0到255之间

}

// 回溯函数

void backtrack(char* s, int start, int parts, char* current_ip) {

if (parts == 4)

{

if (start == strlen(s))

{

// 找到一个有效的IP地址，将其加入结果

results[result_count] = (char*)malloc(strlen(current_ip) + 1); // 分配内存

if (results[result_count] != NULL)

{

strcpy(results[result_count], current_ip); // 复制字符串

}

result_count++;

}

return;

}

for (int len = 1; len <= 3; len++)

{

if (start + len <= strlen(s))

{

char segment[4] = {0}; // 用于存放当前段

strncpy(segment, s + start, len);

if (is_valid_segment(segment))

{

// 继续递归

char new_ip[16]; // 存放当前构建的IP地址

sprintf(new_ip, "%s%s%s", current_ip, segment, parts == 3 ? "" : ".");

backtrack(s, start + len, parts + 1, new_ip);

}

char** restoreIpAddresses(char* s, int* returnSize )

{

// 如果字符串长度不在合法范围，直接返回 NULL

if (strlen(s) < 4 || strlen(s) > 12)

{

*returnSize = 0;

return NULL;

}

results = (char**)malloc(100 * sizeof(char*)); // 假设最多有 100 个结果

result_count = 0;

// 以空字符串开始，开始构建 IP 地址

char current_ip[16] = "";

backtrack(s, 0, 0, current_ip);

*returnSize = result_count;

return results; // 返回结果

}

发表于 2024-08-02 16:09:21 回复(0)

一个优雅的程序猿

int strsearch(char* s, char c) {
    int i;
    for(i=0;i<strlen(s);i++) {
        if(s[i]==c)
            return i;
    }
    return -1;
}
bool judgenum(char* s, int n) {
    int i,num=0;
    if(!n)
        return false;
    for(i=0;i<n;i++) {
        if((s[i]<'0')||(s[i]>'9'))
            return false;
        if((i==0)&&(s[i]=='0')&&(n!=1))
            return false;
        num *= 10;    
        num += s[i]-'0';
    }
    if(num>255)
        return false;
    return true;
}
bool solve(char* IP ) {
    int i;
    int Point_LOC=0;
    for(i=0;i<4;i++) {
        int NumLength = strsearch(IP+Point_LOC,'.');
        if(NumLength>0) {
            if(!judgenum(IP+Point_LOC,NumLength))
                return false;
            Point_LOC += NumLength+1;
        }
        else {
            if(!judgenum(IP+Point_LOC,strlen(IP)-Point_LOC))
                return false;
            Point_LOC += NumLength+1;
            break;
        }
    }
    return true;
}
char** restoreIpAddresses(char* s, int* returnSize ) {
    int i,j,k,m=0;
    char buf[12+4], **res;
    if(strlen(s)<4) {
        *returnSize = 0;
        return NULL;
    }
    res = (char**)malloc(100*sizeof(char*));
    for(i=0; i<strlen(s)-2; i++) {
        for(j=0; j<strlen(s)-1-i; j++) {
            for(k=0; k<strlen(s)-i-j; k++) {
                strncpy(buf, s, i);
                buf[i]='.';
                strncpy(buf+i+1, s+i, j);
                buf[i+1+j]='.';
                strncpy(buf+i+1+j+1, s+i+j, k);
                buf[i+1+j+1+k]='.';
                strcpy(buf+i+1+j+1+k+1, s+i+j+k);
                if(solve(buf)) {
                    res[m] = (char*)malloc(sizeof(buf));
                    strcpy(res[m++], buf);
                }
            }
        }
    }
    *returnSize = m;
    return res;
}

发表于 2024-03-24 16:09:59 回复(0)