申请一个网站得多钱,台商网站建设公司黄页,百度网站推广怎么样,界面设计的基本原则将数字字符串转化为IP地址 题目描述解题思路回溯法步骤分解 代码实现全局变量有效性验证函数回溯函数主函数完整代码 复杂度分析关键点说明总结 这题难度还挺大的#xff0c;整体上实现并不容易。建议参考视频 和https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%… 将数字字符串转化为IP地址 题目描述解题思路回溯法步骤分解 代码实现全局变量有效性验证函数回溯函数主函数完整代码 复杂度分析关键点说明总结 这题难度还挺大的整体上实现并不容易。建议参考视频 和https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html#%E6%80%9D%E8%B7%AF 题目描述
给定一个仅包含数字的字符串将其转换为所有可能的有效IP地址形式。有效的IP地址由四个整数0到255之间构成各部分用.分隔且不能有前导零除非该段本身为0。
示例 输入25525522135 输出[255.255.22.135, 255.255.221.35] 输入000256 输出[]因256超过255
解题思路
回溯法
分割逻辑IP地址由四段组成需在字符串中找到三个分割点将字符串分为四段。有效性检查每段必须满足 值在0到255之间无前导零除非段本身为0仅包含数字。 递归终止条件当分割点数量为3时检查最后一段是否有效。剪枝若当前分割无效跳过后续尝试。
步骤分解
回溯函数记录当前分割点位置和已分割段数。有效性验证检查子串是否合法。生成结果将合法分割组合成IP地址格式。 代码实现
全局变量
char** result; // 存储结果数组
int resultTop; // 结果数组当前索引
int segments[3]; // 记录三个分割点的位置有效性验证函数
int isValid(char* s, int start, int end) {if (start end) return 0;if (s[start] 0 start ! end) return 0; // 前导零无效int num 0;for (int i start; i end; i) {if (s[i] 0 || s[i] 9) return 0; // 非数字字符num num * 10 (s[i] - 0);if (num 255) return 0; // 超过255}return 1;
}回溯函数
void backTracking(char* s, int startIndex, int pointNum) {if (pointNum 3) { // 分割点已满3个// 检查最后一段是否有效if (isValid(s, startIndex, strlen(s) - 1)) {char* temp (char*)malloc(strlen(s) 4); // 分配新字符串内存int count 0, count1 0;for (int j 0; j strlen(s); j) {temp[count] s[j];// 在分割点后插入.if (count1 3 j segments[count1]) {temp[count] .;count1;}}temp[count] \0;// 扩展结果数组并保存result (char**)realloc(result, sizeof(char*) * (resultTop 1));result[resultTop] temp;}return;}for (int i startIndex; i strlen(s); i) {if (isValid(s, startIndex, i)) { // 当前分割有效segments[pointNum] i; // 记录分割点backTracking(s, i 1, pointNum 1); // 递归下一段} else break; // 无效分割剪枝}
}主函数
char** restoreIpAddresses(char* s, int* returnSize) {result (char**)malloc(0);resultTop 0;backTracking(s, 0, 0);*returnSize resultTop;return result;
}完整代码
#include stdio.h
#include stdlib.h
#include string.h
#include stdbool.hchar** result; // 用于存储所有可能的IP地址
int resultTop; // 当前result数组中的IP地址数量
// 记录应该加入.的位置数组大小为3因为IP地址有3个分隔点
int segments[3];// 检查字符串是否为合法的IP段
// start和end分别表示当前检查的子字符串的起始和结束位置
int isValid(char* s, int start, int end) {// 如果起始位置大于结束位置说明子字符串无效if (start end) {return 0;}// 如果子字符串以0开头且长度大于1则该子字符串无效例如01、001等if (s[start] 0 start ! end) {return false;}int num 0; // 用于存储子字符串转换后的数字值// 遍历子字符串检查是否为合法数字for (int i start; i end; i) {// 如果字符不是数字则子字符串无效if (s[i] 9 || s[i] 0) {return false;}num num * 10 (s[i] - 0); // 将字符转换为数字并累加// 如果数字大于255则子字符串无效if (num 255) {return false;}}return true; // 如果通过所有检查则子字符串有效
}// 回溯函数用于生成所有可能的IP地址
// startIndex表示当前处理的字符串起始位置pointNum表示当前已放置的.数量
void backTracking(char* s, int startIndex, int pointNum) {// 如果已放置3个.说明已经生成了一个完整的IP地址if (pointNum 3) {// 检查最后一段字符串是否合法if (isValid(s, startIndex, strlen(s) - 1)) {// 为存储当前IP地址分配内存char* tempString (char*)malloc(sizeof(char) * (strlen(s) 4));int count 0; // 用于记录tempString的当前索引int count1 0; // 用于记录已使用的.数量// 遍历字符串根据segments数组插入.生成IP地址for (int j 0; j strlen(s); j) {tempString[count] s[j]; // 将当前字符添加到tempString// 如果当前索引是.的位置则插入.最多插入3个if (count1 3 j segments[count1]) {tempString[count] .;count1;}}tempString[count] \0; // 添加字符串结束符// 扩容result数组以存储新的IP地址result (char**)realloc(result, sizeof(char*) * (resultTop 1));result[resultTop] tempString; // 将新生成的IP地址加入result}return;}// 遍历字符串尝试将当前子字符串作为IP地址的一部分for (int i startIndex; i strlen(s); i) {// 检查当前子字符串是否合法if (isValid(s, startIndex, i)) {// 记录当前.的位置segments[pointNum] i;// 递归处理下一段字符串backTracking(s, i 1, pointNum 1);} else {// 如果当前子字符串不合法则停止当前分支的搜索break;}}
}// 主函数用于恢复IP地址
char** restoreIpAddresses(char* s, int* returnSize) {// 初始化result数组result (char**)malloc(0);resultTop 0;// 开始回溯搜索backTracking(s, 0, 0);*returnSize resultTop; // 设置返回的IP地址数量return result;
} 复杂度分析
时间复杂度O(n!)回溯尝试所有可能分割方式。空间复杂度O(n!)存储所有可能的IP地址。 关键点说明
回溯终止条件当分割点数为3时验证最后一段。剪枝优化遇到无效分割时立即终止当前循环。动态内存管理结果字符串需动态分配并适时扩展结果数组。 总结
通过回溯法遍历所有可能的分割方式结合有效性剪枝可高效生成所有合法IP地址。注意处理边界条件如前导零、数值范围和内存管理确保程序健壮性。
