3593、找到小镇的法官

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

小镇法官不会信任任何人。

每个人（除了小镇法官）都信任这位小镇法官。

只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

示例 1：

输入：n = 2, trust = [[1,2]]

输出：2

示例 2：

输入：n = 3, trust = [[1,3],[2,3]]

输出：3

示例 3：

输入：n = 3, trust = [[1,3],[2,3],[3,1]]

输出：-1

提示：

1 <= n <= 1000

0 <= trust.length <= 104

trust[i].length == 2

trust 中的所有trust[i] = [ai, bi] 互不相同

ai != bi

1 <= ai, bi <= n

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/find-the-town-judge

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package cn.fansunion.leecode.intelligence;

import java.util.HashMap;

import java.util.Map;

/**

 * 997. 找到小镇的法官 <br/>

 * 小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

 *

 * 如果小镇法官真的存在，那么：

 *

 * 小镇法官不会信任任何人。 每个人（除了小镇法官）都信任这位小镇法官。 只有一个人同时满足属性 1 和属性 2 。 <br/>

 * 给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

 *

 * 如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

 *

 * 来源：力扣（LeetCode） 链接：力扣 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 *

 * @author [email protected]

 *

 *         2022-3-9

 */

public class FindTheTownJudge {

    /*示例 1：

     

    输入：n = 2, trust = [[1,2]]

    输出：2

    示例 2：

     

    输入：n = 3, trust = [[1,3],[2,3]]

    输出：3

    示例 3：

     

    输入：n = 3, trust = [[1,3],[2,3],[3,1]]

    输出：-1

      

    提示：

     

    1 <= n <= 1000

    0 <= trust.length <= 104

    trust[i].length == 2

    trust 中的所有trust[i] = [ai, bi] 互不相同

    ai != bi

    1 <= ai, bi <= n*/

    /**

     * 思路：严格按照题目定义。遍历数组，维护from-to,to-from 2个维度的数量map。再遍历1到n，判定是否同时存在满足2个条件的数。<br/>

     * 本题遇到的2个问题：<br/>

     * 1、几百年不用二维数组，题目看懵了。二维数组：数组的数组，直接用foreach循环，得到每一个元素“数组”即可。<br/>

     * 2、从map取数字，经常需要处理null。用Map.getOrDefault(i, 0)可以完美解决null的问题<br/>

     * 本题中的map，可以用数组代替，数组的默认值为0，已经避免了null的情况<br/>

     *

     * @param n

     * @param trust

     * @return

     */

    public int findJudge(int n, int[][] trust) {

        // 一个人信任其他人的次数

        Map<Integer, Integer> trustCountMap = new HashMap<>();

        // 一个人被其他人信任的次数

        Map<Integer, Integer> beTrustCountMap = new HashMap<>();

        for (int[] array : trust) {

            //一个人信任其他人的次数

            int trustNo = array[0];

            Integer trustNoCount = countPlus(trustCountMap, trustNo);

            trustCountMap.put(trustNo, trustNoCount);

            //一个人被其他人信任的次数

            int beTrustNo = array[1];

            Integer beTrustNoCount = countPlus(beTrustCountMap,beTrustNo);

            beTrustCountMap.put(beTrustNo, beTrustNoCount);

        }

        // 信任 次数为0 && beTrustNo，被信任次数为(n-1)

        for (int i = 1; i <= n; i++) {

            final Integer beTrustCount = beTrustCountMap.getOrDefault(i, 0);

            final Integer trustCount = trustCountMap.getOrDefault(i, 0);

            //不信任别人，可以为null（和习惯性的null判断不同）

            //final boolean trustOtherZero = trustCount == null || trustCount.equals(0);

             final boolean trustOtherZero = trustCount.equals(0);

            // 被人信任

            final boolean beTrustNPlusOne =  beTrustCount.equals(n - 1);

            if (trustOtherZero && beTrustNPlusOne) {

                return i;

            }

        }

        return -1;

    }

    private Integer countPlus(Map<Integer, Integer> countMap, int key) {

        Integer trustNoCount = countMap.getOrDefault(key, 0);

        trustNoCount++;

        return trustNoCount;

    }

}

package test.leecode.intelligence;

import org.junit.Assert;

import org.junit.Test;

import cn.fansunion.leecode.intelligence.FindTheTownJudge;

/**

 * @author [email protected]

 *

 *         2022-3-12

 */

public class FindTheTownJudgeTest {

    @Test

    public void test() {

        FindTheTownJudge test = new FindTheTownJudge();

        int junde1 = test.findJudge(1, new int[][] {});

        Assert.assertEquals(1, junde1);

         

        int junde2 = test.findJudge(2, new int[][] {{1, 2}});

        Assert.assertEquals(2, junde2);

         

        int junde3 = test.findJudge(3, new int[][] {{1,3},{2,3}});

        Assert.assertEquals(3, junde3);

         

        int jundeN1 = test.findJudge(3, new int[][] {{1,3},{2,3},{3,1}});

        Assert.assertEquals(-1, jundeN1);

    }

}