【算法优选】前缀和专题——叁

这篇具有很好参考价值的文章主要介绍了【算法优选】前缀和专题——叁。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

😎前言

含义

  • 前缀和实际上就是对于长度为n的数组,我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素)

特点

  1. 前缀和数组比原数组多一个长度。
  2. 前缀和的第0个元素的值为0。
  3. 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值+第i-1个前缀个数组的值就可能得到第i个前缀和数组的值。(这也是一种动态规划的思想)。

应用

  • 前缀和算法可以解决一些在数组中与连续有关的问题

🌴和为K的子数组

🚩题目描述

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

  • 示例 1:
    输入:nums = [1,1,1], k = 2
    输出:2

  • 示例 2:
    输入:nums = [1,2,3], k = 3
    输出:2

class Solution {
    public int subarraySum(int[] nums, int k) {

    }
}

🚩思路解析

【算法优选】前缀和专题——叁,算法优选,算法,数据结构,java,开发语言,前缀和
设 i 为数组中的任意位置,⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。

想知道有多少个「以 i 为结尾的和为 k 的⼦数组」,就要找到有多少个起始位置为 x1, x2,x3… 使得 [x, i] 区间内的所有元素的和为 k 。

那么 [0, x] 区间内的和是不是就是sum[i] - k 了。于是问题就变成:

  • 找到在 [0, i - 1] 区间内,有多少前缀和等于 sum[i] - k 的即可。

我们不⽤真的初始化⼀个前缀和数组,因为我们只关⼼在 i 位置之前,有多少个前缀和等于sum[i] - k 。因此,我们仅需⽤⼀个哈希表,⼀边求当前位置的前缀和,⼀边存下之前每⼀种前缀和出现的次数

🚩代码实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(0, 1);
        int sum = 0;
        int ret = 0;
        for(int x : nums)
        {
            sum += x; // 计算当前位置的前缀和
            ret += hash.getOrDefault(sum - k, 0); // 统计结果
            hash.put(sum, hash.getOrDefault(sum, 0) + 1); // 把当前的前缀和丢到哈希表⾥⾯
        }
        return ret;
    }
}

🎄和可被 K 整除的子数组

🚩题目描述

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空) 子数组 的数目。

子数组 是数组的 连续 部分。

  • 示例 1:
    输入:nums = [4,5,0,-2,-3,1], k = 5
    输出:7
    解释:
    有 7 个子数组满足其元素之和可被 k = 5 整除:
    [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

  • 示例 2:
    输入: nums = [5], k = 9
    输出: 0

class Solution {
    public int subarraysDivByK(int[] nums, int k) {

    }
}

🚩解题须知:

  • 同余定理

如果 (a - b) % n == 0 ,那么我们可以得到⼀个结论: a % n = = b % n 。

⽤⽂字叙述就是,如果两个数相减的差能被n整除,那么这两个数对n取模的结果相同。

  • Java中负数取模的结果,以及如何修正「负数取模」的结果

Java中关于负数的取模运算,结果是「把负数当成正数,取模之后的结果加上⼀个负号」。

例如: -1 % 3 = -(1 % 3) = -1

因为有负数,为了防⽌发⽣「出现负数」的结果,以 (a % n + n) % n 的形式输出保证为正。

例如: -1 % 3 = (-1 % 3 + 3) % 3 = 2

🚩算法思路:

思路与和为K的⼦数组这道题的思路相似
【算法优选】前缀和专题——叁,算法优选,算法,数据结构,java,开发语言,前缀和
设 i 为数组中的任意位置,⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。

  • 想知道有多少个「以 i 为结尾的可被 k 整除的⼦数组」,就要找到有多少个起始位置为 x1,x2, x3… 使得 [x, i] 区间内的所有元素的和可被 k 整除。

  • 设 [0, x - 1] 区间内所有元素之和等于 a , [0, i] 区间内所有元素的和等于 b ,可得(b - a) % k == 0 。

  • 由同余定理可得, [0, x - 1] 区间与 [0, i] 区间内的前缀和同余。于是问题就变成:

    • 找到在 [0, i - 1] 区间内,有多少前缀和的余数等于 sum[i] % k 的即可。

我们不⽤真的初始化⼀个前缀和数组,因为我们只关⼼在 i 位置之前,有多少个前缀和等于sum[i] - k 。因此,我们仅需⽤⼀个哈希表,⼀边求当前位置的前缀和,⼀边存下之前每⼀种前缀和出现的次数。

🚩代码实现

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(0 % k, 1);
        int sum = 0;
        int ret = 0;
        for(int x : nums)
        {
            sum += x; // 计算当前位置的前缀和
            int r = (sum % k + k) % k;
            ret += hash.getOrDefault(r, 0); // 统计结果
            hash.put(r, hash.getOrDefault(r, 0) + 1);
        }
        return ret;
    }
}

🌲连续数组

🚩题目描述

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

  • 示例 1:
    输入: nums = [0,1]
    输出: 2
    说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

  • 示例 2:
    输入: nums = [0,1,0]
    输出: 2
    说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

class Solution {
    public int findMaxLength(int[] nums) {

    }
}

🚩思路解析

稍微转化⼀下题⽬,就会变成我们熟悉的题:

  • 本题让我们找出⼀段连续的区间, 0 和 1 出现的次数相同。

  • 如果将 0 记为 -1 , 1 记为 1 ,问题就变成了找出⼀段区间,这段区间的和等于 0 。

  • 于是,就和560.和为K的⼦数组这道题的思路⼀样

【算法优选】前缀和专题——叁,算法优选,算法,数据结构,java,开发语言,前缀和
设 i 为数组中的任意位置,⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。
想知道最⼤的「以 i 为结尾的和为 0 的⼦数组」,就要找到从左往右第⼀个 x1 使得 [x1, i] 区间内的所有元素的和为 0 。那么 [0, x1 - 1] 区间内的和是不是就是 sum[i] 了。于是问题就变成:

  • 找到在 [0, i - 1] 区间内,第⼀次出现 sum[i] 的位置即可。我们不⽤真的初始化⼀个前缀和数组,因为我们只关⼼在 i 位置之前,第⼀个前缀和等于 sum[i] 的位置。因此,我们仅需⽤⼀个哈希表,⼀边求当前位置的前缀和,⼀边记录第⼀次出现该前缀和的位置。

🚩代码实现

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> hashmap = new HashMap<>();
        hashmap.put(0,-1);
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 0 ? -1 : 1);
            if(hashmap.containsKey(sum)) {
                ret = Math.max(ret,i - hashmap.get(sum));
            } else {
                hashmap.put(sum,i);
            }
        }
        return ret;
    }
}

🍀矩阵区域和

🚩题目描述

给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:

i - k <= r <= i + k, j - k <= c <= j + k 且(r, c) 在矩阵内。

  • 示例 1:
    输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
    输出:[[12,21,16],[27,45,33],[24,39,28]]

  • 示例 2:
    输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
    输出:[[45,45,45],[45,45,45],[45,45,45]]

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {

    }
}

🚩思路解析

⼆维前缀和的简单应⽤题,关键就是我们在填写结果矩阵的时候,要找到原矩阵对应区域的「左上⻆」以及「右下⻆」的坐标(推荐⼤家画图)

关于二维前缀和的求法,不懂得宝子可以去看看博主写的《【算法优选】 前缀和专题——壹》进行查看学习

左上⻆坐标: x1 = i - k,y1 = j - k ,但是由于会「超过矩阵」的范围,因此需要对 0 取⼀个 max 。因此修正后的坐标为: x1 = max(0, i - k), y1 = max(0, j - k) ;
右下⻆坐标: x1 = i + k,y1 = j + k ,但是由于会「超过矩阵」的范围,因此需要对 m- 1 ,以及 n - 1 取⼀个 min 。因此修正后的坐标为: x2 = min(m - 1, i + k),
y2 = min(n - 1, j + k)

然后将求出来的坐标代⼊到「⼆维前缀和矩阵」的计算公式上即可~(但是要注意下标的映射关系)

🚩代码实现

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        // 1. 预处理前缀和矩阵
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        // 2. 使⽤
        int[][] ret = new int[m][n];
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1;
                int y2 = Math.min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
}

⭕总结

关于《【算法优选】 前缀和专题——叁》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!文章来源地址https://www.toymoban.com/news/detail-737380.html

到了这里,关于【算法优选】前缀和专题——叁的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构和算法专题---4、限流算法与应用

    本章我们会对限流算法做个简单介绍,包括常用的限流算法(计数器、漏桶算法、令牌桶案发、滑动窗口)的概述、实现方式、典型场景做个说明。 限流是对系统的一种保护措施。即限制流量请求的频率(每秒处理多少个请求)。一般来说,当请求流量超过系统的瓶颈,则丢

    2024年02月04日
    浏览(49)
  • 【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    什么是前缀表达式、中缀表达式、后缀表达式 前缀表达式、中缀表达式、后缀表达式,是通过树来存储和计算表达式的三种不同方式 以如下公式为例 ( a + ( b − c ) ) ∗ d ( a+(b-c) )*d ( a + ( b − c ) ) ∗ d 通过树来存储该公式,可以表示为 那么问题就来了,树只是一种抽象的数据

    2024年02月08日
    浏览(44)
  • 数据结构——前缀、中缀、后缀表达式实现和转换(Java)

    1.7.1 概念 它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于 运算符相对与操作数的位置 不同 前缀 表达式的运算符位于与其相关的 操作数之前 ;中缀和后缀同理。 平时我们 日常使用 并最为熟悉的就是中缀表达式。如: 1 + 2 *

    2024年02月05日
    浏览(52)
  • 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(下)

    承接上一篇文章【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(上)】我们基本上对层级时间轮算法的基本原理有了一定的认识,本章节就从落地的角度进行分析和介绍如何通过Java进行实现一个属于我们自

    2023年04月08日
    浏览(42)
  • 【算法优选】 二分查找专题——贰

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用 顺序存储结构 ,而且表中元素按 有序排列 。 查找过程 : 首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,

    2024年02月08日
    浏览(43)
  • 【算法优选】 二分查找专题——壹

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用 顺序存储结构 ,而且表中元素按 有序排列 。 查找过程 : 首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,

    2024年02月08日
    浏览(46)
  • 【算法优选】双指针专题——壹

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(47)
  • 【算法优选】双指针专题——叁

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(46)
  • 【算法优选】双指针专题——贰

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(51)
  • 【算法优选】 滑动窗口专题——壹

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长

    2024年02月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包