Question

2782. Number of Unique Categories

中文文档

Description

You are given an integer n and an object categoryHandler of class CategoryHandler.

There are n elements, numbered from 0 to n - 1. Each element has a category, and your task is to find the number of unique categories.

The class CategoryHandler contains the following function, which may help you:

• boolean haveSameCategory(integer a, integer b): Returns true if a and b are in the same category and false otherwise. Also, if either a or b is not a valid number (i.e. it's greater than or equal to nor less than 0), it returns false.

Return _the number of unique categories._

 

Example 1:

Input: n = 6, categoryHandler = [1,1,2,2,3,3]
Output: 3
Explanation: There are 6 elements in this example. The first two elements belong to category 1, the second two belong to category 2, and the last two elements belong to category 3. So there are 3 unique categories.

Example 2:

Input: n = 5, categoryHandler = [1,2,3,4,5]
Output: 5
Explanation: There are 5 elements in this example. Each element belongs to a unique category. So there are 5 unique categories.

Example 3:

Input: n = 3, categoryHandler = [1,1,1]
Output: 1
Explanation: There are 3 elements in this example. All of them belong to one category. So there is only 1 unique category.

 

Constraints:

• 1 <= n <= 100

Solutions

Solution 1

# Definition for a category handler.
# class CategoryHandler:
#   def haveSameCategory(self, a: int, b: int) -> bool:
#     pass
class Solution:
  def numberOfCategories(
    self, n: int, categoryHandler: Optional['CategoryHandler']
  ) -> int:
    def find(x: int) -> int:
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    p = list(range(n))
    for a in range(n):
      for b in range(a + 1, n):
        if categoryHandler.haveSameCategory(a, b):
          p[find(a)] = find(b)
    return sum(i == x for i, x in enumerate(p))

/**
 * Definition for a category handler.
 * class CategoryHandler {
 *   public CategoryHandler(int[] categories);
 *   public boolean haveSameCategory(int a, int b);
 * };
 */
class Solution {
  private int[] p;

  public int numberOfCategories(int n, CategoryHandler categoryHandler) {
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    for (int a = 0; a < n; ++a) {
      for (int b = a + 1; b < n; ++b) {
        if (categoryHandler.haveSameCategory(a, b)) {
          p[find(a)] = find(b);
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (i == p[i]) {
        ++ans;
      }
    }
    return ans;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

/**
 * Definition for a category handler.
 * class CategoryHandler {
 * public:
 *   CategoryHandler(vector<int> categories);
 *   bool haveSameCategory(int a, int b);
 * };
 */
class Solution {
public:
  int numberOfCategories(int n, CategoryHandler* categoryHandler) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    };
    for (int a = 0; a < n; ++a) {
      for (int b = a + 1; b < n; ++b) {
        if (categoryHandler->haveSameCategory(a, b)) {
          p[find(a)] = find(b);
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += i == p[i];
    }
    return ans;
  }
};

/**
 * Definition for a category handler.
 * type CategoryHandler interface {
 *  HaveSameCategory(int, int) bool
 * }
 */
func numberOfCategories(n int, categoryHandler CategoryHandler) (ans int) {
  p := make([]int, n)
  for i := range p {
    p[i] = i
  }
  var find func(int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  for a := 0; a < n; a++ {
    for b := a + 1; b < n; b++ {
      if categoryHandler.HaveSameCategory(a, b) {
        p[find(a)] = find(b)
      }
    }
  }
  for i, x := range p {
    if i == x {
      ans++
    }
  }
  return
}

/**
 * Definition for a category handler.
 * class CategoryHandler {
 *   constructor(categories: number[]);
 *   public haveSameCategory(a: number, b: number): boolean;
 * }
 */
function numberOfCategories(n: number, categoryHandler: CategoryHandler): number {
  const p: number[] = new Array(n).fill(0).map((_, i) => i);
  const find = (x: number): number => {
    if (p[x] !== x) {
      p[x] = find(p[x]);
    }
    return p[x];
  };
  for (let a = 0; a < n; ++a) {
    for (let b = a + 1; b < n; ++b) {
      if (categoryHandler.haveSameCategory(a, b)) {
        p[find(a)] = find(b);
      }
    }
  }
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    if (i === p[i]) {
      ++ans;
    }
  }
  return ans;
}