每日算法-250507
每日算法学习记录 - 250507
3228. 将 1 移动到末尾的最大操作次数
题目
思路
贪心算法。
解题过程
我们的目标是最大化操作次数。题目的操作定义为：选择一个 ‘1’ 并将其移动到字符串的“最右端”（可以理解为所有 ‘0’ 之后，与其他 ‘1’ 一起形成连续的 ‘1’ 块）。
我们从左到右遍历字符串 s：
- 使用一个变量
count来记录当前已经遇到的、且尚未“结算”操作的 ‘1’ 的数量。 - 如果
s[i] == '1'，我们就将count加一。 - 如果
s[i] == '0'，这个 ‘0’ 就构成了一个“障碍”或者说一个结算点：- 情况一：
s[i] == '0'且其后紧跟着 ‘1’ (即i < s.length - 1 && s[i+1] == '1')。
这意味着在s[i]左边的count个 ‘1’ 都需要进行一次操作，以“越过”s[i]这个 ‘0’。因此，我们将总操作数ret增加count。这些 ‘1’ 虽然越过了当前的 ‘0’，但由于后面还有 ‘1’，它们仍被视为“活动的”，需要继续向右移动，所以count的值（代表活动的 ‘1’ 的数量）保持不变，并会继续累加后续遇到的 ‘1’。 - 情况二：
s[i] == '0'且这是字符串的最后一个字符 (即i == s.length - 1 && s[i] == '0')。
这意味着在s[i]左边的count个 ‘1’ 都需要进行一次操作，以移动到这个末尾 ‘0’ 的后面，从而到达字符串的最右端。因此，操作数ret同样增加count。
- 情况一：
这种贪心策略的核心在于，每当一个 ‘0’ 出现在活动的 ‘1’ 序列之后，并且这个 ‘0’ 之后还有 ‘1’（表明当前的 ‘1’ 序列尚未到达最终位置），或者这个 ‘0’ 本身就是字符串的末尾（所有 ‘1’ 都必须移动到它之后），那么所有这些活动的 ‘1’ 都必须进行一次操作。
复杂度
- 时间复杂度: O ( N ) O(N) O(N), 其中 N N N 是字符串
s的长度。我们只需要遍历一次字符串。 - 空间复杂度: O ( 1 ) O(1) O(1), 我们只使用了常数个额外变量。
Code
class Solution {public int maxOperations(String ss) {char[] s = ss.toCharArray();int ret = 0, count = 0; for (int i = 0; i < s.length; i++) {if (s[i] == '1') {count++;} else if (i < s.length - 1 && s[i + 1] == '1') {ret += count;}if (i == s.length - 1 && s[i] == '0') { ret += count; }}return ret;}
}
1144. 递减元素使数组呈锯齿状
题目
思路
贪心算法。
解题过程
题目指出锯齿数组有两种主要形式：
A[0] > A[1] < A[2] > A[3] < ...(偶数下标元素为峰，奇数下标元素为谷)A[0] < A[1] > A[2] < A[3] > ...(偶数下标元素为谷，奇数下标元素为峰)
我们只需要考虑将元素减小。因此，对于一个元素 nums[i]，如果要使其成为“谷”（即小于其左右邻居），我们贪心地将其减小到 min(left_neighbor, right_neighbor) - 1。
我们分别计算两种情况的总操作数：
ret[0]: 尝试使所有偶数下标的元素成为“谷”。即，对于每个偶数下标i，如果nums[i]不小于其任一邻居，则计算将其减小到比左右邻居都小的最小值的操作数。奇数下标的元素在此情况下不修改，它们自然形成“峰”。ret[1]: 尝试使所有奇数下标的元素成为“谷”。即，对于每个奇数下标i，如果nums[i]不小于其任一邻居，则计算将其减小到比左右邻居都小的最小值的操作数。偶数下标的元素在此情况下不修改，它们自然形成“峰”。
具体步骤：
- 初始化
ret = [0, 0]。 - 遍历数组
nums中的每个元素nums[i](从0到n-1)：
a. 获取左邻居left：如果i > 0，则为nums[i-1]；否则，视为Integer.MAX_VALUE(边界处理，相当于没有左侧限制)。
b. 获取右邻居right：如果i < n-1，则为nums[i+1]；否则，视为Integer.MAX_VALUE(边界处理，相当于没有右侧限制)。
c. 计算使nums[i]成为谷所需的操作数moves_needed：
moves_needed = nums[i] - (Math.min(left, right) - 1)
如果nums[i]已经小于Math.min(left, right)，则moves_needed会小于等于0。所以实际操作数为Math.max(0, moves_needed)。
d. 将此moves_needed加到对应的ret数组中：
- 如果i是偶数 (i % 2 == 0)，则累加到ret[0]。
- 如果i是奇数 (i % 2 == 1)，则累加到ret[1]。 - 最终结果是
Math.min(ret[0], ret[1])。
使用 Integer.MAX_VALUE 作为越界邻居的值，可以确保在计算 Math.min(left, right) 时，存在的那个邻居成为较小值，从而正确计算边界元素成为谷所需的操作数。
复杂度
- 时间复杂度: O ( N ) O(N) O(N), 其中 N N N 是数组
nums的长度。我们只需要遍历一次数组。 - 空间复杂度: O ( 1 ) O(1) O(1), 我们只使用了固定大小的
ret数组和几个临时变量。
Code
class Solution {public int movesToMakeZigzag(int[] nums) {int[] ret = new int[2];int n = nums.length;for (int i = 0; i < n; i++) {int left = i > 0 ? nums[i - 1] : Integer.MAX_VALUE;int right = i < n - 1 ? nums[i + 1] : Integer.MAX_VALUE;ret[i % 2] += Math.max(nums[i] - Math.min(left, right) + 1, 0);}return Math.min(ret[0], ret[1]);}
}