LeetCode 热题 100-普通数组

最大子数组和

动态规划

划分阶段：按子数组结尾的位置划分阶段。
定义状态：dp[i]表示以nums[i]结尾的最大子数组和。
状态转移方程：dp[i] = max(dp[i-1], 0) + nums[i]。
初始条件：dp[0] = nums[0]。
返回结果：维护一个最大和变量。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.size(); i++){
            sum = max(sum, 0) + nums[i];
            ans = max(ans, sum);
        }
        return ans;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

终于能够不看提示和题解写出来了o(╥﹏╥)o，但是线段树的部分又忘了。

分治法

维护四个变量：

lSum：以l为左端点的最大子段和，lSum要么等于左子区间的lSum，要么等于左子区间的iSum+右子区间的lSum，取较大值。
rSum：以r为右端点的最大子段和，rSum要么等于右子区间的rSum，要么等于右子区间的iSum+左子区间的rSum，取较大值。
mSum：[l,r]区间内的最大和，它要么等于左子区间的mSum，要么等于右子区间的mSum，要么横跨两区间，即左子区间的rSum + 右子区间的lSum，三者取较大值。
iSum：[l,r]区间的和，等于左子区间的iSum + 右子区间iSum。

用结构体定义线段树的这4个状态；
定义线段树的pushup操作：即给定状态left和right，计算合并后的状态。
定义获取子区间的和的函数：给定数组和左右下标，递归计算左右子区间状态，返回合并后的状态。
返回结果：get(nums, 0, nums.size() - 1).mSum;

class Solution {
public:
    struct Status{
        int lSum, rSum, mSum, iSum;
    };

    // 定义线段树的pushup操作
    Status pushUp(Status left, Status right){
        int lSum = max(left.lSum, left.iSum + right.lSum);
        int rSum = max(right.rSum, right.iSum + left.rSum);
        int mSum = max({left.mSum, right.mSum, left.rSum + right.lSum});
        int iSum = left.iSum + right.iSum;

        return (Status){lSum, rSum, mSum, iSum}; 
    }
    // 获取区间和
    Status get(vector<int>& nums, int left, int right){
        // 递归结束
        if(left == right){
            return (Status){nums[left], nums[left], nums[left], nums[left]};
        }

        // 递归计算左右子区间
        int mid = (left + right) / 2;
        Status lSub = get(nums, left, mid);
        Status rSub = get(nums, mid+1, right);

        return pushUp(lSub, rSub);
    }
    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

时间复杂度：O(n)，把递归的过程看作是一颗二叉树的先序遍历。
空间复杂度：O(logn)，递归会使用 O(logn) 的栈空间，故渐进空间复杂度为 O(logn)。

合并区间

分析

先将所有区间安装起始时间升序排序，将第一个区间放入结果集，然后逐个遍历区间，如果当前区间的开始时间小于等于结果集中最后一个区间的结束时间，则将两区间合并，修改前一个区间的结束时间为两个区间结束时间的较大值。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        // 排序
        sort(intervals.begin(), intervals.end());
        ans.push_back(intervals[0]);
        // 逐个遍历
        for(int i = 1; i < intervals.size(); i++){
            // 合并区间
            if(intervals[i][0] <= ans.back()[1]){
                ans.back()[1] = max(intervals[i][1], ans.back()[1]);
            }else{
                ans.push_back(intervals[i]);
            }
        }

        return ans;
    }
};

时间复杂度：O(nlogn)，排序消耗的时间。
空间复杂度：O(logn)，结果不计入，排序所需要的空间复杂度。

补充知识

排序小技巧：

// 假如按照第1个数排序
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
});

轮转数组

直观解法

(下标 + k) % n就是新的位置。但是不能直接进行赋值，因为会覆盖还没有经过轮转的数字。可以用一个额外的数组：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> arr = nums;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            int index = (i + k) % n;
            nums[index] = arr[i];
        }
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

逆转数组

考虑将数组逆转，然后对于0~~k-1及k~~n-1的位置再进行逆转。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + (k % n));
        reverse(nums.begin() + (k % n), nums.end());
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

上面的解法是根据力扣提示做出来的，最后一个提示没太明白。

将元素放置在其正确的位置，并在附加变量中跟踪已经存在的元素或被覆盖的元素。

从位置 0 开始，最初令 temp=nums[0]。根据规则，位置 0 的元素会放至 (0+k)modn 的位置，令 x=(0+k)modn，此时交换 temp 和 nums[x]，完成位置 x 的更新。然后，我们考察位置 x，并交换 temp 和 nums[(x+k)modn]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0。

从 0 开始不断遍历，最终回到起点 0 的过程中，我们遍历了多少个元素？

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for(int start = 0; start < count; start++){
            int cur = start;
            int prev = nums[start];
            do{
                int next = (cur + k) % n;
                swap(prev, nums[next]);
                cur = next;
            }while(start != cur);
        }
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

这种解法不太好理解，之后再好好想想。

除自身以外数组的乘积

分析

计算前缀积和后缀积即可。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 1);
        vector<int> suffix(n, 1);

        for(int i = 1; i < n; i++){
            prefix[i] = prefix[i-1] * nums[i-1];
        }
        for(int i = n-2; i >= 0; i--){
            suffix[i] = suffix[i+1] * nums[i+1];
        }

        vector<int> ans(n);
        for(int i = 0; i < n; i++){
            ans[i] = prefix[i] * suffix[i];
        }

        return ans;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

优化空间

由于结果数组不计入空间复杂度，因此可以用结果数组直接保存前后缀积。即先计算后缀积，然后一边计算前缀积，一边得到最终结果。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> suffix(n, 1);
        for(int i = n - 2; i >= 0; i--){
            suffix[i] = suffix[i+1] * nums[i+1];
        }

        int pre = 1;
        for(int i = 0; i < n; i++){
            suffix[i] *= pre;
            pre *= nums[i];
        }

        return suffix;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

缺失的第一个正数

置换

对数组进行一次遍历，对于遍历到的数 x=nums[i]，如果 x∈[1,N]，我们就知道 x 应当出现在数组中的 x−1 的位置，因此交换 nums[i] 和 nums[x−1]，这样 x 就出现在了正确的位置。在完成交换后，新的 nums[i] 可能还在 [1,N] 的范围内，我们需要继续进行交换操作，直到 $x \notin [1,N]$。

注意到上面的方法可能会陷入死循环。如果 nums[i] 恰好与 nums[x−1] 相等，那么就会无限交换下去。此时我们有 nums[i]=x=nums[x−1]，说明 x 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            // 只考虑1~n之间的数，不断交换
            while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){
                swap(nums[i], nums[nums[i] - 1]); 
            }
        }

        // 找到不在位的数字
        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }

        return n + 1;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

算法笔记 > 数组

#leetcode-hot100

LeetCode 热题 100-普通数组

http://example.com/2024/11/26/posts/hot100-5/

作者

Xuan Yang

发布于

2024年11月26日

许可协议

LeetCode 热题 100-矩阵上一篇

LeetCode 热题 100-子串下一篇