科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文围绕 LeetCode 960「删除列以使其有序 III」展开完整讲解如何把删除最少列、使每一行字符串按字典序非递减的问题转化为求解最多能保留多少列的 LIS最长递增子序列问题并给出 Python / Java / C / C / Go / JavaScript / Rust 七种语言的完整实现与复杂度分析。同时结合算法竞赛模板库 codeforces-go 仓库中 Go 实现 与其测试用例说明这一 DP 套路在实际竞赛模板库中是如何落地与验证的。读完本文你将掌握列视角 LIS 化这一解决二维数组删列问题的通用思考框架。一、题目理解删除列让每一行都字典序非递减LeetCode 960 题目简述给定由若干长度相同的字符串组成的数组strs可以删除其中若干列任意列均可删除删除后各行的字符会被拼接起来要求最终每一行字符串都是字典序非递减的求最少删除多少列。题目之所以是III是因为 LeetCode 还包含两道同系列但限制更严格的题目删除列以使其有序 I / II而本题不要求各行的字典序一致只要求每一行自身非递减因此解法的自由度更高也更有意思。先看仓库中 d_test.go 里收录的三组官方样例输入strs输出最少删除列数[babca,bbazb]3[edcba]4[ghi,def,abc]0第三组样例中每一行本身已完全递增一列都不需要删第二组只有单行edcba严格递减最多保留 1 列故删除5 - 1 4列。二、核心思路把删除改成保留退化成 LIS删多少列不好直接想但删除最少列与保留最多列是同一枚硬币的两面最少删除列数 总列数m− 最多可保留列数那么问题就变成在m列中选出一个尽可能长的列序列子序列不要求连续使得每一行的这些列拼起来都是字典序非递减的。特例n 1时就是经典 LIS当strs只有一行n 1时问题退化为在单个字符串中选一个最长子序列使其字典序非递减。这正是允许相邻元素相等的 300. 最长递增子序列——两者一脉相承。这也是本题最重要的启示行数n 1时是否还能用同样的枚举选哪个的 DP 套路答案是肯定的只需把 300 题的两两比较大小推广成逐行比较整列即可。三、DP 设计与转移方程状态定义设共有m列m len(strs[0])定义f[i]每个保留的子序列都以第i列结尾时最多能保留的列数。f数组的语义与 300 题中dp[i]以i结尾的最长递增子序列长度完全对应只是把单元素大小比较换成了整列逐行比较。转移枚举倒数第二列j枚举子序列的倒数第二列j0 ≤ j i如果对于每一行j列的字母都不超过i列的字母即满足s[j] s[i]那么j列的序列之后可以合法地接上i列用f[j] 1来更新f[i]的最大值若j列与i列之间不满足该条件则不能衔接。代码实现上有一个常用技巧先用f[j]更新f[i]的最大值整个内层循环结束后再统一f[i] 1。这样就把空序列 只选i列自己单独形成长为 1 的子序列的情况天然包含了进去因为所有f初始为 01后至少为 1。此外内层循环还做了一次剪枝if f[j] f[i] lessEq(j, i) { f[i] f[j] }当f[j] f[i]时即使j, i两列可以衔接更新后也不会让f[i]变大因此可以跳过这次需要遍历全部n行的lessEq检查从而省下不少常数时间。答案设m为列数max(f)为最长可保留列数则最少删除列数 m - max(f)四、七种语言完整实现Python 3class Solution: def minDeletionSize(self, strs: List[str]) - int: m len(strs[0]) f [0] * m for i in range(m): for j in range(i): # 如果 f[j] f[i]就不用跑 O(n) 的 all 了 if f[j] f[i] and all(s[j] s[i] for s in strs): f[i] f[j] f[i] 1 return m - max(f)Javaclass Solution { public int minDeletionSize(String[] strs) { int m strs[0].length(); int[] f new int[m]; int maxF 0; for (int i 0; i m; i) { for (int j 0; j i; j) { // 如果 f[j] f[i]就不用跑 O(n) 的 lessEq 了 if (f[j] f[i] lessEq(strs, j, i)) { f[i] f[j]; } } f[i]; maxF Math.max(maxF, f[i]); } return m - maxF; } // 对于每一行j 列的字母都 i 列的字母 private boolean lessEq(String[] strs, int j, int i) { for (String s : strs) { if (s.charAt(j) s.charAt(i)) { return false; } } return true; } }Cclass Solution { public: int minDeletionSize(vectorstring strs) { // 对于每一行j 列的字母都 i 列的字母 auto less_eq - bool { for (auto s : strs) { if (s[j] s[i]) { return false; } } return true; }; int m strs[0].size(); vectorint f(m); for (int i 0; i m; i) { for (int j 0; j i; j) { // 如果 f[j] f[i]就不用跑 O(n) 的 less_eq 了 if (f[j] f[i] less_eq(j, i)) { f[i] f[j]; } } f[i]; } return m - ranges::max(f); } };C#define MAX(a, b) ((b) (a) ? (b) : (a)) int minDeletionSize(char** strs, int strsSize) { // 对于每一行j 列的字母都 i 列的字母 bool less_eq(int j, int i) { for (int k 0; k strsSize; k) { if (strs[k][j] strs[k][i]) { return false; } } return true; } int m strlen(strs[0]); int* f calloc(m, sizeof(int)); int max_f 0; for (int i 0; i m; i) { for (int j 0; j i; j) { // 如果 f[j] f[i]就不用跑 O(n) 的 less_eq 了 if (f[j] f[i] less_eq(j, i)) { f[i] f[j]; } } f[i]; max_f MAX(max_f, f[i]); } free(f); return m - max_f; }Go与仓库 d.go 一致func minDeletionSize(strs []string) int { // 对于每一行j 列的字母都 i 列的字母 lessEq : func(j, i int) bool { for _, s : range strs { if s[j] s[i] { return false } } return true } m : len(strs[0]) f : make([]int, m) for i : range m { for j : range i { // 如果 f[j] f[i]就不用跑 O(n) 的 lessEq 了 if f[j] f[i] lessEq(j, i) { f[i] f[j] } } f[i] } return m - slices.Max(f) }这里用到了 Go 标准库slices.MaxGo 1.21来求f的最大值其余逻辑与其它语言版本完全同构。JavaScriptvar minDeletionSize function(strs) { // 对于每一行j 列的字母都 i 列的字母 function lessEq(j, i) { for (const s of strs) { if (s[j] s[i]) { return false; } } return true; } const m strs[0].length; const f Array(m).fill(0); for (let i 0; i m; i) { for (let j 0; j i; j) { // 如果 f[j] f[i]就不用跑 O(n) 的 lessEq 了 if (f[j] f[i] lessEq(j, i)) { f[i] f[j]; } } f[i]; } return m - Math.max(...f); };Rustimpl Solution { pub fn min_deletion_size(strs: VecString) - i32 { let m strs[0].len(); let mut f vec![0; m]; for i in 0..m { for j in 0..i { // 如果 f[j] f[i]就不用跑 O(n) 的 all 了 if f[j] f[i] strs.iter().all(|s| s.as_bytes()[j] s.as_bytes()[i]) { f[i] f[j]; } } f[i] 1; } m as i32 - *f.iter().max().unwrap() } }五、复杂度分析时间复杂度O(n·m²)。外层枚举i、内层枚举j共m²/2对组合每对组合的最坏情况要逐行比较n个字符n len(strs)m len(strs[0])。加上f[j] f[i]就跳过检查的剪枝平均实际开销通常更低。空间复杂度O(m)仅需要一个长度为m的f数组。六、仓库实战Go 实现与测试框架1. 算法实现文件本题的 Go 解法收录在 leetcode/weekly/115/d/d.go对应 LeetCode 第 115 场周赛的 D 题即 960 号题。实现完全遵循上述先取f[j]最大值、循环结束后统一1的写法并以注释保留了核心判断条件对于每一行j列的字母都 i列的字母方便后续复习时秒懂题意与做法。2. 测试用例文件leetcode/weekly/115/d/d_test.go 是由copypasta/template/leetcode/generator_test.go自动生成的测试文件内嵌三组官方示例输入 期望输出并通过 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithExamples驱动执行examples : [][]string{ {[babca,bbazb], 3}, {[edcba], 4}, {[ghi,def,abc], 0}, // TODO 测试入参最小的情况 } targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithExamples(t, minDeletionSize, examples, targetCaseNum); err ! nil { t.Fatal(err) }用仓库测试框架跑一遍即可得到结论三组样例全部通过且三组样例恰好覆盖了三种典型形态——需要删除多列3、单行递减串、最多只留 1 列4、完全有序无需删除0。从源码结构看targetCaseNum参数支持两种用法0表示全量运行所有用例可附带超时检测-1表示只跑最后一个用例便于本地调试。3. 测试框架如何工作RunLeetCodeFuncWithExamples实现位置的核心机制是反射调用它读取被测试函数的签名入参个数fNumIn、出参个数fNumOut把字符串形式的输入输出解析成对应类型的reflect.Value数组、字符串、整数等解析细节见 parseRawArray再调用fValue.Call(ins)执行并比对结果。这一设计让同一套测试代码可以复用于仓库里成百上千道 LeetCode 题解且对超长输入会自动截断显示、在DebugTLE开启时还能做超时检测。4. 测试文件与示例数据是怎么生成的copypasta/template/leetcode/generator.go 展示了仓库的周赛代码生成工作流writeTestFile负责按固定模板生成xxx_test.go调用RunLeetCodeFuncWithFile读取外部.txt数据文件writeTestDataFile负责把抓取到的官方样例p.sampleIns/p.sampleOuts落盘成xxx.txt。也就是说周赛结束后只需运行生成器就能批量得到题解 自动测试的完整骨架后续再人工补齐实现即可——这也是该仓库能持续沉淀数千道题解的重要原因。七、总结与延伸一句话记住本题套路先想最多保留多少列再把逐列比较推广成逐行比较整列最后套用 LIS 的O(m²)DP 模板答案是m - max(f)。与经典题的关系n 1时本题即允许相等的 300 题最长递增子序列n 1时只是把单字符比较升级为整列向量逐分量比较思维模型完全复用。延伸训练方向本题属于动态规划中最长递增子序列LIS大类的变形应用相关专题还包括基于数据结构树状数组/线段树优化的 LIS、二维 LIS最长递增子序列套娃、以及删列使其有序 I/II系列题想系统刷 LIS 系列可重点练习状态定义中以某个元素结尾与枚举前驱j这两种基本套路。从删除列到保留列从字符比较到整列比较——这道题把 LIS 的思想移植到了二维数组上是一道非常适合用来巩固状态定义 枚举前驱 剪枝三位一体 DP 功力的中等偏上难度题。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐OptiScaler任何游戏都能用上 FSR4 和帧生成吗超分替换完全指南OptiScaler任何游戏都能用上 FSR4 和帧生成吗超分替换完全指南 OptiScaler 是一款开源的超分辨率替换工具把游戏里原生的 DLSS /图形学游戏开发CLRS 15.4 习题精讲最长公共子序列LCS与最长递增子序列LIS的动态规划算法CLRS 15.4 习题精讲最长公共子序列LCS与最长递增子序列LIS的动态规划算法 本文围绕《算法导论》Introduction to Algor文档教程示例工程Karpenter NodePool 完全指南基于 karpenter-provider-aws 的节点池配置、调度约束与资源管控Karpenter NodePool 完全指南基于 karpenter provider aws 的节点池配置、调度约束与资源管控 NodePool 是 Ka科学计算上一篇Switch 手柄看B站wiliwili 跨平台B站客户端上手记下一篇typescript-eslint 文档写作规范如何编写可验证、自包含、经得起审查的文档创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考