如何建三网合一网站,自己可以进行网站建设吗,西安高风险调整,h5网站和传统网站117. 软件构建#xff08;拓扑排序#xff09;
继续边看解析边做题#xff0c;思考时的问题做个如下的总结#xff1a; 1. 存边用什么数据结构#xff1f;
在题目中#xff0c;我们需要存储节点之间的依赖关系#xff08;边信息#xff09;。选择适合的数据结构非常重…117. 软件构建拓扑排序
继续边看解析边做题思考时的问题做个如下的总结 1. 存边用什么数据结构
在题目中我们需要存储节点之间的依赖关系边信息。选择适合的数据结构非常重要
选择 unordered_mapint, vectorint 这个结构的作用是将节点 int 映射到一个 vectorint即以 O(1) 的复杂度找到所有依赖当前节点的节点集合。在代码中rela[left].push_back(right) 表示从节点 left 指向节点 right 的边。
这种结构方便快捷是处理稀疏图的常见选择。如果用二维数组存储虽然逻辑上也可以但会浪费内存并导致效率下降。 2 队列是否需要初始化代码
自己思考的时候感觉队列需要一个初始化代码但是却想不明白能不能合到主循环的代码里面去。看了卡哥的解析之后发现了并不能所以无须担心。 3 循环逻辑问题GPT优化版
我在写这道题时曾经因为对循环逻辑的处理不当导致代码变成了死循环。具体问题是我把初始化代码直接搬到了主循环里导致一些节点被重复插入队列。比如节点 1 在初始化时已经被插入队列了但后面又因为错误的逻辑反复地被插入队列这显然是不正确的。
当时我的想法是在节点进入队列后把它对应的 indegree 值设置成 -1这样能避免重复插入。但是后来忘记实现这一点结果还是出现了问题。虽然这种方式能够解决问题但仔细想想其实有更简单的方法只要在 indegree[tominus[i]]--; 这一步之后立即判断节点的入度是否减到 0如果是 0就将它加入队列。
这样处理有两个明显的优点
避免重复插入节点 减少入度操作的节点必然是与其他节点存在依赖关系的即入度不为 0 的节点只有在入度变为 0 时才会被加入队列从逻辑上保证了节点最多只会入队一次。减少不必要的遍历 在减少入度时直接判断是否需要入队避免了每次操作后全量扫描所有节点显著提高了代码效率。
最终通过这样的调整不仅解决了死循环问题还让代码的逻辑更加清晰执行效率也更高。这种在操作中即时判断的优化思路给我很大的启发。
#includeiostream
#includevector
#includequeue
#includeunordered_map
using namespace std;int main(){int n,m;cin n m;vectorint indegree(n);vectorint result;unordered_mapint, vectorint rela;for(int i0; im; i){int left, right;cin left right;indegree[right];rela[left].push_back(right);}queueint zerodegree;for(int i0; in; i){if(indegree[i] 0){zerodegree.push(i);}}while(!zerodegree.empty()){int top zerodegree.front();zerodegree.pop();result.push_back(top);vectorint tominus rela[top];for(int i0; itominus.size(); i){indegree[tominus[i]]--;if (indegree[tominus[i]] 0) {zerodegree.push(tominus[i]);}}}if(result.size() n){for(int i0; in; i){cout result[i];if(in-1){cout ;}}return 0;}cout -1;
} 47. 参加科学大会dijkstra朴素版精讲
虽然的确是第一次写最短路算法也是边看着解析边做的但确实感觉这个题和prim算法非常的像只要稍微改一下更新的公式就行自信就来了。
然后自己上手一写一塌糊涂。
来看GPT给我分析的问题
1. 未初始化输入的边信息
在读取边信息时你直接将 distance[left][right] val但没有先读取 left 和 right会导致程序读取未定义的值。
修正方法 在读取边之前添加 cin left right val
for (int i 0; i m; i) {int left, right, val;cin left right val; // 读取边信息distance[left][right] val;distance[right][left] val;
}
并且这里其实还有一个更严肃的问题那就是这是一个有向图而非无向图所以我不能给左右赋同样的值因为这个做不对还想了半天不然会导致算出来的结果不对所以正确的应该是
for (int i 0; i m; i) {int left, right, val;cin left right val; // 读取边信息distance[left][right] val;
} 2. 忘了在计算距离最小值的判断力加入对visited数组的判断
在第一个循环中你将 visited[1] 设置为 true但后续并没有在循环中检查哪些节点已经被访问过可能会导致重复访问或者访问逻辑错误。
修正方法 在主循环和内层循环中增加对 visited 的判断
if (!visited[j] mindist[j] dis_min) { 3. 访问越界问题
当所有节点都访问过后pos 可能仍然是 -1表示当前没有未访问的节点。这会导致接下来的代码逻辑失效导致访问出现越界问题。
修正方法 在找到最小 pos 后立即判断
if (pos -1) {break; // 无法找到更短的路径直接退出
} 顺带一提卡哥的做法是直接给pos赋值成1这样即使是没找到也不会导致访问越界。但这样做的坏处在于卡哥的这种写法会让循环继续执行但假设我们循环一整圈都没有找到比INT_MAX更小的距离此时其实说明已经没边了所以循环没有必要继续执行了直接break掉还能省点事情。
脑子里的杠精如果刚好有一个距离就等于INT_MAX你这个判断不就失效了吗
emm... 那如果是这样距离总和都超过INT能表示的范围了不如放他一马。 4. 在更新距离时也忘了对visited数组的判断
if (!visited[k] distance[pos][k] ! INT_MAX) {mindist[k] min(mindist[pos] distance[pos][k], mindist[k]);
}
以上就是本期的全部内容了喜欢不要忘了点个一键三连哦串台
#includeiostream
#includevector
#include climits
using namespace std;int main(){int n,m;cin n m;vectorvectorint distance(n1, vectorint(n1, INT_MAX));for(int i0; im; i){int left, right, val;cin left right val;distance[left][right] val;//distance[right][left] val; //不能加加了你就完了}vectorint mindist(n1, INT_MAX);vectorbool visited(n1);mindist[1] 0;for(int i1; in; i){int dis_min INT_MAX;int pos -1;for(int j1; jn; j){if(!visited[j] mindist[j] dis_min){dis_min mindist[j];pos j;}}if (pos -1) {break; // 无法找到更短的路径直接退出}visited[pos] true;for(int k1; kn; k){if(!visited[k] distance[pos][k] ! INT_MAX){mindist[k] min(mindist[pos] distance[pos][k], mindist[k]);}}}if(mindist[n] INT_MAX){cout -1;return 0;}cout mindist[n];
}
