前缀和数组—动态规划的一种

LeetCode 303 区域和检索-数组不可变 2023.12.30

• 题目链接
• labuladong讲解[链接]
  

class NumArray {
public:
    NumArray(vector<int>& nums) {
        //num = nums; //暴力求解
        //简单动态规划
        dp.resize(nums.size());
        dp[0] = nums[0];
        for(int i = 1; i < nums.size(); i++)
            dp[i] = dp[i-1] + nums[i];
    }
    
    int sumRange(int left, int right) {
        //暴力求解
        // int sum = 0;
        // while(left <= right)
        // {
        //     sum += num[left];
        //     left++;
        // }
        // return sum;
        //简单动态规划
        //因为dp[i]表示nums[0]+xxx+nums[i]，所以需要区分left是否为0
        if(left == 0)
            return dp[right];
        return dp[right] - dp[left-1];

    }
    //vector<int> num; //暴力求解
    vector<int> dp;
};

---

LeetCode 304 二维区域和检索-矩阵不可变 2023.12.31

• 题目链接
• labuladong讲解[链接]
  

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        //暴力求解超时
        // matrix_value = matrix;
        
        //简直就是动态规划，我写的很low，看题解吧
        dp.resize(matrix.size());
        int num = 0;
        for(int i = 0; i < matrix.size(); i++)
        {
            dp[i].resize(matrix[0].size());
            dp[i][0] = num + matrix[i][0];
            num = dp[i][0];
        }
        num = 0;
        for(int j = 0; j < matrix[0].size(); j++)
        {
            dp[0][j] = num + matrix[0][j];
            num = dp[0][j];
        }
        for(int i = 1; i < matrix.size(); i++)
        {
            for(int j = 1; j < matrix[0].size(); j++)
            {
                dp[i][j] = dp[i][j-1] + dp[i-1][j] + matrix[i][j] - dp[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        /*暴力求解超时
        int sum = 0;
        int curcol = col1;
        while(row1 <= row2)
        {
            while(curcol <= col2)
            {
                sum += matrix_value[row1][curcol];
                curcol++;
            }
            curcol = col1;
            row1++;
        }
        return sum; */
        // cout << dp[0][2] << endl << dp[0][1] << endl;
        if(row1 == 0 && col1 == 0)
            return dp[row2][col2];
        else if(row1 == 0 && col1 != 0)
            return dp[row2][col2] - dp[row2][col1-1];
        else if(row1 != 0 && col1 == 0)
            return dp[row2][col2] - dp[row1-1][col2];
        return dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1-1] + dp[row1-1][col1-1];
    }
    //暴力求解超时
    // vector<vector<int>> matrix_value;
    vector<vector<int>> dp;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

---

差分数组–前缀和数组的升级

LeetCode 1094 拼车 2023.12.31

• 题目链接
• labuladong讲解[链接]
  

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        //差分数组，第一次见，对着答案写的
        //num[i]表示到达每个车站时车上的人数,默认每一站车上人数为0
        vector<int> nums(1001, 0);
        //构造差分解法
        Difference df(nums);
        
        //遍历每一次trip
        for(const auto& trip : trips)
        {
            //乘客数量
            int val = trip[0];
            //乘客上站的位置,从该站开始车上人数增多
            int i = trip[1];
            //乘客下站的位置，从该站开始车上人数减少
            int j = trip[2]-1;
            //那么人数增多的区间是[trip[0], trip[j]-1]
            df.increment(i, j, val);
        }
        //到此就更新完了diff数组

        //更新nums数组
        vector<int> res = df.result();

        //判断车辆在每个站的人数是否超过capacity
        for(int i = 0; i < res.size(); i++)
            if(capacity < res[i])
                return false;
        return true;
    }

    //差分数组工具类
    class Difference
    {
        //差分数组
        vector<int> diff;
        //输入一个初始数组，区间操作将在这个数组上进行
    public:
        Difference(vector<int>& nums)
        {
            //构造差分数组df
            diff.resize(nums.size());
            diff[0] = nums[0];
            for(int i = 1; i < nums.size(); i++)
                diff[i] = nums[i] - nums[i-1];
        }

        //给nums数组中[i, j]区间增加val值，其可正可负
        void increment(int i, int j,  int val)
        {
            //从nums[i]开始增加val
            diff[i] += val;
            //从nums[j+1]开始恢复正常，不变
            if(j+1 < diff.size())
                diff[j+1] -= val;
        }

        //返回变动后的nums数组
        vector<int> result()
        {
            vector<int> res(diff.size());
            //根据diff数组更新nums新数组的值
            res[0] = diff[0];
            for(int i = 1; i < diff.size(); i++)
                res[i] = res[i-1] + diff[i];
            //返回nums新数组
            return res;
        }
    };
};

---