April 14, 2025
最直接的方法就是扫描三遍，<, = , > pivot。
时间复杂度：O(n)
空间复杂度：O(1) // no extra space used except for output
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: vector<int> pivotArray(vector<int>& nums, int pivot) { vector<int> ans; for (int x: nums) if (x < pivot) ans.push_back(x); for (int x : nums) if (x == pivot) ans.push_back(x); for (int x : nums) if (x > pivot) ans.push_back(x); return ans; } }; |
数据规模高达5 *104,我们只能使用O(n)的算法了。
可以想到的就是滑动窗口(sliding window)，由于最长长度未知，我们可以使用动态滑动窗口。
记录当前滑动窗口中T和F出现的次数，如果其中较少的一个<=k，那么就可以全部替换它，使得整个滑动窗口都变成相同的值。如果这个时候滑动窗口长度大于当前最大长度，我们就把滑动窗口变大，右侧+1，并更新最大长度。否则，减少滑动窗口，左侧-1。
时间复杂度：O(n)
空间复杂度：O(2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: int maxConsecutiveAnswers(string_view A, int k) { int ans = 0; int f = 0; array<int, 2> count; // number of 'F' and 'T' in the sliding window for (int i = 0; i < A.size(); ++i) { ++count[A[i] == 'T']; if (min(count[0], count[1]) <= k && count[0] + count[1] > ans) ++ans; else --count[A[i - ans] == 'T']; } return ans; } }; |
方法1: Brute Force
枚举所有的(nums[i], nums[j])组合，相加在和target比较。
时间复杂度：O(mn2) m为字符串的最长长度。
空间复杂度：O(m)
优化前 67ms, 49.3M
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int numOfPairs(vector<string>& nums, string target) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j && nums[i] + nums[j] == target) ++ans; return ans; } }; |
一些工程上的优化
优化后 3ms, 12.88MB
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int numOfPairs(vector<string>& nums, string_view target) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j && nums[i].size() + nums[j].size() == target.size() && target.substr(0, nums[i].size()) == nums[i] && target.substr(nums[i].size()) == nums[j]) ++ans; return ans; } }; |
数据规模比较大，算法必须是O(n)的。
可以预先使用O(n)时间计算nums[0] .. nums[i]的最大值，存在left[i]中，以及nums[i] .. nums[n-1]的最小值存在right[i]中。然后再按题目的定义计算即可。
时间复杂度：O(n)
空间复杂度：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 sumOfBeauties(vector<int>& nums) { const int n = nums.size(); vector<int> left(n, nums[0]); vector<int> right(n, nums.back()); for (int i = 1; i < n; ++i) left[i] = max(left[i - 1], nums[i]); for (int i = n - 2; i >= 0; --i) right[i] = min(right[i + 1], nums[i]); int ans = 0; for (int i = 1; i < n - 1; ++i) if (left[i - 1] < nums[i] && nums[i] < right[i + 1]) ans += 2; else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) ans += 1; return ans; } }; |
已经告诉你所有的农田都是规整的矩形，题目难度一下子降低了。
对于每一个农田的左上角，找到它的宽度和高度即可。
然后把整个农田矩形标记为林地/非农田即可。
时间复杂度：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; } }; |