Go/C语言LeetCode题解997找到小镇法官

目录
  • 题目描述
  • 思路分析
  • go 代码
  • C语言
    • 暴力法

题目描述

997. 找到小镇的法官 - 力扣（LeetCode）

小镇里有 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 <= 10^4

trust[i].length == 2[=

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

ai != bi

1 <= ai, bi <= n

思路分析

记录每个人被信任的次数。 信任次数为n-1的人就是法官

同时如果这个人信任别过人就让他的被信任次数-1 (这个操作主要是判断一个人不是法官，如果一个人被其他人信任了n-1次，那么这个人可能是法官，如果这个人信任过别人，那么让他的被信任次数-1，他的被信任次数为n-2!=n-1。这样就满足了法官不能信别人的逻辑，他也就不是法官。)

有人被信任的次数为n-1,那么他就是法官！没有这样的人，那么返回-1.

go 代码

class Solution {
    public static int findJudge(int n, int[][] trust) {
        int[] times=new int[n+1];
        for(int i=0;i&lt;trust.length;i++){
            times[trust[i][1]]++;
            times[trust[i][0]]--;
        }
        for(int i=1;i&lt;=n;i++){
            if(times[i]==n-1) return i;
        }
        return -1;
    }
}

C语言

暴力法

关键点：

1：关键点两个，一个是相信的人数，一个是不能相信人

2：用hashSet去记录，如果相信别人，那么这个人的信用设置为负数。

3：被相信的人，hashSet信用值增加

时间复杂度：O(n)

空间复杂度：O(n)

代码

int findJudge(int n, int** trust, int trustSize, int* trustColSize)
{
    //根据入度进行遍历
    int hashSet[n+1]; //相信这个i的人数
    memset(hashSet,0, sizeof(hashSet));
    for(int i = 0; i < trustSize; i++)
    {
        hashSet[trust[i][1]]++;
        //相信别人 就不能是法官
        hashSet[trust[i][0]] = INT_MIN;

    }
      for(int i = 1; i <= n; i++)
    {
        if(hashSet[i] == n-1 )
        {
            return i;
        }
    }
          return -1;
}

参考

一题两解：哈希表 & 优化！ - 找到小镇的法官 - 力扣（LeetCode）

以上就是Go/C语言LeetCode题解997找到小镇法官的详细内容，更多关于Go/C语言题解找到小镇法官的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode1796字符串中第二大数字

    目录 LeetCode 1796.字符串中第二大的数字 方法一:遍历 题目分析 解题思路 复杂度分析 AC代码 C++ LeetCode 1796.字符串中第二大的数字 力扣题目链接:leetcode.cn/problems/se… 给你一个混合字符串 s ,请你返回 s 中 第二大 的数字,如果不存在第二大的数字,请你返回 -1 . 混合字符串 由小写英文字母和数字组成. 示例 1: 输入:s = "dfa12321afd"输出:2解释:出现在 s 中的数字包括 [1, 2, 3]

  • C++ LeetCode1769移动所有球到每个盒子最小操作数示例

    目录 LeetCode 1769.移动所有球到每个盒子所需的最小操作数 方法一:数学思维 AC代码 C++ LeetCode 1769.移动所有球到每个盒子所需的最小操作数 力扣题目链接:leetcode.cn/problems/mi… 有 n 个盒子.给你一个长度为 n 的二进制字符串 boxes ,其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的,而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球. 在一步操作中,你可以将 一个 小球从某个盒子移动到一个与之相

  • C/C++哈希表优化LeetCode题解997找到小镇的法官

    目录 方法一.哈希表 方法二.优化 方法一.哈希表 今天这道题比较简单,我们可以统计每个人信任别人的数量和被信任的数量,如果存在某个人信任别人的数量为0,且被信任的数量为 n-1,那么,这个人就是法官. 因为本题的数据范围为 [1,1000],数据范围比较小,所以,直接使用数组作为哈希表来使用. 请看代码: class Solution { public int findJudge(int n, int[][] trust) { // 不信任任何人的人 & 被所有人信任的人 // 计算每个人信任

  • go语言LeetCode题解1030距离顺序排列矩阵单元格

    目录 一 描述 二 分析 三 答案 一 描述 1030. 距离顺序排列矩阵单元格 - 力扣(LeetCode) (leetcode-cn.com) 给定四个整数 row ,   cols ,  rCenter 和 cCenter .有一个 rows x cols 的矩阵,你在单元格上的坐标是 (rCenter, cCenter) . 返回矩阵中的所有单元格的坐标,并按与 (rCenter, cCenter) 的 距离 从最小到最大的顺序排.你可以按 任何 满足此条件的顺序返回答案. 单元格(r1

  • Go/C语言LeetCode题解997找到小镇法官

    目录 题目描述 思路分析 go 代码 C语言 暴力法 题目描述 997. 找到小镇的法官 - 力扣(LeetCode) 小镇里有 n 个人,按从 1 到 n 的顺序编号.传言称,这些人中有一个暗地里是小镇法官. 如果小镇法官真的存在,那么: 小镇法官不会信任任何人. 每个人(除了小镇法官)都信任这位小镇法官. 只有一个人同时满足属性 1 和属性 2 . 给你一个数组 trust ,其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人. 如果小镇法官存在并且可

  • Go语言LeetCode题解706设计哈希映射

    目录 题目描述 思路分析 AC 代码 题目描述 706. 设计哈希映射 不使用任何内建的哈希表库设计一个哈希映射(HashMap). 实现 MyHashMap 类: MyHashMap() 用空映射初始化对象 void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) .如果 key 已经存在于映射中,则更新其对应的值 value . int get(int key) 返回特定的 key 所映射的 value :如果映射中不包含 key

  • go语言LeetCode题解720词典中最长的单词

    目录 一 描述 二 分析 三 答案 四 总结 一 描述 720. 词典中最长的单词 - 力扣(LeetCode) (leetcode-cn.com) 给出一个字符串数组 words 组成的一本英语词典.返回 words 中最长的一个单词,该单词是由 words 词典中其他单词逐步添加一个字母组成. 若其中有多个可行的答案,则返回答案中字典序最小的单词.若无答案,则返回空字符串. 示例 1: 输入:words = ["w","wo","wor",&

  • Go语言LeetCode题解937重新排列日志文件

    目录 一 题目描述 二 分析 三 答案 一 题目描述 937. 重新排列日志文件 - 力扣(LeetCode) (leetcode-cn.com) 给你一个日志数组 logs.每条日志都是以空格分隔的字串,其第一个字为字母与数字混合的 标识符 . 有两种不同类型的日志: 字母日志:除标识符之外,所有字均由小写字母组成 数字日志:除标识符之外,所有字均由数字组成 请按下述规则将日志重新排序: 所有 字母日志 都排在 数字日志 之前. 字母日志 在内容不同时,忽略标识符后,按内容字母顺序排序:在内容

  • Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

    目录 题目描述 思路分析 AC 代码 题目描述 961. 在长度 2N 的数组中找出重复 N 次的元素 给你一个整数数组 nums ,该数组具有以下属性: nums.length == 2 * n. nums 包含 n + 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素. 示例 1: 输入:nums = [1,2,3,3] 输出:3 示例 2: 输入:nums = [2,1,2,5,3,2] 输出:2 示例 3: 输入:nums = [5,1,5,

  • Go语言leetcode题解953验证外星语词典示例详解

    目录 题目描述 思路分析 AC 代码 题目描述 953. 验证外星语词典 某种外星语也使用英文小写字母,但可能顺序 order 不同.字母表的顺序(order)是一些小写字母的排列. 给定一组用外星语书写的单词 words,以及其字母表的顺序 order,只有当给定的单词在这种外星语中按字典序排列时,返回 true:否则,返回 false. 示例 1: 输入:words = ["hello","leetcode"], order = "hlabcdefgi

  • LeetCode 题解 Swift 有效的完全平方数

    LeetCode 题解 Swift 有效的完全平方数

    目录 题目 方法一:使用内置的库函数 思路及解法 复杂度分析 方法二:暴力 思路及解法 代码 复杂度分析 方法三:二分查找 思路及解法 细节 代码 复杂度分析 题目 给定一个 正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 true,否则返回 false. 进阶:不要 使用任何内置的库函数,如 sqrt. 示例 1: 输入: num = 16 输出: true 示例 2: 输入: num = 14 输出: false 方法一:使用内置的库函数 思路及解法 根据完全平方数的性

  • C C++ LeetCode题解在二叉树中增加一行示例详解

    C C++ LeetCode题解在二叉树中增加一行示例详解

    目录 题目描述 整理题意 解题思路分析 层序遍历(广度优先搜索) 递归(深度优先搜索) 具体实现 复杂度分析 代码实现 层序遍历(广度优先搜索) 递归(深度优先搜索) 总结 题目描述 题目链接:623. 在二叉树中增加一行 给定一个二叉树的根 root 和两个整数 val 和 depth ,在给定的深度 depth 处添加一个值为 val 的节点行. 注意,根节点 root 位于深度 1 . 加法规则如下: 给定整数 depth,对于深度为 depth - 1 的每个非空树节点 cur ,创建两

  • go语言算法题解二叉树的最小深度

    目录 题目: 说明: 解法: 题目: 给定一个二叉树,找出其最小深度. 最小深度是从根节点到最近叶子节点的最短路径上的节点数量. 说明: 叶子节点是指没有子节点的节点. 解法: func minDepth(root *TreeNode) int { if root == nil { return 0 } minDepth := math.MaxInt64 var dfs func(node *TreeNode, depth int) dfs = func(node *TreeNode, dept

随机推荐