亿点点震撼，Sora 会生成多机位视频！

OpenAI Sora 新进展

近日，OpenAI 科学家比尔·皮布尔斯（Bill Peebles）在 X（前推特）上发文称，Sora 可以同时生成多个并排在一起的视频，即多机位视频。

根据推文展示的动图，Sora 生成了 5 个人在下雪天漫步，以及玩雪的视频。

重点是：这是 Sora 一次性生成的视频，并非 5 个视频的拼接。

皮布尔斯在推文中称："Sora 决定同时拥有五个不同的视角。"

这无疑又是属于 OpenAI 的"亿点点震撼"。

可惜的是，目前 OpenAI 尚未向公众开放 Sora。

OpenAI 称，该模型正在接受测试，只分享给了一批精选的研究人员和学者，他们将研究 Sora，以寻找该模型被滥用的风险。

但随着 OpenAI 的多位高管在 X 中不断造势预热，我们有理由相信将来 Sora 和 ChatGPT 一样地面向大众，只是有限的时间问题。

...

回归主线。

相信今天绝大多数小伙伴都已经正式复工，那简单模拟题估计也不够大家醒脑（摸鱼）的了。

来一道热乎的，甚至还没来得及同步到 LeetCode 题解区的算法题。

题目描述

平台：LeetCode

题号：1253

给你一个 2 行 n 列的二进制数组：

• 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
• 第 0 行的元素之和为 upper。
• 第 1 行的元素之和为 lower。
• 第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。

如果有多个不同的答案，那么任意一个都可以通过本题。

如果不存在符合要求的答案，就请返回一个空的二维数组。

示例 1：

输入：upper = 2, lower = 1, colsum = [1,1,1]

输出：[[1,1,0],[0,0,1]]

解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。

示例 2：

输入：upper = 2, lower = 3, colsum = [2,2,1,1]

输出：[]

示例 3：

输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]

输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

提示：

• 1<=colsum.length<=1051 <= colsum.length <= 10^51<=colsum.length<=105
• 0<=upper,lower<=colsum.length0 <= upper, lower <= colsum.length0<=upper,lower<=colsum.length
• 0<=colsum[i]<=20 <= colsum[i] <= 20<=colsum[i]<=2

贪心 + 构造

创建数组 a 和 b 分别代表目标二进制矩阵的第 0 行和第 1 行。

从前往后处理 colsum，复用 upper 和 lower 分别代表两行剩余 111 的个数。

根据当前的 colsum[i]colsum[i]colsum[i] 进行分情况讨论：

• 若 colsum[i]=0colsum[i] = 0colsum[i]=0，只有一种情况，当前位置两行均为 000
• 若 colsum[i]=2colsum[i] = 2colsum[i]=2，只有一种情况，当前位置两行均为 111
• 若 colsum[i]=1colsum[i] = 1colsum[i]=1，选剩余 1 个数较大的行，填入 111，另外行则填入 000

若处理完 colsum 后，两行剩余 111 个数恰好均为 000，说明构造出了合法方案。

容易证明：不存在某个决策回合中，必须先填入剩余个数少的一方，才能顺利构造。

可用反证法进行证明，若存在某个回合必须填入剩余个数少的一方（假设该回合上填 1 下填 0），必然能够找到同为 colsum[j]=1colsum[j] = 1colsum[j]=1 的回合进行交换，同时不影响合法性（上下行的总和不变，同时 colsum[i]=colsum[j]=1colsum[i] = colsum[j] = 1colsum[i]=colsum[j]=1）。

Java 代码：

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int m = colsum[i];
            if (m == 0) {
                a.add(0); b.add(0);
            } else if (m == 2) {
                upper--; lower--;
                a.add(1); b.add(1);
            } else {
                if (upper >= lower) {
                    upper--;
                    a.add(1); b.add(0);
                } else {
                    lower--;
                    a.add(0); b.add(1);
                }
            }
        }
        if (upper == 0 && lower == 0) {
            ans.add(a); ans.add(b);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<vector<int>> ans;
        vector<int> a, b;
        for (int i = 0; i < n; i++) {
            int m = colsum[i];
            if (m == 0) {
                a.push_back(0); b.push_back(0);
            } else if (m == 2) {
                upper--; lower--;
                a.push_back(1); b.push_back(1);
            } else {
                if (upper >= lower) {
                    upper--;
                    a.push_back(1); b.push_back(0);
                } else {
                    lower--;
                    a.push_back(0); b.push_back(1);
                }
            }
        }
        if (upper == 0 && lower == 0) {
            ans.push_back(a); ans.push_back(b);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        n = len(colsum)
        ans = []
        a, b = [], []
        for i in range(n):
            m = colsum[i]
            if m == 0:
                a.append(0)
                b.append(0)
            elif m == 2:
                upper, lower = upper - 1, lower - 1
                a.append(1)
                b.append(1)
            else:
                a.append(1 if upper >= lower else 0)
                b.append(0 if upper >= lower else 1)
                if upper >= lower: upper -= 1
                else: lower -= 1
        if upper == lower == 0:
            ans.append(a)
            ans.append(b)
        return ans

TypeScript 代码：

function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
    const n = colsum.length;
    let ans: number[][] = [];
    let a: number[] = [], b: number[] = [];
    for (let i = 0; i < n; i++) {
        const m = colsum[i];
        if (m === 0) {
            a.push(0); b.push(0);
        } else if (m === 2) {
            upper--; lower--;
            a.push(1); b.push(1);
        } else {
            if (upper >= lower) {
                upper--;
                a.push(1); b.push(0);
            } else {
                lower--;
                a.push(0); b.push(1);
            }
        }
    }
    if (upper === 0 && lower === 0) {
        ans.push(a); ans.push(b);
    }
    return ans;
};

• 时间复杂度：O(C×n)O(C \times n)O(C×n)，其中 C=2C = 2C=2 代表行数
• 空间复杂度：O(C×n)O(C \times n)O(C×n)

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

欢迎关注，明天见。

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