力扣热题100道-普通数组篇

普通数组

53.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

/**
思路：求前缀和：
如果前缀和为负数，则舍弃掉前缀，采用当前值为最大。
如果为正数，则利用上前缀和
**/

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //可以求出前缀和 找出最大值和最小值
        int n = nums.size();
        if(n==1) return nums[0];
        vector<int> f(n);
        f[0] = nums[0];
        int res = -2e9;
        for(int i=1;i<n;i++){
            f[i]=max(nums[i],f[i-1]+nums[i]);
            res = max(f[i],res);
        }
        return max(res,f[0]);
    }
};

56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

/*
先将起始位置从头到尾进行排序，然后判断是否有重叠的，有重叠的将末尾更新为最新的即可
*/

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<pair<int,int>> s;
        vector<vector<int>> res;
        for(auto c:intervals) s.push_back({c[0],c[1]});
        sort(s.begin(),s.end());
        int st=-1,ed=-1;
        for(auto c:s){
            if(ed<c.first){
                //说明是分离的
                if(ed != -1) res.push_back({st,ed});
                st = c.first,ed=c.second;
            }else ed=max(ed,c.second);
        }
        res.push_back({st,ed});
        return res;
    }
};

189.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

/*
思路 
两部分都逆置
然后整体逆置
*/

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; // 处理 k 大于数组长度的情况
        reverse(nums.begin(),nums.end()-k);
        reverse(nums.end()-k,nums.end());
        reverse(nums.begin(),nums.end());
    }
};

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

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(*n*) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

/*
思路：针对每个数字算左边的乘积和右边的乘积，然后遍历每个数字将左右两部分的乘积乘起来即可
*/

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //针对每个数算一个左边的乘积和右边的乘积
        int n=nums.size();
        vector<int> left(n),right(n);
        left[0]=1;
        right[n-1]=1;
        for(int i=1;i<nums.size();i++){
            left[i]=left[i-1]*nums[i-1];            
            right[n-i-1] =right[n-i]*nums[n-i];
        }
        vector<int> res(n);
        for(int i=0;i<n;i++){
            res[i]=left[i]*right[i];
        }
        return res;
    }
};

41.缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

/**
思路1：哈希表法，但不是使用常数级别额外空间，代码较简单
思路2：将每个元素放到正确的位置，原地交换，不停进行检查直到当前位置为负数或者大于n或者已经放到正确位置才退出循环
**/

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(auto c:nums) hash[c]++;
        for(int i=1;;i++){
            if(!hash.count(i)) return i;
        }
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<nums.size();i++){
            while(nums[i] !=i+1)
            {
                //while循环是不停检查
                if(nums[i]<=0 || nums[i]>n || nums[i] == nums[nums[i]-1]){
                    break;
                }
                //进行互换 nums[3]=8则 将nums[7]的值赋值为nums[3],nums[7]=8;
                int idx = nums[i]-1;
                nums[i] = nums[idx];
                nums[idx] = idx+1;
            }

        }
        for(int i=0;i<nums.size();i++){
            if(nums[i] != i+1) return i+1;
        }
        return nums.size()+1;
    }
};