html商业网站模板,云南 房地产网站建设,购物商城网站搭建,义乌网站建设方案详细作者推荐
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
本文涉及的知识点
单调栈
题目
给定长度分别为 m 和 n 的两个数组#xff0c;其元素由 0-9 构成#xff0c;表示两个自然数各位上的数字。现在从这两个数组中选出 k (k m n) 个数字…作者推荐
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
本文涉及的知识点
单调栈
题目
给定长度分别为 m 和 n 的两个数组其元素由 0-9 构成表示两个自然数各位上的数字。现在从这两个数组中选出 k (k m n) 个数字拼接成一个新的数要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。 说明: 请尽可能地优化你算法的时间和空间复杂度。 示例 1: 输入: nums1 [3, 4, 6, 5] nums2 [9, 1, 2, 5, 8, 3] k 5 输出: [9, 8, 6, 5, 3] 示例 2: 输入: nums1 [6, 7] nums2 [6, 0, 4] k 5 输出: [6, 7, 6, 0, 4] 示例 3: 输入: nums1 [3, 9] nums2 [8, 9] k 3 输出: [9, 8, 9]
单调栈
时间复杂度: O(k(mnmax(n,m)*max(n,m)))。枚举m和n时间复杂度O(k)。对于任意m,n组合处理分如下四步一计算nums1的长度为m的最大字典序子序列v1。二计算nums2的长度为n的最大字典序子序列v2。三合并v1和v2到cur。四比较cur和vRet大小。
对应任意m,n只需要考虑最大字典序
假定最终结果中来自于nums1的元素组成的子序列不是最大字典序换成最大字典序列。也符合题意字典序不变或变大。
长度为len的最大字典序
vVet[0,i]记录长度i1的最大字典序子序列。可以把vRet看成队列当新元素大于队尾元素时替换队尾元素会形成新的最大子序列。可以一直替换指导队尾元素大于等于当前元素或队列为空。这样的问题是vRet的长度可能不为空解决方法
如果出队后剩余数字全部入队都无法让vRet的长度大于等于k则不出队如果vRet.size()k则不入队
合并v1v2
我们把v1,v2看成队列每次只能取队首。每次取两个队首的较大值如果相等则 假定v1和v2有相同的前缀vPre其长度为len假定v1的vPre后面是c假定v2和vPre后面的d。选择v1或v2前len个字符都可以相同。选择v1第len1个字符可以是c不能是d。选择v2第len1个字符是d不能是c。显然c大选择v1d大选择v2。我们来考虑特殊情况
c和d不存在v1和v2完全相同选v1和v2的效果一样c存在d不存在为了len1能选择c选择v1d存在c不存在为了len1能选择d,选择v2
综上所述就是选择字典序大的可用lexicographical_compare 简化代码。
代码
核心代码
class Solution {
public:vectorint maxNumber(vectorint nums1, vectorint nums2, int k) {vectorint vRet(k);for (int len1 0; len1 min((int)nums1.size(), k); len1){const int len2 k - len1;if (len2 nums2.size()){continue;}if (len2 0){break;}vectorint v1 TopMax(nums1, len1);vectorint v2 TopMax(nums2, len2);vectorint cur;int i1 0, i2 0;while ((i1 v1.size()) (i2 v2.size())){auto Cmp [v1,v2](int i1,int i2){ while((i1v1.size())(i2 v2.size())){const int iCmp v1[i1] - v2[i2];if (iCmp 0 ){return true;;}else if (iCmp 0){return false;}i1;i2;} return i1 v1.size();};if (Cmp(i1,i2)){cur.emplace_back(v1[i1]);}else{cur.emplace_back(v2[i2]);}}cur.insert(cur.end(), v1.begin() i1, v1.end());cur.insert(cur.end(), v2.begin() i2, v2.end());vRet max(cur, vRet);}return vRet;}vectorint TopMax(const vectorint nums, int k){vectorint ret;for (int i 0; i nums.size(); i){while (ret.size() (ret.back() nums[i]) (ret.size() nums.size() - i k)){ret.pop_back();}if (ret.size() k){ret.emplace_back(nums[i]);}}return ret;}
};测试用例
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorint nums1, nums2;int k;{Solution slu; nums1 { 3, 4, 6, 5 };nums2 { 9, 1, 2, 5, 8, 3 };k 5;auto res slu.maxNumber(nums1, nums2, k);Assert(vectorint{9, 8, 6, 5, 3}, res);}{Solution slu;nums1 { 6, 7 };nums2 { 6, 0, 4 };k 5;auto res slu.maxNumber(nums1, nums2, k);Assert(vectorint{6, 7, 6, 0, 4}, res);}{Solution slu;nums1 { 3, 9 };nums2 { 8,9 };k 3;auto res slu.maxNumber(nums1, nums2, k);Assert(vectorint{9, 8, 9}, res);}
}简化后的代码
class Solution {
public:vectorint maxNumber(vectorint nums1, vectorint nums2, int k) {vectorint vRet(k);for (int len1 0; len1 min((int)nums1.size(), k); len1){const int len2 k - len1;if (len2 nums2.size()){continue;}if (len2 0){break;}vectorint v1 TopMax(nums1, len1);vectorint v2 TopMax(nums2, len2);vectorint cur;auto it1 v1.begin();auto it2 v2.begin();for (;(it1 ! v1.end()) (it2 ! v2.end());){ if (lexicographical_compare(it1,v1.end(),it2,v2.end())){cur.emplace_back(*it2);}else{cur.emplace_back(*it1);} }cur.insert(cur.end(), it1, v1.end());cur.insert(cur.end(), it2, v2.end());vRet max(cur, vRet);}return vRet;}vectorint TopMax(const vectorint nums, int k){vectorint ret;for (int i 0; i nums.size(); i){while (ret.size() (ret.back() nums[i]) (ret.size() nums.size() - i k)){ret.pop_back();}if (ret.size() k){ret.emplace_back(nums[i]);}}return ret;}
};2023年3月
class Solution { public: vector maxNumber(vector nums1, vector nums2, int k) { vector vRet; for (int iLeft 0; iLeft k; iLeft) { const vector v1 maxNumber(nums1, iLeft); const vector v2 maxNumber(nums2, k - iLeft); if (v1.size() v2.size() ! k) { continue; } vector nums; auto it1 v1.begin(); auto it2 v2.begin(); while ((it1 ! v1.end() ) (it2 ! v2.end() )) { if (*it1 *it2 ) { nums.push_back(*it1); it1; } else if(*it1 *it2) { nums.push_back(*it2); it2; } else { if (Less(it1, v1.end(), it2, v2.end())) { nums.push_back(*it2); it2; } else { nums.push_back(*it1); it1; } } } std::copy(it1, v1.end(), std::back_inserter(nums)); std::copy(it2, v2.end(), std::back_inserter(nums)); if ((vRet.size() 0) || Less(vRet,nums)) { vRet.swap(nums); } } return vRet; } template bool Less(IT itBegin1, IT itEnd1, IT itBegin2, IT itEnd2) { while ((itBegin1 ! itEnd1) (itBegin2 ! itEnd2)) { if (*itBegin1 *itBegin2) { return true; } else if (*itBegin1 *itBegin2) { return false; } itBegin1; itBegin2; } return itBegin1 itEnd1; } bool Less(const vector v1, const vector v2) { for (int i 0; i v1.size(); i) { if (v1[i] v2[i]) { return true; } else if (v1[i] v2[i]) { return false; } } return false; } vector maxNumber(const vector nums, int k) { vector ret; for (int i 0; i nums.size(); i) { const int n nums[i]; while (ret.size() (n ret.back()) ((ret.size() nums.size() - i - 1) k)) { ret.pop_back(); } if (ret.size() k) { ret.push_back(n); } } return ret; } };
2023 年8月
templateclass T int,class _Pr std::less class CTopK { public: CTopK(int k):m_iMinNum(k) { } void Do(vector m_v,T* begin, int num) { for (; num ; begin,num–) { while (m_v.size() _Pr()( *begin, m_v.back()) (m_iMinNum - m_v.size()1 num)) { m_v.pop_back(); } if (m_v.size() m_iMinNum) { m_v.push_back(*begin); } } } protected: const int m_iMinNum; };
class Solution { public: vector maxNumber(vector nums1, vector nums2, int k) { CTopKint,std::greater tok(k); vectorvector vNums1(k 1), vNums2(k 1); tok.Do(vNums1[k], nums1.data(), nums1.size()); tok.Do(vNums2[k], nums2.data(), nums2.size()); for (int i k - 1; i 0; i–) { CTopKint, std::greater tok(i); tok.Do(vNums1[i], vNums1[i 1].data(), vNums1[i 1].size()); tok.Do(vNums2[i], vNums2[i 1].data(), vNums2[i 1].size()); } vector vRet(k); for (int i max(0,k-(int)nums2.size()); i min(k,(int)nums1.size()); i) { const auto v1 vNums1[i]; const auto v2 vNums2[k - i]; vector cur; auto it v1.begin(); auto ij v2.begin(); while ((it ! v1.end()) || (ij ! v2.end())) { bool b lexicographical_compare(it, v1.end(), ij, v2.end()); if (b) { cur.emplace_back((ij)); } else { cur.emplace_back((it)); } } if (cur vRet) { vRet.swap(cur); } } return vRet; } }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
