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;}};

沒什么可說的，簡單模擬題。

2400. 恰好移動 k 步到達某一位置的方法數目

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)$去求組合數，而且還需要求逆元，相比之下自己用記憶化搜索硬搞出來也挺不容易的。用記憶化搜索的一個關鍵在于首先是用距離表示減少變量，然后是負距離和正距離是等價的。

什么時候應該總結一下組合數、逆元這部分的知識。

2401. 最長優雅子數組

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，也就是優雅子區間。

看了一下其他人的寫法，發現自己可以復用左區間的位置，當時還是對題目的理解不夠深刻。

2402. 會議室 III

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通過了，還是有些遺憾。不過沒有注意題目的數據范圍，這個鍋我自己背。