【LeetCode 1143】最长公共子序列——C++利用new生成动态数组代替vector容器减少执行时间
2021/10/2 22:11:21
本文主要是介绍【LeetCode 1143】最长公共子序列——C++利用new生成动态数组代替vector容器减少执行时间,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、题目
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1:
输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 。
示例 2:
输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。
示例 3:
输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。
提示:
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解法
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); // vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); int** dp = new int*[m+1]; for (int i = 0; i < m+1; ++i) { dp[i] = new int[n + 1](); //初始化为0 } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (text1[i - 1] == text2[j - 1]) // 第i个元素在text1中的下标为i - 1 dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = dp[i][j - 1] > dp[i - 1][j] ? dp[i][j - 1] : dp[i - 1][j]; } } return dp[m][n]; } };
三、说明
注:28ms为使用vector容器生成二维动态数组dp,12ms为使用new生成二维动态数组dp
注意,dp[i] = new int[n + 1](); 是将一维数组初始化为0
C++初始化动态数组详情请见:C++动态数组初始化 -- new/delete_小肥羊快快跑-CSDN博客_c++动态数组初始化
这篇关于【LeetCode 1143】最长公共子序列——C++利用new生成动态数组代替vector容器减少执行时间的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08测试人员在 Scrum 中的角色是什么?
- 2024-07-07Dify + TiDB Vector,快速构建你的AI Agent
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享