leetcode_811. 子域名访问计数
题目链接:https://leetcode.cn/problems/subdomain-visit-count/description/
涉及知识点:库函数atoi,库函数strstr,库函数strchr,库函数sprintf,UT_hash
解法一:自己构造结构体
#define LEN 100
typedef struct {
char str[LEN];
int cnt;
} MARK_S;
char ** subdomainVisits(char ** cpdomains, int cpdomainsSize, int* returnSize){
int i ,j;
MARK_S mark[300] = {0};
char temp[LEN];
int mark_size = 0;
for (i = 0; i < cpdomainsSize; i++) {
char *p = strstr(cpdomains[i], " ");
int space_index = p - cpdomains[i];
char rep[LEN] = {0};
memcpy(rep, cpdomains[i], sizeof(char) * space_index);
int count = atoi(rep);
strcpy(temp, cpdomains[i] + space_index + 1);
for (j = 0; j < mark_size; j++) {
if (strcmp(mark[j].str, temp) == 0) {
mark[j].cnt += count;
break;
}
}
if (j == mark_size) {
strcpy(mark[mark_size].str, temp);
mark[mark_size++].cnt = count;
}
p = strstr(cpdomains[i], ".");
while (p) {
strcpy(temp, p + 1);
for (j = 0; j < mark_size; j++) {
if (strcmp(mark[j].str, temp) == 0) {
mark[j].cnt += count;
break;
}
}
if (j == mark_size) {
strcpy(mark[mark_size].str, temp);
mark[mark_size++].cnt = count;
}
p = strstr(p + 1, ".");
}
}
*returnSize = mark_size;
char **ans = (char **)malloc(sizeof(char*) * mark_size);
for (i = 0; i < mark_size; i++) {
ans[i] = (char*)malloc(sizeof(char) * 110);
sprintf(ans[i], "%d %s", mark[i].cnt, mark[i].str);
}
return ans;
}
解法二:哈希表
typedef struct {
char *key;
int cnt;
UT_hash_handle hh;
} HASH_S;
HASH_S *usrs = NULL;
char ** subdomainVisits(char ** cpdomains, int cpdomainsSize, int* returnSize) {
HASH_S *cur, *next;
for (int i = 0; i < cpdomainsSize; i++) {
int count = atoi(cpdomains[i]);
int space_index = strchr(cpdomains[i], ' ') - cpdomains[i];
HASH_FIND_STR(usrs, cpdomains[i] + space_index + 1, cur);
if (!cur) {
cur = (HASH_S*)malloc(sizeof(HASH_S));
cur->key = cpdomains[i] + space_index + 1;
cur->cnt = count;
HASH_ADD_STR(usrs, key, cur);
} else {
cur->cnt += count;
}
int len = strlen(cpdomains[i]);
for (int j = space_index + 1; j < len; j++) {
if (cpdomains[i][j] != '.') {
continue;
}
HASH_FIND_STR(usrs, cpdomains[i] + j + 1, cur);
if (!cur) {
cur = (HASH_S*)malloc(sizeof(HASH_S));
cur->key = cpdomains[i] + j + 1;
cur->cnt = count;
HASH_ADD_STR(usrs, key, cur);
} else {
cur->cnt += count;
}
}
}
char **ans = (char**)malloc(sizeof(char*) * HASH_COUNT(usrs));
*returnSize = 0;
HASH_ITER(hh, usrs, cur, next) {
ans[*returnSize] = (char*)malloc(sizeof(char) * 110);
sprintf(ans[(*returnSize)++], "%d %s", cur->cnt, cur->key);
HASH_DEL(usrs, cur);
free(cur);
}
return ans;
}