algo-aha

一组数的总hamming距离

• https://leetcode.com/problems/total-hamming-distance/

int totalHammingDistance(vector<int>& nums) {
    // 两数的hamming距离指两数二进制的不同比特数。
    // 可以总体考虑一组数的某一位，该位有ones个1、(N-ones)个零，
    // 那么这组数在该位上的hamming距离是ones*(N-ones)。累加所有位。
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        // 考查整组数的第i位
        int ones = 0;
        for (int num : nums) {
            if (num & (1 << i)) ones++;
        }
        ans += ones * (nums.size() - ones);
    }
    return ans;
}

任意两点的最大hamming距离

• https://leetcode.com/problems/maximum-of-absolute-value-expression/

int maxAbsValExpr(vector<int>& x, vector<int>& y) {
    // |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| (1)
    // 如果没有绝对值，式(1)=(arr1[i]+arr2[i]+i)-(arr1[j]+arr2[j]+j)
    // 令arr3[i]=arr1[i]+arr2[i]+i，式(1)=arr3[i]-arr3[j]，在arr3[]中找两数的最大差值
    // 现在加回绝对值，前两项各两种可能、第三项只一种可能，变成共有四种可能
    // 相当于在四种arr3[]中找两数的最大差值
    const int N = x.size();
    int ans = 0;
    vector<int> P{{-1, 1}};
    for (auto p1 : P) {
        for (auto p2 : P) {
            // 四种arr3[]，(x,y) => (p1*x, p2*y)
            // 每种都找其中两数的最大差值
            int theMin = INT_MAX, theMax = INT_MIN;
            for (int i = 0; i < N; i++) {
                int val = p1 * x[i] + p2 * y[i] + i;
                theMin = min(theMin, val);
                theMax = max(theMax, val);
                ans = max(ans, theMax - theMin);
            }
        }
    }
    return ans;
}