LeetCode Hot100 普通数组

Posted on Edited on

最大子数组和

Problem

https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int sum = 0;
        for (int num : nums)
        {
            sum = max(num, num + sum);
            ans = max(ans, sum);
        }
        return ans;
    }
};

合并区间

Problem

https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked

Solution

按区间起点排序，若有重叠则合并区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        auto cmp = [](vector<int> a, vector<int> b)
        {
            return a[0] < b[0];
        };

        sort(intervals.begin(), intervals.end(), cmp);

        vector<vector<int>> ans;

        int tempStart = intervals[0][0];
        int tempEnd = intervals[0][1];
        for (int i = 1; i < intervals.size(); i ++)
        {
            if (intervals[i][0] <= tempEnd)
            {
                tempEnd = max(tempEnd, intervals[i][1]);
            }
            else
            {
                ans.push_back({tempStart, tempEnd});
                tempStart = intervals[i][0];
                tempEnd = intervals[i][1];
            }
        }

        ans.push_back({tempStart, tempEnd});
        return ans;
    }
};

轮转数组

Problem

https://leetcode.cn/problems/rotate-array/?envType=study-plan-v2&envId=top-100-liked

Solution

首先反转前n-realK个数，然后反转后realK个数，最后将整个数组反转

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int realK = k % n;

        reverse(nums.begin(), nums.begin() + (n - realK));
        reverse(nums.begin() + n - realK, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

除自身以外数组的乘积

Problem

https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked

Solution

从右往左遍历，记录从右往左的数组乘积，从左往右遍历，记录从左往右的乘积，结果=左右乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {

        int n = nums.size();
        vector<int> rightMul(n, 1);

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

        vector<int> ans(n, 1);
        int leftMul = 1;
        for (int i = 0; i < n; i ++)
        {
            ans[i] = leftMul * rightMul[i];
            leftMul = leftMul * nums[i];
        }
        return ans;
    }
};

缺失的第一个正数

Problem

https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked

Solution

大小为n的数组中，缺失第一个正整数一定在[1,n+1]中，将[1, n]以外的数全部修改为n+1，若存在[1, n]中的数，则将该数对应位置置为相反数，最后从左往右遍历数组，第一个正数位置对应的数即为缺失的第一个正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n; i ++)
        {
            if (nums[i] <= 0 || nums[i] > n)
            {
                nums[i] = n + 1;
            }
        }

        for (int i = 0; i < n; i ++)
        {
            int absNum = abs(nums[i]);
            if (absNum >= 1 && absNum <= n)
            {
                nums[absNum-1] = -abs(nums[absNum-1]);
            }
        }

        for (int i = 0; i < n; i ++)
        {
            if (nums[i] > 0)
            {
                return i + 1;
            }
        }
        return n + 1;
    }
};