December 12, 2025
C++ 也能写one-liner了。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 |
class Solution { public: int finalValueAfterOperations(vector<string>& operations) { return accumulate(begin(operations), end(operations), 0, [](const auto s, const auto& op){ return s + (op[1] == '+' ? 1 : -1); }); } }; |
已经告诉你所有的农田都是规整的矩形，题目难度一下子降低了。
对于每一个农田的左上角，找到它的宽度和高度即可。
然后把整个农田矩形标记为林地/非农田即可。
时间复杂度：O(m*n) 每个格子最多遍历3遍。
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: vector<vector<int>> findFarmland(vector<vector<int>>& land) { const int m = land.size(); const int n = land[0].size(); vector<vector<int>> ans; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (!land[i][j]) continue; int w = 0; int h = 0; while (j + w < n && land[i][j + w]) ++w; while (i + h < m && land[i + h][j]) ++h; ans.push_back({i, j, i + h - 1, j + w - 1}); for (int p = 0; p < h; ++p) for (int q = 0; q < w; ++q) land[i + p][j + q] = 0; // mark as seen. } return ans; } }; |
这道题目还是可以的。每个阶段有两种选择，求最短的决策次数。有好多种不同的做法，我们一个一个来。
方法1: BFS
把问题看成求无权重图中的最短路径，BFS可以找到最优解。
我们的节点有两个状态，当前的长度，剪贴板（上次复制后）的长度。
长度超过n一定无解，所以我们的状态最多只有n2种，每个状态最多拓展2个新的节点。
时间复杂度：O(n2)
空间复杂度：O(n2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution { public: int minSteps(int n) { vector<vector<bool>> seen(n + 1, vector<bool>(n + 1)); queue<pair<int, int>> q; auto expand = [&](int len, int clip) { if (len > n || len > n || seen[len][clip]) return; q.emplace(len, clip); seen[len][clip] = true; }; int steps = 0; expand(1, 0); // init state. while (!q.empty()) { int size = q.size(); while (size--) { auto [len, clip] = q.front(); q.pop(); if (len == n) return steps; expand(len, len); // copy. expand(len + clip, clip); // paste. } ++steps; } return -1; } }; |
这题我选DP，因为不需要证明，直接干就行了。
方法1: DP
首先还是需要对pairs的right进行排序。一方面是为了方便chaining，另一方面是可以去重。
然后定义 dp[i] := 以pairs[i]作为结尾，最长的序列的长度。
状态转移：dp[i] = max(dp[j] + 1) where pairs[i].left > pairs[j].right and 0 < j < i.
解释：对于pairs[i]，找一个最优的pairs[j]，满足pairs[i].left > pairs[j].right，这样我就可以把pairs[i]追加到以pairs[j]结尾的最长序列后面了，长度+1。
边检条件：dp[0:n] = 1，每个pair以自己作为序列的最后元素，长度为1。
时间复杂度：O(n2)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){ return p1[1] < p2[1]; }); const int n = pairs.size(); vector<int> dp(n, 1); for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) if (pairs[i][0] > pairs[j][1]) dp[i] = max(dp[i], dp[j] + 1); return *max_element(begin(dp), end(dp)); } }; |
方法2: 贪心
和DP一样，对数据进行排序。
每当我看到 cur.left > prev.right，那么就直接把cur接在prev后面。我们需要证明这么做是最优的，而不是跳过它选后面的元素。
Case 0: cur已经是最后一个元素了，跳过就不是最优解了。
假设cur后面有next, 因为已经排序过了，我们可以得知 next.right >= cur.right。
Case 1: next.right == cur.right。这时候选cur和选next对后面的决策来说是一样的，但由于Case 0的存在，我必须选cur。
Case 2: next.right > cur.right。不管left的情况怎么样，由于right更小，这时候选择cur一定是优于next。
综上所述，看到有元素可以连接起来就贪心的选它就对了。
时间复杂度：O(nlogn)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){ return p1[1] < p2[1]; }); int right = INT_MIN; int ans = 0; for (const auto& p : pairs) if (p[0] > right) { right = p[1]; ++ans; } return ans; } }; |
一眼DP，看数据规模标程应该是O(1003)。
阶段肯定就是吟唱完一个字符，状态和哪个字符在12:00点有关。
所以我们定义 dp[i][j] := 吟唱完keys[0~i]后，rings[j]停在12:00点所需要的最少步数。
转移方程：dp[i][j] = min(dp[i-1][k] + steps(k, j) + 1) if keys[i] == rings[j] else +inf.
第i-1字符吟唱完ring停留在k，第i个字符吟唱完ring停留在j (rings[j] 必须和 keys[i] 相同)，steps(k, j)表示ring从k转到j所需要的最少步数，最后还要+1，表示吟唱当前字符所需要的额外步骤。
边界条件：对于第0个字符，ring一开始停留在第0个字符，最小步数就是1 + steps(0, key[0])。
时间复杂度：O(mn2)
空间复杂度：O(mn) 可以降维到 O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int findRotateSteps(string ring, string key) { const int n = ring.size(); const int m = key.size(); auto steps = [n](int i, int j) { return min(abs(i - j), n - abs(i - j)); }; // dp[i][j] min steps to spell key[0~i] and ring[j] is at 12:00. vector<vector<int>> dp(m, vector<int>(n, INT_MAX/2)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (ring[j] != key[i]) continue; for (int k = 0; k < n; ++k) dp[i][j] = min(dp[i][j], 1 + (i == 0 ? steps(0, j) : (dp[i - 1][k] + steps(j, k)))); } return *min_element(begin(dp.back()), end(dp.back())); } }; |