三、网站开发使用软件环境,app下载赚钱,网店美工课程,网站开发网站开发题目描述#xff1a;
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 ‘.’ 分隔。
例如#xff1a;“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址#xff0c;但是 “0.011…题目描述
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
题目解答
class Solution {
private:vectorstring res; // 创建容器储存结果// 回溯的主体void backtrack(string s, int startIndex, int pointNum) {if (pointNum 3) {if (isLegal(s, startIndex, s.size() - 1))res.push_back(s);return;}for (int i startIndex; i s.size(); i) {if (isLegal(s, startIndex, i)) {s.insert(s.begin() i 1, .);pointNum;backtrack(s, i 2, pointNum);pointNum--;s.erase(s.begin() i 1);} else {break;}}}// 判断该串在给定区间内组成数字是否合法bool isLegal(string s, int start, int end) {if (start end || (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);if (num 255)return false;}return true;}public:vectorstring restoreIpAddresses(string s) {res.clear();if (s.size() 4 s.size() 12) // 长度符合ip地址规则backtrack(s, 0, 0);return res;}
};题目思路 私有成员变量 vectorstring res;用于存储所有可能的合法 IP 地址。 回溯函数 backtrack 参数 string s输入的字符串。int startIndex当前处理位置的起始索引。int pointNum当前已经插入的点号数量。 功能递归地尝试在字符串 s 的不同位置插入点号以生成可能的 IP 地址。终止条件当已经插入了 3 个点号即 IP 地址的 4 部分都已经形成并且当前的字符串 s 在 startIndex 到末尾的部分是一个合法的数字时将 s 添加到结果集 res 中。递归过程从 startIndex 开始遍历字符串 s尝试在每个位置插入点号。如果插入点号后的子串是合法的数字则递归调用 backtrack 函数继续处理剩余部分。 辅助函数 isLegal 参数 string s输入的字符串。int start检查的起始索引。int end检查的结束索引。 功能判断字符串 s 在 start 到 end 的子串是否表示一个合法的数字在 IP 地址的上下文中。判断逻辑 如果子串的长度超过 3 或以 ‘0’ 开头但不是单个 ‘0’则不合法。遍历子串的每个字符如果字符不是数字则不合法。计算子串表示的数字如果数字大于 255则不合法。 公有函数 restoreIpAddresses 参数 string s输入的字符串。 功能主函数用于启动整个恢复 IP 地址的过程。首先清空结果集 res。检查输入字符串 s 的长度确保它符合 IP 地址的长度规则4 到 12 个字符。调用 backtrack 函数开始回溯过程。返回结果集 res。
通过回溯算法尝试在输入字符串的不同位置插入点号以生成所有可能的合法 IP 地址组合。在每次尝试插入点号时都通过 isLegal 函数来检查当前部分是否是一个合法的数字。
