免费素材网站mixkit,优化前网站现状分析,六盘水南宁网站建设,离石网站建设公司力扣日记#xff1a;【回溯算法篇】93. 复原 IP 地址 日期#xff1a;2023.1.28 参考#xff1a;代码随想录、力扣 93. 复原 IP 地址
题目描述 难度#xff1a;中等 有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0【回溯算法篇】93. 复原 IP 地址 日期2023.1.28 参考代码随想录、力扣 93. 复原 IP 地址
题目描述 难度中等 有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 ‘.’ 分隔。
例如“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址但是 “0.011.255.245”、“192.168.1.312” 和 “192.1681.1” 是 无效 IP 地址。 给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1 输入s “25525511135” 输出[“255.255.11.135”,“255.255.111.35”] 示例 2 输入s “0000” 输出[“0.0.0.0”] 示例 3 输入s “101023” 输出[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”] 提示
1 s.length 20s 仅由数字组成
题解
class Solution {
public:vectorstring results;string path ; vectorstring restoreIpAddresses(string s) {backtracking(s, 0, 0);return results;}int validInt(string s) {// 0xx 异常情况if (s.size() 1 s[0] 0) return -1; // 注意这里是0啊!!!if (s.size() 4) return -1; // 四位数则一定无效int num stoi(s);if (num 0 num 255) return num;return -1; // 其他情况返回-1表示invalid}// 参数count为path中已有.的数量void backtracking(string s, int startindex, int count) {// 终止条件count达到3if (count 3) {// 直接对最后一个值进行判断当.有3个了剩余的就是最后一个值了string sub s.substr(startindex, s.size() - startindex);if (validInt(sub) ! -1) { // 最后一个值有效path sub;results.push_back(path); // 添加之后记得回溯path.resize(path.size() - sub.size());}return; // 无效则直接返回}// for 循环横向遍历 [startindex, i]表示截取的元素for (int i startindex; i s.size(); i) {// 如果剩余的字符个数不足使ip达到四个数直接return这个也可以写在条件里if (s.size() - i - 1 4 - count - 1) return;// count 在进入下一层时才会1// 截取当前元素并转换string sub s.substr(startindex, i - startindex 1);int num validInt(sub);// 如果当前值无效直接return不需再遍历当前层后面都无效if (num -1) return;// 如果值有效path sub .;// 递归backtracking(s, i 1, count 1); // startindex指向i下一个元素count 1 表示.多了一个// 回溯path.resize(path.size() - (sub.size() 1)); // 删除sub .}}
};复杂度
时间复杂度: O(3^4)IP地址最多包含4个数字每个数字最多有3种可能的分割方式则搜索树的最大深度为4每个节点最多有3个子节点。 空间复杂度: O(n) by 代码随想录 思路总结 本题也是一道切割类型的题目“切割”思路截取、纵向递归、横向for遍历可类比131. 分割回文串。 首先关键也是要转换为组合问题得到树状结构这里我对示例3即s“101023”进行模拟构建出树状图 从树状图总结规律 参数首先根据 131. 分割回文串的截取思路这里还是需要一个startindex来表示截取的起始位置除此之外定义一个count表示截取的次数path中.的数量见下方。终止条件当我们截取了三次即添加了三个.之后实际上就完成了分割得到四个值了此时path中已经添加了前三个有效值因此在终止条件处对直接对最后一个值进行判断如果剩余的字符能构成一个有效值则path为有效的ip地址可添加入results中这里尤其要注意path添加了最后一个值后要回溯即弹出该值for 横向遍历 基础每次遍历截取[startindex, i]的元素作为当前值节点。剪枝这里观察图中“剩余值不足不再遍历”的情况表示剩余的字符个数不足以使得ip地址达到四个数如对“10.1023”取102后剩余3而构成ip地址还需要两个值所以不足。用count记录当前path中已有的值的个数则此剪枝条件可表示为 if (s.size() - i - 1 4 - count - 1) return;// count 在进入下一层时才会1至于开始递归的条件即当前值需有效才能放入path并递归截取后面的元素类比131. 分割回文串中需为回文串才处理节点并开始递归——因此将截取的元素进行s-int转换并判断转换是否有效 如果值无效则由图可知后面都无效不需要再遍历当前层直接return值有效的话便是处理节点添加值、递归、回溯注意path字符串添加时可直接用但是回溯删除时得用resize()或erase()递归时startindex指向i的下一个值而count也要1表示path多添加了一个值多了一个. 判断值是否有效 首先是排除0xx的情况如023这里要注意比较时需与字符0进行比较 接着是截取元素对应整数需在[0,255]范围内。注意这里由于stoi()函数在值较大时溢出所以先排除了字符个数4的情况。对有效值返回对应值无效值返回-1。 经过调试才发现的bug validInt()排除0xx异常值时写成了s[0]0注意应该是0stoi()值溢出所以添加了先排除四位数及以上的情况。终止条件中path添加了最后一个值但没有回溯导致结果集出现异常值记得path每次添加都要回溯。 TODO进一步优化 不使用path而是直接在原字符串上添加.s.insert(s.begin() i 1 , .); // 在i的后面插入一个逗点
...
s.erase(s.begin() i 1); // 回溯删掉逗点不切割字符串得到子串进行是否为有效值的判断而是用下标索引。// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string s, int start, int end) {if (start end) {return false;}if (s[start] 0 start ! end) { // 0开头的数字不合法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);if (num 255) { // 如果大于255了不合法return false;}}return true;
}详见代码随想录思路。
