文章目录
普通数组53.最大子数组和56.合并区间189.轮转数组238.除自身以外数组的乘积41.缺失的第一个正数
普通数组
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 n = nums.size();
if(n==1) return nums[0];
vector
f[0] = nums[0];
int res = -2e9;
for(int i=1;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 vector 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 //说明是分离的 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 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 n=nums.size(); vector left[0]=1; right[n-1]=1; for(int i=1;i left[i]=left[i-1]*nums[i-1]; right[n-i-1] =right[n-i]*nums[n-i]; } vector for(int i=0;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 unordered_map for(auto c:nums) hash[c]++; for(int i=1;;i++){ if(!hash.count(i)) return i; } } }; class Solution { public: int firstMissingPositive(vector int n=nums.size(); for(int i=0;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 if(nums[i] != i+1) return i+1; } return nums.size()+1; } }; 精彩链接
发表评论