每日算法-250510
每日算法学习记录 - 250510
1. LeetCode 2086. 喂食仓鼠的最小食物桶数
题目描述:
解题思路
这是一个典型的贪心问题。我们的目标是用最少的食物桶喂饱所有仓鼠。
解题过程
核心思想是：当遇到一只仓鼠时，如何放置食物桶才能最有效地利用这个桶。
- 遍历字符串
hamsters。 - 当遇到一只仓鼠
s[i] == 'H'时：- 优先考虑在其右侧（
i+1）放置食物桶。 这样做是因为放在右边的食物桶s[i+1]不仅可以喂饱当前仓鼠s[i]，还有可能喂饱它右边的仓鼠s[i+2]（如果s[i+2]也是 ‘H’）。这使得一个桶的效益最大化。 - 如果右侧
s[i+1]是空地'.'：我们在此处放置一个桶，计数器ret加 1。由于s[i+1]上的桶可以喂饱s[i]和潜在的s[i+2]，我们可以跳过检查s[i+1](现在是桶) 和s[i+2](已被喂饱)。因此，我们将索引i向前移动 2 格（i += 2），加上循环自身的i++，相当于下次从i+3开始检查。 - 如果右侧不能放置（比如
i+1越界，或者s[i+1]是另一只仓鼠 ‘H’），再考虑在其左侧（i-1）放置食物桶。 - 如果左侧
s[i-1]是空地'.'：我们在此处放置一个桶，计数器ret加 1。这个桶喂饱了s[i]。索引i正常通过循环的i++后移。 - 如果左右两侧都无法放置食物桶：那么当前仓鼠
s[i]无法被喂饱，根据题意返回 -1。
- 优先考虑在其右侧（
- 遍历完成后，返回
ret。
复杂度分析
- 时间复杂度:
O
(
N
)
O(N)
O(N), 其中
N
N
N 是字符串
hamsters的长度。我们只需要遍历一次字符串。 - 空间复杂度: O ( N ) O(N) O(N) 或 O ( 1 ) O(1) O(1)。
代码实现
class Solution {
public int minimumBuckets(String hamsters) {
int ret = 0;
char[] s = hamsters.toCharArray();
int n = s.length;
for (int i = 0; i < n; i++) {
if (s[i] == 'H') {
char left = i > 0 ? s[i - 1] : 'H';
char right = i < n - 1 ? s[i + 1] : 'H';
if (right == '.') {
ret++;
i += 2;
} else if (left == '.') {
ret++;
} else {
return -1;
}
}
}
return ret;
}
}
2. LeetCode 2571. 将整数减少到零需要的最少操作数
题目描述:
解题思路
这个问题可以通过分析数字的二进制表示，并采用贪心策略来解决。目标是每次操作都尽可能有效地减少 n 或将其转化为更容易处理的形式（更接近2的幂）。
解题过程
我们将整数 n 视为其二进制表示。每次操作我们可以选择加上或减去一个2的幂。
-
获取最低位的 ‘1’:
使用位运算lowbit = n & (-n)可以得到n的二进制表示中，最低位的那个 ‘1’ 以及它之后的所有 ‘0’ 组成的数。这个lowbit值本身就是一个2的幂，对应题目中可以操作的数。 -
贪心决策:
对于当前的n和其lowbit：- 情况1:
lowbit的左边（更高一位）也是 ‘1’。
例如，n = 6 (0110_2)，lowbit = 2 (0010_2)。此时lowbit的左边是 ‘1’。
这种情况通过(n & (lowbit << 1)) > 0来判断。
我们选择n = n + lowbit。6 + 2 = 8 (1000_2)。
这样做的好处是，...011...形式的位序列通过加法可以变成...100...，有效地将两个（或更多连续的）'1’s 通过进位合并，从而可能更快地减少 ‘1’ 的总数或简化数字结构。 - 情况2:
lowbit的左边是 ‘0’。
例如，n = 4 (0100_2)，lowbit = 4 (0100_2)。或者n = 10 (1010_2)，lowbit = 2 (0010_2)。
这种情况是(n & (lowbit << 1)) == 0。
我们选择n = n - lowbit。4 - 4 = 0或10 - 2 = 8 (1000_2)。
这样做直接消除了最低位的 ‘1’。
- 情况1:
-
迭代与计数:
每次操作后，操作数ret加 1。
循环继续，直到n变为0。 -
特殊循环终止条件 (优化):
当n变成一个2的幂时（即(n & (n - 1)) == 0且n > 0），我们知道只需要再进行一次操作（减去n本身）就可以将其变为0。
代码中的循环条件(n & (n - 1)) != 0利用了这一点：当n成为2的幂或0时，循环终止。
ret初始化为1。如果n初始就是2的幂，循环不进入，直接返回1（一次操作）。如果n不是2的幂，进入循环，每执行一次n += lowbit或n -= lowbit，ret增加。当循环结束时，n必然是一个2的幂（因为n不会是0退出循环，除非一开始就是0，但题目约束1 <= n <= 10^5）。此时的ret值已经包含了将这个最终的2的幂减到0的那次操作。
复杂度分析
- 时间复杂度:
O
(
log
N
)
O(log N)
O(logN)。在二进制表示下，每次操作要么消除一个 ‘1’，要么通过进位合并 ‘1’，总体上使问题规模减小。操作的次数与
N的二进制位数大致成正比。 - 空间复杂度: O ( 1 ) O(1) O(1)。我们只需要常数级别的额外空间。
代码实现
class Solution {
public int minOperations(int n) {
int ret = 1;
while ((n & (n - 1)) != 0) {
int lowbit = n & (-n);
if ((n & (lowbit << 1)) > 0) {
n += lowbit;
} else {
n -= lowbit;
}
ret++;
}
return ret;
}
}
