字节面试官让候选人闭眼答题：761.特殊二进制序列的排序构造解法

AI 作弊

昨天我们聊到大厂对于 AI 作弊零容忍，一旦发现就会永不录用。

评论区一位小伙伴的留言差点让我笑出声：

他建议候选人带上镜子面试，这样能通过摄像头看到候选人的视觉镜像。

带着好奇心，我去脉脉看了一下，目前常见的“防 AI 作弊手段”有哪些。

最朴素的，还是那个“随时闭眼回答问题”模式。

当然，除了这些“物理隔离”手段，更多公司开始在技术层面加码。

例如全程录屏加录脸，过程中除了传统的屏幕检测，还会做实时候选人眼球跟踪检测。

甚至在面试结束后，会把录屏后的代码回放再交给 AI，进一步判定编码过程中的停顿、复制粘贴行为是否存在使用 AI 的痕迹。

这已经不只是一场猫鼠游戏，而是纯粹的攻防战了 😂。

AI 虽然很强，但更适合用来好好学习。劝大家别动歪脑筋拿它作弊，单纯靠 AI 作弊进大厂，难度非常高。

面试通常有多轮，很难每一轮都靠作弊蒙混过去。稍微逻辑清晰的面试官，如果感觉候选人表现有异样，现场改题或者调整边界条件，AI 作弊往往很难立刻响应。

骗来的 offer 就像借来的钱，迟早要连本带利还回去。

你怎么看？你身边有靠 AI 作弊进大厂的人吗？欢迎聊聊。

题目描述

平台：LeetCode

题号：761

特殊的二进制序列，是同时具备以下两个性质的二进制序列：

• 0 的数量与 1 的数量相等。
• 二进制序列的每一个前缀码中，1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。

定义一个操作为：首先选择 S 的两个连续且非空的特殊子串，然后将它们交换。两个子串为连续的，当且仅当第一个子串的最后一个字符，恰好是第二个子串第一个字符的前一个字符。

在任意次数的操作之后，交换后的字符串按字典序排列得到的最大结果是什么？

示例 1:

输入: S = "11011000"

输出: "11100100"

解释:
将子串 "10"（在S[1]出现） 和 "1100"（在S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

说明:

• S 的长度不超过 50。
• S 保证为一个满足上述定义的特殊二进制序列。

构造

我们可以定义每个字符的得分：字符 1 得分为 1 分，字符 0 得分为 -1 分。

根据题目对“特殊字符串”的定义可知，给定字符串 s 的总得分为 0，且任意前缀串不会出现得分为负数的情况。

考虑将 s 划分成多个足够小的特殊字符串 item。所谓“足够小”，就是每个 item 无法再继续划分。每个 item 的总得分都是 0。根据 s 的定义，必然可以恰好划分成多个 item。

每次操作都可以交换相邻的特殊字符串，于是问题就转换为：将 s 进行重排，求重排后字典序最大的方案。

首先要证明一个合法 item 必然满足 1...0 的形式，这里可以用反证法说明：item 的总得分为 0，且长度不为 0，因此必然既有 1 又有 0。如果第一位字符是 0，就必然能从第一位字符作为起点，找到一个得分为负数的子串，这与 s 本身定义冲突，因为 s 中不存在得分为负数的前缀串；如果最后一位是 1，根据 item 总得分为 0，可知当前 item 去掉最后一位后得分为负，同样与 s 本身定义冲突。

因此可以将构造拆成两步：

1. 对每个 item 进行重排，使其调整为字典序最大。
2. 对 item 之间的顺序进行重排，使整体字典序最大。

由于题目没有规定重排后仍必须保持特殊串性质，为了让第一步调整和第二步调整相对独立，我们只能对 item 中 1...0 的非边缘部分进行调整，也就是递归处理中间子串部分。

假设所有 item 都已经处理完毕，接下来考虑如何重排才能让最终方案字典序最大。

若有两个 item，分别为 a 和 b，我们可以根据拼接结果 ab 和 ba 的字典序大小，来决定把谁放在前面。

这样基于“排序比较逻辑”，还需要证明它在集合上具有“全序关系”。

我们使用符号 @ 来代指这种“排序”逻辑：

• 如果 a 必须排在 b 的前面，我们记作 a@b；
• 如果 a 必须排在 b 的后面，我们记作 b@a；
• 如果 a 既可以排在 b 的前面，也可以排在 b 的后面，我们记作 a#b。

2.1 完全性

具有完全性，是指从集合 items 中任意取出两个元素 a 和 b，必然满足 a@b、b@a 和 a#b 三者之一。

这一点其实不需要额外证明。因为由 a 和 b 拼接得到的字符串 ab 与 ba，在字典序大小关系中，要么完全相等，要么存在明确的字典序大小关系，从而决定 a 必须排在前面或后面。

2.2 反对称性

具有反对称性，是指由 a@b 和 b@a 能够推导出 a#b。

a@b 说明字符串 ab 的字典序大小，要比字符串 ba 的字典序大小大。

b@a 则说明字符串 ba 的字典序大小，要比字符串 ab 的字典序大小大。

这样，基于“字典序本身满足全序关系”以及数学上“大于且小于可推导出相等”，就能得证 a@b 和 b@a 能够推导出 a#b。

2.3 传递性

具有传递性，是指由 a@b 和 b@c 能够推导出 a@c。

我们可以利用“两个等长的拼接字符串，字典序大小关系与数值大小关系一致”这一性质来证明，因为字符串 ab 和 ba 必然是等长的。

接下来，让我们从“自定义排序逻辑”出发，换个思路来证明 a@c：

然后，我们只需要证明在不同的 i、j 关系之间，共三种情况下，a@c 都恒成立即可：

1. 当 i == j 的时候：

2. 当 i > j 的时候：

3. 当 i < j 的时候：

综上，我们证明了无论在何种情况下，只要有 a@b 和 b@c，那么 a@c 恒成立。

我们之所以能这样证明“传递性”，本质是利用了自定义排序逻辑中一个重要性质：确定任意元素 a 和 b 之间的排序关系，只依赖于它们第一个不同元素之间的大小关系。

最终，我们证明了该“排序比较逻辑”必然能排出字典序最大的方案。

Java 代码：

class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() == 0) return s;
        List<String> list = new ArrayList<>();
        char[] cs = s.toCharArray();
        for (int i = 0, j = 0, k = 0; i < cs.length; i++) {
            k += cs[i] == '1' ? 1 : -1;
            if (k == 0) {
                list.add("1" + makeLargestSpecial(s.substring(j + 1, i)) + "0");
                j = i + 1;
            }
        }
        Collections.sort(list, (a, b)->(b + a).compareTo(a + b));
        StringBuilder sb = new StringBuilder();
        for (String str : list) sb.append(str);
        return sb.toString();
    }
}

C++ 代码：

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s.empty()) return s;
        vector<string> list;
        for (int i = 0, j = 0, k = 0; i < s.length(); i++) {
            k += s[i] == '1' ? 1 : -1;
            if (k == 0) {
                list.push_back("1" + makeLargestSpecial(s.substr(j + 1, i - j - 1)) + "0");
                j = i + 1;
            }
        }
        sort(list.begin(), list.end(), [](const string &a, const string &b) {
            return (b + a).compare(a + b) < 0;
        });
        string result;
        for (const string &str : list) result += str;
        return result;
    }
};

TypeScript 代码：

function makeLargestSpecial(s: string): string {
    const list = new Array<string>()
    for (let i = 0, j = 0, k = 0; i < s.length; i++) {
        k += s[i] == '1' ? 1 : -1
        if (k == 0) {
            list.push('1' + makeLargestSpecial(s.substring(j + 1, i)) + '0')
            j = i + 1
        }
    }
    list.sort((a, b)=>(b + a).localeCompare(a + b));
    return [...list].join("")
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

最后

这道题最有趣的地方，不只是“闭眼防作弊”的段子，而是它背后涉及的递归拆分与自定义排序关系。对这类字符串字典序重排问题感兴趣的话，可以继续看看 面试求职 里的算法题解与八股文整理。

对于题解本身，LeetCode 761 其实很适合用来练习字符串递归和排序比较器设计。类似的排序比较逻辑也常见于 算法/数据结构 中的排序、字符串与递归题型。