某大厂员工爆料：我们技术总监，40岁，是行业里公认的大牛。他立了个规矩:周3定为不加雷打不动，号召大家下班去生活，拒绝无效忙碌
老鬼约 3 分钟刚刷到这个爆料，某大厂网友说，他们的技术总监，40岁，是行业里公认的大牛。他立了个规矩:周3定为不加雷打不动，号召大家下班去生活，拒绝无效忙碌
这个就挺狠的，因为很多公司最怕的不是没效率，是没人表演忙。灯亮着、电脑开着、群里有动静，好像公司就运转得特别努力。
其实一堆人坐那儿耗着，脑子早糊了，代码写不动，方案想不出，就剩个“我还在”的姿态。
这个总监讨厌的估计就是这种无效忙碌。
周三不加班，听着像福利，实际是在提醒大家，别把上班过成一种慢性消耗。
面试题：最优除法
看到“最优除法”这题，我第一反应不是写 DP。
这种题很容易把人带沟里：一看到括号、一看到最大值，就开始想区间 DP，dp[i][j] 存最大最小值。能做，但有点重。面试里真这么写，代码一长，边界一多，自己先把自己绕晕。
题目大概是这样：
给一个正整数数组，比如：
[1000, 100, 10, 2]
数字顺序不能变，只能在除法表达式里加括号，让结果最大。
比如：
1000/(100/10/2)
这个值就比：
1000/100/10/2
大很多。
这里有个地方要盯住：除法想变大，要么分子变大，要么分母变小。
第一个数一定在最前面，它基本就是大分子：
nums[0] / 后面那坨
所以问题变成了：怎么让后面那坨尽量小。
后面是：
nums[1] / nums[2] / nums[3] / ...
如果不加括号，就是一路往左算，分母其实没被压到最小。
但只要这样放：
nums[0] / (nums[1] / nums[2] / nums[3] / ...)
括号里的值会变成：
nums[1] / nums[2] / nums[3] / ...
因为除以后面的数，会越来越小。外层再拿 nums[0] 去除这个很小的数，结果自然最大。
拿刚才的例子看：
1000/(100/10/2)
括号里：
100/10/2 = 5
最后结果：
1000/5 = 200
如果老老实实不加括号：
1000/100/10/2 = 0.5
差得不是一点点。
这题真正要写代码的时候，别搞花活。就三个分支：
classSolution{
public String optimalDivision(int[] nums){
int n = nums.length;
if (n == 1) {
return String.valueOf(nums[0]);
}
if (n == 2) {
return nums[0] + "/" + nums[1];
}
StringBuilder exp = new StringBuilder();
exp.append(nums[0]).append("/(");
for (int i = 1; i < n; i++) {
if (i > 1) {
exp.append("/");
}
exp.append(nums[i]);
}
exp.append(")");
return exp.toString();
}
}
这里我一般会特意把 n == 1 和 n == 2 单独拎出来。
不是为了显得严谨，是因为括号不能乱加。
只有一个数时：
5
不能写成别的。
两个数时：
5/2
也不需要括号，写成：
5/(2)
虽然数学上没错，但题目通常要的是最简表达式，这种多余括号就别给自己找事。
三个数以上才是固定套路：
a/(b/c/d/e)
这块有个坑，很多人会下意识写成：
a/((b/c)/d)
这个其实和括号里正常从左到右算是一样的，没有改变结构。题目要的是把 b 后面的所有数都放到除数链里，让 b 被连续除下去。
也就是说，最关键的一刀是外层括号：
nums[0] / (nums[1] / nums[2] / ... / nums[n-1])
不是每两个数之间瞎套括号。
这题如果用 DP，当然也能算出最大值和最小值，再记录表达式。但你想想，输入全是正数，顺序又不能变，除法结构还固定，最后规律已经这么明显了，再用 DP 就像查一个慢 SQL，执行计划都摆脸上了，你还去翻业务代码。
没必要。
复杂度也很干净，遍历一遍数组拼字符串：
时间复杂度：O(n)
空间复杂度：O(n)
空间主要花在返回的表达式上。
所以这题别被“最优”两个字吓住。真正的最优不是把所有括号试一遍，而是看清楚第一个数的位置不能动，后面整体都在当分母。把分母压到最小，答案就出来了。