Date: September 4, 2022
Difficulty: medium
Rate by others: ⭐⭐⭐⭐
Time consuming: 1h30min
题目链接
题目解析
2399. 检查相同字母间的距离
class Solution {
public:
bool checkDistances(string s, vector<int>& distance) {
vector<int> arr(26, -1);
int n = s.size(), t;
for (int i = 0; i < n; ++i) {
t = s[i] - 'a';
if (arr[t] == -1) arr[t] = i;
else if (i - arr[t] - 1 != distance[t]) return false;
}
return true;
}
};
没什么可说的，简单模拟题。
class Solution {
static constexpr int MAXN = 1050;
static constexpr int MOD = 1e9 + 7;
vector<vector<int>> memo_;
public:
Solution(): memo_(MAXN, vector<int>(MAXN, -1)) {}
int aux(int dis, int k) {
dis = std::abs(dis);
if (memo_[dis][k] != -1) return memo_[dis][k];
if (dis > k) memo_[dis][k] = 0;
else if (dis == k) memo_[dis][k] = 1;
else memo_[dis][k] = aux(dis - 1, k - 1) + aux(dis + 1, k - 1);
if (memo_[dis][k] > MOD) {
memo_[dis][k] %= MOD;
}
return memo_[dis][k];
}
int numberOfWays(int startPos, int endPos, int k) {
return aux(endPos - startPos, k);
}
};
看了一眼题解，发现真的是道数学题，自己没有推出来，没有想到去思考用排列组合的想法去做。其实就算想到组合数，自己可能也想不到用递推式的做法O ( k 2 ) O(k^2)O(k2)或者O ( k ) O(k)O(k)去求组合数，而且还需要求逆元，相比之下自己用记忆化搜索硬搞出来也挺不容易的。用记忆化搜索的一个关键在于首先是用距离表示减少变量，然后是负距离和正距离是等价的。
什么时候应该总结一下组合数、逆元这部分的知识。
class Solution {
public:
int longestNiceSubarray(vector<int>& nums) {
constexpr int MAXN = 1e5 + 5;
constexpr int N = 31;
vector<int> BITS(N);
int t = 1;
for (int i = 0; i < N; ++i) {
BITS[i]= t;
t <<= 1;
}
vector<int> memo(N, -1);
int n = nums.size();
int ans = 0, last = -1;
for (int i = 0; i < n; ++i) {
t = -1;
for (int j = 0; j < N; ++j) {
if (nums[i] & BITS[j]) {
t = std::max(t, memo[j]);
memo[j] = i;
}
}
last = std::max(t, last);
ans = std::max(ans, i - last);
}
return ans;
}
};
自己的思路总体上没有什么问题，就是滑动窗口，每次将左边窗口移动到元素最近的&不为0的位置的后面，这个区间内右边元素和区间内的元素&都是0，但是不能保证在这个区间内前面的元素&为0，需要保存元素的最右左区间，也就是说在这个区间任意两个元素&都为0，也就是优雅子区间。
看了一下其他人的写法，发现自己可以复用左区间的位置，当时还是对题目的理解不够深刻。
class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
using ll = long long;
vector<vector<ll>> room(n);
sort(meetings.begin(), meetings.end(), [&](auto &&a, auto &&b) {
return a[0] < b[0];
});
for (auto &&meeting : meetings) {
bool flag = false;
for (int i = 0; i < n; ++i) {
if (room[i].empty() || meeting[0] >= room[i].back()) {
room[i].push_back(meeting[1]);
flag = true;
break;
}
}
if (flag) continue;
ll minT = room[0].back();
int minI = 0;
for (int i = 0; i < n; ++i) {
if (room[i].back() < minT) {
minT = room[i].back();
minI = i;
}
}
room[minI].push_back(meeting[1] - meeting[0] + room[minI].back());
}
int ansN = 0, ansIdx;
for (int i = 0; i < n; ++i) {
if (room[i].size() > ansN) {
ansN = room[i].size();
ansIdx = i;
}
}
return ansIdx;
}
};
写完前三道题时间只剩下十几分钟了，本来想放弃这道题，但是看了一眼题目觉得就是一个很简单的模拟题嘛，踌躇了一会还是开始写，越写越觉得简单，结果11:55提交一次爆long long，改正没有改正完全，12:02通过了，还是有些遗憾。不过没有注意题目的数据范围，这个锅我自己背。
周赛总结
优点
总体思维比较活跃，思维转换速度比较快，实现也还可以。虽然和厉害的人相比还是有差距，但是我觉得已经很不错了，尤其是第二题在没有思路的情况下用记忆化搜索过了真不错。
缺点
还是有些不自信，第四题如果我在第三题做完就全力以赴可能是可以A的，另一个方面是自己忘记去看数据范围了，导致爆long long，改正又忘记后面没有改，自食恶果。
改进方案
多加训练，再接再厉。