领导让我带新人，但他连 Git都不会用，怎么教?

看到一个有意思的吐槽，到现在我脑袋都是嗡嗡的……

领导安排他带新人，结果那新人连 Git 都不会用。你说这不是拿人开涮吗？

咱写代码的都知道，Git 就是程序员的呼吸机，不会用 Git，咋合作？咋提测？咋改 Bug？要我说这是带人？这是带祖宗吧！

但话说回来，这种事真挺憋屈的。带新人没问题，但你好歹给我个基本能跑起来的吧？就像打游戏队友连键盘都不会用，那这局还能赢？

有时候我觉得领导安排任务就是拍脑袋，想着“反正你也没事干”，可没事干≠可以无限额接锅啊……

整不会了，真的整不会了……【备注:文末可领最新资料】

说到“解码方法”这道题，我第一反应是：“啊这不就是那个跟斐波那契有关的老熟人吗？”不过别小看它，这玩意看着简单，实则潜藏着不少坑，尤其是你要是硬刚递归，分分钟让你怀疑人生……

问题大概长这样：给一个只包含数字的字符串，每个数字对应字母表中某个字母（比如 1=A, 2=B,...26=Z），问有多少种不同的解码方法。举个栗子，“12”可以解码成“AB”（1和2）或者“L”（12），所以答案是2。

一开始我也被诱导着想用递归来解，毕竟你可以说，“前一个字符解不解我都可以试试嘛”，写起来大概是这样：

publicintnumDecodings(String s){
if (s == null || s.length() == 0) return0;
return decode(s, 0);
}

privateintdecode(String s, int index){
if (index == s.length()) return1;
if (s.charAt(index) == '0') return0;

int ways = decode(s, index + 1);
if (index + 1 < s.length()) {
int val = Integer.parseInt(s.substring(index, index + 2));
if (val <= 26) {
            ways += decode(s, index + 2);
        }
    }
return ways;
}

但，这么干你很快就会碰到运行时堆栈溢出，尤其是给你个"1111111111"这种输入，直接一脚把你踢进了超时地狱。

优化方案当然是用动态规划，毕竟重复子问题都摆在那了。我们可以搞一个 dp[i] 表示以第 i 个字符结尾的子串解码方式的总数，这种方式从逻辑上更清晰，性能上也更稳健：

publicintnumDecodings(String s){
if (s == null || s.length() == 0 || s.charAt(0) == '0') return0;
int n = s.length();
int[] dp = newint[n + 1];
    dp[0] = 1;
    dp[1] = 1;

for (int i = 2; i <= n; i++) {
int one = Integer.parseInt(s.substring(i - 1, i));
int two = Integer.parseInt(s.substring(i - 2, i));

if (one >= 1 && one <= 9) {
            dp[i] += dp[i - 1];
        }
if (two >= 10 && two <= 26) {
            dp[i] += dp[i - 2];
        }
    }
return dp[n];
}

这里面有几个小细节必须注意的，比如不能忽略掉前导0的情况。“06”是非法的，因为没有“0”开头的编码；再比如“10”虽然合法，但只能当作“J”处理，也就是说它不能拆成“1”和“0”两个部分来解。

说实话，这题最坑人的是那些 corner case，比如全是0的字符串，或者像“1001”这种中间掺了“死点”的。曾经有次面试我就是因为没考虑到这些情况，被面试官现场劈头盖脸教育了一顿，从此我每次写字符串解析的题目都像写遗嘱一样小心谨慎。

当然如果你是个极致的空间优化狂热者，还可以把dp数组压缩成两个变量滚动着来算，内存能省一点是一点嘛：

publicintnumDecodings(String s){
if (s == null || s.length() == 0 || s.charAt(0) == '0') return0;
int prev = 1, curr = 1;

for (int i = 1; i < s.length(); i++) {
int temp = 0;
if (s.charAt(i) != '0') {
            temp = curr;
        }
int twoDigit = Integer.parseInt(s.substring(i - 1, i + 1));
if (twoDigit >= 10 && twoDigit <= 26) {
            temp += prev;
        }
        prev = curr;
        curr = temp;
    }
return curr;
}

这种写法看起来简洁，但是对可读性要求比较高，尤其是你同事维护你代码时会一脸问号 😵‍💫，建议写清楚注释，否则回头谁踩坑谁知道。

你以为这题就到这了？还真不。很多人做这题是为了刷LeetCode，刷完就完了。但在真实项目里，字符串解析可是常客，比如短信指令、二维码编码、加密信息解码等，全是这套路。所以掌握这种带状态依赖的字符串分析技巧，其实是对你逻辑能力和代码组织能力的一次小考验。