从AI裁员杂谈到字节面试题：煎饼排序（LeetCode 969）详解

自从小龙虾（OpenClaw）爆火以来，关于AI导致裁员的讨论就愈发频繁。

这些消息真真假假，难以分辨。例如Meta（原Facebook）宣布裁员20%（约1.6万人），Block（原Square）裁员40%（约4000人），这些都是已经发生的真实案例。而像上周末传出的“飞书关闭武汉”，以及这两天热传的“网易裁撤所有外包”，则被证实为谣言。

一个有趣的现象是：海外的裁员消息往往为真，而我们这边的则常被“辟谣”。个中缘由，大家不妨自己琢磨，这似乎也“符合常识”。

眼下可能还不会出现大规模的“AI裁员”公告，但这绝不代表它不会发生。如果你还在问“AI裁员何时会轮到中国”，那可能意味着你离AI技术的实际影响还有点远，尚未看清它对生产力带来的巨大变革。

“何时轮到中国”本身或许就是个伪命题，因为这一进程早已开始，只是表现形式和节奏与美国有所不同。硅谷的裁员，更像是一种“预算挪移”，核心目的是将资金集中投入到算力采购和数据中心建设上。同时，为了维持财报的利润率，必须削减非核心业务（如招聘、中层管理、实验性项目）的人力成本，从而为AI基础设施腾出资金。

而在国内，情况则更偏向于实实在在的“降本增效”。AI在某些领域（如游戏美术、广告设计）已经能够有效替代人力，其应用势头甚至比美国更为迅猛。因此，与其在听到每一次AI裁员“辟谣”后长舒一口气，陷入隐形的焦虑，不如冷静下来，审视一下自己当前的工作是否具有高度的“机械化”或“标准化”特性，并为此提前做好打算。

聊到这里，我们不妨来看一道与「字节跳动」相关的算法题，它出现在许多技术面试中。

题目描述

平台：LeetCode
题号：969

给你一个整数数组 arr，请使用煎饼翻转完成对数组的排序。

一次煎饼翻转的执行过程如下：

• 选择一个整数 k，
• 反转子数组 arr[0...k-1]（下标从 0 开始）

例如，arr = [3,2,1,4]，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

示例 1：

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 arr = [3, 2, 4, 1]
第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。

示例 2：

输入：[1,2,3]
输出：[]
解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。

提示：

• 1 <= arr.length <= 100
• 1 <= arr[i] <= arr.length
• arr 中的所有整数互不相同（即 arr 是从 1 到 arr.length 整数的一个排列）

冒泡排序思路

由于每次操作都是对「某段前缀」进行整体翻转，并且题目规定了在合理范围内的翻转方案均为有效，同时数组 arr 又是 1 到 arr.length 的一个排列。

我们可以很自然地联想到「冒泡排序」的思路：每次确定未排序部分最右端的元素（即当前最大值）。

具体来说，假设下标 [i + 1, n - 1] 部分已经有序，如果我们希望当前最大值 i+1 (数值为 i+1 的元素) 出现在位置 i 上，可以进行的操作如下：

1. 如果当前值已在位置 i 上，则无须进行任何操作。
2. 如果当前值不在位置 i 上，则根据其当前位置进行分情况讨论：
   • 当前值在数组头部（下标为 0）：直接将 [0...i] 部分进行翻转（将 i+1 加入答案中），即可将该值放到位置 i 上。
   • 当前值不在数组头部，而是在位置 idx 上：需要先将 [0...idx] 部分进行翻转（将 idx+1 加入答案中），这样使得当前值被翻转到数组头部（下标为 0）；然后再将 [0...i] 部分进行翻转（将 i+1 加入答案中），即可将该值放到位置 i 上。

而翻转某个前缀的操作可以使用「双指针」轻松实现，复杂度为 O(n)。

Java 代码：

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        int[] idxs = new int[n + 10];
        for (int i = 0; i < n; i++) idxs[arr[i]] = i;
        List<Integer> ans = new ArrayList<>();
        for (int i = n; i >= 1; i--) {
            int idx = idxs[i];
            if (idx == i - 1) continue;
            if (idx != 0) {
                ans.add(idx + 1);
                reverse(arr, 0, idx, idxs);
            }
            ans.add(i);
            reverse(arr, 0, i - 1, idxs);
        }
        return ans;
    }
    void reverse(int[] arr, int i, int j, int[] idxs) {
        while (i < j) {
            idxs[arr[i]] = j; idxs[arr[j]] = i;
            int c = arr[i];
            arr[i++] = arr[j];
            arr[j--] = c;
        }
    }
}

C++ 代码：

class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        int n = arr.size();
        vector<int> idxs(n + 10);
        for (int i = 0; i < n; i++) idxs[arr[i]] = i;
        vector<int> ans;
        for (int i = n; i >= 1; i--) {
            int idx = idxs[i];
            if (idx == i - 1) continue;
            if (idx != 0) {
                ans.push_back(idx + 1);
                reverse(arr, 0, idx, idxs);
            }
            ans.push_back(i);
            reverse(arr, 0, i - 1, idxs);
        }
        return ans;
    }
    void reverse(vector<int>& arr, int i, int j, vector<int>& idxs) {
        while (i < j) {
            idxs[arr[i]] = j; idxs[arr[j]] = i;
            int c = arr[i];
            arr[i++] = arr[j];
            arr[j--] = c;
        }
    }
};

Python 代码：

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        n = len(arr)
        idxs = [0] * (n + 10)
        for i in range(n):
            idxs[arr[i]] = i
        ans = []
        for i in range(n, 0, -1):
            idx = idxs[i]
            if idx == i - 1:
                continue
            if idx != 0:
                ans.append(idx + 1)
                self.reverse(arr, 0, idx, idxs)
            ans.append(i)
            self.reverse(arr, 0, i - 1, idxs)
        return ans

    def reverse(self, arr: list[int], i: int, j: int, idxs: list[int]) -> None:
        while i < j:
            idxs[arr[i]], idxs[arr[j]] = j, i
            c = arr[i]
            arr[i], arr[j] = arr[j], c
            i, j = i + 1, j - 1

TypeScript 代码：

function reverse(arr: number[], i: number, j: number, idxs: number[]): void {
    while (i < j) {
        idxs[arr[i]] = j;
        idxs[arr[j]] = i;
        const c = arr[i];
        arr[i++] = arr[j];
        arr[j--] = c;
    }
}

function pancakeSort(arr: number[]): number[] {
    const n = arr.length;
    const idxs = Array.from({ length: n }, () => 0);
    for (let i = 0; i < n; i++) idxs[arr[i]] = i;
    const ans = [];
    for (let i = n; i >= 1; i--) {
        const idx: number = idxs[i];
        if (idx === i - 1) continue;
        if (idx !== 0) {
            ans.push(idx + 1);
            reverse(arr, 0, idx, idxs);
        }
        ans.push(i);
        reverse(arr, 0, i - 1, idxs);
    }
    return ans;
};

• 时间复杂度：需要对 n 个元素进行排序，每个元素最多触发两次翻转，每次翻转的复杂度为 O(n)。整体复杂度为 O(n²)。
• 空间复杂度：O(n)，用于存储索引数组。

最后

无论是面对AI带来的职业变局，还是在技术面试中应对算法挑战，持续学习和深入理解核心原理总是关键。这道“煎饼排序”题很好地考察了我们对基础算法的理解和灵活应用能力。如果你对这类面试求职中的算法问题感兴趣，或者想与更多开发者交流技术心得，欢迎来云栈社区一起探讨。