最近看到一个有意思的帖子，一位清华的牛人，他自曝接到了省烟草局的 offer，就拒绝了华为，结果华为立马给他开出了一个“特殊涨薪”，年总包直接拉到了 70w！比烟草局的 offer 足足多了两倍。
要是我，我就选烟草，毕竟“烟草一世，华为一时”，犹豫一秒都是对自己的不尊重。。
算法题：复原 IP 地址
相信大家平时在编程中或多或少都碰到过这类题目。这种题不仅考察你对基本数据结构的理解，还考察你如何灵活运用一些常见的字符串处理技巧。
那这道题呢，虽然看上去简单，但仔细考虑后会发现它其实包含了一些考验耐心的部分，尤其是涉及到多个可能的组合时。
每个数字段的值必须在 0 到 255 之间； 每个数字段的前面不能有多余的 0，除非它的值就是 0。
每个部分的长度最多为 3 个字符（因为最大值是 255）。 每个部分的数字不能有前导零，除非它本身就是 0。
我们从字符串中提取出所有可能的 IP 地址段。 每次提取一个段时，我们需要判断它是否符合要求：
长度不超过 3； 数字不超过 255； 没有前导零，除非数字是 "0"。
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
// 如果字符串长度不在 4 到 12 之间，直接返回空
if (s.length() < 4 || s.length() > 12) {
return result;
}
// 尝试所有的分割方式
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int start, List<String> current, List<String> result) {
// 如果已经找到四个部分并且处理完了字符串
if (current.size() == 4) {
// 如果刚好处理完了字符串，说明这是一个有效的 IP 地址
if (start == s.length()) {
result.add(String.join(".", current));
}
return;
}
// 从当前起始点开始，最多处理三个字符
for (int length = 1; length <= 3; length++) {
// 如果剩余部分不足以填充，直接跳过
if (start + length > s.length()) {
break;
}
String segment = s.substring(start, start + length);
// 如果段的数字超出 255，或者有前导零且不为 "0"，则跳过
if ((segment.length() > 1 && segment.charAt(0) == '0') || Integer.parseInt(segment) > 255) {
continue;
}
// 选择当前段并进行递归
current.add(segment);
backtrack(s, start + length, current, result);
// 回溯，移除最后一个段
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "25525511135";
List<String> res = solution.restoreIpAddresses(s);
System.out.println(res); // ["255.255.11.135", "255.255.111.35"]
}
}
restoreIpAddresses是主函数，首先检查输入字符串的长度，如果不在合理范围内（4到12），直接返回空列表。然后调用 backtrack函数开始回溯处理。回溯的关键在于：
每次递归时，我们尝试从当前位置开始切割长度为1到3的子串。 对每个切割出的子串，我们检查它是否符合 IP 地址的规则（长度不超过3，且不超过255，不能有前导零）。 如果符合条件，我们继续递归，直到所有四个段都被处理完。
result 列表中，返回给用户。-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
