Problem: 3153. 所有数对中数位不同之和
思路
本题关键在于如何处理数位不同的个数,其实就是组合问题,两个不同数字的不同数位只能算一对,所以我们不妨把后方元素与前方元素数位不同算作一对,保持单调性避免重复计数。
那么后方元素不同的数位应该如何统计呢,我们不妨使用哈希表,一维表示统计的数位位数,二维表示数位0~9。
某一数位位数下数位与前方元素不同的个数,就是当前遍历到的所有元素数目 - 该数位相同的元素个数(存储在哈希表中)。
Code
class Solution {
public:
long long sumDigitDifferences(vector<int>& nums) {
long long ans = 0;
vector<vector<int>> cnt(to_string(nums[0]).length(), vector<int>(10));
for(int k = 0; k < nums.size(); k++)
{
int x = nums[k];
for(int i = 0; x; x /= 10, i++)
{
ans += k - cnt[i][x % 10]++;
}
}
return ans;
}
};
标签:组合,nums,int,元素,long,算法,ans,数位
From: https://blog.csdn.net/2302_77423323/article/details/141713722