数组

看着就简单好欺负

以后再写…

启动!

53.最大子数组和

Kadane算法

DP + 贪心

很好理解

解:

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

56.合并区间

先按区间起点排序，然后维护一个结果数组，每次只需要判断当前区间是否和结果数组最后一个区间重叠，重叠就合并，不重叠就加入新区间~

注意auto的使用~

解:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.empty()) return {};

        // 按区间起点排序
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> res;
        res.push_back(intervals[0]);

        // 扫描并合并
        for(int i = 1; i < intervals.size(); i++) {
            auto& last = res.back();
            auto& cur = intervals[i];

            if(cur[0] <= last[1]) {
                // 有重叠 合并
                last[1] = max(last[1], cur[1]);
            }else {
                // 无重叠 加入新区间
                res.push_back(cur);
            }
        }
        return res;
    }
};

189.轮转数组

非常easy好吧

解法1:

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

解法2:

class Solution {
public:
    void reverse(vector<int>& nums, int l, int r) {
        while (l < r) {
            swap(nums[l++], nums[r--]);
        }
    }
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
};

238.除了自身以外数组的乘积

解法1:

前缀积 + 后缀积

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

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

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

解法2:

滚动后缀积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);

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

        int right = 1;
        for(int i = n - 1; i >= 0; i--) {
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }
};

41.缺失的第一个正数

解:

数学思想

“困难”?

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for(int i = 0; i < n; i++) {
            while(nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                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;
    }
};