LeetCode 五月每日一题

28 汉明距离综合（Mid）

477. 汉明距离总和（Middle）

思路：用乘法法则，计算所有数字在每一位上的汉明距离差，再求总和

乘法法则：集合A有n种选择，集合B有m种选择，从A、B各选一个有nm种可能，在此处，因为在第i位上为1的数字和为0的数字汉明距离为1，因此组合后所有可能性即为第i位上的汉明距离数

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int cnt = 0;
        for (int i = 0; i < 32; i++)
        {
            int c = 0;
            for (int v : nums)
            {
                c += (v >> i) & 1;     // v的右数第i位为1，加入集合
            }
            cnt += c * (nums.size() - c);   // 乘法原理，计算在i位上所有数字的汉明距离之和
        }
        return cnt;
    }
};

小结：

• 更换一下遍历的顺序，可能会发现新思路，比如外层遍历每个数字改为外层遍历每一位

29 元素和为目标值的子矩阵数量 （Hard）

1074. 元素和为目标值的子矩阵数量（Hard）

解法：枚举列之和+前缀和+哈希

思路：

首先枚举行的上边界i和下边界j，

然后累计第i行到第j行之间的列元素之和sum，这个和也代表着列子矩阵元素之和，而累计过程中的相邻和之和又可以表示[i..j]行之间的任意子矩阵元素之和

最后利用和为k的子数组解法求sum中和为target的连续子数组个数，这些子数组即代表着元素和为target的子矩阵个数

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = 0;

        for (int i = 0; i < n; i++)			// 枚举上边界
        {
            vector<int> sum(m);
            for (int j = i; j < n; j++)			// 枚举下边界
            {
                for (int c = 0; c < m; c++)
                {
                    sum[c] += matrix[j][c];			// 累计各列元素之和
                }
                ans += subArraySum(sum, target);	// O(n), 求解和为k的子数组个数
            }
        }
        return ans;
    }
}

560. 和为K的子数组：

解法：前缀和+哈希

思路：

前缀和pre[i]表示[0..i]的元素之和，则字数组[j…i]元素和为pre[i] - pre[j - 1]

为了令pre[i] - pre[j - 1] = k，作移位，只需找到满足p = pre[j - 1] = pre[i] - k的前缀和p，p的个数即为所求

从左至右遍历计算前缀和，unordered_map使用前缀和的值作key，值出现的次数作value。初始时令mp[0]=1，因为未遍历时，前缀和初始值为0，因此0出现一次

class Solution {
public:
    int subArraySum(vector<int>& nums, int k) {
        int pre = 0;
        unordered_map<int, int> mp;     // 前缀和及其对应个数
        int ans = 0;
        mp[0] = 1;      // 未遍历时，有一个为0的前缀和
        for (auto& x : nums)
        {
            pre += x;
            if (mp.find(pre - k) != mp.end())
                ans += mp[pre - k];     // 记录满足条件的子数组个数
            mp[pre]++;      // 记录前缀
        }
        return ans;
    }
};

小结：

• 时间复杂度$O(n^2m)$，外两层循环$n^2$，最内层循环和subArraySum都为$m$

• 空间复杂度$O(m)$，sum数组占用

  • subArraySum的空间复杂度$O(n)$，其中n为输入的数组长度。因为哈希表最多有n个元素

30 2的幂（Easy）

231. 2 的幂（Easy）

思路：二进制表示的n只有一个1

解法一：n & (n - 1) == 0

原理：n & (n - 1)可消去一个数二进制表示的最低位1

以12为例，(1100) & (1011) = (1000) = 8，第2位的1被消去了

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && !(n & (n - 1));
    }
};

小结：

• n & (n - 1)消去最后一位1的思路，可以用于计算一个数二进制表示的1的个数

  while (n)
  {
      cnt++;
      n &= n - 1;
  }

---

解法二：-n & n == n

原理：-n & n仅保留二进制数的最低位1

令原数为$n = (a1000..)$，则$-n$补码表示为除符号位外按位取反，然后加一：

$$-n = (\bar{a}0111) + (1) = (\bar{a}1000)$$

因此$-n \& n = (0..01000…)$

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

31 4的幂（Easy）

342. 4的幂（Easy）

解法一：判断二进制表示中1的位置

原理：先确保仅有一个1（即n是2的幂，参考30），然后用掩码判断1所在的位置

掩码：

mask = 0b10101010101010101010101010101010 = 0xaaaaaaaa

class Solution {
public:
    bool isPowerOfFour(int n) {
        //return n > 0 && (n & (n - 1)) == 0 
        //    && (n & 0b10101010101010101010101010101010) == 0;
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

小结：使用掩码判断二进制中1的位置

本人的垃圾做法：用循环计算1的位置，然后判断位置是奇数还是偶数

日后遇到二进制1的位置判断要想到掩码

---

解法二：模3余1

原理：n是2的幂且是4的幂，$4^x$模3一定余1；若仅是2的幂而非4的幂，表示为$4^x \times 2$，模3余2

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
};