喂食仓鼠的最小食物桶数 图解题解

这道题到底在问什么

输入

hamsters = "H..H"

输出

2

输入

hamsters = ".H.H."

输出

1 (下标 2 一个桶喂两只)

输入

hamsters = ".HHH."

输出

-1 (中间那只两边都是仓鼠,喂不到)

最优解：一步一步想明白

1. 3记牢这套口诀:见仓鼠先看右,右边空位就往右放让一桶喂两只;右边堵住再往左放;左右皆堵就无解。下面从最左边一格一格扫。
2. 4先把这条街看清楚。H 是仓鼠,点是空位。这条街上有四只仓鼠,分别蹲在下标 0、2、4、5 的位置。我们要在空位上放桶,把它们全喂到,而且桶要放得最少。
3. 5把规则再捋一遍:一只仓鼠只要它紧挨着的左边一格,或者右边一格有桶,就算喂到了。反过来看,一个桶其实能同时照顾它左右两边的仓鼠,这正是我们能少放桶的地方。
4. 6用一个指针 i 从最左边开始,从左往右扫。ans 记已经放了几个桶,现在是 0。指针先停在下标 0。
5. 7指针停在下标 0,这里是个 H,有一只仓鼠。它必须被喂到,也就是左边或右边得挨着一个桶。按口诀,先看它右边能不能放。
6. 8顺带说一句,下标 0 的左边已经是街道尽头,越界了,根本没有空位可放。所以对这只仓鼠来说,右边是唯一的指望。正好也符合我们优先往右放的原则。
7. 9看它右边,下标 1 是个点,是空位。太好了,能往右放。这里藏着贪心的小心思:右边的桶不光喂当前这只,还可能顺带喂到再往右的那只仓鼠,所以能往右就优先往右。
8. 10就在下标 1 放一个桶,涂成绿色。这样下标 0 的仓鼠右边挨着桶了,喂饱,标成蓝色。ans 加到 1。
9. 11关键一步来了。下标 1 的这个桶,右边正好是下标 2 的仓鼠,所以这一个桶把下标 0 和下标 2 两只仓鼠一起喂了。既然下标 2 已经安顿好,指针就多跳一格,越过下标 1 和 2,直接蹦到下标 3,你看指针现在就停在下标 3 上,省得回头重复看。这就是优先往右放换来的好处。
10. 12指针已经停在下标 3 了,这里只是回头看一眼下标 2 那只仓鼠,并不是把指针挪回去重新扫它。它的左边就是下标 1 的桶,规则说左邻有桶就算喂到,所以它是被顺带喂饱的,不用再单独为它花一个桶。你看,一个桶服务两只,桶数就这么省下来了。
11. 13指针落到下标 3,这里是个点,空位,没有仓鼠要照顾。空位本身不需要我们做任何决定,直接往右走。
12. 14走到下标 4,又是一只仓鼠。老规矩,先看它右边能不能放桶。
13. 15看右边,下标 5 偏偏也是一只仓鼠,不是空位,桶塞不进去。右边这条路堵住了,标成红色。别急,还有左边可以退一步。
14. 16右边堵住,回头看左边,下标 3 是个点,空位。那就往左放,先把下标 4 这只仓鼠喂上要紧。注意这是右边放不下时的退路,不是首选。
15. 17在下标 3 放一个桶,涂绿。下标 4 的仓鼠左边挨着桶了,喂饱,标蓝。ans 加到 2。这次因为往左放,右边没有第二只能顺带喂,指针就正常往右走一格。
16. 18指针来到下标 5,就是刚才右边那只仓鼠,它还没被喂。继续给它安排,还是先看右边。
17. 19它右边是下标 6,一个点,空位。能往右放,那就往右放,依然是优先右边这条原则。
18. 20在下标 6 放一个桶,涂绿。下标 5 的仓鼠右边挨着桶了,喂饱,标蓝。ans 加到 3。至此四只仓鼠全部有着落。
19. 21指针越过街道最右边,循环结束。回头看,下标 0、2、4、5 四只仓鼠全都标成了蓝色,一个不落全喂饱了。
20. 22把全局再扫一眼,四只蓝色的仓鼠都被绿色的桶挨着照顾到了。绿色的桶一共三个,分别在下标 1、3、6。三个桶喂饱四只仓鼠,靠的就是让桶 1 一桶喂了两只。
21. 23回放整条思路。从左往右扫,遇到仓鼠优先往右放桶好让一桶喂两只,右边放不下才退而往左放,哪边都放不了就返回 -1。数一数绿色的桶,一共三个,这就是喂饱所有仓鼠的最少桶数,答案是 3。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minimumBuckets(self, street: str) -> int:
        ans = 0
        i, n = 0, len(street)
        while i < n:
            if street[i] == 'H':
                if i + 1 < n and street[i + 1] == '.':
                    i += 2
                    ans += 1
                elif i and street[i - 1] == '.':
                    ans += 1
                else:
                    return -1
            i += 1
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minimumBuckets(string street) {
        int n = street.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (street[i] == 'H') {
                if (i + 1 < n && street[i + 1] == '.') {
                    ++ans;
                    i += 2;
                } else if (i && street[i - 1] == '.') {
                    ++ans;
                } else {
                    return -1;
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int minimumBuckets(String street) {
        int n = street.length();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (street.charAt(i) == 'H') {
                if (i + 1 < n && street.charAt(i + 1) == '.') {
                    ++ans;
                    i += 2;
                } else if (i > 0 && street.charAt(i - 1) == '.') {
                    ++ans;
                } else {
                    return -1;
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问