刷题交流｜一败涂地的「中年程序员」刷 leetcode的一些碎碎念，以及2023.01.22每日一题的另

14257

2023.01.26

发布于未知归属地

2023.01.22的每日一题1815. 得到新鲜甜甜圈的最多组数

失败的「中年人」刷leetcode的一些碎碎念
思路分析
动态规划：思路基于官解但不做状态压缩
参考灵佬的优化，但依然不状态压缩
1. 代码
2. 灵佬版题解和官解不一样的地方

失败的「中年人」刷leetcode的一些碎碎念

大过年的，但初二那天我突然又抑郁了，不是抑郁情绪，而是抑郁症的抑郁，那种会产生自我了结冲动的抑郁。诱因，是年 30 和大年初一的那两次周赛，打的稀碎，然后又遇上这道题。再加上过年没脸回家，北京过年点外卖又比较痛苦，凄惨的感觉突然就涌上心头，一下子就绷不住了。

这段时间，因为失业导致的中年危机，把自己关在屋子里，沉迷刷题三个月多月了，以至于连过年也都在刷。刷题确实让我分泌了一些多巴胺。

但是我内心一直清楚，普通的开发工作其实完全不用刷题的，日常用不到，面试也用不到。我真的只是逃避现实而已。当然，大厂除外。但大厂也不会要我的。此外，应届生也除外，但是我是中年人了。

我已经工作十年了，这十年可谓是兢兢业业，连身体也垮了。我是非科班自学转码，这十年间，只有上帝知道我付出了多少心血。我担任过创业公司的前端负责人，而且前后端皆通，自认为是为公司做出了很多贡献的。我开发的产品，也有过相当多的用户。如今因为公司倒闭，一朝失业，才发现了生活的可怕真相。

我属于内向的性格，对管理岗毫无兴趣，不想管人，也不想被人管。或许 34 岁没做到管理岗，真的废了，但是我好不甘心。在我的潜意识里，我真的可以做一辈子技术的。

大厂现在也不要我。因为我经历和性格的原因，我年轻时不是特别纠结进大厂，感觉只要技术到位，在任何地方踏踏实实的干，将来都不会愁工作的。这个错误的观念，导致我没有大厂镀金的经历，现在真的很被动。

面试的时候，有面试官甚至建议我去掉简历里后端的经验，只留下前端的，说这样会显得我不专一。我真的很困惑。

我现在去找纯前端的工作，发现要被年轻的面试官，问很多八股问题，以及一些花里胡哨的新概念。我承认，我老了，不是学不动了，而是真的不想学了，打心底里觉的无聊。无聊透顶。一些 google 能直接解决的问题，非要被面试官纠缠着反复问。前端，这 10 年真的挺能折腾的。但是不做前端，我还能做什么呢？

而且即便能找到工作，工资也会被砍去三分之一，这真的让我难以接受。

最可悲的是，我这几年，根本没关注市场上的工资情况。和猎头接触后，我才知道，以我的工作年限，我失业前的工资远远低于市场价。这让我更加被动。

去年，好不容易接到一个工资没降，但是五险一金按照最低标准来的口头offer，hr 说很快发正式邮件，我都准备第二周去上班了，但是最后被那家公司放了鸽子。

在那之后，我彻底不想找工作了，因为现在找工作，完全就是被羞辱的状态。

我对我的工作本身的意义，也产生了巨大的怀疑。互联网开发，大家其实都心知肚明，前端写页面，后端写接口，都是搬砖，没多少技术含量，写着写着人就废了。我做开发期间，担心这种结局，所以在 996 之余抓住一切机会，扩展额外的技能。我开发过公司用内部的前端框架，并且这个框架撑起了老板两家创业公司至少 6 年的前端稳定的运行。我也有很多业余项目，全栈我都能搞。然而，这并不能改变什么。我还是被现实打败了。

培训机构还在一批一批制造程序员，和你竞争。他们更年轻，更便宜。

人世间本质上是修罗场，疯狂竞争，残酷内卷，稍微停下，就会死的很难看。

我本科是学心理学的，我一直是一个好奇心很重的人，对宇宙，对意识，对命运，都是一样好奇。我曾经像司马迁一下，立志“究天人之际，通古今之变，成一家之言”。大学毕业时，我打算先工作 15 年，实现经济自由，解决生存问题，然后再去大学搞研究，研究我热爱的宇宙和意识。现在想来，我真的太天真了。本科学校不好，又天真地没有考研，真的是好被动好被动。

我是怎么接触计算机的呢？我一直对意识很好奇，想不通为什么没有生命的分子和原子，怎么就组装出了意识。大学学的虽然是心理学专业，但是解决不了我这个困惑。有一天我突发奇想：既然电脑和人脑都是脑，前者是人工的，后者是天然的，那我研究通了电脑，是不是就能理解意识了？

以此为契机，我接触了电脑，并且对强人工智能开始狂热。工作的这 10 年间，我也一直没放弃这方面的探索。因为这个执念，我有幸从事了 IT，但也正是因为这个执念，导致我错过了很多东西。

10 年前刚踏入前端界，我也很迷茫，我觉得这和我的终极目标强人工智能，毫无关系。但是迫于生存的压力，只能一边做前端，一边尝试学习人工智能。或许一开始这个决定就错了。现代社会真的只会让人变成螺丝钉和工作狂，学不完的新技术，加不完的班，只能让我在人工智能的边缘徘徊。加班久了以后，人会变木，激情也会褪色。我很痛苦。我知道结局，但是我无力改变。

这 10 年间，我也利用有限的业余时间，想系统地学习计算机和人工智能。但是发现 CS 考研的那四门专业课，以及前几年兴起的深度学习浪潮，都和我心心念念的强人工智能，几乎毫无关系。而且我也根本没有精力学习太多。每到周末，经常是躺在北京的出租屋里，两眼无神，一整天不下床，什么也不做，但累到麻木。

此外，因为原生家庭的原因，我很容易悲伤。这种悲伤是弥散性的，不是悲伤一会就会过去。每当悲伤袭来，内心就会像经历一场海啸，海啸过处，生机全无。其实我早就患上了严重的抑郁症，但是我不自知，或者说，我不愿意承认我有病。尽管我是学心理学出身的。疲惫、对一切失去兴趣、健忘，都是抑郁症的表现。

抑郁是一种疾病，需要吃药。不是矫情，而是科学。

但我把一切抑郁，归结为我我不够坚强，以及工作太累。

19 年初，因为各种原因，我感觉身体透支、精神透支，一分钟也不想不想工作了，只想找个没人的地方，静静地休息一段时间。当时，我依然是把一切归结于太累了，觉得自己调整调整就好。于是我离开了公司一年多，后来又回去了。期间我买了个很远的小城市的房子，装修了一番。装修真的很可怕，我本来打算调理身体，并理顺人生，结果都被装修吞没了。

再后来，疫情来了。

再后来，公司垮了。我们老板连续创业两次都失败了，也是可惜。同样可惜的，我有我的 10 年青春。

最可悲的是，为了摆脱困境，我尝试了以前绝对不会尝试的事：炒股+投资。然后，结果，你懂得。在尝试之前，我一直以为股票约等于赌博。可悲如我。或许投资有一天会回来，但是，我的心境却不会了。

我内心还藏着那个关于强人工智能的梦想，或者说，幻想。毕竟，我现在已经被重重摔落在了红尘里了。

我现在甚至害怕工作，就算找到工作，我也感到恐惧，恐惧和人说话，恐惧和新同事磨合。除了恐惧，还有无尽的乏味。前端那些折腾来折腾去的新玩意儿，真的让我乏味。

我不想继续南辕北辙，但是我毫无办法。

大概是因为过年，这个春节，北京点外卖像往年一样，又艰难了很多。悲凉感突然就再次袭来，让我陷入了更深的黑。这一次，我不想讳疾忌医了，我觉得我真的病了，我能感受到，这一次的抑郁发作，比任何以往一次都让我害怕。因为这一次，我真的产生了打开窗户跳下去的冲动。

当然，我不会真的跳的。悲伤泛滥过后，庆幸理智还在。我才 34 周岁，或者已经 35 了吧，懒得算了，总之，我还有后半生，我不能放弃。

我把如今的处境，归结为是个字：命苦 + 蠢。蠢占大头。

蠢是分多方面的：

没有考研，为了赚钱，直接远离了自己的兴趣和爱好：做研究。到了最后，离钱也越来越远。
发现前端和之际的理想南辕北辙，没有及时止损，而是被加班和生活裹挟，虚度了光阴。
没有考研，导致无论自己多么努力，都很难进大厂。学历歧视，一直都在。
性格孤傲，认为大厂俯视我，老子索性就不会伺候了。认为凭借一腔孤勇，在中场和小厂里，也能闯出一番天地。现实是：中小厂呆 10 年，最后自己只能是一只被拔完毛放进社会大铁锅里炖的公鸡。因为没还学历，进不了大厂，因为进不了大厂，产生不了光环和影响力，因为产生不了影响力，最后只能继续呆在小厂。完美闭环。
在自己工资最高的时候，选择了离职休息，没有再坚持一下，多攒点钱。
讳疾忌医，没有及时控制自己的抑郁症，导致严重影响了人生的节奏。可笑的是我还是学心理的。

我发现在 leetcode 刷题的很多人，都是在校大学生。我这个工作 10 年的失败中年男人，在这里格格不入。希望大家能吸取我的教训，珍惜大好光阴，并不要犯蠢。

但我会继续刷题的。我是非科班的，且一不小心人生 10 年就蒸发了。都10 年了，我才开始混迹 leetcode，和在校大学生一起刷本该属于计算机基础的《算法和数据结构》。可悲，可叹。

但是既然是基础，现在亡羊补牢还是有必要的。就算今年为了生活继续苟且，被迫继续做一份和算法毫无关系的开发工作，但是还是要补。何况，刷题可以分泌一些多巴胺，给生活找点乐趣。比如本文这道被我因为抑郁被搁置好几天的题，今晚又给我带来了一些快乐。

众生皆苦，生活很可怕，但是祝大家永不失业，永远快乐，永远不秃。

思路分析

对这道题，我的原始思路是，将 groups 被尽可能多地分成这样的组：组内的数字的和，可以整除 $ba t c h S i ze$ 。这样的组数，就是答案。

换句话说，将 groups 中的每个数模 $ba t c h S i ze$ ，然后尽可能多地划分成若干组，每组的和等于 $ba t c h S i ze$ 。

但是我绞尽脑汁，依然不知道如何划分。对于这种最值问题，我首先能想到的就是贪心和动态规划。我对动态规划，现在真的是望而生畏，每次都只能乖乖拜服于在各种神鬼莫测的状态转移方程下。

于是我看又看了官解。

等到过两天能喘口气了，是时候好好学习和总结一下各种不同种类的动态规划了。

动态规划：思路基于官解但不做状态压缩

官解详见这里：得到新鲜甜甜圈的最多组数。

官解果然用的动态规划，状态转移方程一如既往地让我拜服，好在这次并不难懂。但是官解中的一句话，把我吓坏了：

我们可以使用一个 9 维的数组进行上述的状态转移，但这样做显然会使得代码看起来非常混乱且不易维护。因此我们需要思考更好的解决方法。

好家伙，现在用来解释宇宙的超弦理论，也就是试图统一相对论和量子力学的那个凡人看不懂的高深理论，认为宇宙是由 $11$ 维的一些“弦”构成的。有那么一瞬间，我感觉这道题把 $ba t c h S i ze$ 调大 $2$ ，就可以和宇宙媲美，这逼格瞬间就上来了🤣。

为什么是 $9$ 维数组呢？因为任何数字模 $ba t c h S i ze$ 后，只有 $0, 1, 2, \dots, ba t c h S i ze - 1$ 这 $ba t c h S i ze$ 种可能，题目限制了 $ba t c h S i ze$ 最大为 $9$ 。所以在这道题中，动态规划的每个子问题（或者每个状态），都需要用 $9$ 个数来来描述。

刷题时，动态规划通常用数组而不是哈希表来储存子问题的值，是因为数组更底层，性能通常比哈希表更美丽。既然手动维护一个 $9$ 维数组很可怕，为什么不直接用哈希表来做呢？

可以将一个长度为 $9$ 的一维数组，作为哈希表的键。java 中，原始数组没有改写 Object的 hashCode方法，不能直接用，但是我们可以用动态数组 ArrayList。

再不济，还可以自己写一个类，来实现 $9$ 元组。

官解采用位运算进行状态压缩，是一种很棒的策略，但是这道题我的关注点在动态规划，我觉得用哈希表直接进行，会更加聚焦核心。而且理解这种思路后，会更容易理解状态压缩。

复杂度

复杂度分析的过程，和官解大体上是一致的。唯一的额外代价是，对哈希表 put和 get时会调用列表的hashCode方法，遍历一个长度为 9 的列表：

所以，依然可以期待和官解相同的渐进复杂度，只是高阶项的系数略大。

代码

/**
执行用时：564 ms, 在所有 Java 提交中击败了6.13%的用户
内存消耗：83.2 MB, 在所有 Java 提交中击败了5.11%的用户
通过测试用例：74 / 74

这个执行时间只是比官解的503ms 略长。
**/
class Solution {
    public int maxHappyGroups(int batchSize, int[] groups) {
        // 使用一个哈希表dp，做自上而下带缓存的动态规划。如果用数组，需要一个 9 维数组
        // 这个哈希表的键，是一个动态数组 list，其中list.get(i)代表了
        // groups 中模 batchSize后，等于 i 的数。
        // 之所以用动态数组，是因为 java 中的原始数组类，没有重写 hashCode 方法
        Map<List<Integer>, Integer> dp = new HashMap<>(); 
        
        // 构造动态规划的边界子问题，也就是可以直接求出值的子问题
        List<Integer> start = new ArrayList<>(batchSize);
        for(int i = 0; i < batchSize; i++)start.add(0);
        dp.put(start, 0);

        // 构造动态规划的的目标问题
        List<Integer> target = new ArrayList<>(batchSize);
        for(int i = 0; i < batchSize; i++)target.add(0);
        for(int g: groups){
            int index = g % batchSize;
            int value = target.get(index) + 1;
            target.set(index, value);
        }
        dfs(dp, target);
        return dp.get(target) + target.get(0);
    }

    public void dfs(Map<List<Integer>, Integer> dp, List<Integer> cntList){
        if(dp.containsKey(cntList))return;
        int n = cntList.size();
        int sum = 0;
        // 模batchsize 后为 0 的 数字，不参与动态规划的过程
        for(int i = 1; i < n; i++) sum += i * cntList.get(i);
        int ret = 0;
        for(int i = 1; i < n; i++){
            int cnt = cntList.get(i);
            if(cnt == 0)continue;
            List<Integer> sub = new ArrayList<>(cntList);
            sub.set(i, cnt - 1);
            dfs(dp, sub);
            int extra = (sum - i) % n == 0 ? 1 : 0;
            ret = Math.max(dp.get(sub) + extra, ret);
        }
        //System.out.printf("%s, %s\n", cntList, ret);
        dp.put(cntList, ret);
    }
}

子问题数量统计

简单地给上面的 dfs 方法加点统计，看看子问题被依赖了多少个，独立求解了多少个子问题：

用例：
9
[1,8,1,8,1,8,1,8,2,7,2,7,2,7,2,7,3,6,3,6,3,6,3,6,4,5,4,5,4,5]

输出：

总共调用了1575001次子问题, 总共求解了249999次子问题

对于这个用例，两个数字相差了 5 倍。避免反复求解相同的子问题，这就是动态规划的好处。

/**
用例：
9
[1,8,1,8,1,8,1,8,2,7,2,7,2,7,2,7,3,6,3,6,3,6,3,6,4,5,4,5,4,5]

输出：
总共调用了13次子问题, 总共求解了9次子问题
 */
class Solution {
    public int maxHappyGroups(int batchSize, int[] groups) {
        Map<List<Integer>, Integer> dp = new HashMap<>();
        List<Integer> start = new ArrayList<>(batchSize);
        for(int i = 0; i < batchSize; i++)start.add(0);
        dp.put(start, 0);

        List<Integer> target = new ArrayList<>(batchSize);
        for(int i = 0; i < batchSize; i++)target.add(0);
        for(int g: groups){
            int index = g % batchSize;
            int value = target.get(index) + 1;
            target.set(index, value);
        }
        int[] analysis = new int[2];
        dfs(dp, target, analysis);
        System.out.printf("总共调用了%s次子问题, 总共求解了%s次子问题\n", analysis[0], analysis[1]);
        return dp.get(target) + target.get(0);
    }

    public void dfs(Map<List<Integer>, Integer> dp, List<Integer> cntList, int[] arr){
        arr[0]++;
        if(dp.containsKey(cntList))return;
        int n = cntList.size();
        int sum = 0;
        for(int i = 1; i < n; i++) sum += i * cntList.get(i);
        int ret = 0;
        for(int i = 1; i < n; i++){
            int cnt = cntList.get(i);
            if(cnt == 0)continue;
            List<Integer> sub = new ArrayList<>(cntList);
            sub.set(i, cnt - 1);
            dfs(dp, sub, arr);
            int extra = (sum - i) % n == 0 ? 1 : 0;
            ret = Math.max(dp.get(sub) + extra, ret);
        }
        //System.out.printf("%s, %s\n", cntList, ret);
        arr[1]++;
        dp.put(cntList, ret);
    }

}

参考灵佬的优化，但依然不状态压缩

灵佬的题解中有下面的优化思路：

灵佬的题解：[位运算的魔法（Python/Java/C++/Go）]

利用这个思路，即便不进行状态压缩，也可以取得很好的效果，所以我尝试把前面的哈希表版改造了一下，但dp 的部分没有做任何更改，依然采用哈希表而不是状态压缩。可以看到，执行时间真的大幅度提升了：

代码

/**
执行用时：3 ms, 在所有 Java 提交中击败了86.30%的用户
内存消耗：40.8 MB, 在所有 Java 提交中击败了84.08%的用户
通过测试用例：74 / 74
 */
class Solution {
    public int maxHappyGroups(int batchSize, int[] groups) {
        Map<List<Integer>, Integer> dp = new HashMap<>();
        List<Integer> start = new ArrayList<>(batchSize);
        for(int i = 0; i < batchSize; i++)start.add(0);
        dp.put(start, 0);

        int ret = 0;
        List<Integer> target = new ArrayList<>(batchSize);
        for(int i = 0; i < batchSize; i++)target.add(0);
        for(int g: groups){
            int index = g % batchSize;
            int opIndex = batchSize - index;
            if(index == 0){
                ret++;
            }else if(target.get(opIndex) > 0){
                ret++;
                target.set(opIndex, target.get(opIndex) - 1);
            }else{
                target.set(index, target.get(index) + 1);
            }
        }
        dfs(dp, target);
        return ret + dp.get(target);
    }

    public void dfs(Map<List<Integer>, Integer> dp, List<Integer> cntList){
        if(dp.containsKey(cntList))return;
        int n = cntList.size();
        int sum = 0;
        for(int i = 1; i < n; i++) sum += i * cntList.get(i);
        int ret = 0;
        for(int i = 1; i < n; i++){
            int cnt = cntList.get(i);
            if(cnt == 0)continue;
            List<Integer> sub = new ArrayList<>(cntList);
            sub.set(i, cnt - 1);
            dfs(dp, sub);
            int extra = (sum - i) % n == 0 ? 1 : 0;
            ret = Math.max(dp.get(sub) + extra, ret);
        }
        //System.out.printf("%s, %s\n", cntList, ret);
        dp.put(cntList, ret);
    }
}

灵佬版题解和官解不一样的地方

阅读灵佬的题解时，我发现其状态转移时和官解略有不同。官解是判断转移前后是否同余，灵佬是将 left更新为 left + x + 1，尽管灵佬亲自下场解答了，但我现在也还没有理解这个点😭：

我决定先放过这个差别，先按照官解的思路进行状态转移。