1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
// 2284. Sender With Largest Word Count
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* you have a chat log of 'n' messages. you are given two string arrays
* 'messages' and 'senders' where 'messages[i]' is a message sent by
* 'senders[i]'. a message is a list of words that are separated by a single
* space with no leading or trailing spaces. the word count of a sender is the
* total number of words sent by the sender. note that a sender may send more
* than one message. return the sender with the largest word count. if there is
* more than one sender with the largest word count, return the one with the
* lexicographically largest name
*/
typedef struct {
uint val;
char *str;
int cnt;
} dict;
uint rs_hash(char *str) {
uint a = 63689, b = 378551, hash = 0;
while (*str) {
hash = hash * a + (*str++);
a *= b;
}
return (hash & 0x7FFFFFFF);
}
int cmp(const void *a, const void *b) {
dict aa = **(dict **)a;
dict bb = **(dict **)b;
if (aa.cnt == bb.cnt)
return strcmp(aa.str, bb.str);
return aa.cnt - bb.cnt;
}
char *largestWordCount(char **messages, int messages_size, char **senders,
int senders_size) {
int n = senders_size, *words = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
int len = strlen(messages[i]);
if (!len) {
words[i] = 0;
continue;
}
words[i] = 1;
for (int j = 0; j < len; j++)
if (messages[i][j] == ' ')
words[i]++;
dict **hash = malloc(n * sizeof(dict *));
for (int i = 0; i < n; i++) {
hash[i] = malloc(sizeof(dict));
hash[i]->cnt = 0;
}
int max = 0, pos = 0;
dict **max_data = malloc(n * sizeof(dict *));
for (int i = 0; i < n; i++) {
uint h = rs_hash(senders[i]);
if (!hash[h % n]->cnt) {
hash[h % n]->cnt = words[i];
int len = strlen(senders[i]);
hash[h % n]->str = malloc((len + 1) * sizeof(char));
strcpy(hash[h % n]->str, senders[i]);
hash[h % n]->val = h;
if (hash[h % n]->cnt == max) {
max_data[pos] = hash[h % n];
pos++;
}
if (hash[h % n]->cnt > max) {
pos = 0;
max = hash[h % n]->cnt;
max_data[pos] = hash[h % n];
pos++;
}
} else if (hash[h % n]->val == h) {
hash[h % n]->cnt += words[i];
if (hash[h % n]->cnt == max) {
max_data[pos] = hash[h % n];
pos++;
}
if (hash[h % n]->cnt > max) {
pos = 0;
max = hash[h % n]->cnt;
max_data[pos] = hash[h % n];
pos++;
}
} else {
int k = (h + 1) % n;
bool done = false;
while (hash[k]->cnt) {
if (hash[k]->val == h) {
hash[k]->cnt += words[i];
if (hash[k]->cnt == max) {
max_data[pos] = hash[k];
pos++;
}
if (hash[k]->cnt > max) {
pos = 0;
max = hash[k]->cnt;
max_data[pos] = hash[k];
pos++;
}
done = true;
break;
}
k = (k + 1) % n;
}
if (!done) {
hash[k]->val = h;
hash[k]->cnt = words[i];
int len = strlen(senders[i]);
hash[k]->str = malloc((len + 1) * sizeof(char));
strcpy(hash[k]->str, senders[i]);
if (hash[k]->cnt == max) {
max_data[pos] = hash[k];
pos++;
}
if (hash[k]->cnt > max) {
pos = 0;
max = hash[k]->cnt;
max_data[pos] = hash[k];
pos++;
}
}
}
}
qsort(max_data, pos, sizeof(dict *), cmp);
return max_data[pos - 1]->str;
}
}
int main() {
char m1[4][19] = {"Hello userTwooo", "Hi userThree", "Wonderful day Alice",
"Nice day userThree"};
char s1[4][9] = {"Alice", "userTwo", "userThree", "Alice"};
char m2[2][31] = {"How is leetcode for everyone",
"Leetcode is useful for practice"};
char s2[2][7] = {"Bob", "Charlie"};
printf("%s\n", largestWordCount(m1, 4, s1, 4)); // expect: Alice
printf("%s\n", largestWordCount(m2, 2, s2, 2)); // expect: Charlie
}
|