Skip to content

Latest commit

 

History

History
185 lines (146 loc) · 5.28 KB

File metadata and controls

185 lines (146 loc) · 5.28 KB
comments difficulty edit_url rating source tags
true
中等
1622
第 66 场双周赛 Q2
贪心
字符串
动态规划

English Version

题目描述

给你一个下标从 0 开始的字符串 hamsters ,其中 hamsters[i]  要么是:

  • 'H' 表示有一个仓鼠在下标 i ,或者
  • '.' 表示下标 i 是空的。

你将要在空的位置上添加一定数量的食物桶来喂养仓鼠。如果仓鼠的左边或右边至少有一个食物桶,就可以喂食它。更正式地说,如果你在位置 i - 1 或者 i + 1 放置一个食物桶,就可以喂养位置为 i 处的仓鼠。

空的位置 放置食物桶以喂养所有仓鼠的前提下,请你返回需要的 最少 食物桶数。如果无解请返回 -1 。

 

示例 1:

输入:hamsters = "H..H"
输出:2
解释:
我们可以在下标为 1 和 2 处放食物桶。
可以发现如果我们只放置 1 个食物桶,其中一只仓鼠将得不到喂养。

示例 2:

输入:street = ".H.H."
输出:1
解释:
我们可以在下标为 2 处放置一个食物桶。

示例 3:

输入:street = ".HHH."
输出:-1
解释:
如果我们如图那样在每个空位放置食物桶,下标 2 处的仓鼠将吃不到食物。

 

提示:

  • 1 <= hamsters.length <= 105
  • hamsters[i] 要么是 'H' ,要么是 '.'

解法

方法一:贪心

从左到右遍历字符串,遇到 H 时,优先考虑右边是否有空位,如果有则放置水桶,并且跳过水桶的下一个位置;如果右边没有空位,则考虑左边是否有空位,如果有则放置水桶,否则无解。

时间复杂度 $O(n)$,空间复杂度 $O(1)$。其中 $n$ 为字符串 street 的长度。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

func minimumBuckets(street string) int {
	ans, n := 0, len(street)
	for i := 0; i < n; i++ {
		if street[i] == 'H' {
			if i+1 < n && street[i+1] == '.' {
				ans++
				i += 2
			} else if i > 0 && street[i-1] == '.' {
				ans++
			} else {
				return -1
			}
		}
	}
	return ans
}