莱芜民生网谷歌独立站seo
题目描述：
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
题目解答：
class Solution {
private:vector<string> 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:vector<string> restoreIpAddresses(string s) {res.clear();if (s.size() >= 4 && s.size() <= 12) // 长度符合ip地址规则backtrack(s, 0, 0);return res;}
};
题目思路：
-
私有成员变量：
vector<string> 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 函数来检查当前部分是否是一个合法的数字。