这次只做出了三道题
6184. 统计共同度过的日子数
- 不熟悉api，没用过
sscanf，在处理日期字符串的时候耽误了很多时间，最后用的substr()和stoi(stoi还是现场在网上搜的,哈哈哈) - 没有及时把重复代码提取出去，多写了很多行
class Solution {
public:
int month[32] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int getDays(string date){
int mon, day;
sscanf(date.c_str(), "%d-%d", &mon, &day);
for(int i = 1; i < mon; i++)
day += month[i];
return day;
}
int countDaysTogether(string as, string ae, string bs, string be){
int ast = getDays(as), aed = getDays(ae),
bst = getDays(bs), bed = getDays(be);
if(aed < bst || ast > bed) return 0;
return min(aed, bed) - max(ast, bst) + 1;
}
};
6185. 运动员和训练师的最大匹配数
这道题做的很快，3分钟就出来了，就是一个很简单的贪心问题，这里给出证明
经过排序后进行的选择一定是最优解，假设某个解不是按照顺序进行选择的，比如说，能力为2的运动员训练师能力为8，而能力为4的运动员训练师能力为6，此时可以把他们的训练师对换且结果不会发生变化，因此得证，
这是很经典的贪心证明方法
class Solution {
public:
int matchPlayersAndTrainers(vector<int>& a, vector<int>& b) {
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0, j = 0, ans = 0;
for(; i < a.size() && j < b.size(); j++)
if(a[i] <= b[j]) i++, ans++;
return ans;
}
};
6186. 按位或最大的最小子数组长度
这个题我用的方法比较复杂
//我的垃圾代码
class Solution {
public:
vector<int> smallestSubarrays(vector<int>& nums) {
vector<int> save(32); //save数组存储每个位置1的个数
int n = nums.size();
vector<int> ans(n);
int max = 0, tmp = 0;
for(int i = 0; i < n; i++) max |= nums[i];
for(int i = 0, j = -1; i < n - 1; i++){
if(i){ //从1位置开始,每次都要删除前一个位置的数
int val = nums[i - 1];
for(int k = 0; val; k++, val >>= 1) //把要删除数的1去掉,
if(val & 1) {
--save[k];
if (!save[k]) //如果去掉后对应位置1个数变为0,那就异或掉这个数
tmp ^= 1 << k;
}
}
int ss = j, st = tmp;
while(j < n - 1 && tmp < max){ //每次向后移动 或 一个新的数时
int val = nums[++j];
tmp |= val;
if(tmp > st)
ss = j, st = tmp;
for(int k = 0; val; k++, val >>= 1) //把这个数每个有1的位置加到save数组中
if(val & 1)
save[k]++;
}
for(int u = ss + 1; u <= j; u++){
int val = nums[u];
for(int k = 0; val; k++, val >>= 1)
if(val & 1)
--save[k];
}
if(i > ss) ss = i;
j = ss;
ans[i] = j - i + 1;
}
ans[n - 1] = 1;
return ans;
}
};
然后看了大神的题解，就...很简洁，
(位运算) \(O(nlogS)\)
独立每一位看，每个位置的最短子数组就是寻找其位置之后第一个出现 1 的位置，如果其之后没有出现 1 的位置，则当前位置的最短子数组就是自身。
这样可以从后向前维护一个指针 p（初始位置可以为 0），记录出现 1 时最靠前的位置，每次用当前位置的值来更新 p。
拓展到更多位也同理，相当于寻找所有位中，出现 1 且最靠后的位置作为最短子数组的结束点。
时间复杂度
遍历数组一次，每个位置需要 \(O(logS)\) 的时间遍历所有位，故总时间复杂度为 \(O(nlogS)\)。
空间复杂度
需要 \(O(n+logS)\) 的额外空间存储答案和 p 数组。
class Solution {
public:
vector<int> smallestSubarrays(vector<int>& nums) {
vector<int> p(30);
vector<int> ans(nums.size());
for(int i = nums.size() - 1; i >= 0; i--){
int ma = i, val = nums[i];
for(int j = 0; j < 30; j++){
if((val >> j) & 1)
p[j] = i;
ma = max(ma, p[j]);
}
ans[i] = ma - i + 1;
}
return ans;
}
};
6187. 完成所有交易的初始最少钱数
对于任一笔交易，其前序交易的交易顺序不会影响到当前这笔交易前的钱数。所以对于最坏情况，可以枚举每一笔交易都作为最后一笔交易进行测试，找到需要的最大开始钱数。
例如，样例数据[[2,1],[5,0],[4,2]]
最坏情况是[4,2]作为最后一笔交易时,需要的钱最多,前两笔交易任意顺序都不会影响结果,只要当[4,2]是最后一笔交易,就一定能得到最大亏钱结果
class Solution {
public:
long long minimumMoney(vector<vector<int>>& a) {
long long sum = 0, res = 0;
for(auto &t : a)
if(t[0] > t[1])
sum += t[0] - t[1];
for(auto &t : a){
int x = t[0], y = t[1];
auto s = sum;
if(x > y)
s -= x - y;
res = max(res, s + x);
}
return res;
}
};