当前位置：首页 > article >正文

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

article 2024/11/17 19:26:04

文章目录

- 1. 题目来源
- 2. 题目解析

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;
    }
};