[M模拟] lc3153. 所有数对中数位不同之和(模拟+按位统计)
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接：3153. 所有数对中数位不同之和
题单：
- 无
- 无
2. 题目解析
简单题，数据范围很小，简单做即可。
思路：
- 按每一个数位进行统计。假设当前数位下有 x, y, z 这些不同的值，分别有 a,b,c 个。
- 显然根据乘法原理。就有
(a*b)+(a*c)+(b*c)个 不相同的数对答案了呗。 - 即，两两相乘即可。这里枚举本身是有顺序的，不需要再对答案 /2。
- 当然也可以直接 a * (n-a) 即可，即统计当前位与其他不相同的位两两组合也行。这样的话最终需要将答案 / 2，因为是没有顺序的。
- 时间复杂度： O ( 1 0 3 ) O(10^3) O(103)
- 空间复杂度： O ( 1 0 2 ) O(10^2) O(102)
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;}
};