C++ 最长公共子数组
2022/1/1 11:07:17
本文主要是介绍C++ 最长公共子数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
//给定两个整数数组,求两个数组的最长的公共子数组的长度。子数组是连续的,比如[1, 3, 5, 7, 9]的子数组有[1, 3],[3, 5, 7]等等,但是[1, 3, 7]不是子数组 //数据范围:两个数组的长度都满足1-1000,数组中的值都满足0-100 //关键是动态规划,本例子优化了缓冲的大小,但还是没有最优化 //缓冲最优化需要比较alen和blen,取小的为缓冲 int longestCommonSubarry(vector<int>& A, vector<int>& B) { int alen = A.size(); int blen = B.size(); //前半是保存该行迭代的结果,后半保存上一行迭代结果的缓冲 vector<int> buff(blen, 0);//由于第一次行迭代没有上一行,所以都为0 int leftTop = 0;//保留上一行,上一列的长度 int maxV = 0;//当前最大长度 for (int row = 0; row < alen; ++row) { leftTop = 0;//每行开头没有前一列,所以为0 for (int col = 0; col < blen; ++col) { if (A[row] == B[col]) { int temp = leftTop + 1; leftTop = buff[col];//保留上一行,上一列的长度 buff[col] = temp; if (temp > maxV) maxV = temp; } else { leftTop = buff[col];//保留上一行,上一列的长度 buff[col] = 0; } } } return maxV; }
解析:
这篇关于C++ 最长公共子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享