2782. 唯一类别的数量
现给定一个整数 n 和一个 CategoryHandler 类的对象 categoryHandler 。
有 n 个元素，编号从 0 到 n - 1。每个元素都有一个类别，你的任务是找出唯一类别的数量。
CategoryHandler 类包含以下方法，可能对你有帮助：
boolean haveSameCategory(integer a, integer b)：如果 a 和 b 属于相同的类别，则返回 true，否则返回 false。同时，如果 a 或 b 不是有效的数字（即大于等于 n 或小于 0），它也会返回 false。返回 唯一类别的数量。
示例 1：
输入：n = 6, categoryHandler = [1,1,2,2,3,3] 输出：3 解释：这个示例中有 6 个元素。前两个元素属于类别 1，接下来两个属于类别 2，最后两个元素属于类别 3。所以有 3 个唯一类别。
示例 2：
输入：n = 5, categoryHandler = [1,2,3,4,5] 输出：5 解释：这个示例中有 5 个元素。每个元素属于一个唯一的类别。所以有 5 个唯一类别。
示例 3：
输入：n = 3, categoryHandler = [1,1,1] 输出：1 解释：这个示例中有 3 个元素。它们全部属于同一个类别。所以只有 1 个唯一类别。
提示：
1 <= n <= 100原站题解
java 解法, 执行用时: 39 ms, 内存消耗: 42.7 MB, 提交时间: 2023-10-16 21:02:18
/**
* Definition for a category handler.
* class CategoryHandler {
* public CategoryHandler(int[] categories);
* public boolean haveSameCategory(int a, int b);
* };
*/
class Solution {
public int numberOfCategories(int n, CategoryHandler categoryHandler) {
int[] ids = new int[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (ids[i] == 0) dfs(n,i,categoryHandler,ids,++count);
}
return count;
}
public void dfs(int n,int v , CategoryHandler categoryHandler ,int[] ids,int id){
if (ids[v] != 0) return;
ids[v] = id;
for (int i = v+1; i < n; i++) {
if (categoryHandler.haveSameCategory(v,i)) dfs(n,i,categoryHandler,ids,id);
}
}
}
// 并查集
class Solution2 {
int count;
public int numberOfCategories(int n, CategoryHandler categoryHandler) {
int[] parent = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (categoryHandler.haveSameCategory(i,j)) quickUnion(i,j,parent);
}
}
return count;
}
public void quickUnion(int x,int y,int[] parent){
int rx = getParent(x,parent);
int ry = getParent(y,parent);
if (rx != ry){
count--;
parent[rx] = ry;
}
}
public int getParent(int x,int[] parent){
if (x != parent[x]){
parent[x] = getParent(parent[x],parent);
}
return parent[x];
}
}
typescript 解法, 执行用时: 176 ms, 内存消耗: 51.3 MB, 提交时间: 2023-10-16 21:01:31
/**
* 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 set = new Set();
for (let i = 0; i < n; i++) {
let f = false;
for(let j of Array.from(set)) {
if(categoryHandler.haveSameCategory(i, j as number)) {
f = true;
break;
}
}
if(!f) {
set.add(i);
}
}
return set.size;
};
python3 解法, 执行用时: 1964 ms, 内存消耗: 16.7 MB, 提交时间: 2023-10-16 21:00:57
# 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:
dc = set()
for i in range(n):
for j in dc:
if categoryHandler.haveSameCategory(i,j): break
else: dc.add(i)
return len(dc)