微信公众号 做不了微网站吗,网站更改文章标题,做网站常用的jquery,个人博客网站html模板作者推荐
动态规划的时间复杂度优化
本文涉及知识点
深度优先搜索
LeetCode2003. 每棵子树内缺失的最小基因值
有一棵根节点为 0 的 家族树 #xff0c;总共包含 n 个节点#xff0c;节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents #xff0c;其中…作者推荐
动态规划的时间复杂度优化
本文涉及知识点
深度优先搜索
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 vectorint 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);}}}vectorvectorint m_vNeiBo;int m_root-1;
};class Solution {
public:vectorint smallestMissingValueSubtree(vectorint parents, vectorint nums) {CParentToNeiBo neiBo(parents);m_nums nums;m_vIs1.resize(nums.size());m_ans.assign(nums.size(),1);m_vHas.resize(10000010);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, vectorvectorint 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, vectorvectorint neiBo){bool b (1 m_nums[cur]); for (const auto next : neiBo[cur]){b | DFS1(next, neiBo);}return m_vIs1[cur]b;}vectorint m_nums,m_ans;vectorbool m_vIs1;int m_iNeed 1;vectorbool m_vHas;
};1及其祖先不用DFS
class CParentToNeiBo
{
public:CParentToNeiBo(const vectorint 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);}}}vectorvectorint m_vNeiBo;int m_root-1;
};class Solution {
public:vectorint smallestMissingValueSubtree(vectorint parents, vectorint nums) {CParentToNeiBo neiBo(parents);m_nums nums;m_vIs1.resize(nums.size());m_ans.assign(nums.size(),1);m_vHas.resize(10000010);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, vectorvectorint 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;}}vectorint m_nums,m_ans;vectorbool m_vIs1;int m_iNeed 1;vectorbool m_vHas;
};测试用例 templateclass T,class T2
void Assert(const T t1, const T2 t2)
{assert(t1 t2);
}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]);}}int main()
{vectorint 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; vectorvector 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
