求合取余即可，余数就是答案。
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; } }; |
Posts tagged as “easy”
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); }); } }; |
青铜 Brute Force：每次需要花费O(n*n)的时间去查找query所在的格子，求和是O(1)。总的时间复杂度达到O(n^4)，肯定会超时。
白银 Hashtable：由于所有元素的值的唯一的，我们可以使用hashtable（或者数组）来记录value所在的格子坐标，这样每次Query都是O(1)时间。
时间复杂度：初始化O(n^2)，query O(1)。
空间复杂度：O(n^2)
|
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 NeighborSum { public: NeighborSum(vector<vector<int>>& grid): n_(grid.size()), g_(&grid), xy_(n_ * n_) { for (int i = 0; i < n_; ++i) for (int j = 0; j < n_; ++j) xy_[grid[i][j]] = {j, i}; } int adjacentSum(int value) { auto [x, y] = xy_[value]; return val(x, y - 1) + val(x, y + 1) + val(x + 1, y) + val(x - 1, y); } int diagonalSum(int value) { auto [x, y] = xy_[value]; return val(x - 1, y - 1) + val(x - 1, y + 1) + val(x + 1, y - 1) + val(x + 1, y + 1); } private: inline int val(int x, int y) const { if (x < 0 || x >= n_ || y < 0 || y >= n_) return 0; return (*g_)[y][x]; } int n_; vector<vector<int>>* g_; vector<pair<int, int>> xy_; }; |
黄金 Precompute：在初始化的时候顺便求合，开两个数组一个存上下左右的，一个存对角线的。query的时候直接返回答案就可以了。
时间复杂度和白银是一样的，但会快一些（省去了求合的过程）。
|
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 28 29 |
class NeighborSum { public: NeighborSum(vector<vector<int>>& grid) { int n = grid.size(); adj_.resize(n * n); dia_.resize(n * n); auto v = [&](int x, int y) -> int { if (x < 0 || x >= n || y < 0 || y >= n) return 0; return grid[y][x]; }; for (int y = 0; y < n; ++y) for (int x = 0; x < n; ++x) { adj_[grid[y][x]] = v(x, y - 1) + v(x, y + 1) + v(x + 1, y) + v(x - 1, y); dia_[grid[y][x]] = v(x - 1, y - 1) + v(x - 1, y + 1) + v(x + 1, y - 1) + v(x + 1, y + 1); } } int adjacentSum(int value) { return adj_[value]; } int diagonalSum(int value) { return dia_[value]; } private: vector<int> adj_; vector<int> dia_; }; |
An ant is on a boundary. It sometimes goes left and sometimes right.
You are given an array of non-zero integers nums. The ant starts reading nums from the first element of it to its end. At each step, it moves according to the value of the current element:
- If
nums[i] < 0, it moves left by-nums[i]units. - If
nums[i] > 0, it moves right bynums[i]units.
Return the number of times the ant returns to the boundary.
Notes:
- There is an infinite space on both sides of the boundary.
- We check whether the ant is on the boundary only after it has moved
|nums[i]|units. In other words, if the ant crosses the boundary during its movement, it does not count.
Example 1:
Input: nums = [2,3,-5] Output: 1 Explanation: After the first step, the ant is 2 steps to the right of the boundary. After the second step, the ant is 5 steps to the right of the boundary. After the third step, the ant is on the boundary. So the answer is 1.
Example 2:
Input: nums = [3,2,-3,-4] Output: 0 Explanation: After the first step, the ant is 3 steps to the right of the boundary. After the second step, the ant is 5 steps to the right of the boundary. After the third step, the ant is 2 steps to the right of the boundary. After the fourth step, the ant is 2 steps to the left of the boundary. The ant never returned to the boundary, so the answer is 0.
Constraints:
1 <= nums.length <= 100-10 <= nums[i] <= 10nums[i] != 0
Solution: Simulation
Simulate the position of the ant by summing up the numbers. If the position is zero (at boundary), increase the answer by 1.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 |
class Solution { public: int returnToBoundaryCount(vector<int>& nums) { int ans = 0; int pos = 0; for (int x : nums) ans += !(pos += x); return ans; } }; |
You are given an array nums consisting of positive integers.
Return the total frequencies of elements in nums such that those elements all have the maximum frequency.
The frequency of an element is the number of occurrences of that element in the array.
Example 1:
Input: nums = [1,2,2,3,1,4] Output: 4 Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array. So the number of elements in the array with maximum frequency is 4.
Example 2:
Input: nums = [1,2,3,4,5] Output: 5 Explanation: All elements of the array have a frequency of 1 which is the maximum. So the number of elements in the array with maximum frequency is 5.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Solution: Hashtable
Use a hashtable to store the frequency of each element, and compare it with a running maximum frequency. Reset answer if current frequency is greater than maximum frequency. Increment the answer if current frequency is equal to the maximum frequency.
Time complexity: O(n)
Space complexity: O(n)
C++
// Author: Huahua
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int maxFrequencyElements(vector<int>& nums) { unordered_map<int, int> m; int freq = 0; int ans = 0; for (int x : nums) { if (++m[x] > freq) freq = m[x], ans = 0; if (m[x] == freq) ans += m[x]; } return ans; } }; |