建设网站制作怎样维护网站的安全和备份

当前位置： 首页 > news >正文

建设网站制作,怎样维护网站的安全和备份,绍兴市住房与城乡建设厅网站,织梦资源网模板文章目录 1.问题分析2.代码解析2.1 代码步骤1. 初始化数据结构2. 构建图和入度数组3. 初始化队列4. 拓扑排序和动态规划5. 检查是否存在环并返回结果 3. 问题扩展1. 最长路径问题#xff08;DAG#xff09;2. 最短路径问题#xff08;DAG#xff09;3. 最大路径和问题4. 路… 文章目录 1.问题分析2.代码解析2.1 代码步骤1. 初始化数据结构2. 构建图和入度数组3. 初始化队列4. 拓扑排序和动态规划5. 检查是否存在环并返回结果 3. 问题扩展1. 最长路径问题DAG2. 最短路径问题DAG3. 最大路径和问题4. 路径计数问题5. 关键路径法Critical Path Method, CPM6. DAG上的单源最短路径Single Source Shortest Path in DAG7. 有向无环图中的最大子序列和问题8. DAG中的最长递增子序列问题9. 资源分配问题DAG LeetCode1857. 有向图中最大颜色值 本题乍一看和求所有路径中的最长路径没啥区别直接暴力枚举所有路径但是时间复杂度不允许我们这样做。 1.问题分析 数据结构图的拓扑排序与关键路径 其实关键路径就是使用了动态规划解法它先将有向无环图进行拓扑排序然后按照拓扑序进行动态规划。 有向无环图一定存在拓扑排序按照拓扑序顺序遍历每次更新该结点的后继按照这个方法遍历到某结点时一定能够保证其前驱都已经遍历过并且进行过更新。我们并不需要关心具体的顺序是什么但一定有边 u , v u,v u,v u u u的状态能够更新 v v v。 因此本题也可以使用拓扑排序动态规划。
2.代码解析 我们定义一个 d p [ i ] [ c ] dp[i][c] dp[i][c]表示第 i i i个节点的颜色 c c c。 则必有 d p [ i ] [ c ] m a x ( d p [ i p r e ] [ c ] ) I ( i p r e , i ) dp[i][c] max(dp[i{pre}][c]) I(i{pre},i) dp[i][c]max(dp[ipre​][c])I(ipre​,i) 求到达第 i i i个节点时 能够包含的最多颜色 c c c的个数等价于到达其前驱 i p r e i_{pre} ipre​能够包含的最多颜色 c c c的个数再一步到达 i i i包含的个数。 class Solution { public:int largestPathValue(string colors, vectorvectorint edges) {vectorvectorint dp(colors.size(), vectorint(26, 0));vectorint inDegrees(colors.size(), 0);vectorvectorint graph(colors.size());for(int i 0; i edges.size(); i){inDegrees[edges[i][1]] ;graph[edges[i][0]].emplace_back(edges[i][1]);}vectorint topo;//拓扑序queueint q;for(int i 0; i colors.size(); i){if(inDegrees[i] 0){q.push(i);}}while(!q.empty()){int u q.front(); q.pop();topo.emplace_back(u);for(auto v : graph[u]){– inDegrees[v];if(inDegrees[v] 0) {q.push(v);}}}int ans 0;for(auto u : topo){for(int i 0; i 26; i){if(colors[u] a i) dp[u][i] ;ans max(ans, dp[u][i]);for(auto v : graph[u]){dp[v][i] max(dp[u][i], dp[v][i]);}}}if(topo.size() ! colors.size()) return -1;return ans;} };可以进行进一步优化 1拓扑排序的过程中更新这样就不用求出拓扑序了因为排序的过程中就是拓扑序了所以边排序边更新状态。 2ans的求解使用 a n s m a x ( a n s , d p [ u ] [ c o l o r s [ u ] − ′ a ′ ] ) ans max(ans, dp[u][colors[u] - a]) ansmax(ans,dp[u][colors[u]−′a′])原因在于任何一个颜色最大路径该颜色的最后一个结点都会被遍历到用该结点就能求出最大值。 3由于是固定大小的数组直接使用array即可。这是加速的关键 使用vectorint(26, 0)
使用arrayint, 26 这说明在不使用动态数组的情况下固定大小的静态数组使用array比vector快很多。 class Solution { public:int largestPathValue(string colors, vectorvectorint edges) {vectorarrayint, 26 dp(colors.size());vectorint inDegrees(colors.size(), 0);vectorvectorint graph(colors.size());for(int i 0; i edges.size(); i){inDegrees[edges[i][1]] ;graph[edges[i][0]].emplace_back(edges[i][1]);}queueint q;for(int i 0; i colors.size(); i){if(inDegrees[i] 0){q.push(i);}}int ans 0;int topo 0;while(!q.empty()){int u q.front(); q.pop();topo ;dp[u][colors[u] - a] ;ans max(ans, dp[u][colors[u] - a]);for(auto v : graph[u]){– inDegrees[v];if(inDegrees[v] 0) {q.push(v);}for(int i 0; i 26; i){dp[v][i] max(dp[u][i], dp[v][i]);}}}if(topo ! colors.size()) return -1;return ans;} };好的让我们详细解释这段代码。该代码的目的是解决一个有向图中的最大路径值问题其中每个节点都有一个颜色。目标是找到从图的起点到终点路径中某种颜色出现最多的次数。 2.1 代码步骤

1. 初始化数据结构 vectorarrayint, 26 dp(colors.size()); vectorint inDegrees(colors.size(), 0); vectorvectorint graph(colors.size());dp一个二维数组dp[i][j] 表示从起点到节点 i 的路径中颜色 j用0到25表示的最大出现次数。inDegrees记录每个节点的入度。graph表示图的邻接表。
2. 构建图和入度数组 for(int i 0; i edges.size(); i){inDegrees[edges[i][1]];graph[edges[i][0]].emplace_back(edges[i][1]); }遍历 edges填充 inDegrees 和 graph。对于每一条边 (u, v)增加 v 的入度并在 graph[u] 中添加 v。
3. 初始化队列 queueint q; for(int i 0; i colors.size(); i){if(inDegrees[i] 0){q.push(i);} }初始化一个队列 q将所有入度为 0 的节点入队。这些节点作为拓扑排序的起点。
4. 拓扑排序和动态规划 int ans 0; int topo 0; while(!q.empty()){int u q.front(); q.pop();topo;dp[u][colors[u] - a];ans max(ans, dp[u][colors[u] - a]);for(auto v : graph[u]){–inDegrees[v];if(inDegrees[v] 0) { q.push(v); }for(int i 0; i 26; i){dp[v][i] max(dp[u][i], dp[v][i]);}} }ans记录路径上颜色出现的最大次数。topo记录拓扑排序的节点数量用于检测是否存在环。 主要逻辑 取队首节点 u更新 topo。更新 dp[u][colors[u] - a]表示节点 u 的颜色出现次数增加。更新 ans 为当前颜色出现的最大次数。遍历 u 的邻接节点 v 减少 v 的入度。如果 v 的入度为 0入队 q。更新 dp[v]根据从 u 到 v 的路径更新 v 的颜色出现次数。
   
5. 检查是否存在环并返回结果 if(topo ! colors.size()) return -1; return ans;如果拓扑排序遍历的节点数量不等于 colors 的长度说明图中存在环返回 -1。否则返回 ans即路径上某种颜色的最大出现次数。
6. 问题扩展
7. 最长路径问题DAG 问题描述 在一个有向无环图DAG中找到从一个起点到终点的最长路径。 解决方案 使用拓扑排序确定处理节点的顺序。按照拓扑序进行动态规划计算每个节点的最长路径长度。
8. 最短路径问题DAG 问题描述 在一个有向无环图DAG中找到从一个起点到终点的最短路径。 解决方案 使用拓扑排序确定处理节点的顺序。按照拓扑序进行动态规划计算每个节点的最短路径长度。
9. 最大路径和问题 问题描述 在一个有向无环图DAG中找到从起点到终点的路径中权重总和最大的路径。 解决方案 使用拓扑排序确定处理节点的顺序。按拓扑序进行动态规划计算每个节点的路径权重总和。
10. 路径计数问题 问题描述 计算从起始点到终点的所有可能路径的数量。 解决方案 使用拓扑排序确定处理节点的顺序。按拓扑序计算从起始点到每个节点的路径数量。
11. 关键路径法Critical Path Method, CPM 问题描述 在项目管理中给定一组任务及其依赖关系找出项目的关键路径和项目的最短完成时间。 解决方案 使用拓扑排序确定任务的处理顺序。按拓扑序进行动态规划计算每个任务的最早开始时间和最晚开始时间从而确定关键路径。
12. DAG上的单源最短路径Single Source Shortest Path in DAG 问题描述 在一个有向无环图DAG中找到从一个起点到所有其他节点的最短路径。 解决方案 使用拓扑排序确定处理节点的顺序。按拓扑序进行动态规划计算从起点到每个节点的最短路径长度。
13. 有向无环图中的最大子序列和问题 问题描述 在一个有向无环图DAG中找到从起点到终点的最大子序列和。 解决方案 使用拓扑排序确定处理节点的顺序。按拓扑序进行动态规划计算每个节点的最大子序列和。
14. DAG中的最长递增子序列问题 问题描述 在一个有向无环图DAG中找到从起点到终点的最长递增子序列。 解决方案 使用拓扑排序确定处理节点的顺序。按拓扑序进行动态规划计算每个节点的最长递增子序列长度。
15. 资源分配问题DAG 问题描述 在一个有向无环图DAG中给定每个节点的资源需求和资源量计算从起点到终点的最大资源分配路径。 解决方案 使用拓扑排序确定处理节点的顺序。按拓扑序进行动态规划计算每个节点的最大资源分配路径。