LeetCode-Go 题解精讲997. Find the Town Judge小镇法官——入度出度统计的 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 0997.Find-the-Town-Judge 题目文档 展开完整讲解 LeetCode 第 997 题「小镇法官」的题意、约束与判定条件并结合仓库内真实的 Go 源码 与 单元测试 深入剖析入度与出度统计这一核心思路。读完本文你将掌握如何用一张哈希表同时完成信任关系计数与候选人剔除理解法官存在的充要条件并能直接运行仓库测试验证解法正确性。一、题目原文英文In a town, there arenpeople labeled from1ton. There is a rumor that one of these people is secretly the town judge.If the town judge exists, then:The town judge trusts nobody.Everybody (except for the town judge) trusts the town judge.There is exactly one person that satisfies properties 1 and 2.You are given an arraytrustwheretrust[i] [ai, bi]representing that the person labeledaitrusts the person labeledbi.Return the label of the town judge if the town judge exists and can be identified, or return-1otherwise.二、题目大意中文小镇里有n个人按从1到n的顺序编号。传言称这些人中有一个暗地里是小镇法官。如果小镇法官真的存在那么小镇法官不会信任任何人。每个人除了小镇法官都信任这位小镇法官。只有一个人同时满足上面两个属性。给你一个数组trust其中trust[i] [ai, bi]表示编号为ai的人信任编号为bi的人。如果小镇法官存在并且可以确定他的身份请返回该法官的编号否则返回-1。三、示例与约束条件3.1 官方示例示例输入输出说明示例 1n 2, trust [[1,2]]22 号被 1 号信任且 2 号没有信任任何人示例 2n 3, trust [[1,3],[2,3]]33 号被 1、2 号同时信任且 3 号没有信任任何人示例 3n 3, trust [[1,3],[2,3],[3,1]]-13 号虽然被 1、2 号信任但 3 号又信任了 1 号违反法官不信任任何人3.2 约束条件Constraints1 n 10000 trust.length 10000trust[i].length 2所有trust二元组都是唯一的ai ! bi一个人不会信任自己1 ai, bi n从约束可以看出n最大 1000信任关系最多 10000 条数据规模很小即使采用哈希表 多次遍历的方案也能轻松通过这也意味着该题的考察重点是建模能力而非常数优化。四、核心解题思路入度与出度统计原文档给出的核心思路可概括为四个字入度、出度。在信任关系这个有向图中把谁信任谁建模为一条有向边入度indegree被多少人信任。即指向该节点的边数。出度outdegree信任了多少人。即从该节点出发的边数。那么小镇法官的判定条件可以严格翻译为图论语言法官的出度为 0——法官不信任任何人没有任何出边法官的入度为n - 1——除法官外其余n - 1个人都信任法官有且仅有n - 1条入边指向法官同时满足上述两条的人必须唯一。因此算法只需要在1到n的范围内寻找那个入度为n - 1且出度为 0的唯一编号x找到即返回x否则返回-1。五、仓库源码实现与逐行剖析仓库中的实现位于 997.Find the Town Judge.go完整代码如下package leetcode func findJudge(n int, trust [][]int) int { if n 1 len(trust) 0 { return 1 } judges : make(map[int]int) for _, v : range trust { judges[v[1]] 1 } for _, v : range trust { if _, ok : judges[v[0]]; ok { delete(judges, v[0]) } } for k, v : range judges { if v n-1 { return k } } return -1 }这段代码用一张哈希表巧妙地把入度统计和出度剔除合并完成逻辑分四个阶段5.1 阶段一特判n 1if n 1 len(trust) 0 { return 1 }当小镇只有一个人n 1且没有任何信任关系时这个人天然满足不信任任何人且其余 0 个人都信任他空真条件所以 1 号就是法官直接返回1。这是最容易漏掉的边界情况仓库源码单独做了特判。5.2 阶段二统计入度judges : make(map[int]int) for _, v : range trust { judges[v[1]] 1 }第一轮遍历只统计每条边的终点v[1]即被信任的人。judges这个 map 的语义是键 候选人值 该候选人被信任的次数入度。凡是出现在信任关系中的被信任者都会进入 map。5.3 阶段三剔除有出度的人for _, v : range trust { if _, ok : judges[v[0]]; ok { delete(judges, v[0]) } }第二轮遍历检查每条边的起点v[0]即主动信任别人的人。只要某个人曾经信任过别人出度大于 0就把它从judges中删除。这一步相当于一次性完成了法官出度必须为 0的筛选一个人如果既被信任又信任别人如示例 3 中的 3 号会被删除一个人如果只信任别人而从不被信任本来就不在 map 中无需处理只有从不信任别人、但被若干人信任的候选人才能存活下来。5.4 阶段四按入度n - 1确认法官for k, v : range judges { if v n-1 { return k } } return -1经过前两轮筛选后judges中剩下的都是出度为 0的候选人。第三轮遍历检查存活者的入度是否为n - 1命中即返回编号k若没有任何人满足说明法官不存在返回-1。5.5 一个值得注意的实现细节由于题目保证所有二元组唯一且ai ! bi一个人的入度至多n - 1。若某个候选人的入度恰好为n - 1意味着他已被除自己外的所有人信任此时他若仍留在 map 中说明他没有任何出边必然就是法官。因此入度n - 1且出度 0这两个条件在同一个人身上只会出现一次天然满足法官唯一的约束无需额外去重。六、测试用例验证仓库在 997.Find the Town Judge_test.go 中通过表格驱动方式覆盖了 4 个用例测试输入期望输出覆盖场景n 2, trust [[1,2]]2官方示例 1标准法官场景n 3, trust [[1,3],[2,3]]3官方示例 2多人信任同一人n 3, trust [[1,3],[2,3],[3,1]]-1官方示例 3法官候选人自身信任他人被剔除n 1, trust []1边界情况单人小镇直接判定测试代码的结构如下type question997 struct { para997 ans997 } // para 是参数 type para997 struct { n int trust [][]int } // ans 是答案 type ans997 struct { ans int } func Test_Problem997(t *testing.T) { qs : []question997{ {para997{2, [][]int{{1, 2}}}, ans997{2}}, {para997{3, [][]int{{1, 3}, {2, 3}}}, ans997{3}}, {para997{3, [][]int{{1, 3}, {2, 3}, {3, 1}}}, ans997{-1}}, {para997{1, [][]int{}}, ans997{1}}, } // ...遍历 qs 并调用 findJudge(p.n, p.trust) 打印结果 }这也是 LeetCode-Go 仓库一贯的测试风格每个题解目录下配套一个*_test.go文件用参数 答案的结构体组织用例。项目根目录的 gotest.sh 脚本使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部题解做覆盖率统计保证每个题解都有对应的测试佐证。七、复杂度分析时间复杂度O(n E)其中E len(trust)。三次遍历均为线性第一、二轮各遍历全部信任关系O(E)第三轮遍历 map 中最多n个键O(n)总复杂度O(n E)。空间复杂度O(n)。judgesmap 最多容纳n个键即每个编号至多出现一次。在题目约束n 1000E 10000下该解法时间与空间都绰绰有余。八、易错点与边界情况盘点忘记处理n 1单人小镇且无信任关系时法官就是 1 号。若不做特判map 为空、第三轮遍历直接返回-1答案错误。只统计入度、不剔除出度示例 3 中 3 号入度同样为n - 1但因为它信任了别人并非法官。只统计入度会导致误判。混淆v[0]与v[1]trust[i] [ai, bi]中ai是信任者出边起点bi是被信任者入边终点。统计入度应累加v[1]剔除出度应检查v[0]二者不可颠倒。法官唯一性题目明确要求只有一个人同时满足两个属性但由图论性质可知入度n - 1与出度 0 的组合在同一图上至多对应一个人因此满足条件即返回即可。九、延伸从 map 方案到数组计分方案仓库当前采用 map 方案核心是计数 剔除两步。从算法思路上可以进一步归纳出等价的计分视角这是对同一思路的推广并非仓库现有实现为每个人维护一个分数score[i]遍历每条信任关系时令score[bi]、score[ai]--最终分数恰好等于n - 1的那个人就是法官。该变体用两个长度为n 1的数组替代 map省去哈希开销思路本质与仓库的入度出度统计完全一致。十、如何在本地运行与验证本仓库是 Go 项目可在仓库根目录直接运行以下命令验证本题解# 运行 0997 题目的单元测试 go test -v ./leetcode/0997.Find-the-Town-Judge/ # 或按仓库约定对全部题解做覆盖率统计 bash gotest.sh题目文档、题解源码与测试文件三者位于同一目录下方便对照阅读题目与思路文档leetcode/0997.Find-the-Town-Judge/README.md题解实现997.Find the Town Judge.go单元测试997.Find the Town Judge_test.go小结LeetCode 997 题表面是找小镇法官的图论入门题本质考察把业务规则抽象为入度/出度统计的能力。LeetCode-Go 仓库用一张哈希表完成了统计入度 → 剔除有出度者 → 按n - 1确认的全流程配合n 1边界特判与 4 组表格化单元测试构成了一个正确、简洁、可验证的题解闭环。掌握这一建模思路后诸如寻找被所有人信任且不信任任何人的节点一类问题均可照此套路快速求解。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考