LeetCode #997 Find the Town Judge

問題概要

入力値：s(string)
出力値：bool
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
[問題のリンク](Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.)

入力例

Input: n = 2, trust = [[1,2]]
Output: 2

解答例1

計算量：O(n)
Python

class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        if n == 1:
            return 1
        trust_dict = dict()
        trust_count = dict()
        for a, b in trust:
            if a in trust_dict:
                trust_dict[a] += 1
            else:
                trust_dict[a] = 1
            if b in trust_count:
                trust_count[b] += 1
            else:
                trust_count[b] = 1
        for i in range(1, n+1):
            if i not in trust_dict and \
               i in trust_count and \
               trust_count[i] == n - 1:
                return i
        return -1

Runtime: 550ms
Beats: 58.97%

C++

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if (n == 1) {
            return 1;
        }
        unordered_map<int, int> trust_dict;
        unordered_map<int, int> trust_count;
        for (auto data : trust) {
            int a = data[0];
            int b = data[1];
            if (trust_dict.contains(a)) {
                trust_dict[a] += 1;
            } else {
                trust_dict[a] = 1;
            }
            if (trust_count.contains(b)) {
                trust_count[b] += 1;
            } else {
                trust_count[b] = 1;
            }
        }
        for (int i=1; i<n+1; i++) {
            if (!trust_dict.contains(i) && trust_count.contains(i) && trust_count[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }
};

Runtime: 163ms
Beats: 7.86%