[leetcode/lintcode 题解] 阿里巴巴面试题:浇花

简介: [leetcode/lintcode 题解] 阿里巴巴面试题:浇花

描述
你和你的朋友都是园丁,你们要照顾好你们的植物。这些植物是连续种植的,而且每种植物都需要一定量的水。你们要用水罐给它们浇水。为了避免错误,比如浇水太多,或者根本不给植物浇水,你们决定:
按植物出现的顺序浇水:你要从左到右浇水,你的朋友要从右到左浇水;
如果你有足够的水来浇灌每一棵植物,否则请重新装满你的水壶;
一次浇灌每株植物,即在给一株植物浇灌的过程中,不需要休息一下就可以重新灌满浇灌罐。这意味需要在浇灌植物之前或之后重新灌满浇水罐,即使浇水罐不是完全空的。
你从浇灌第一株植物开始,你的朋友从浇灌最后一株植物开始,你和你的朋友同时浇灌植物(当你浇灌第一株植物时,你的朋友浇灌最后一株;当你浇灌第二株植物时,你的朋友浇灌倒数第二株植物;
等等)这意味着你们将在一排植物中间相遇。如果那里有一棵没有浇水的植物,而且你和你的朋友一起有足够的水来浇水,你可以不用再装满你的水罐来浇水;否则,你们中只有一个人需要再重灌。
一开始你们的浇水罐都是空的,你和你的朋友需要给你的浇水罐重灌多少次水才能浇灌整排的植物?
Write a function::
class Solution{public int solution(int[] plants, int capacity1, int capacity2);}
给定一个包含n个整数(表示每株植物所需的水量)的数组和变量capacity1和capacity2(表示你和你朋友的浇水罐的容量),则返回你和你朋友需要重新装满浇水罐来浇灌所有植物的次数。

  • N 的范围[1..1,000];
  • plants数组中每个元素范围[1..1,000,000];
  • capacity1 和 capacty2 范围[1..1,000,000,000];
  • 两个浇水罐都足够大,可以完全浇灌任何一株植物。

在线评测地址:领扣题库官网

样例1
Input:[2,4,5,1,2],5,7
Output:3
Explanation:First you refill and water plants[0] and simultaneously your friend refills and waters plants[4].Then you refill and water plants[1] and simultaneously your friend waters plants[3].Finally you water plants[2] togerther (as together you have exactly 5 units of water).
样例2
Input:[43,48,29],49,34
Output:3
Explanation:First you water the plants [0], your friends water the plants [2], and finally you water the plants [1].

考点
模拟

题解
按照题意模拟,最后相遇时特判两人能否一起浇灌最后一株植物即可。

class Solution {
public:
    int waterPlants(vector<int> &plants, int capacity1, int capacity2) {
        int can1 = 0;
        int can2 = 0;
        int lo = 0;
        int hi = plants.size() - 1;
        int numRefils = 0;
        while (lo < hi) {
            if (can1 < plants[lo]) {
                can1 = capacity1;
                ++numRefils;
            }
            if (can2 < plants[hi]) {
                can2 = capacity2;
                ++numRefils;
            }
            can1 -= plants[lo++];
            can2 -= plants[hi--];
        }
        if (lo == hi && (plants[lo] > can1 + can2)) {
            return ++numRefils;
        } 
        else {
            return numRefils;
        }
        
    }
};

更多题解参考:九章官网solution
https://www.jiuzhang.com/solution/watering-flowers/?utm_source=sc-tianchi-sz-0226

相关文章
|
4月前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
4月前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
5月前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
5月前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
5月前
|
SQL 算法 大数据
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
|
5月前
|
存储 算法 搜索推荐
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
|
5月前
|
SQL 大数据 数据挖掘
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
|
5月前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)
|
5月前
|
存储 算法 数据挖掘
力扣173题:二叉搜索树迭代器(含模拟面试)
力扣173题:二叉搜索树迭代器(含模拟面试)