求合取余即可，余数就是答案。
Time complexity: O(n)
Space complexity: O(1)
|
1 2 3 4 5 6 |
class Solution { public: int minOperations(vector<int>& nums, int k) { return accumulate(begin(nums), end(nums), 0) % k; } }; |
Huahua's Tech Road
最直接的方法就是扫描三遍，<, = , > 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; } }; |
一些工程上的优化
- 用string_view作为参数类型，减少一次string copy
- 先比较长度，再判断内容。
- string_view.substr 是O(1)时间，和直接用strncmp比较内容是一样的。
优化后 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; } }; |
数据规模 n <= 1000。O(n2) 的算法也是能过的。
方法1: Brute Force
双重循环枚举所有的(nums[i], nums[j])的组合。
时间复杂度：O(n2)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) ans = max(ans, nums[j] - nums[i]); return ans ? ans : -1; } }; |
方法2: 空间换时间
使用prefix sum算法，预先计算num[i] ~ nums[n-1]的最大值，存储在right[i]中。
时间复杂度：O(n)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; vector<int> right(n, nums.back()); for (int i = n - 2; i >= 0; --i) right[i] = max(right[i + 1], nums[i]); for (int i = 0; i < n; ++i) ans = max(ans, right[i] - nums[i]); return ans ? ans : -1; } }; |
方法3: Running Min
从左到右遍历，记录当前为止出现过最小的值。比较 nums[i] – 最小值 和 最优解。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; int smallest = nums[0]; for (int i = 1; i < n; ++i) { ans = max(ans, nums[i] - smallest); smallest = min(smallest, nums[i]); } return ans ? ans : -1; } }; |