程序员老鬼

昨天review代码,看到一哥们用极其风骚的stream流配合各种lambda表达式,把原本需要十行代码的逻辑,硬压缩成一行

刚看到个贴子,说有同事写代码非得追求“一行优雅”,结果 stream + lambda 玩得飞起,把十行逻辑压成一行,还配了个得意的注释。

Image

我觉得这事吧,问题的关键不是能不能写成一行,而是别人能不能看懂。写代码就像做饭,你搞得花里胡哨,摆盘是好看了,可要是没人能尝出味儿,意义在哪?网友们有的觉得这很酷,有的说这就是炫技,我更认同后者。代码是给人看的,再简短也要有可读性,不然维护的人头大,后续团队效率全掉。

换个角度想,写“聪明代码”图一时爽,但半年后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)。

  • 易错点:

  1. 重复值要用 2^f - 1 表示“至少选一个”的方案数。
  2. 断链分段别忘了乘进总答案再重置 DP。
  3. k==0 单独处理成乘 (f+1)。
  4. 结果可能很大,用 BigInteger 更稳;若题目要求取模,把乘加处换成取模即可。
  5. 是否包含空集?用 excludeEmpty 控制,想要非空答案就最后减一。

-END-

我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html

最后给大家分享一份不错的副业资料,点击下方公众号,回复关键字: 副业 领取,也可以链接我领取,微信:hls404