不要认为996是开玩笑

996 预防针

随着秋招进程的不断推进，有部分同学已经 OC，有部分同学还在苦苦挣扎，并不断降低自己的预期，包括在和 HR 沟通过程中，主动说出自己愿意接受加班，愿意接受 996，以此来博得企业方面的加分。

我的建议是，不要这么做。

不要以为 996 是开玩笑。如果在工位上的时间都已经是 996，那么投入到这份工作上的时间只会更多。

应届生一般经济情况不算宽裕，直接住在公司边上的概率较低（园区附近房子租金较高），通勤时间就算半个小时吧，这意味着 8 点左右必须起床，8 点 30 必须出发，为了避免迟到，实际情况还会比这个时间点更早；晚上下班算你 9 点准时走，到家 9 点 30，基本洗漱结束后差不多就是 11 点了。可以说一天下来，娱乐和休息两者不可兼得。

更残忍的是，这样的节奏一周有 6 天，一周休息两天和休息一天体验上千差万别。双休本质上是有完全放松的一天（周六），但单休你只能抓紧时间休息，而不敢安排其他活动，因为你还要考虑第二天 8 点起床的问题。

这就是 996 作为日常的真实分析，而非停留在口号上的感受，没试过的东西，永远不要觉得自己能轻易承受。

再强调一遍：不要以为 996 是开玩笑，不要轻易将"愿意 996"挂在嘴边。可能原本你能进入一个作息正常的部门，但因为你主动强调自己接受 996，HR 会因此另外安排你去比较卷的部门，毕竟你自己说的愿意熬。

996 作为了一个出现了几年，但还在不断被提起的长青词，你真的体验过吗？你的工作时间是什么？你对 996 的看法又是什么？一起评论区交流呀。

...

回归主题。

来一道和「校招」相关的算法原题。

题目描述

平台：LeetCode

题号：368

给你一个由无重复正整数组成的集合 nums，请你找出并返回其中最大的整除子集 answer，子集中每一元素对 都应当满足：answer[i] % answer[j] = 0 或 answer[j] % answer[i] = 0。

如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

输入：nums = [1,2,3]

输出：[1,2]

解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]

输出：[1,2,4,8]

提示：

• nums 中的所有整数互不相同

基本分析

根据题意：「对于符合要求的「整除子集」中的任意两个值，必然满足「较大数」是「较小数」的倍数。」

数据范围是 ，我们不可能采取获取所有子集，再检查子集是否合法的爆搜解法。

通常「递归」做不了，我们就往「递推」方向去考虑。

「由于存在「整除子集」中任意两个值必然存在倍数/约数关系的性质，我们自然会想到对 nums 进行排序，然后从集合 nums 中从大到小进行取数，每次取数只考虑当前决策的数是否与「整除子集」中的最后一个数成倍数关系即可。」

这时候你可能会想枚举每个数作为「整除子集」的起点，然后从前往后遍历一遍，每次都将符合「与当前子集最后一个元素成倍数」关系的数加入答案。

举个🌰，假设有原数组 [1,2,4,8]，“或许”我们期望的决策过程是：

1. 遍历到数字 1，此时「整除子集」为空，加到「整除子集」中；
2. 遍历到数字 2，与「整除子集」的最后一个元素（ 1）成倍数关系，加到「整除子集」中；
3. 遍历到数字 4，与「整除子集」的最后一个元素（ 2）成倍数关系，自然也与 2 之前的元素成倍数关系，加到「整除子集」中；
4. 遍历到数字 8，与「整除子集」的最后一个元素（ 4）成倍数关系，自然也与 4 之前的元素成倍数关系，加到「整除子集」中。

「但这样的做法只能够确保得到「合法解」，无法确保得到的是「最长整除子集」」。

当时担心本题数据太弱，上述错误的解法也能够通过，所以还特意实现了一下，还好被卡住了（🤣

同时也得到这个反例：[9,18,54,90,108,180,360,540,720]，如果按照我们上述逻辑，我们得到的是 [9,18,54,108,540] 答案（长度为 5），但事实上存在更长的「整除子集」： [9,18,90,180,360,720]（长度为 6）。

「其本质是因为同一个数的不同倍数之间不存在必然的「倍数/约数关系」，而只存在「具有公约数」的性质，这会导致我们「模拟解法」错过最优解。」

比如上述 🌰，54 & 90 和 18 存在倍数关系，但两者本身不存在倍数关系。

因此当我们决策到某一个数 nums[i] 时（nums 已排好序），我们无法直接将 nums[i] 直接接在符合「约数关系」的、最靠近位置 i 的数后面，而是要「检查位置 i 前面的所有符合「约数关系」的位置，找一个已经形成「整除子集」长度最大的数」。

「换句话说，当我们对 nums 排好序并从前往后处理时，在处理到 nums[i] 时，我们希望知道位置 i 之前的下标已经形成的「整除子集」长度是多少，然后从中选一个最长的「整除子集」，将 nums[i] 接在后面（前提是符合「倍数关系」）。」

动态规划

基于上述分析，我们不难发现这其实是一个序列 DP 问题：「某个状态的转移依赖于与前一个状态的关系。即 nums[i] 能否接在 nums[j] 后面，取决于是否满足 nums[i] % nums[j] == 0 条件。」

可看做是「最长上升子序列」问题的变形题。

「定义 为考虑前 i 个数字，且以第 i 个数为结尾的最长「整除子集」长度。」

我们不失一般性的考虑任意位置 i，存在两种情况：

• 如果在 i 之前找不到符合条件 nums[i] % nums[j] == 0 的位置 j，那么 nums[i] 不能接在位置 i 之前的任何数的后面，只能自己独立作为「整除子集」的第一个数，此时状态转移方程为 ；
• 如果在 i 之前能够找到符合条件的位置 j，则取所有符合条件的 f[j] 的最大值，代表如果希望找到以 nums[i] 为结尾的最长「整除子集」，需要将 nums[i] 接到符合条件的最长的 nums[j] 后面，此时状态转移方程为 。

同时由于我们需要输出具体方案，需要额外使用 g[] 数组来记录每个状态是由哪个状态转移而来。

「定义 为记录 是由哪个下标的状态转移而来，如果 , 则有 。」

对于求方案数的题目，多开一个数组来记录状态从何转移而来是最常见的手段。

当我们求得所有的状态值之后，可以对 f[] 数组进行遍历，取得具体的最长「整除子集」长度和对应下标，然后使用 g[] 数组进行回溯，取得答案。

Java 代码：

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        for (int i = 0; i < n; i++) {
            // 至少包含自身一个数，因此起始长度为 1，由自身转移而来
            int len = 1, prev = i;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    // 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」
                    if (f[j] + 1 > len) {
                        len = f[j] + 1;
                        prev = j;
                    }
                }
            }
            // 记录「最终长度」&「从何转移而来」
            f[i] = len; g[i] = prev;
        }
        // 遍历所有的 f[i]，取得「最大长度」和「对应下标」
        int max = -1, idx = -1;
        for (int i = 0; i < n; i++) {
            if (f[i] > max) {
                idx = i;
                max = f[i];
            }
        }
        // 使用 g[] 数组回溯出具体方案
        List<Integer> ans = new ArrayList<>();
        while (ans.size() != max) {
            ans.add(nums[idx]);
            idx = g[idx];
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> f(n, 0), g(n, 0);
        for (int i = 0; i < n; i++) {
            int len = 1, prev = i;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (f[j] + 1 > len) {
                        len = f[j] + 1;
                        prev = j;
                    }
                }
            }
            f[i] = len; g[i] = prev;
        }
        int max = -1, idx = -1;
        for (int i = 0; i < n; i++) {
            if (f[i] > max) {
                max = f[i];
                idx = i;
            }
        }
        vector<int> ans;
        while (ans.size() != max) {
            ans.push_back(nums[idx]);
            idx = g[idx];
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        f, g = [0] * n, [0] * n
        for i in range(n):
            lenv, prev = 1, i
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if f[j] + 1 > lenv:
                        lenv, prev = f[j] + 1, j
            f[i], g[i] = lenv, prev
        maxv, idx = -1, -1
        for i in range(n):
            if f[i] > maxv:
                maxv, idx = f[i], i
        ans = []
        while len(ans) != maxv:
            ans.append(nums[idx])
            idx = g[idx]
        return ans

• 时间复杂度：
• 空间复杂度：

证明

「之所以上述解法能够成立，问题能够转化为「最长上升子序列（LIS）」问题进行求解，本质是利用了「全序关系」中的「可传递性」。」

在 LIS 问题中，我们是利用了「关系运算符 」的传递性，因此当我们某个数 a 能够接在 b 后面，只需要确保 成立，即可确保 a 大于等于 b 之前的所有值。

那么同理，如果我们想要上述解法成立，我们还需要证明如下内容：

「倍数/约数关系」具有传递性

由于我们将 nums[i] 往某个数字后面接时（假设为 nums[j]），只检查了其与 nums[j] 的关系，并没有去检查 nums[i] 与 nums[j] 之前的数值是否具有「倍数/约数关系」。

换句话说，我们只确保了最终答案 [a1, a2, a3, ..., an] 相邻两数值之间具有「倍数/约数关系」，并不明确任意两值之间具有「倍数/约数关系」。

因此需要证得由 和 ，可推导出 的传递性：

由 可得 由 可得

最终有 ，由于 和 都是整数，因此可得 。

得证「倍数/约数关系」具有传递性。

最后

巨划算的 LeetCode 会员优惠通道目前仍可用 ~

使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉