首页 > 分享 > LeetCode 2105. 给植物浇水 II

LeetCode 2105. 给植物浇水 II

花匠小妙招
2024-11-24 03:26

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知

一、题目

1、题目描述

Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的。他们按下面描述的方式完成浇水：
Alice 按从左到右的顺序给植物浇水，从植物 0 开始。Bob 按从右到左的顺序给植物浇水，从植物 n - 1 开始。他们同时给植物浇水。
如果没有足够的水完全浇灌下一株植物，他 / 她会立即重新灌满浇水罐。
不管植物需要多少水，浇水所耗费的时间都是一样的。
不能提前重新灌满水罐。
每株植物都可以由 Alice 或者 Bob 来浇水。
如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水更多的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的次数。
样例输入： plants = [2,2,3,3], capacityA = 5, capacityB = 5
样例输出： 1

2、基础框架

C语言给出的基础框架代码如下：

int minimumRefill(int* plants, int plantsSize, int capacityA, int capacityB { } 12

3、原题链接

LeetCode 2105. 给植物浇水 II

二、解题报告

1、思路分析

( 1 ) (1) (1) 对于偶数个植物的情况，两个人分别判断，没有问题。
( 2 ) (2) (2) 对于奇数个植物的情况，也就是最后一株植物，我们需要判断两者剩余的水量：
( 2.1 ) (2.1) (2.1) 如果至少有一人可以浇水，则直接跳出循环。
( 2.2 ) (2.2) (2.2) 否则，只需要选择一个人浇水就行啦，浇水次数加一。

2、时间复杂度

最坏时间复杂度 O ( n ) O(n) O(n) 。

3、代码详解

int minimumRefill(int* plants, int plantsSize, int capacityA, int capacityB){ int l = 0; int r = plantsSize - 1; int na = capacityA; int nb = capacityB; int ans = 0; while(l <= r) { if(l == r) { // 不需要灌水 if(na >= plants[l] || nb >= plants[r]) { break; } ++ans; ++l; }else { if(na < plants[l]) { na = capacityA; ++ans; } na -= plants[l]; if(nb < plants[r]) { nb = capacityB; ++ans; } nb -= plants[r]; ++l; --r; } } return ans; }

1234567891011121314151617181920212223242526272829303132333435

三、本题小知识

对于模拟题，有些模棱两可的点，反复阅读，仔细看题。

四、加群须知

相信看我文章的大多数都是「大学生」，能上大学的都是「精英」，那么我们自然要「精益求精」，如果你还是「大一」，那么太好了，你拥有大把时间，当然你可以选择「刷剧」，然而，「学好算法」，三年后的你自然「不能同日而语」。
那么这里，我整理了「几十个基础算法」的分类，点击开启：

《算法入门指引》

如果链接被屏蔽，或者有权限问题，可以私聊作者解决。

大致题集一览：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

为了让这件事情变得有趣，以及「照顾初学者」，目前题目只开放最简单的算法「枚举系列」（包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有一半成员刷完「枚举系列」的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「夜深人静写算法」专家团的一员。
不要小看这个专家团，三年之后，你将会是别人望尘莫及的存在。如果要加入，可以联系我，考虑到大家都是学生，没有「主要经济来源」，在你成为神的路上，「不会索取任何」。
联系作者，或者扫作者主页二维码加群，加入刷题行列吧