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
|
// 3265. Count Almost Equal Pairs I
#include "leetcode.h"
/*
* you are given an array 'nums' consisting of positive integers. we call two
* integers 'x' and 'y' in this problem almost equal if both integers can become
* equal after performing the following operation at most once: choose either
* 'x' or 'y' and swap any two digits within the chosen number. return the
* number of indices 'i' and 'j' in 'nums' where 'i < j' such that 'nums[i]' and
* 'nums[j]' are almost equal. note that it is allowed for an integer to have
* leading zeros after performing an operation.
*/
struct hash {
int num;
int8_t count;
UT_hash_handle hh;
};
int countPairs(int *nums, int numsSize) {
int ans = 0, swapped, pow10[7] = {1000000, 100000, 10000, 1000, 100, 10, 1};
struct hash *table = NULL, *item;
for (int i = 0; i < numsSize; i++) {
swapped = nums[i];
HASH_FIND_INT(table, &swapped, item);
if (item)
ans += item->count++;
else {
item = (struct hash *)malloc(sizeof(struct hash));
item->num = swapped;
item->count = 1;
HASH_ADD_INT(table, num, item);
}
for (int j = 0; j < 6; j++)
for (int k = j + 1; k < 7; k++) {
int n = swapped / pow10[j] % 10;
int m = swapped / pow10[k] % 10;
if (n != m) {
swapped -= n * pow10[j];
swapped += m * pow10[j];
swapped -= m * pow10[k];
swapped += n * pow10[k];
HASH_FIND_INT(table, &swapped, item);
ans += item ? item->count : 0;
swapped -= n * pow10[k];
swapped += m * pow10[k];
swapped -= m * pow10[j];
swapped += n * pow10[j];
}
}
}
HASH_CLEAR(hh, table);
return ans;
}
int main() {
int n1[] = {3, 12, 30, 17, 21}, n2[] = {1, 1, 1, 1, 1}, n3[] = {123, 231};
printf("%d\n", countPairs(n1, ARRAY_SIZE(n1))); // expect: 2
printf("%d\n", countPairs(n2, ARRAY_SIZE(n2))); // expect: 10
printf("%d\n", countPairs(n3, ARRAY_SIZE(n3))); // expect: 0
}
|