本題為12月17日力扣每日一題
題目來源:力扣第1764題
題目tag:雙指標 kmp
題面
題目描述
給你一個長度為n的二維整數陣列groups，同時給你一個整數陣列nums，
你是否可以從nums中選出n個不相交的子陣列，使得第i個子陣列與groups[i]（下標從0開始）完全相同，且如果i>0，那么第(i-1)個子陣列在nums中出現的位置在第i個子陣列前面，（也就是說，這些子陣列在nums中出現的順序需要與groups順序相同）
如果你可以找出這樣的n個子陣列，請你回傳true，否則回傳false，
如果不存在下標為k的元素nums[k]屬于不止一個子陣列，就稱這些子陣列是不相交的，子陣列指的是原陣列中連續元素組成的一個序列，
示例
示例 1
輸入：
groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
輸出：
true
解釋：
你可以分別在 nums 中選出第 0 個子陣列 [1,-1,0,1,-1,-1,3,-2,0] 和第 1 個子陣列 [1,-1,0,1,-1,-1,3,-2,0] ，
這兩個子陣列是不相交的，因為它們沒有任何共同的元素，
示例 2
輸入：
groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
輸出：
false
解釋：
選擇子陣列 [1,2,3,4,10,-2] 和 [1,2,3,4,10,-2] 是不正確的，因為它們出現的順序與 groups 中順序不同，
[10,-2] 必須出現在 [1,2,3,4] 之前，
示例 3
輸入：
groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
輸出：
false
解釋：
選擇子陣列 [7,7,1,2,3,4,7,7] 和 [7,7,1,2,3,4,7,7] 是不正確的，因為它們不是不相交子陣列，
它們有一個共同的元素 nums[4] （下標從 0 開始），
提示
groups.length == n
1 <= n <= $ 10^3 $
1 <= groups[i].length, sum(groups[i].length) <= $ 10^3 $
1 <= nums.length <= $ 10^3 \(
\) -10^7 $ <= groups[i][j], nums[k] <= $ 10^7 $
思路分析
這題的題目翻譯過來就是,對nums陣列,挨個匹配二維陣列groups中的每一行,如果能全部匹配就是匹配成功,如果不能則為失敗.
再簡單一點說就是對nums陣列進行多次子串匹配,而子串匹配顯然可以直接使用kmp演算法來完成.由于本篇博客僅為題解,所以這里不對kmp演算法展開討論,如感興趣可以自行搜索學習,下面的參考代碼也不會對kmp演算法的部分進行注釋.
那如果不會kmp演算法怎么辦呢?這道題的資料量比較小,所以直接使用雙指標暴力比較也是可以的.kmp其實就是對下面這樣的暴力匹配的一種優化方案.
我們使用i指標指向nums,j指標指向groups,看看nums中以i指向的元素為開頭的子串,是否能和當前j指向的那行groups(下用group指代)匹配:
- 如果當前匹配,那就把i移動group的長度,然后j指向下一個group,繼續匹配.
- 如果不匹配,那就把i后移,匹配下一個子串.
如果最終j成功移到groups末尾,那證明groups中的所有group成功匹配,回傳true,否則證明其中存在group匹配失敗,那就回傳false.
參考代碼
雙指標暴力比較
class Solution
{
public:
bool canChoose(vector<vector<int>> &groups, vector<int> &nums)
{
int i = 0, j = 0; // i為nums上的指標,j為groups上的指標
while (i < nums.size() && j < groups.size())
{
if (equal(groups[j], nums, i)) // 如果當前從i開始的子串與當前對應的group匹配
{
i += groups[j].size(); // 跳過這些已匹配部分
j++; // 匹配下一個group
}
else // 當前未匹配
{
i++; // 從下一個開始繼續嘗試比較
}
}
return j == groups.size(); // 如果是因為j遍歷完畢而退出的回圈,就是匹配成功,否者就是匹配失敗
}
private:
// 比較nums中以start開頭的子串是否和group匹配
bool equal(vector<int> group, vector<int> nums, int start)
{
if (group.size() > nums.size() - start) // 當前nums子串的長度已不夠,必然不匹配
{
return false;
}
for (int i = 0; i < group.size(); i++) // 逐個遍歷即可
{
if (group[i] != nums[start + i])
{
return false;
}
}
return true;
}
};
kmp
class Solution
{
public:
bool canChoose(vector<vector<int>> &groups, vector<int> &nums)
{
int i = 0; // i為nums上的指標
for (int k = 0; k < groups.size(); k++)
{
int j = 0; // j為當前group上的指標
///////// kmp核心代碼 /////////
vector<int> next = getNext(groups[k]);
while (i < nums.size() && j < groups[k].size())
{
if (nums[i] == groups[k][j])
{
i++;
j++;
}
else if (next[j] != -1)
{
j = next[j];
}
else
{
i++;
}
}
///////// kmp核心代碼 /////////
if (j != groups[k].size()) // 當前串匹配失敗,則一定不匹配
{
return false;
}
}
return true;
}
private:
///////// kmp核心代碼 /////////
vector<int> getNext(vector<int> group)
{
vector<int> next(group.size(), -1);
if (group.size() == 1)
{
return next;
}
next[1] = 0;
int i = 2, cn = 0;
while (i < group.size())
{
if (group[i - 1] == group[cn])
{
next[i++] = ++cn;
}
else if (cn > 0)
{
cn = next[cn];
}
else
{
next[i++] = 0;
}
}
return next;
}
///////// kmp核心代碼 /////////
};
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/geministar/p/LeetCode1764.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540198.html
標籤：其他
上一篇：理解01背包的一維和二維
下一篇：Docker網路模式