动态规划专练:力扣第1035、392题
力扣第1035题-不相交的线1.本题和力扣第1143题-最长公共子序列一模一样不能让线相交本质上就是不能走回头路相对顺序不能改变即公共子序列需要按顺序排列。完整代码如下1. int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size) { 2. // 一维滚动dp数组dp[j]表示nums1前i个数字、nums2前j个数字能绘制的最多不相交连线 3. int dp[nums2Size 1]; 4. memset(dp, 0, sizeof(dp)); 5. 6. for (int i 1; i nums1Size; i){ 7. // pre存储二维dp[i-1][j-1]的值即本轮更新前的dp[j-1] 8. int pre dp[0]; 9. for (int j 1; j nums2Size; j){ 10. // 保存更新前dp[j]作为下一轮j1的pre 11. int cur dp[j]; 12. if (nums1[i - 1] nums2[j - 1]){ 13. // 数字相等可以连线数量等于左上角状态1 14. dp[j] pre 1; 15. } else { 16. // 数字不等继承上方或左侧更大的连线数 17. dp[j] fmax(dp[j], dp[j - 1]); 18. } 19. pre cur; 20. } 21. } 22. 23. return dp[nums2Size]; 24. }该算法时间复杂度为O(nums1Size * nums2Size)空间复杂度为O(nums2Size)。力扣第392题-判断子序列1.可以使用双指针t的指针cur2一直1s的指针cur1只有在两个指针所指字符相等的时候才1最后如果cur1 len1就说明s是t的子集否则就不是。完整代码如下1. bool isSubsequence(char* s, char* t) { 2. int len1 strlen(s); 3. int len2 strlen(t); 4. // s长度大于t不可能是子序列 5. if (len1 len2) return false; 6. 7. // cur1s匹配指针cur2t遍历指针 8. int cur1 0, cur2 0; 9. while (cur1 len1 cur2 len2){ 10. // 字符匹配s指针后移 11. if (s[cur1] t[cur2]){ 12. cur1; 13. } 14. // t指针持续后移 15. cur2; 16. } 17. 18. // s全部匹配完成则为子序列 19. if (cur1 len1) return true; 20. return false; 21. }该算法时间复杂度为O(m n)空间复杂度为O(1)m和n为字符串s和t的长度。2.本题也可以使用动态规划本质上和力扣第1143题-最长公共子序列一模一样只不过字符串s一定不会删除字符。最后只需要判断dp[len2]是否等于len1即可判断是否全部匹配。完整代码如下1. bool isSubsequence(char* s, char* t) { 2. int len1 strlen(s); 3. int len2 strlen(t); 4. // s更长一定不可能是子序列直接返回false 5. if (len1 len2) return false; 6. 7. // 一维滚动dp数组dp[j]代表s前i个字符、t前j个字符的最长公共子序列长度 8. int dp[len2 1]; 9. memset(dp, 0, sizeof(dp)); 10. for (int i 1; i len1; i){ 11. // pre保存二维dp[i-1][j-1]更新前左上角的值 12. int pre dp[0]; 13. for (int j 1; j len2; j){ 14. // 记录更新前dp[j]作为下一轮j1的pre 15. int cur dp[j]; 16. if (s[i - 1] t[j - 1]){ 17. // 字符匹配公共子序列长度 左上角值 1 18. dp[j] pre 1; 19. } else { 20. // 字符不匹配取上方旧值或左侧新值较大者 21. dp[j] fmax(dp[j], dp[j - 1]); 22. } 23. pre cur; 24. } 25. } 26. // 若最长公共子序列长度等于s全长说明s是t的子序列 27. return dp[len2] len1; 28. }该算法时间复杂度为O(m * n)空间复杂度为O(n)。

相关新闻

动态规划专练:力扣第718、1143题

动态规划专练:力扣第718、1143题

力扣第718题-最长重复子数组1.本题是一道考察动态规划的经典问题,设置一个二维dp[nums1Size 1][nums2Size 1]数组,来记录长度为i的nums1和长度为j的nums2的最长公共子数组长度,元素初始化为0。当nums1[i - 1] nums2[j - 1]时说明当前元素相…

2026/11/20 6:30:29 阅读更多 →
从零开始玩转 klogg 日志查看器:30 分钟上手极速搜索与超大日志分析

从零开始玩转 klogg 日志查看器:30 分钟上手极速搜索与超大日志分析

从零开始玩转 klogg 日志查看器:30 分钟上手极速搜索与超大日志分析 【免费下载链接】klogg Really fast log explorer based on glogg project 项目地址: https://gitcode.com/gh_mirrors/kl/klogg 凌晨两点,监控大屏突然一片飘红。你哆嗦着把一…

2026/11/16 18:39:06 阅读更多 →
sys-con 手柄插件使用终极指南:免费让 Xbox 与 PlayStation 手柄在 Switch 上一步到位

sys-con 手柄插件使用终极指南:免费让 Xbox 与 PlayStation 手柄在 Switch 上一步到位

sys-con 手柄插件使用终极指南:免费让 Xbox 与 PlayStation 手柄在 Switch 上一步到位 【免费下载链接】sys-con Nintendo Switch sysmodule that allows support for third-party controllers 项目地址: https://gitcode.com/gh_mirrors/sy/sys-con 刚入坑 …

2026/11/19 13:12:03 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻