leetcode997：找到小镇的法官（find-the-town-judge）

carloscn commented 1 year ago

问题描述

code:find_the_town_judge_997.rs

小镇里有 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/problems/find-the-town-judge

carloscn commented 1 year ago

问题分析

以测试驱动开发：

    #[test]
    fn test_demo() {
        let ret = find_judge(3,vec![
            vec![1, 3],
            vec![2, 3]]);
        assert_eq!(ret, 3); // pass

        let ret = find_judge(3,vec![
            vec![1, 2],
            vec![1, 3],
            vec![2, 3]]);
        assert_eq!(ret, 3); // all trust 3, 3 don't trust others., pass

        let ret = find_judge(3,vec![
            vec![1, 2],
            vec![1, 3],
            vec![1, 1]]);
        assert_eq!(ret, -1); // 2 cannot trust 3, failed

        let ret = find_judge(3,vec![
            vec![1, 2],
            vec![2, 3],
            vec![3, 1]]);
        assert_eq!(ret, -1); // 3 trusted 1, failed
    }

准备一个数组AUX，按照坐标位布局，出现信任别人，在自己的位就-1，然后信任的那个人+1：

循环e in vec，aux[vec[i][0]] -= 1; aux[vec[i][1]] += 1. 对aux循环，找到 e in aux { if e == n - 1 找到，else -1}

pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32
{
    if 0 == trust.len() || 0 == n {
        return -1;
    }
    let mut aux:Vec<i32> = vec![0;(n + 1) as usize];

    for i in 0..trust.len() {
        aux[trust[i][0] as usize] -= 1;
        aux[trust[i][1] as usize] += 1;
    }

    for i in 1..(aux.len()) {
        if aux[i] == n - 1 {
            return i as i32;
        }
    }

    return -1;
}

carloscn commented 1 year ago

code

https://github.com/carloscn/structstudy/commit/e23c05348e674b8c458da631e5d1b0150de010b9 https://review.gerrithub.io/c/carloscn/structstudy/+/552151

carloscn / structstudy