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; } }; |
送分题，简单仿真即可。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 |
// https://zxi.mytechroad.com/blog/string/leetcode-3498-reverse-degree-of-a-string/ class Solution { public: int reverseDegree(string s) { int ans = 0; for (int i = 0; i < s.size(); ++i) ans += ('z' - s[i] + 1) * (i + 1); 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; } }; |