April 11, 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; } }; |
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:
nums[i] < 0, it moves left by -nums[i] units.nums[i] > 0, it moves right by nums[i] units.Return the number of times the ant returns to the boundary.
Notes:
|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] != 0Simulate 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)
|
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 two 0-indexed integer arrays player1 and player2, that represent the number of pins that player 1 and player 2 hit in a bowling game, respectively.
The bowling game consists of n turns, and the number of pins in each turn is exactly 10.
Assume a player hit xi pins in the ith turn. The value of the ith turn for the player is:
2xi if the player hit 10 pins in any of the previous two turns.xi.The score of the player is the sum of the values of their n turns.
Return
1 if the score of player 1 is more than the score of player 2,2 if the score of player 2 is more than the score of player 1, and0 in case of a draw.Example 1:
Input: player1 = [4,10,7,9], player2 = [6,5,2,3] Output: 1 Explanation: The score of player1 is 4 + 10 + 2*7 + 2*9 = 46. The score of player2 is 6 + 5 + 2 + 3 = 16. Score of player1 is more than the score of player2, so, player1 is the winner, and the answer is 1.
Example 2:
Input: player1 = [3,5,7,6], player2 = [8,10,10,2] Output: 2 Explanation: The score of player1 is 3 + 5 + 7 + 6 = 21. The score of player2 is 8 + 10 + 2*10 + 2*2 = 42. Score of player2 is more than the score of player1, so, player2 is the winner, and the answer is 2.
Example 3:
Input: player1 = [2,3], player2 = [4,1] Output: 0 Explanation: The score of player1 is 2 + 3 = 5 The score of player2 is 4 + 1 = 5 The score of player1 equals to the score of player2, so, there is a draw, and the answer is 0.
Constraints:
n == player1.length == player2.length1 <= n <= 10000 <= player1[i], player2[i] <= 10We can write a function to compute the score of a player.
Time complexity: O(n)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int isWinner(vector<int>& player1, vector<int>& player2) { auto score = [] (const vector<int>& player) { int sum = 0; int twice = 0; for (int x : player) { sum += twice-- > 0 ? x * 2 : x; if (x == 10) twice = 2; } return sum; }; int s1 = score(player1); int s2 = score(player2); if (s1 == s2) return 0; return s1 > s2 ? 1 : 2; } }; |
You are given a 0-indexed m x n integer matrix grid. The width of a column is the maximum length of its integers.
grid = [[-10], [3], [12]], the width of the only column is 3 since -10 is of length 3.Return an integer array ans of size n where ans[i] is the width of the ith column.
The length of an integer x with len digits is equal to len if x is non-negative, and len + 1 otherwise.
Example 1:
Input: grid = [[1],[22],[333]] Output: [3] Explanation: In the 0th column, 333 is of length 3.
Example 2:
Input: grid = [[-15,1,3],[15,7,12],[5,6,-2]] Output: [3,1,2] Explanation: In the 0th column, only -15 is of length 3. In the 1st column, all integers are of length 1. In the 2nd column, both 12 and -2 are of length 2.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 100-109 <= grid[r][c] <= 109Note: width of ‘0’ is 1.
Time complexity: O(m*n*log(x))
Space complexity: O(1)
|
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 |
// Author: Huahua class Solution { public: vector<int> findColumnWidth(vector<vector<int>>& grid) { vector<int> ans; for (int j = 0; j < grid[0].size(); ++j) { int maxWidth = 1; for (int i = 0; i < grid.size(); ++i) { int x = grid[i][j]; int width = 0; if (x < 0) { x = -x; ++width; } while (x) { x /= 10; ++width; } maxWidth = max(maxWidth, width); } ans.push_back(maxWidth); } return ans; } }; |