Leetcode 2086. Minimum Number of Food Buckets to Feed the Hamsters

[Woodyiiiiiii]

这道题带了点DP和Greedy的思想。

类型是辐射型，即数组中元素会对周边元素产生影响。

这种类型的解决问题，是尽量辐射更多范围。所以在这里，因为大部分都是从左到右遍历的，故尽量把Bucket放在hamster的右边；如果放不了，再考虑是否能放左边；都放不了，则失败，返回-1。

class Solution {
    public int minimumBuckets(String hamsters) {
        int ans = 0;
        int n = hamsters.length();
        char[] chars = hamsters.toCharArray();
        for (int i = 0; i < n; ++i) {
            char c = chars[i];
            if (c == 'H') {
                if (i - 1 >= 0 && chars[i - 1] == 'B') {
                    continue;
                }
                if (i + 1 >= n || chars[i + 1] == 'H') {
                    if (i - 1 >= 0 && chars[i - 1] == '.') {
                        ans++;
                        chars[i - 1] = 'B';
                    } else {
                        return -1;
                    }
                } else {
                    chars[i + 1] = 'B';
                    ++ans;
                }
            }
        }
        return ans;
    }
}

类似题目:

• 2528. Maximize the Minimum Powered City

---

• 2086. Minimum Number of Food Buckets to Feed the Hamsters