1.6 - 复制IP地址 vector和list的区别

目录

1.复制IP地址

a.核心思想

b.思路

c.步骤

2.list和vector的区别

1.复制IP地址

93. 复原 IP 地址 - 力扣（LeetCode）https://leetcode.cn/problems/restore-ip-addresses/description/

class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string> result; // 存储结果集 // 输入有效性检查：IP地址最多由12个数字组成 if (s.size() > 12) return result; string path; // 当前路径（存储临时IP地址段） backtrack(s, 0, 0, path, result); // 从第0个字符开始回溯 return result; } void backtrack(string& s, int start, int segment, string& path, vector<string>& result) { // 成功条件：生成4段且用完所有字符 if (start == s.size() && segment == 4) { path.pop_back(); // 移除末尾多余的点（如"192.168.1.1."→"192.168.1.1"） result.push_back(path); return; } // 失败条件：越界或已生成4段 if (start >= s.size() || segment >= 4) return; // 尝试当前段的3种可能长度（1-3位） for (int len = 1; len <= 3; len++) { // 防止越界检查 if (start + len > s.size()) break; string sub = s.substr(start, len); // 截取当前段 // 有效性检查： // 1. 长度>1时不能以0开头（排除"01"类无效地址） // 2. 数值范围必须在0-255之间 if ((sub.size() > 1 && sub[0] == '0') || stoi(sub) > 255) break; // 生成新路径（避免修改原始path） string newPath = path + sub + "."; // 递归：处理下一段（位置后移len，段数+1） backtrack(s, start + len, segment + 1, newPath, result); // 注意：newPath是局部变量，递归返回后自动销毁 // 无需手动恢复path状态 } } };

a.核心思想

通过回溯法，在给定的数字字符串中插入三个点，将字符串分成四部分，判断每部分是否满足有效IP地址的条件，若满足则将其加入结果列表。

b.思路

① 使用回溯法遍历所有可能的插入点的位置。

② 对于每一种分割方式，检查四部分是否都满足有效IP地址的条件（整数在0到255之间，且不能有前导0，除非整数就是0）。

③ 如果满足条件，则将该IP地址加入结果列表。

c.步骤

① 定义回溯函数，参数包括当前字符串、当前分割的段数、当前路径和结果列表。

② 在回溯函数中，如果已经分割成四段且字符串已用完，则将当前路径加入结果列表。

③ 遍历所有可能的分割点，对每一段进行检查，如果满足条件则继续回溯。

④ 返回结果列表。

2.list和vector的区别

希望这些内容对大家有所帮助！

感谢大家的三连支持！