[M模拟] lc3153. 所有数对中数位不同之和(模拟+按位统计)

1. 题目来源

链接：3153. 所有数对中数位不同之和

题单：

• 无
  • 无

2. 题目解析

简单题，数据范围很小，简单做即可。

思路：

• 按每一个数位进行统计。假设当前数位下有 x, y, z 这些不同的值，分别有 a,b,c 个。
• 显然根据乘法原理。就有 (a*b)+(a*c)+(b*c) 个 不相同的数对答案了呗。
• 即，两两相乘即可。这里枚举本身是有顺序的，不需要再对答案 /2。
• 当然也可以直接 a * (n-a) 即可，即统计当前位与其他不相同的位两两组合也行。这样的话最终需要将答案 / 2，因为是没有顺序的。

---

• 时间复杂度：$O(10^3)$
• 空间复杂度：$O(10^2)$

---

class Solution {
public:long long sumDigitDifferences(vector<int>& nums) {typedef long long LL;int cnt[10][10];memset(cnt, 0, sizeof(cnt));for (int x : nums) {int i = 0;while (x) {cnt[i ++ ][x % 10] ++ ;x /= 10;}}int n = to_string(nums[0]).size();LL res = 0;for (int i = 0; i < n; i ++ )for (int j = 0; j < 10; j ++ )for (int k = j + 1; k < 10; k ++ )res += 1ll * cnt[i][j] * cnt[i][k];return res;}
};