?前言?
开更五月集训专题，由浅入深，深入浅出，飞向大厂！
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
?全文大约阅读时间： 20min
全文目录
1480. 一维数组的动态和
解题思路
直接计算就好了。
代码
class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
int n = nums.size();
for(int i = 1;i < n;++i) nums[i] += nums[i -1];
return nums;
}
};
注意的点
没啥
1588. 所有奇数长度子数组的和
解题思路
比上面的更进一步
代码
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
int n = arr.size(),ans = 0;
for(int i = 1;i < n;++i) arr[i] += arr[i -1];
for(int i = 1;i <= n;i += 2){
ans += arr[i - 1];
for(int j = 1;j + i <= n;++j)
ans += arr[j + i - 1] - arr[j - 1];
}
return ans;
}
};
注意的点
我这都快纯c了。。。。
1442. 形成两个异或相等数组的三元组数目
解题思路
直接求前缀异或和就好了。
代码
class Solution {
public:
int countTriplets(vector<int>& arr) {
int n = arr.size(),ans = 0;
for(int i = 1;i < n;++i) arr[i] ^= arr[i-1];
unordered_map<int,int> Maps;
for(int j = 1;j < n;++j){
Maps.clear();
++Maps[arr[j - 1]];//i == 0
for(int i = 1;i < j;++i) ++Maps[arr[j - 1] ^ arr[i - 1]];
for(int k = j;k < n;++k)
ans+= Maps[arr[k] ^ arr[j - 1]];
}
return ans;
}
};
注意的点
三维枚举可以用j做划分，然后用hash表加速。
1094. 拼车
解题思路
根据每个时刻的人数统计出来，不超过座位的个数就是可以的，否则返回false。
代码
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> nownum(1002);
int sum = 0;
for(auto trip : trips)
nownum[trip[2]] -= trip[0],nownum[trip[1]] += trip[0];
for(int i = 0;i < 1001;i++){
sum += nownum[i];
if(sum > capacity) return false;
}
return true;
}
};
注意的点
- C++的好多操作还是不是很熟悉。
写在最后
周赛炸了，水墨屏烧完了，考试快要开始了，心态爆炸ing-。-
