微网站怎么做的好名字,英铭科技做网站和设计制作更专业,公司互联网推广,中国建筑集团有限公司待遇Every day a Leetcode
题目来源#xff1a;2086. 从房屋收集雨水需要的最少水桶数
解法1#xff1a;贪心
我们可以对字符串 hamsters 从左到右进行一次遍历。
每当我们遍历到一个房屋时#xff0c;我们可以有如下的选择#xff1a; 如果房屋的两侧已经有水桶#xff…Every day a Leetcode
题目来源2086. 从房屋收集雨水需要的最少水桶数
解法1贪心
我们可以对字符串 hamsters 从左到右进行一次遍历。
每当我们遍历到一个房屋时我们可以有如下的选择 如果房屋的两侧已经有水桶那么我们无需再放置水桶了 如果房屋的两侧没有水桶那么我们优先在房屋的「右侧」放置水桶这是因为我们是从左到右进行遍历的即当我们遍历到第 i 个位置时前 i−1 个位置的房屋周围都是有水桶的。因此我们在左侧放置水桶没有任何意义而在右侧放置水桶可以让之后的房屋使用该水桶。 如果房屋的右侧无法放置水桶例如是另一栋房屋或者边界那么我们只能在左侧放置水桶。如果左侧也不能放置说明无解。
我们可以通过修改字符串来表示水桶的放置从而实现上述算法。一种无需修改字符串的方法是每当我们在房屋的右侧放置水桶时可以直接「跳过」后续的两个位置因为如果字符串形如 H.H我们在第一栋房屋的右侧即两栋房屋的中间放置水桶后就无需考虑第二栋房屋如果字符串形如 H…后续没有房屋我们也可以全部跳过。
代码
/** lc appleetcode.cn id2086 langcpp** [2086] 从房屋收集雨水需要的最少水桶数*/// lc codestart
class Solution
{
public:int minimumBuckets(string hamsters){int n hamsters.size();int bucket 0;for (int i 0; i n; i){if (hamsters[i] H){if (i 1 n hamsters[i 1] .){bucket;i 2;}else if (i - 1 0 hamsters[i - 1] .)bucket;elsereturn -1;}}return bucket;}
};
// lc codeend结果
复杂度分析
时间复杂度O(n)其中 n 是字符串 hamsters 的长度。
空间复杂度O(1)。
解法2动态规划
设遍历至前 i 个字符满足条件的最小水桶数为 dp[i]。
若 street[i - 1] 为 ‘.’
不放置水桶。此时有若前面一个为房屋street[i - 2] ‘H’可放置水桶。此时有
else if street[i - 1] 为 ‘H’
前方必须放置水桶则必须满足 street[i - 2] ‘.’。此时有上一个条件满足情况下如果水桶前方是房子street[i - 3] ‘H’则这个水桶也可以接到前面房子的水。此时有
所有的状态转移取最小值即可。
代码
/** lc appleetcode.cn id2086 langcpp** [2086] 从房屋收集雨水需要的最少水桶数*/// lc codestart// 贪心// class Solution
// {
// public:
// int minimumBuckets(string hamsters)
// {
// int n hamsters.size();
// int bucket 0;
// for (int i 0; i n; i)
// {
// if (hamsters[i] H)
// {
// if (i 1 n hamsters[i 1] .)
// {
// bucket;
// i 2;
// }
// else if (i - 1 0 hamsters[i - 1] .)
// bucket;
// else
// return -1;
// }
// }
// return bucket;
// }
// };class Solution
{
private:
#define INF 0x3F3F3F3F
#define MAX_LEN 1e5 10public:int minimumBuckets(string street){int n street.size();vectorint dp(MAX_LEN, INF);// 初始化dp[0] 0;// 状态转移for (int i 1; i n; i){if (street[i - 1] .){dp[i] dp[i - 1];if (i - 2 0 street[i - 2] H)dp[i] min(dp[i], dp[i - 2] 1);}else if (street[i - 1] H){if (i - 2 0 street[i - 2] .){dp[i] dp[i - 2] 1;if (i - 3 0 street[i - 3] H){dp[i] min(dp[i], dp[i - 3] 1);}}}}return dp[n] INF ? -1 : dp[n];}
};
// lc codeend结果 复杂度分析
时间复杂度O(n)其中 n 是字符串 street 的长度。
空间复杂度O(MAX_LEN)。状态数组开销MAX_LEN 1e5 10。
