这是悦乐书的第 373 次更新, 第 400 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 234 题(顺位题号是 997). 在一个城镇, 有 N 个人从 1 到 N 标记. 有传言说其中一个人是秘密的镇法官.
如果镇法官存在, 那么:
镇法官不信任任何人.
每个人 (镇法官除外) 都信任镇法官.
只有一个人满足前两条.
给定一个 trust 数组, 一对 trust[i] = [a,b]表示被标记为 a 的人信任标记为 b 的人.
如果镇法官存在并且可以识别, 则返回镇法官的标签. 否则, 返回 - 1.
例如:
输入: N = 2,trust = [[1,2]]
输出: 2
输入: N = 3,trust = [[1,3],[2,3]]
输出: 3
输入: N = 3,trust = [[1,3],[2,3],[3,1]]
输出:-1
输入: N = 3,trust = [[1,2],[2,3]]
输出:-1
输入: N = 4,trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
输出: 3
注意:
- 1 <= N <= 1000
- trust.length <= 10000
trust[i]都是不同的.
- trust[i][0] != trust[i][1]
- 1 <= trust[i][0],trust[i][1] <= N
02 第一种解法
将题目翻译一下就是, 法官的被信任次数等于 N-1, 并且法官不能信任其他人, 即法官是 trust 数组中 trust[i][1]出现次数等于 N-1 的人 (被信任次数等于 N-1), 并且 trust[i][0] 不等于法官所在的标签(法官不能信任其他人).
思路: 利用 HashMap 记录被信任人出现的次数, 找出其中被信任了 N-1 次的人, 然后去 trust 数组中判断此人是否有信任过其他人. 有种特殊情况是 N 为 1 的时候, trust 为空数组, 即只有 1 个人, 那么这个人就是法官.
- public int findJudge(int N, int[][] trust) {
- // 只有 1 个人的时候, 法官就是他本人
- if (N == 1) {
- return N;
- }
- // key 为被信任的人, value 为其被信任的次数
- Map<Integer, Integer> map = new HashMap<Integer, Integer>();
- for (int[] arr : trust) {
- map.put(arr[1], map.getOrDefault(arr[1], 0)+1);
- }
- // 找到被信任次数等于 N-1 的那个人
- int count = -1;
- for (Integer key : map.keySet()) {
- if (map.get(key) == N-1) {
- count = key;
- }
- }
- // 被信任次数等于 N-1 的人, 不能信任其他人
- for (int[] arr : trust) {
- if (arr[0] == count) {
- return -1;
- }
- }
- return count;
- }
03 第二种解法
针对第一种解法中的 HashMap, 我们还可以用 int 数组进行替换, 思路和上面第一种解法一致.
- public int findJudge2(int N, int[][] trust) {
- if (N == 1) {
- return N;
- }
- int[] trusted = new int[N+1];
- for (int i=0; i<trust.length; i++) {
- trusted[trust[i][1]]++;
- }
- int count = -1;
- for (int i=0; i<trusted.length; i++) {
- if (trusted[i] == N-1) {
- count = i;
- }
- }
- for (int[] arr : trust) {
- if (arr[0] == count) {
- return -1;
- }
- }
- return count;
- }
04 第三种解法
针对第二种解法, 我们还可以将其简化成 2 个 for 循环, 将统计被信任次数和寻找被信任次数最多的人合在一起处理.
- public int findJudge3(int N, int[][] trust) {
- if (N == 1) {
- return N;
- }
- int[] trusted = new int[N+1];
- int count = -1, num = -1;
- for (int i=0; i<trust.length; i++) {
- trusted[trust[i][1]]++;
- if (trusted[trust[i][1]]> count) {
- count = trusted[trust[i][1]];
- num = trust[i][1];
- }
- }
- // 被信任次数要等于 N-1
- if (count != N-1) {
- return -1;
- }
- for (int[] arr : trust) {
- if (arr[0] == num) {
- return -1;
- }
- }
- return num;
- }
05 第四种解法
我们还可以使用两个 int 数组来解, 一个数组 arr 存信任的人, 另一个数组 arr2 存被信任的人, 找出被信任次数等于 N-1(arr2[i]=N-1)且没有信任过人 (arr[i]=0) 的人, 他就是法官.
- public int findJudge4(int N, int[][] trust) {
- int[] arr = new int[N+1];
- int[] arr2 = new int[N+1];
- for (int i=0; i<trust.length; i++) {
- arr[trust[i][0]]++;
- arr2[trust[i][1]]++;
- }
- for (int j=1; j<arr.length; j++) {
- if (arr[j] == 0 && arr2[j] == N-1) {
- return j;
- }
- }
- return -1;
- }
06 小结
算法专题目前已连续日更超过七个月, 算法题文章 240 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
LeetCode.997 - 找到镇法官(Find the Town Judge)
来源: http://www.bubuko.com/infodetail-3112648.html