3.1854.人口最多的年份(简单）
思想
1.给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。
年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。
返回 人口最多 且 最早 的年份。
代码
class Solution {
public:
typedef long long ll;
int maximumPopulation(vector<vector<int>>& logs) {
int n=logs.size();
int max_death=INT_MIN;
for(auto& log:logs) max_death=max(max_death,log[1]);
vector<int> d(max_death+1);
for(auto& log:logs){
int birth=log[0],death=log[1];
++d[birth];
--d[death];
}
int res=0;
ll sum=0,resSum=INT_MIN;
for(int i=0;i<max_death;++i){
sum+=d[i];
if(sum>resSum){
resSum=sum;
res=i;
}
}
return res;
}
};
4.2960.统计已测试设备(简单,学习)
思想
1.给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。
你的任务是按照顺序测试每个设备 i，执行以下测试操作：
- 如果
batteryPercentages[i]大于0：- 增加 已测试设备的计数。
- 将下标在
[i + 1, n - 1]的所有设备的电池百分比减少1(条件)，确保它们的电池百分比 不会低于0，即batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。 - 移动到下一个设备。
- 否则，移动到下一个设备而不执行任何测试。
返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。
2,因为题目条件是[i+1,n-1]都要减1，所以可以维护个变量dec,表示要减的值，如果当前的x-dec>0,则满足条件，dec增加，最终答案也是dec，即减的值，即，满足条件的设备数量
代码
class Solution {
public:
int countTestedDevices(vector<int>& batteryPercentages) {
int n=batteryPercentages.size();
int dec=0;
for(int& x:batteryPercentages){
if(x-dec>0){
++dec;
}
}
return dec;
}
};
5.1094.拼车(中等)
思想
1.车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
2.这题是[from,to),而不是[from,to],在to位置下车就不算位置了
代码
class Solution {
public:
typedef long long ll;
bool carPooling(vector<vector<int>>& trips, int capacity) {
int n=trips.size();
int max_to=INT_MIN;
for(auto trip:trips) max_to=max(max_to,trip[2]);
vector<ll> d(max_to+1,0);
for(auto& trip:trips){
int num=trip[0],from=trip[1],to=trip[2];
d[from]+=num;
d[to]-=num;
}
ll sum=0;
for(int i=0;i<max_to;++i){
sum+=d[i];
if(sum>capacity) return false;
}
return true;
}
};
6.1109.航班预定统计(中等)
思想
1.这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
2.[firsti, lasti]加上seatsi,且需显示得到数组a
代码
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
int len = bookings.size();
vector<int> res(n, 0);
vector<int> d(n + 1, 0);
for (auto& booking : bookings) {
int first = booking[0] - 1, last = booking[1] - 1,
seats = booking[2];
d[first] += seats;
d[last + 1] -= seats;
}
res[0] = d[0];
for (int i = 1; i < n; ++i) {
res[i] = res[i - 1] + d[i];
}
return res;
}
};
7.3355.零数组变换I(中等)
思想
1.给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。
对于每个查询 queries[i]：
- 在
nums的下标范围[li, ri]内选择一个下标 子集。 - 将选中的每个下标对应的元素值减 1。
零数组 是指所有元素都等于 0 的数组。
如果在按顺序处理所有查询后，可以将nums转换为 零数组 ，则返回true，否则返回false。
2.此题可以转化为[li,ri]不取下标子集，而去整个连续区间，让nums[i]<=0,若nums[i]<0,只要选择下标子集的时候不选则它让它减1，最终可以变成0
代码
class Solution {
public:
bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size(), m = queries.size();
vector<int> d(n + 1, 0);
d[0] = nums[0];
for (int i = 1; i < n; ++i)
d[i] = nums[i] - nums[i - 1];
for (auto& querie : queries) {
int l = querie[0], r = querie[1];
--d[l];
++d[r + 1];
}
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += d[i];
if (sum > 0)
return false;
}
return true;
}
};
8.56.合并区间(中等,学习.back方法)
思想
1.以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
代码
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
int n = intervals.size();
vector<vector<int>> res;
int start = intervals[0][0], end = intervals[0][1];
for (int i = 1; i < n; ++i) {
if (intervals[i][0] <= end) {
end = max(end, intervals[i][1]);
} else {
res.push_back({start, end});
start = intervals[i][0];
end = intervals[i][1];
}
}
res.push_back({start, end});
return res;
}
};
直接用.back修改res
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
int n = intervals.size();
vector<vector<int>> res;
for (auto& interval : intervals) {
if (!res.empty() && res.back()[1] >= interval[0]) {
// 可以合并取最大的，直接修改答案
res.back()[1] = max(res.back()[1], interval[1]);
} else {
res.push_back(interval);
}
}
return res;
}
};