Leetcode 2771

Link:

2711. 对角线上不同值的数量差 - 给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算： * 令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上不同值的数量。 * 令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上不同值的数量。然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。返回矩阵 answer 。矩阵对角线是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。示例 1： [https://assets.leetcode.com/uploads/2023/04/19/ex2.png] 输入：grid = [[1,2,3],[3,1,5],[3,2,1]] 输出：[[1,1,0],[1,0,1],[0,1,1]] 解释：第 1 个图表示最初的矩阵 grid 。第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。 - 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。 - 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。 - 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。其他单元格的对应答案也可以按照这样的流程进行计算。示例 2：输入：grid = [[1]] 输出：[[0]] 解释：- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。提示： * m == grid.length * n == grid[i].length * 1 <= m, n, grid[i][j] <= 50

https://leetcode.cn/problems/difference-of-number-of-distinct-values-on-diagonals/

题目要求

给定一个m * n矩阵，对每一个位置，求其所在主对角线的 | 左上角所有元素中不同元素的个数 - 右下角所有元素中不同元素的个数 |，记录到answer矩阵的对应位置注：grid[i][j] ≤ 50

核心算法和原理

对角线的遍历模板：对于同一主 / 副对角线上的元素，其下标一定满足i - j / i + j 为定值

主对角线：令k = i - j + n，则左下角的对角线 k = m + n - 1，右上角的 k = 1

副对角线：令k = i + j，则左上角的k = 0，右下角的k = m + n - 2

遍历每条对角线的前后缀（不同元素的个数），则ans[i][j] = 对应位置的前后缀之差的绝对值，可以直接记录到ans里

位运算优化：grid元素最大50，拿一个uint64_t记录不同元素个数

popcount(i): i的二进制表示中1的个数

代码


class Solution {
public:
    vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> ans(m, vector<int>(n, 0));
        uint64_t cntBit = 0;
        // diagnoals iteration: i - j is const
        // k = i - j + n, left below: k = m + n - 1, right above: k = 1
        for (int k = 1; k < m + n; k++) {
            int minj = max(0, n - k);
            int maxj = min(n - 1, m + n - 1 - k);

            cntBit = 0;
            for (int j = minj; j <= maxj; j++) {
                int i = k - n + j;
                ans[i][j] = popcount(cntBit);
                cntBit |= (1ULL << grid[i][j]);
            }

            cntBit = 0;
            for (int j = maxj; j >= minj; j--) {
                int i = k - n + j;
                ans[i][j] = abs(ans[i][j] - popcount(cntBit));
                cntBit |= (1ULL << grid[i][j]);
            }
        }
        return ans;
    }
};