LeetCode_单周赛

6291. 数组元素和与数字和的绝对差

代码

模拟即可

class Solution {

    public int differenceOfSum(int[] nums) {

        int ans = 0;

        int sum = 0;

        for (int i = 0; i < nums.length; i++) {

            int t = nums[i];

            ans += t;

            while (t > 0) {

                sum += t % 10;

                t /= 10;

            }

        }

        return Math.abs(ans - sum);

    }

}

6292. 子矩阵元素加 1

代码

差分模板

但是在处理的时候，因为差分数组下标从 1 开始比较方便，所以我们让 q 中的值都 +1

最后返回结果时，原数组 = 差分数组的前缀和

为了符合下标从 0 开始的要求，我们定义数组 a，作为结果返回，存储时下标 -1 存储

class Solution {

    private int[][] b;

    public int[][] rangeAddQueries(int n, int[][] q) {

        b = new int[n + 10][n + 10];

        for (var a : q) {

            insert(a[0] + 1, a[1] + 1, a[2] + 1, a[3] + 1);

        }

        int[][] a = new int[n][n];

        for (int i = 1; i <= n; i++) {

            for (int j = 1; j <= n; j++) {

                b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1];

                a[i - 1][j - 1] = b[i][j];

            }

        }

        return a;

    }

    private void insert(int x1, int y1, int x2, int y2) {

        b[x1][y1] += 1;

        b[x2 + 1][y1] -= 1;

        b[x1][y2 + 1] -= 1;

        b[x2 + 1][y2 + 1] += 1;

    }

}

6293. 统计好子数组的数目

代码

双指针

map存储每个数出现的次数

从左往右进行双指针，先左指针不动，一直右移右指针，直到满足条件 / 到达边界为止

如果满足条件

则以 l 为左端点，r 右边的端点都满足。左端点为 l 的情况就找完了，不用再遍历左端点为 l 的情况了。
此时不断向右移动左指针，看是否满足(这一步用while，保证此时的右边界 r 不变)

不满足条件就继续移动

class Solution {

    public long countGood(int[] a, int k) {

        int l = 0, r = 1, n = a.length;

        long t = 0;

        long ans = 0;

        boolean[] vis = new boolean[n + 10];

        HashMap<Integer, Integer> map = new HashMap<>();

        map.put(a[l], 1);

        vis[0] = true;

        while (l < r && r < n) {

            if (!vis[r] && map.getOrDefault(a[r], 0) >= 1) {

                t += map.get(a[r]);

            }

            if (!vis[r]) map.put(a[r], map.getOrDefault(a[r], 0) + 1);

            vis[r] = true;

            while (t >= k) {

                ans += n - r;

                t -= map.get(a[l]) - 1;

                map.put(a[l], map.get(a[l]) - 1);

                l++;

            }

            r++;

        }

        return ans;

    }

}

巴特西

LeetCode_单周赛_328

6291. 数组元素和与数字和的绝对差

代码

6292. 子矩阵元素加 1

代码

6293. 统计好子数组的数目

代码

最新文章

热门文章