DeepSeek V4，你可要好好治治它们
DeepSeek V4
今天是 DeepSeek V4 发布的日子。
其实 V4 要发布，很早就有消息传出了，甚至消息都精准到了四月下旬。
但今天正式发布，还是掀起了滔天巨浪。
这场震动，不止局限于技术圈，更是覆盖科技、资本、算力产业链的全方位引爆。
就拿股市来说好了，金融市场的内幕消息、聪明钱是最多的。
常规利好，往往会在落地前就被提前 price in、充分消化，真正官宣当日，反而容易利好兑现、资金出货走跌。
但 DeepSeek V4 不一样，即便消息早已提前泄露，今天寒武纪还是被直线拉升。
足以说明：这不是普通级别利好，而是实打实的核弹级产业催化。
超长上下文、百万级 1M 超长窗口、全维度模型能力全面迭代，都只是常规升级。
真正震慑整个 AI 行业、搅动市场的，还是 DeepSeek 一如既往的"价格屠夫"底色。
技术创新上，DeepSeek 通过在 token 维度进行压缩，结合 DSA 稀疏注意力，大幅降低计算和显存需求。
架构选择上，首次在官方文档中将「华为昇腾」和「英伟达」并列写入硬件验证清单，这说明国产芯片这条路是能完全走通的，而且足够支撑顶级开源模型的开发训练。
而且最最良心的，是 V4 没有藏着捏着，在公布的当天就直接宣布开源，而且给大家预告了，等到国产芯片批量上市，Pro 模型的 API 的价格，还会大幅下调。
反观某些国产模型：提价、限额、限速、限售，几乎什么当时承诺不会发生的事情都做了。
...
聊到这里，来一道和「智谱」不相关的算法题。
题目描述
平台：LeetCode
题号：1004
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
-
-
-
为 或
动态规划（TLE）
看到本题，其实首先想到的是 DP，但是 DP 是 算法。
看到了数据范围是 ，那么时空复杂度应该都是 。
空间可以通过「滚动数组」优化到 ，但时间无法优化，会超时。
「PS. 什么时候我们会用 DP 来解本题？通过如果 K 的数量级不超过 1000 的话，DP 应该是最常规的做法。」
定义 代表考虑前 个数（并以 为结尾的），最大翻转次数为 时，连续 的最大长度。
-
如果 本身就为 1 的话，无须消耗翻转次数， 。 -
如果 本身不为 1 的话，由于定义是必须以 为结尾，因此必须要选择翻转该位置， 。
Java 代码：
class Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length;
int[][] f = new int[2][k + 1];
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (nums[i - 1] == 1) {
f[i & 1][j] = f[(i - 1) & 1][j] + 1;
} else {
f[i & 1][j] = j == 0 ? 0 : f[(i - 1) & 1][j - 1] + 1;
}
ans = Math.max(ans, f[i & 1][j]);
}
}
return ans;
}
}
-
时间复杂度： -
空间复杂度：
前缀和 + 二分
从数据范围上分析，「平方级别」的算法过不了，往下优化就应该是「对数级别」的算法。
因此，很容易我们就会想到「二分」。
当然还需要我们对问题做一下等价变形。
最大替换次数不超过 k 次，可以将问题转换为找出连续一段区间 [l,r]，使得区间中出现 0 的次数不超过 k 次。
我们可以枚举区间 左端点/右端点 ，然后找到其满足「出现 0 的次数不超过 k 次」的最远右端点/最远左端点。
为了快速判断 [l,r] 之间出现 0 的个数，我们需要用到前缀和。
假设 [l,r] 的区间长度为 len，区间和为 tot，那么出现 0 的格式为 len - tol，再与 k 进行比较。
由于数组中不会出现负权值，因此前缀和数组具有「单调性」，那么必然满足「其中一段满足 ，另外一段不满足 」。
因此，对于某个确定的「左端点/右端点」而言，以「其最远右端点/最远左端点」为分割点的前缀和数轴，具有「二段性」。可以通过二分来找分割点。
Java 代码：
class Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length, ans = 0;
int[] sum = new int[n + 1];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (int i = 0; i < n; i++) {
int l = 0, r = i;
while (l < r) {
int mid = l + r >> 1;
if (check(sum, mid, i, k)) r = mid;
else l = mid + 1;
}
if (check(sum, r, i, k)) ans = Math.max(ans, i - r + 1);
}
return ans;
}
boolean check(int[] sum, int l, int r, int k) {
int tol = sum[r + 1] - sum[l], len = r - l + 1;
return len - tol <= k;
}
}
C++ 代码：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
vector<int> sum(n + 1, 0);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (int i = 0; i < n; i++) {
int l = 0, r = i;
while (l < r) {
int mid = l + r >> 1;
if (check(sum, mid, i, k)) r = mid;
else l = mid + 1;
}
if (check(sum, r, i, k)) ans = max(ans, i - r + 1);
}
return ans;
}
bool check(const vector<int>& sum, int l, int r, int k) {
int tol = sum[r + 1] - sum[l];
int len = r - l + 1;
return len - tol <= k;
}
};
Python 代码：
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
n, ans = len(nums), 0
sumv = [0] * (n + 1)
for i in range(1, n + 1):
sumv[i] = sumv[i - 1] + nums[i - 1]
for i in range(n):
l, r = 0, i
while l < r:
mid = l + r >> 1
if self.check(sumv, mid, i, k):
r = mid
else:
l = mid + 1
if self.check(sumv, l, i, k):
ans = max(ans, i - l + 1)
return ans
def check(self, sumv, l, r, k):
tol = sumv[r + 1] - sumv[l]
lenv = r - l + 1
return lenv - tol <= k
TypeScript 代码：
function check(sum: number[], l: number, r: number, k: number): boolean {
const tol = sum[r + 1] - sum[l];
const len = r - l + 1;
return len - tol <= k;
}
function longestOnes(nums: number[], k: number): number {
let n = nums.length, ans = 0;
const sum = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (let i = 0; i < n; i++) {
let l = 0, r = i;
while (l < r) {
let mid = l + r >> 1;
if (check(sum, mid, i, k)) r = mid;
else l = mid + 1;
}
if (check(sum, l, i, k)) ans = Math.max(ans, i - l + 1);
}
return ans;
};
-
时间复杂度： -
空间复杂度：
关于二分结束后再次 check 的说明：由于「二分」本质是找满足某个性质的分割点，通常我们的某个性质会是「非等值条件」，不一定会取得 =。
例如我们很熟悉的：从某个非递减数组中找目标值，找到返回下标，否则返回 -1。
当目标值不存在，「二分」找到的应该是数组内比目标值小或比目标值大的最接近的数。因此二分结束后先进行 check 再使用是一个好习惯。
双指针
由于我们总是比较 len、tot 和 k 三者的关系。
因此我们可以使用「滑动窗口」的思路，动态维护一个左右区间 [j, i] 和维护窗口内和 tot。
右端点一直右移，左端点在窗口不满足「len - tol <= k」的时候进行右移，即可做到线程扫描的复杂度。
Java 代码：
class Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length, ans = 0;
for (int i = 0, j = 0, tot = 0; i < n; i++) {
tot += nums[i];
while ((i - j + 1) - tot > k) tot -= nums[j++];
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
for (int i = 0, j = 0, tot = 0; i < n; i++) {
tot += nums[i];
while ((i - j + 1) - tot > k) tot -= nums[j++];
ans = max(ans, i - j + 1);
}
return ans;
}
};
Python 代码：
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
n, ans = len(nums), 0
j, tot = 0, 0
for i in range(n):
tot += nums[i]
while (i - j + 1) - tot > k:
tot -= nums[j]
j += 1
ans = max(ans, i - j + 1)
return ans
TypeScript 代码：
function longestOnes(nums: number[], k: number): number {
let n = nums.length, ans = 0;
for (let i = 0, j = 0, tot = 0; i < n; i++) {
tot += nums[i];
while ((i - j + 1) - tot > k) tot -= nums[j++];
ans = Math.max(ans, i - j + 1);
}
return ans;
};
-
时间复杂度： -
空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
本文由 mdnice 多平台发布
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
7
0- 0
已为社区贡献8条内容
所有评论(0)