英文网站建设需要注意的五点问题,app软件开发摄像头,钢材贸易网站建设,品牌型网站建设的好处目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们一棵树#xff0c;不过这棵树不是普通的树#xff0c;而是无向无根树。给我们一个二维数组表示节点之间的连接关系#xff…目录
题目
示例
分析
代码 题目 示例 分析
题目给我们一棵树不过这棵树不是普通的树而是无向无根树。给我们一个二维数组表示节点之间的连接关系以及一个一维数组表示每个节点是否有金币。
我们可以从任何一个节点出发并且可以收集距离两格的节点的金币每次可以移动到相邻的节点。问我们要收集完所有的金币并且最终要回到起点最少需要移动几次。
首先题目说了这是一棵树所以是不存在环的两个节点之间连通的路径只会有唯一的一条。
因此我们不管选择哪一个节点当起点都是可以到达任意一个节点的。 我们需要获取所有的金币那么如果一个节点没有金币并且这个节点是叶子节点那么我们是不是可以将这个节点直接从树中移除因为我们根本不需要走到这个节点。
我们把能删除的节点都删除了是不是就说明剩下的节点都是我们需要走到或是收集金币的节点。 如果我们把整棵树剪到只剩下我们必须要走到的节点之后答案就剩下节点数-1再乘2了。
为什么呢
题目要求我们必须在收集完金币之后再返回原点我们有n个必须到达的节点由于这是树是没有环的因此节点之间的连线一共是n-1条。一来一回每个线段要走两次所以答案是n-1*2
问题就变成了我们怎么把树的节点剪到只剩下我们必须要走的节点。
首先没有金币的叶子节点我们是可以先删除的。判断依据也简单如果一个节点没有金币并且和这个节点连接的其他节点只有一个那么它就是没有金币的叶子节点可以把它删除。并且删除某个节点之后可能会诞生出新的无金币叶子节点因此我们删除节点之后还需要判断一下与这个节点连接的节点是否也是无金币叶子节点也就是延伸性地删除节点。
那么怎么删除呢我们可没有构建出树来。
我们其实不需要真的删除。我们之前分析过了答案就是剪枝后的节点数减1再乘2。我们可以当成一开始的树就是我们剪枝后的树把答案初始化成总的节点数减1再乘2。每次我们删除一个节点就等于是移除了一个线段把答案减2即可这样就当成是删除一个节点了。
初步移除了没有金币的叶子节点之后剩下的节点就是我们要达到的节点或者是要收集金币的节点了。
我们把剩下的树看成是图那么图边缘一圈的节点一定都是有金币的。 我们收集金币的时候可以距离金币节点两格因此我们可以再一次把图的外围两层节点删除不过删除是有条件的最外层的叶子节点可以直接删除不过第二层的节点我们得判断删除了外层节点后第二层的节点是不是叶子节点如果是我们才可以删除。
最终我们每次删除节点之后都将答案-2最终就是要返回出去的答案了。
不过最后还有一个问题那就是如果整个树都是可以移除的那么根据我们刚才说的每删除一个节点就把答案-2而我们答案初始化是总的节点数减1再乘2这样答案就变成了-2因此最后我们做个判断如果答案小于0我们就返回0反之就正常返回求出的答案。
代码
class Solution {
public:unordered_mapint,vectorintpic; //记录节点连接图unordered_mapint,intrel; //记录每个节点的邻接数量关系int collectTheCoins(vectorint coins, vectorvectorint edges) {int ncoins.size();int res2*(n-1); //答案初始化成图中线段数乘2,表示每个线段都要走两边//建图for(auto edge:edges){if(pic.find(edge[0])pic.end()) pic[edge[0]]vectorint(0);if(pic.find(edge[1])pic.end()) pic[edge[1]]vectorint(0);pic[edge[0]].push_back(edge[1]);pic[edge[1]].push_back(edge[0]);rel[edge[0]];rel[edge[1]];}queueint q;//删除无金币的叶子节点(可延伸)for(int i0;in;i){if(coins[i]0 rel[i]1) q.push(i);}while(!q.empty()){res-2; //减少一个线段,答案减2,因为默认每个线段走两次.int curq.front();q.pop();for(int i:pic[cur]){if(--rel[i]1coins[i]0) q.push(i);}}//确定到有金币的叶子节点的范围.for(int i0;in;i){if(coins[i]1rel[i]1) q.push(i);}res-2*q.size();//减少叶子节点,不延伸(因为可以收集距离两格的金币,所以可以在边缘处再缩小一圈)while(!q.empty()){int xq.front();q.pop();for(int j:pic[x]){if(--rel[j]1) res-2;}}if(res0) return res;return 0;}
};
