java数据结构与算法刷题-----LeetCode303. 区域和检索 - 数组不可变

2024-01-07 21:51:05
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只不过大家都叫它dp),达到空间换时间的效果。它仅仅只是一种优化思路,因此它目前的境地和线性代数一样----虚假的难。

  1. 想想线性代数,在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时,完全摸不着头脑,一上来就是行列式和矩阵,根本不知道这玩意是干嘛的。
  2. 线性代数从根本上是在空间上研究向量,抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。
  3. 反观国内的教材,直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候,只会觉得一知半解,觉得麻烦,完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候,发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材,什么狗东西(以上是自己学完线性代数后的吐槽,我们同学无一例外都这么觉得)。

而我想告诉你,动态规划和线性代数一样,我学完了才知道,它不过就是研究空间换时间,提前将固定的重复操作规划到dp数组中,而不用暴力求解,从而让效率极大提升。

  1. 但是网上教动态规划的兄弟们,你直接给一个动态方程是怎么回事?和线性代数,一上来就教行列式和矩阵一样,纯属恶心人。我差不多做了30多道动态规划题目,才理解,动态方程只是一个步骤而已,而这已经浪费我很长时间了,我每道题都一知半解不理解,过程及其痛苦。最后只能重新做。
  2. 动态规划,一定是优先考虑重复操作与dp数组之间的关系,搞清楚后,再提出动态方程。而你们前面步骤省略了不讲,一上来给个方程,不是纯属扯淡吗?
  3. 我推荐研究动态规划题目,按5个步骤,从上到下依次来分析
  1. DP数组及下标含义
  2. 递推公式
  3. dp数组初始化
  4. 数组遍历顺序(双重循环及以上时,才考虑)
  5. dp数组打印,分析思路是否正确(相当于做完题,检查一下)

在这里插入图片描述

先理解题目细节

在这里插入图片描述

解题思路
  1. 暴力求解的思想,就是每次都遍历数组,将指定区间的那几个元素相加。
  2. 但是如果我们预先将其存储到dp数组,就可以直接通过dp, 获取数据,而不用枚举。典型的动态规划题目
动态规划思考5步曲
  1. DP数组及下标含义
  1. 先看时间和空间复杂度高的思路:我们要求出的是某个区间的元素和,那么dp数组中存储的就是某个区间元素和。要求出谁的元素和呢?显然是某个区间,那么下标就是代表区间的左右边界,显然,如果这样考虑需要2个下标表示,故这道题的dp数组需要二维数组。例如dp[3][5] = 区间(3,5)的元素和
  2. 但是一个线性区间,我们可以用数学思路,先获取整体的区间和,在去掉多余的。例如(2,5)区间包含在(0,5)中,其中(0,1)区间是我们不需要的。我们只需要保存整个区间,也就是从0开始的区间,然后去掉多余的即可。也就是(2,5) = (0,5) - (0,1)
  1. 递推公式
  1. 很明显,我们只考虑从下标为0的元素开始,到每个边界的元素和。而(0,0)区间只有一个元素,需要特殊考虑。
  1. 起点[0,0]的区间和固定为其本身。F(0) = 其本身
  2. 其余的,都是从0开始到其所在位置的总和,而每个元素前一个位置,都保存了从0开始到它的元素总和。故我们只需要将自己的数值+前面区间的值。F(n) = F(n-1)+其本身的值
  1. 但是别忘了,我们这个dp是抽象处理了的,如果区间要求的是从0开始,那么可以直接用我们这个一维数组的dp返回,但是,如果要的不是从0开始的呢?
  1. 从0开始的区间,直接return dp[n]即可。因为我们dp数组本身保存的就是从0开始到n的区间和
  2. 从left开始的区间(left>0), return dp[n] - dp[left-1]. 例如(2,5)区间,left = 2,我们需要这样获取它:(2,5) = (0,5) - (0,1) === dp[5] - dp[2 - 1]
  1. dp数组初始化

在这里插入图片描述

  1. 数组遍历顺序(单重循环,无需考虑遍历顺序,一共就一维,哪里来的谁先谁后)
  2. 打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)

具体看最上面了解题目细节那里吧。写这篇文章用的学校的电脑,用不了java

代码:时间复杂度初始化dp时O(n),之后查询区间值为O(1).空间复杂度O(n)

在这里插入图片描述

class NumArray {
    private int dp[] = null;//dp数组,一维表示,保存从0开始的区间(0,0),(0,1),(0,2)...(0,n)
    public NumArray(int[] nums) {
        this.dp = new int[nums.length];//让dp数组与nums数组长度保持一致
        this.dp[0] = nums[0];//(0,0)区间只有一个元素值nums[0]
        //保存其余从0开始的区间, 例如(0,1)区间 = (0,0)区间+nums[1]本身
        for(int i = 1;i<nums.length;i++){
            dp[i] = dp[i-1]+nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        if(left == 0) return dp[right];//如果是从0开始的区间,直接返回dp中的值即可
        else return dp[right]-dp[left-1];//不是从0开始,需要特殊处理,(2,5) = (0,5) - (0,1)
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */

文章来源:https://blog.csdn.net/grd_java/article/details/135438129
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。