力扣hot100_普通数组
hot100_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 -
提示：
-
-
1 <= nums.length <= 105
-
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = nums[0];
vector<int> dp(nums.size());//d[i]标识以 nums[i]结尾的连续子序列的最大和
dp[0] = nums[0];
for(int i = 1;i<nums.size();i++)
{
dp[i] = max(dp[i -1] + nums[i],nums[i]); //求子序列的最大和
result = max(result,dp[i]); //d[i]当前子序列最大和，和之前子序列最大和比较
}
return result;
}
};
int main(){
vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
Solution A;
cout << A.maxSubArray(nums) << endl;
return 0;
}
hot100_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] 可被视为重叠区间。
提示：
-
1 <= intervals.length <= 104 -
intervals[i].length == 2 -
0 <= starti <= endi <= 104
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if (intervals.size() == 0) return result;
// 排序的参数使用了lamda表达式
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (result.back()[1] >= intervals[i][0]) { // 合并区间
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]);
}
}
return result;
}
};
int main(){
vector<vector<int>> nums = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
Solution A;
vector<vector<int>> result = A.comp(nums);
for(int i = 0; i < result.size(); i++){
cout << "[" << i[0] <<",3 " << i[1] << "], " ;
}
cout<<endl;
return 0;
}
hot100_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]
提示：
-
1 <= nums.length <= 105 -
-231 <= nums[i] <= 231 - 1 -
0 <= k <= 105
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
k %= len;
if(k == 0) return;
reverse(nums.begin(), nums.begin() + len - k); //逆转前len-k个元素
reverse(nums.begin() +len -k , nums.end()); //逆转后面k个元素
reverse(nums.begin(), nums.end()); //逆转整个数组
}
};
int main(){
vector<int> nums = {1, 2, 3, 4 ,5, 6, 7};
int k = 3;
Solution A;
A.rotate(nums,k);
for(int i = 0; i < nums.size(); i++){
cout << nums[i] << " " ;
}
cout<<endl;
return 0;
}
hot100_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]
提示：
-
2 <= nums.length <= 105 -
-30 <= nums[i] <= 30 -
输入 保证 数组
answer[i]在 32 位 整数范围内
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int length = nums.size();
vector<int> answer(length);
// answer[i] 表示索引 i 左侧所有元素的乘积
// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
answer[0] = 1;
for (int i = 1; i < length; i++) {
answer[i] = nums[i - 1] * answer[i - 1];
}
// R 为右侧所有元素的乘积
// 刚开始右边没有元素，所以 R = 1
int R = 1;
for (int i = length - 1; i >= 0; i--) {
// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
answer[i] = answer[i] * R;
// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
R *= nums[i];//其实就是等到i-1轮的时候用的
}
return answer;
}
};
hot100_41.缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
提示：
-
1 <= nums.length <= 105 -
-231 <= nums[i] <= 231 - 1
class Solution{
public:
int firstMissingPositive(vector<int> &nums){
if (nums.size() == 0){
return 1;
}
int i = 0;
while (i < nums.size()){
if (nums[i] > 0 && nums[i] != i + 1 && nums[i] - 1 < nums.size() && nums[nums[i] - 1] != nums[i]){
swap(nums[i], nums[nums[i] - 1]);
}
else{
i++;
}
}
for (i = 0; i < nums.size(); i++){
if (nums[i] != i + 1){
break;
}
}
return i + 1;
}
};