清华大佬自曝：接到了省烟草局的offer，就拒掉了华为！结果华为立马给申请了特殊涨薪，总包70w是烟草的2倍

最近看到一个有意思的帖子，一位清华的牛人，他自曝接到了省烟草局的 offer，就拒绝了华为，结果华为立马给他开出了一个“特殊涨薪”，年总包直接拉到了 70w！比烟草局的 offer 足足多了两倍。

一边是高薪，一边是稳定与超级福利，怎么选呢？

要是我，我就选烟草，毕竟“烟草一世，华为一时”，犹豫一秒都是对自己的不尊重。。

是你，怎么选呢？

算法题：复原 IP 地址

聊个经典的算法题： 复原 IP 地址 。

相信大家平时在编程中或多或少都碰到过这类题目。这种题不仅考察你对基本数据结构的理解，还考察你如何灵活运用一些常见的字符串处理技巧。

那这道题呢，虽然看上去简单，但仔细考虑后会发现它其实包含了一些考验耐心的部分，尤其是涉及到多个可能的组合时。 题目描述： 给定一个只包含数字的字符串，恢复它并返回所有可能的 IP 地址格式。你需要从字符串中提取出四个整数，使得它们的每一段都是有效的 IP 地址段。

IP 地址有一些特点：

1. 每个数字段的值必须在 0 到 255 之间；
2. 每个数字段的前面不能有多余的 0，除非它的值就是 0。

举个例子，如果给定字符串 "25525511135"，我们可以把它划分为多个合法的 IP 地址，比如 "255.255.11.135" 或者 "255.255.111.35"。

核心思路： 想要复原 IP 地址，最大的难点是如何切割数字。因为 IP 地址总共分成四个部分，所以我们要从字符串中切割出四个部分，并且要确保每个部分都符合 IP 地址的规范。

1. 每个部分的长度最多为 3 个字符（因为最大值是 255）。
2. 每个部分的数字不能有前导零，除非它本身就是 0。

根据这些约束，解法可以采用回溯算法。也就是说，我们要不断地尝试不同的分割方式，直到找到一个符合条件的结果。

步骤：

1. 我们从字符串中提取出所有可能的 IP 地址段。
2. 每次提取一个段时，我们需要判断它是否符合要求：
• 长度不超过 3；
• 数字不超过 255；
• 没有前导零，除非数字是 "0"。
3. 如果当前部分合法，则继续处理下一个部分；如果所有部分都合法，则返回这个解。

Java 代码实现：

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"]
    }
}

代码解释：

1. restoreIpAddresses 是主函数，首先检查输入字符串的长度，如果不在合理范围内（4到12），直接返回空列表。
2. 然后调用 backtrack 函数开始回溯处理。回溯的关键在于：
• 每次递归时，我们尝试从当前位置开始切割长度为1到3的子串。
• 对每个切割出的子串，我们检查它是否符合 IP 地址的规则（长度不超过3，且不超过255，不能有前导零）。
• 如果符合条件，我们继续递归，直到所有四个段都被处理完。
3. 最终，所有合法的 IP 地址会被存储在 result 列表中，返回给用户。

性能优化： 这个算法的时间复杂度是 O(3^4)，因为每个段的长度最多为 3，每次递归有最多 3 种选择（长度为1到3）。对于字符串长度最多为12的输入，3^4 的计算量是完全可以接受的。
总结： 这道题看似简单，但实现起来其实涉及到很多细节，尤其是字符串的切割和回溯处理。不过一旦掌握了回溯的思路，这类题目就会变得轻松一些。 -END -
ok，今天先说到这，老规矩，给大家分享一份不错的副业资料，感兴趣的同学找我领取。

以上，就是今天的分享了， 看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言 。