说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。
图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。
节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的 编号 总和。
返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。
示例 1：
输入：edges = [1,0,0,0,0,7,7,5] 输出：7 解释： - 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。 - 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。 - 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。 - 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。 节点 7 的边积分最高，所以返回 7 。
示例 2：
输入：edges = [2,0,0,2] 输出：0 解释： - 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。 - 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。 节点 0 和 2 的边积分都是 3 。由于节点 0 的编号更小，返回 0 。
提示：
- n == edges.length
- 2 <= n <= 10^5
- 0 <= edges[i] < n
- edges[i] != i
思路分析
首先我们应该要先读懂题意，知道题目要求我们做什么。题目会给我们一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。我们需要统计每个节点的边积分，那么在这里的边积分是怎么定义的呢？题目的定义是这样的：所有存在一条指向节点 i 的边的节点的 编号 总和。所以我们可以使用一个hash表来记录每一个节点的边积分，只需要遍历每一个节点，将其出边的节点积分加上当前节点的编号，找出其中边积分最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。
- 1、使用hash表记录每个节点边积分
let map = {},max = 0,res = 0;
- 2、遍历计算边积分
for(let i = 0; i < edges.length; i++){ map[edges[i]] = (map[edges[i]] || 0) + i; …… }
- 3、更新边积分最高的节点
if(map[edges[i]] > max){ max = map[edges[i]]; res = edges[i]; }else if(map[edges[i]] == max){ if(res > edges[i]){ res = edges[i]; } }
完整代码如下：
AC代码
/** * @param {number[]} edges * @return {number} */ var edgeScore = function(edges) { let map = {},max = 0,res = 0; for(let i = 0; i < edges.length; i++){ map[edges[i]] = (map[edges[i]] || 0) + i; if(map[edges[i]] > max){ max = map[edges[i]]; res = edges[i]; }else if(map[edges[i]] == max){ if(res > edges[i]){ res = edges[i]; } } } return res; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
