作者推薦

【動(dòng)態(tài)規(guī)劃】【廣度優(yōu)先搜索】LeetCode:2617 網(wǎng)格圖中最少訪問(wèn)的格子數(shù)

本文涉及的知識(shí)點(diǎn)

單調(diào)棧

題目

給定長(zhǎng)度分別為 m 和 n 的兩個(gè)數(shù)組，其元素由 0-9 構(gòu)成，表示兩個(gè)自然數(shù)各位上的數(shù)字。現(xiàn)在從這兩個(gè)數(shù)組中選出 k (k <= m + n) 個(gè)數(shù)字拼接成一個(gè)新的數(shù)，要求從同一個(gè)數(shù)組中取出的數(shù)字保持其在原數(shù)組中的相對(duì)順序。
求滿足該條件的最大數(shù)。結(jié)果返回一個(gè)表示該最大數(shù)的長(zhǎng)度為 k 的數(shù)組。
說(shuō)明: 請(qǐng)盡可能地優(yōu)化你算法的時(shí)間和空間復(fù)雜度。
示例 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]

單調(diào)棧

時(shí)間復(fù)雜度: O(k(m+n+max(n,m)*max(n,m)))。枚舉m和n，時(shí)間復(fù)雜度O(k)。對(duì)于任意m,n組合，處理分如下四步：一，計(jì)算nums1的長(zhǎng)度為m的最大字典序子序列v1。二，計(jì)算nums2的長(zhǎng)度為n的最大字典序子序列v2。三，合并v1和v2到cur。四，比較cur和vRet大小。

對(duì)應(yīng)任意m,n只需要考慮最大字典序

假定最終結(jié)果中來(lái)自于nums1的元素組成的子序列不是最大字典序，換成最大字典序列。也符合題意，字典序不變或變大。

長(zhǎng)度為len的最大字典序

vVet[0,i]記錄長(zhǎng)度i+1的最大字典序子序列?？梢园裿Ret看成隊(duì)列，當(dāng)新元素大于隊(duì)尾元素時(shí)，替換隊(duì)尾元素，會(huì)形成新的最大子序列?？梢砸恢碧鎿Q指導(dǎo)隊(duì)尾元素大于等于當(dāng)前元素或隊(duì)列為空。這樣的問(wèn)題是vRet的長(zhǎng)度可能不為空，解決方法：

如果出隊(duì)后，剩余數(shù)字全部入隊(duì)，都無(wú)法讓vRet的長(zhǎng)度大于等于k	則不出隊(duì)
如果vRet.size()>=k	則不入隊(duì)

合并v1v2

我們把v1,v2看成隊(duì)列，每次只能取隊(duì)首。每次取兩個(gè)隊(duì)首的較大值，如果相等，則：
假定v1和v2有相同的前綴vPre，其長(zhǎng)度為len，假定v1的vPre后面是c，假定v2和vPre后面的d。選擇v1或v2，前l(fā)en個(gè)字符都可以相同。選擇v1，第len+1個(gè)字符可以是c，不能是d。選擇v2，第len+1個(gè)字符是d，不能是c。顯然c大，選擇v1；d大，選擇v2。我們來(lái)考慮特殊情況：

c和d不存在	v1和v2完全相同，選v1和v2的效果一樣
c存在，d不存在	為了len+1能選擇c，選擇v1
d存在，c不存在	為了len+1能選擇d,選擇v2

綜上所述：就是選擇字典序大的，可用lexicographical_compare 簡(jiǎn)化代碼。

代碼

核心代碼

class Solution {
public:vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {vector<int> 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;}vector<int> v1 = TopMax(nums1, len1);vector<int> v2 = TopMax(nums2, len2);vector<int> cur;int i1 = 0, i2 = 0;while ((i1 < v1.size()) && (i2 < v2.size())){auto Cmp = [&v1,&v2](int i1,int i2){		while((i1<v1.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;}vector<int> TopMax(const vector<int>& nums, int k){vector<int> 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;}
};

測(cè)試用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> 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(vector<int>{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(vector<int>{6, 7, 6, 0, 4}, res);}{Solution slu;nums1 = { 3, 9 };nums2 = { 8,9 };k = 3;auto res = slu.maxNumber(nums1, nums2, k);Assert(vector<int>{9, 8, 9}, res);}
}

簡(jiǎn)化后的代碼

class Solution {
public:vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {vector<int> 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;}vector<int> v1 = TopMax(nums1, len1);vector<int> v2 = TopMax(nums2, len2);vector<int> 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;}vector<int> TopMax(const vector<int>& nums, int k){vector<int> 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月

template<class 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) {
CTopK<int,std::greater> tok(k);
vector<vector> 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–)
{
CTopK<int, 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;
}
};

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡(jiǎn)單的課程，請(qǐng)移步CSDN學(xué)院，聽(tīng)白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請(qǐng)學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)

下載

想高屋建瓴的學(xué)習(xí)算法，請(qǐng)下載《喜缺全書算法冊(cè)》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想對(duì)大家說(shuō)的話
聞缺陷則喜是一個(gè)美好的愿望，早發(fā)現(xiàn)問(wèn)題，早修改問(wèn)題，給老板節(jié)約錢。
子墨子言之：事無(wú)終始，無(wú)務(wù)多業(yè)。也就是我們常說(shuō)的專業(yè)的人做專業(yè)的事。
如果程序是一條龍，那算法就是他的是睛

測(cè)試環(huán)境

操作系統(tǒng)：win7 開(kāi)發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開(kāi)發(fā)環(huán)境： VS2022 C++17
如無(wú)特殊說(shuō)明，本算法用**C++**實(shí)現(xiàn)。