作者推薦
動態規劃的時間復雜度優化
本文涉及知識點
深度優先搜索
LeetCode2003. 每棵子樹內缺失的最小基因值
有一棵根節點為 0 的 家族樹 ，總共包含 n 個節點，節點編號為 0 到 n - 1 。給你一個下標從 0 開始的整數數組 parents ，其中 parents[i] 是節點 i 的父節點。由于節點 0 是 根 ，所以 parents[0] == -1 。
總共有 105 個基因值，每個基因值都用 閉區間 [1, 105] 中的一個整數表示。給你一個下標從 0 開始的整數數組 nums ，其中 nums[i] 是節點 i 的基因值，且基因值 互不相同 。
請你返回一個數組 ans ，長度為 n ，其中 ans[i] 是以節點 i 為根的子樹內 缺失 的 最小 基因值。
節點 x 為根的 子樹 包含節點 x 和它所有的 后代 節點。
示例 1：
輸入：parents = [-1,0,0,2], nums = [1,2,3,4]
輸出：[5,1,1,1]
解釋：每個子樹答案計算結果如下：
- 0：子樹包含節點 [0,1,2,3] ，基因值分別為 [1,2,3,4] 。5 是缺失的最小基因值。
- 1：子樹只包含節點 1 ，基因值為 2 。1 是缺失的最小基因值。
- 2：子樹包含節點 [2,3] ，基因值分別為 [3,4] 。1 是缺失的最小基因值。
- 3：子樹只包含節點 3 ，基因值為 4 。1是缺失的最小基因值。
示例 2：
輸入：parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
輸出：[7,1,1,4,2,1]
解釋：每個子樹答案計算結果如下：
- 0：子樹內包含節點 [0,1,2,3,4,5] ，基因值分別為 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1：子樹內包含節點 [1,2] ，基因值分別為 [4,6] 。 1 是缺失的最小基因值。
- 2：子樹內只包含節點 2 ，基因值為 6 。1 是缺失的最小基因值。
- 3：子樹內包含節點 [3,4,5] ，基因值分別為 [2,1,3] 。4 是缺失的最小基因值。
- 4：子樹內只包含節點 4 ，基因值為 1 。2 是缺失的最小基因值。
- 5：子樹內只包含節點 5 ，基因值為 3 。1 是缺失的最小基因值。
示例 3：
輸入：parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
輸出：[1,1,1,1,1,1,1]
解釋：所有子樹都缺失基因值 1 。
提示：
n == parents.length == nums.length
2 <= n <= 105
對于 i != 0 ，滿足 0 <= parents[i] <= n - 1
parents[0] == -1
parents 表示一棵合法的樹。
1 <= nums[i] <= 105
nums[i] 互不相同。
深度優先搜索
除了基因1的節點及它的祖先，其它節點都缺少1。
DFS(cur)結束時，處理了且只處理了它哥哥及自己的后代，如果我們將基因1及其祖先調整成長子。可以將空間復雜從O(nlogn)降低到O(n)。
注意：如果不優化，空間復雜度是O(nn)，就是直接為每個節點分配空間，復制所有的后代。極端情況下，獨子樹的空間復雜度是O(nn)。直接用子樹的空間，獨子樹空間復雜度O(n)；非獨子樹O(nlong)。
超時代碼
class CParentToNeiBo
{
public:CParentToNeiBo(const vector<int>& parents){m_vNeiBo.resize(parents.size());for (int i = 0; i < parents.size(); i++){if (-1 == parents[i]){m_root = i;}else{m_vNeiBo[parents[i]].emplace_back(i);}}}vector<vector<int>> m_vNeiBo;int m_root=-1;
};class Solution {
public:vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {CParentToNeiBo neiBo(parents);m_nums = nums;m_vIs1.resize(nums.size());m_ans.assign(nums.size(),1);m_vHas.resize(100'000+10);DFS1(neiBo.m_root, neiBo.m_vNeiBo);for (auto& v : neiBo.m_vNeiBo){for (int j = 1; j < v.size(); j++){if (m_vIs1[v[j]]){std::swap(v[0], v[j]);}}}DFS2(neiBo.m_root, neiBo.m_vNeiBo);return m_ans;}void DFS2(int cur, vector<vector<int>>& neiBo){ for (const auto& next : neiBo[cur]){DFS2(next, neiBo);}m_vHas[m_nums[cur]] = true;while (m_vHas[m_iNeed]){m_iNeed++;}if (m_vIs1[cur]){m_ans[cur] = m_iNeed;}}bool DFS1(int cur, vector<vector<int>>& neiBo){bool b = (1 == m_nums[cur]); for (const auto& next : neiBo[cur]){b |= DFS1(next, neiBo);}return m_vIs1[cur]=b;}vector<int> m_nums,m_ans;vector<bool> m_vIs1;int m_iNeed = 1;vector<bool> m_vHas;
};
1及其祖先不用DFS
class CParentToNeiBo
{
public:CParentToNeiBo(const vector<int>& parents){m_vNeiBo.resize(parents.size());for (int i = 0; i < parents.size(); i++){if (-1 == parents[i]){m_root = i;}else{m_vNeiBo[parents[i]].emplace_back(i);}}}vector<vector<int>> m_vNeiBo;int m_root=-1;
};class Solution {
public:vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {CParentToNeiBo neiBo(parents);m_nums = nums;m_vIs1.resize(nums.size());m_ans.assign(nums.size(),1);m_vHas.resize(100'000+10);int i1 = std::find(nums.begin(), nums.end(), 1)- nums.begin();while ((-1 != i1) && (nums.size() != i1)){m_vIs1[i1] = true;i1 = parents[i1];}for (auto& v : neiBo.m_vNeiBo){for (int j = 1; j < v.size(); j++){if (m_vIs1[v[j]]){std::swap(v[0], v[j]);}}}DFS2(neiBo.m_root, neiBo.m_vNeiBo);return m_ans;}void DFS2(int cur, vector<vector<int>>& neiBo){ for (const auto& next : neiBo[cur]){DFS2(next, neiBo);}m_vHas[m_nums[cur]] = true; if (m_vIs1[cur]){while (m_vHas[m_iNeed]){m_iNeed++;}m_ans[cur] = m_iNeed;}}vector<int> m_nums,m_ans;vector<bool> m_vIs1;int m_iNeed = 1;vector<bool> m_vHas;
};
測試用例
template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}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]);}}int main()
{vector<int> parents, nums;{Solution sln;parents = { -1, 0, 0, 2 }, nums = { 1, 2, 3, 4 };auto res = sln.smallestMissingValueSubtree(parents, nums);Assert({ 5,1,1,1 }, res);}{Solution sln;parents = { -1, 0, 1, 0, 3, 3 }, nums = { 5, 4, 6, 2, 1, 3 };auto res = sln.smallestMissingValueSubtree(parents, nums);Assert({ 7,1,1,4,2,1 }, res);}{Solution sln;parents = { -1, 2, 3, 0, 2, 4, 1 }, nums = { 2, 3, 4, 5, 6, 7, 8 };auto res = sln.smallestMissingValueSubtree(parents, nums);Assert({ 1,1,1,1,1,1,1 }, res);}
}
2023年2月版（當時能過）
class Solution {
public:
vector smallestMissingValueSubtree(const vector& parents, const vector& nums) {
m_c = nums.size();
m_vDirect.resize(m_c);
for (int i = 1; i < parents.size(); i++)
{
m_vDirect[parents[i]].push_back(i);
}
m_vVisiteValue.resize(m_c + 1);
m_vRet.assign(m_c, 1);
for (int i = 0; i < nums.size(); i++)
{
if (1 == nums[i])
{
DFS(i, -1,parents, nums);
break;
}
}
return m_vRet;
}
void DFS(int iCur, int iFromChild,const vector& parents, const vector& nums)
{
if (-1 == iCur)
{
return;
}
DFSForValue(iCur, iFromChild, nums);
int iMiss = (-1 == iFromChild) ? 1 : m_vRet[iFromChild];
while ((iMiss < m_vVisiteValue.size()) && (m_vVisiteValue[iMiss]))
{
iMiss++;
}
m_vRet[iCur] = iMiss;
DFS(parents[iCur], iCur, parents, nums);
}
void DFSForValue(int iCur, int iFromChild, const vector& nums)
{
m_vVisiteValue[nums[iCur]] = true;
for (auto& next : m_vDirect[iCur])
{
if (next == iFromChild)
{
continue;
}
DFSForValue(next, iFromChild, nums);
}
}
int m_c;
vector<vector> m_vDirect;
vector m_vRet;
vector m_vVisiteValue;
};
擴展閱讀
視頻課程
有效學習：明確的目標 及時的反饋 拉伸區（難度合適），可以先學簡單的課程，請移步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 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。
)
)
