5

算法系列：数组类题目

 2 years ago
source link: https://muyuuuu.github.io/2022/05/22/array-series/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

算法系列：数组类题目

2022-05-22

1 6k 5 分钟

之前没有很留意，没想到大一学过的数组也能有很多精彩的算法题。本文收录了数组类算法常见的：前缀和、差分数组、常数时间查找和删除数组元素和数组去重问题。

  • 前缀和数组：用于频繁求解给定区间内，数组元素的和
  • 差分数组：用于频繁更改给定区间内数组元素的取值，最后得到数组

前面两个侧重频繁修改数组，常规模拟算法必然超时。而至于常数时间内查找和删除数组元素，数组元素去重已经是固定要求的题目了，文末直接给出题解。

前缀和就是输入数组的累计和：

presum[0] = arr[0];
for (int i = 1; i < n; i++)
    presum[i] = presum[i-1] + sum[i];

因此， presum[r] - presum[l-1] 就是数组在区间 [l,r] 内的和。

前缀和算法一般用于求解以下问题：需要频繁的调用某个方法，这个方法需要求出数组在给定区间中元素的和。如果每次查询都要遍历数组求和，会超时的很严重，因此需要使用前缀和来解决。但是众所周知算法不可能这么简单，一边看题一边看前缀和的细节。

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

给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和 ，其中 left <= right。实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] ) 。示例 1：
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

这个是典型的求解区间数组和的题目，如果每次都暴力计算会超时。因此我们使用前缀和数组来解决问题。

class NumArray {
public:

vector<int> presum;
    NumArray(vector<int>& nums) {
        presum.resize(nums.size());
        presum.assign(nums.size(), 0);
        // 构建前缀和
        presum[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            presum[i] = presum[i-1] + nums[i];
        }
    }

int sumRange(int left, int right) {
        if (left == 0)
            return presum[right];
        return presum[right] - presum[left - 1];
    }
};

一般不建议这么写，因为 left-1 很容易越界，涉及到二维数组十分不好处理。因此，推荐的写法是，前缀和数组比输入数组大一个维度。此时，只需要让 right+1 即可。

class NumArray {
public:

vector<int> presum;
    NumArray(vector<int>& nums) {
        presum.resize(nums.size() + 1);
        presum.assign(nums.size() + 1, 0);
        // 前缀和数组
        for (int i = 1; i <= nums.size(); i++) {
            presum[i] = presum[i-1] + nums[i-1];
        }
    }

int sumRange(int left, int right) {
        return presum[right + 1] - presum[left];
    }
};

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

给定一个二维矩阵 matrix，以下类型的多个请求：计算其子矩形范围内元素的总和，该子矩阵的 左上角为 (row1, col1) ，右下角为 (row2, col2) 。实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

对于二维数组，方法还是和一维数组一样，我们求某个坐标对应的前缀和就可以了。但是迫切建议前缀和数组大一个维度，不然边界情况真的很难处理。和一维数组一样，构建数组的前缀和数组，在求解指定区间的数组和时，也是两个边界相减就行，但是有一点点细节要处理。

class NumMatrix {
public:
    vector<vector<int>> presum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        presum.resize(m + 1);
        for (int i = 0; i <= m; i++) {
            presum[i].assign(n + 1, 0);
        }
        presum[0][0] = matrix[0][0];
        // 构建二维前缀和数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                presum[i][j] = matrix[i-1][j-1] + presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1];
            }
        }
    }
    // 区间相减，但是要注意 presum[row1][col1] 减了两次
    int sumRegion(int row1, int col1, int row2, int col2) {
        return presum[row2+1][col2+1] - presum[row1][col2+1] - presum[row2+1][col1] + presum[row1][col1];
    }
};

1124. 表现良好的最长时间段

这个是和单调栈的梦幻联动，掌握了这个题，前缀和学的就可以了。

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格大于「不劳累的天数」。请你返回「表现良好时间段」的最大长度。示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

一开始的时候毫无头绪，甚至暴力模拟也没有什么太好的思路，直到看了题解。

  1. 因为工作时长以 8 小时为划分，不管是 10 小时还是 13 小时，本质是一样的，7 小时和 8 小时的本质也是一样的。因此，我们新建一个数组 score，大于 8 为 1，否则为 -1。
  2. 根据 score 构建前缀和数组，前缀和数组元素的值越大，表示近期的工作表现越良好。换一种说法，如果 score 数组呈现了上升的趋势，那么说明今天在好好工作。
  3. 因此，我们只需要求前缀和数组中的最大上升跨度，就是劳累天数严格大于不劳累天数，结果即为表现良好的时间段。最大跨度请参考单调栈那篇文章的最后一题。
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        vector<int> presum(n + 1, 0);
        vector<int> socre(n, 0);
        for (int i = 0; i < n; i++) {
            socre[i] = hours[i] > 8 ? 1 : -1;
        }
        // 前缀和
        for (int i = 1; i <= n; i++) {
            presum[i] = presum[i-1] + socre[i-1];
        }
        // 单调递减栈
        stack<int> stk;
        for (int i = 0; i < n + 1; i++) {
            if (stk.empty() || presum[stk.top()] > presum[i]) {
                stk.push(i);
            }
        }
        // 最大上升跨度
        int ans = 0;
        for (int i = n; i >= 0; i--) {
            while (stk.size() && presum[stk.top()] < presum[i]) {
                ans = max(ans, i - stk.top());
                stk.pop();
            }
        }
        return ans;
    }
};

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减，然后问你修改后的数组是多少。差分数组的构造方式为：

diff[0] = arr[0];
for (int i = 1; i < n; i++) {
    diff[i] = arr[i] - arr[i-1];
}

如果让数组区间 [l, r] 内的元素增加 3，只需要让 diff[l]+3, diff[r]-3 即可 （自己画图理解下）。而通过 diff 也能得到原始的数组：

arr[0] = diff[0];
for (int i = 1; i < n; i++) {
    arr[i] = arr[i-1] + diff[i];
}

1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [first[i], last[i], seats[i]] 意味着在从 first[i] 到 last[i] （包含 first[i] 和 last[i] ）的每个航班上预订了 seats[i] 个座位。请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

典型的差分数组应用：

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto i : bookings) {
            int s = i[0] - 1;
            int e = i[1] - 1;
            int v = i[2];
            diff[s] += v;
            // 防止越界
            if (e + 1 <= n - 1)
                diff[e + 1] -= v;
        }
        vector<int> res(n, 0);
        res[0] = diff[0];
        for (int i = 1; i < n; i++) {
            res[i] = res[i-1] + diff[i];
        }
        return res ;
    }
};

车上最初有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向。给定整数 capacity 和一个数组 trips , trip[i] = [numPassengers[i], from[i], to[i]] 表示第 i 次旅行有 numPassengers[i] 乘客，接他们和放他们的位置分别是 from[i] 和 to[i] 。这些位置是从汽车的初始位置向东的公里数。当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

这里需要注意的是，比如客户 A 在 5 下车，而客户 B 在 5 上车，此时是能顺利交接的。因此，下车的时候，diff[r]-n 即可，不需要占用 r 处的容量。可以理解为，在地点 4 ，车上就没有客户了。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1005, 0);
        for (auto i : trips) {
            int v = i[0];
            int s = i[1];
            int e = i[2];
            diff[s] += v;
            diff[e] -= v;
        }
        vector<int> res(1005, 0);
        res[0] = diff[0];
        // 细节判断
        if (res[0] > capacity)
            return false;
        for (int i = 1; i < 1005; i++) {
            res[i] = res[i-1] + diff[i];
            if (res[i] > capacity)
                return false;
        }
        return true;
    }
};

O(1)时间的数组查找与删除


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK