昨天review代码,看到一哥们用极其风骚的stream流配合各种lambda表达式,把原本需要十行代码的逻辑,硬压缩成一行
刚看到个贴子,说有同事写代码非得追求“一行优雅”,结果 stream + lambda 玩得飞起,把十行逻辑压成一行,还配了个得意的注释。
我觉得这事吧,问题的关键不是能不能写成一行,而是别人能不能看懂。写代码就像做饭,你搞得花里胡哨,摆盘是好看了,可要是没人能尝出味儿,意义在哪?网友们有的觉得这很酷,有的说这就是炫技,我更认同后者。代码是给人看的,再简短也要有可读性,不然维护的人头大,后续团队效率全掉。
换个角度想,写“聪明代码”图一时爽,但半年后debug的人流泪。真正的优雅,是让团队的人都能顺畅接手,而不是制造“谜语人”难题。说到底,工作不是秀个人技巧,而是合作交付结果。
总的来说,写代码别为炫技,能让大家都轻松才是真正的优雅。【备注:文末可领最新资料】
算法题:查找具有螺旋学习模式的学生
先把事儿说清:给你一个数组 nums 和整数 k。我们想数一数,有多少个子集,满足任意两数的差不等于 k。这种子集就叫 K-Free。空集要不要算?很多题默认算,我下面的代码给了个开关,爱算不算你自己定。
为啥分组?因为差值等于 k 的数,它们对 k 取模后余数一样。举个例子,k=3 时,像 1、4、7、10…(都 ≡1 mod 3)是一个“链”,这些数之间的冲突只发生在相邻相差 k 的那对,比如 1 和 4、4 和 7……不同余数组之间互不影响,可以各算各的,最后把结果相乘就行。
还有个细节:数组里可能有重复值。假设值 x 出现了 f 次,只要 k>0,你可以从这 f 个里随便挑(任意个都行),因为相同数字的差是 0,不会等于 k。所以对值 x 来说,“至少挑一个”的方案数是 2^f - 1,“一个都不挑”是 1。
把同余的一坨数按升序排成“链”(相邻差为 k 才有边),就变成了一个线性不相邻选点的问题(像在数轴上选点,不能选相邻点)。这玩意儿是经典的“打家劫舍”/斐波那契型 DP:
设
prev2是到前前个点的方案数,prev1是到前一个点的方案数。当前值出现
f次:不选它:贡献 prev1选它(至少选 1 个):贡献 (2^f - 1) * prev2合起来: curr = prev1 + (2^f - 1) * prev2遇到“断链”(相邻差大于
k)就把当前段的prev1乘进总答案,重新开一段。
特判 k == 0
如果 k==0,那就不能在子集中选两个相等的数。对每个不同的值,只有“选 0 个”或者“选 1 个”的选择,一共有 f+1 种(从 f 个里挑 1 个有 f 种,再加上不选)。最终答案就是所有 (f+1) 的乘积(空集自然包含在里面,想去掉就最后减 1)。
import java.math.BigInteger;
import java.util.*;
publicclassKFreeSubsets{
publicstatic BigInteger countKFreeSubsets(int[] nums, int k, boolean excludeEmpty){
// 按数值计数
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
// k==0 的特判:每个值只能取至多一个
if (k == 0) {
BigInteger ans = BigInteger.ONE;
for (int f : freq.values()) {
ans = ans.multiply(BigInteger.valueOf(f + 1L));
}
return excludeEmpty ? ans.subtract(BigInteger.ONE) : ans;
}
// 按余数分组
Map<Integer, List<Integer>> byRem = new HashMap<>();
for (int x : freq.keySet()) {
int r = mod(x, k);
byRem.computeIfAbsent(r, _ -> new ArrayList<>()).add(x);
}
BigInteger total = BigInteger.ONE;
for (List<Integer> group : byRem.values()) {
Collections.sort(group);
BigInteger segPrev2 = BigInteger.ONE; // 空段起点
BigInteger segPrev1 = BigInteger.ONE;
Integer last = null;
for (int val : group) {
if (last != null && val - last != k) {
// 断链:把上一段收尾
total = total.multiply(segPrev1);
segPrev2 = BigInteger.ONE;
segPrev1 = BigInteger.ONE;
}
int f = freq.get(val);
BigInteger pickAtLeastOne = BigInteger.ONE.shiftLeft(f).subtract(BigInteger.ONE); // 2^f - 1
BigInteger curr = segPrev1.add(segPrev2.multiply(pickAtLeastOne));
segPrev2 = segPrev1;
segPrev1 = curr;
last = val;
}
// 把最后一段乘进去
total = total.multiply(segPrev1);
}
return excludeEmpty ? total.subtract(BigInteger.ONE) : total;
}
privatestaticintmod(int a, int k){
int r = a % k;
return r >= 0 ? r : r + Math.abs(k);
}
// 小测一下
publicstaticvoidmain(String[] args){
int[] nums = {1,1,2,3,4,7,7,10};
int k = 3;
System.out.println(countKFreeSubsets(nums, k, false)); // 包含空集
System.out.println(countKFreeSubsets(nums, k, true)); // 不包含空集
}
}
复杂度:排序主导,按余数组分别排序,整体
O(n log n);空间O(n)。易错点:
重复值要用 2^f - 1表示“至少选一个”的方案数。断链分段别忘了乘进总答案再重置 DP。 k==0 单独处理成乘 (f+1)。结果可能很大,用 BigInteger更稳;若题目要求取模,把乘加处换成取模即可。是否包含空集?用 excludeEmpty控制,想要非空答案就最后减一。
-END-
我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html