关于后端:面试高频题难度-15可灵活切换数据范围的小小思维题

这是 LeetCode 上的 2335. 装满杯子须要的最短总时长 ，难度为简略。

Tag :「排序」、「递归」、「模仿」、「贪婪」、「数学」

现有一台饮水机，能够制备冷水、温水和热水。每秒钟，能够装满 2 杯不同类型的水或者 1 杯任意类型的水。

给你一个下标从 0 开始、长度为 3 的整数数组 amount，其中 amount[0]、amount[1] 和 amount[2] 别离示意须要装满冷水、温水和热水的杯子数量。

返回装满所有杯子所需的起码秒数。

示例 1：

输出：amount = [1,4,2]

输入：4

解释：上面给出一种计划：第 1 秒：装满一杯冷水和一杯温水。第 2 秒：装满一杯温水和一杯热水。第 3 秒：装满一杯温水和一杯热水。第 4 秒：装满一杯温水。能够证实起码须要 4 秒能力装满所有杯子。

示例 2：

输出：amount = [5,4,4]

输入：7

解释：上面给出一种计划：第 1 秒：装满一杯冷水和一杯热水。第 2 秒：装满一杯冷水和一杯温水。第 3 秒：装满一杯冷水和一杯温水。第 4 秒：装满一杯温水和一杯热水。第 5 秒：装满一杯冷水和一杯热水。第 6 秒：装满一杯冷水和一杯温水。第 7 秒：装满一杯热水。

示例 3：

输出：amount = [5,0,0]

输入：5

解释：每秒装满一杯冷水。

提醒：

$amount.length = 3$
$0 <= amount[i] <= 100$

水的品种固定为 3，且每种水的数据范畴只有 $100$，可间接应用递归进行求解。

为了尽可能的凑成多的对数，咱们能够每次取残余数量最多且不为 0 的两类水进行成组（因而每次解决前须要先对以后 amount 进行排序），直到没有水残余，或只有一类水的残余数据量不为 0（剩下的水只能单独生成）。

代码：

class Solution {public int fillCups(int[] amount) {Arrays.sort(amount);
        if (amount[1] == 0) return amount[2];
        amount[1]--; amount[2]--;
        return 1 + fillCups(amount);
    }
}

工夫复杂度：因为 amount 的长度固定为 3，因而排序耗费可视为常量；每次至多会耗费两杯水，直到递归完结或只剩下一种水。复杂度为 $O(\sum_{i = 0}^{2} amount[i])$
空间复杂度：疏忽递归和排序带来的额定空间开销，复杂度为 $O(1)$

咱们曾经晓得能够通过「每次取残余数量最多且不为 0 的水成对」来实现起码生成次数。

那么是否存在间接计算起码生成次数的办法，而不是采纳逐回合模仿。

思考对 amount 进行排序，别离应用 a、b 和 c 代表剩余次数递增的三种品种。

依据 $a + b$ 和 $c$ 的大小关系进行分状况探讨：

$a + b \leq c$，此时每耗费一个 $c$ 都能够顺带打消一个 $a$ 或 $b$，因而起码生成次数为 $c$；
$a + b > c$，此时思考其之间的差值 $t = a + b – c$，若能顺利通过 $\frac{t}{2}$ 次对 $a$ 和 $b$ 的合并，能够将场面转成状况一，起码生成次数为 $\frac{t}{2} + c$；

思考起始是否能先对 $a$ 和 $b$ 进行 $\frac{t}{2}$ 个回合，因为咱们有 $a \leq b$，咱们只需思考是否必然有 $a \geq \frac{t}{2}$ 即可，可通过反证法证实 $a < \frac{t}{2}$ 必然不成立，若有 $a < \frac{t}{2}$，则有 $2a < a + b – c$ => $a < b – c$，因为 $b \leq c$，则有 $a < 0$，与原条件抵触。

最初，为了解决 $t$ 的奇偶性问题，先用 $a$ 和 $b$ 进行 $\left \lceil \frac{a + b – c}{2} \right \rceil$ 对消操作，再与 $c$ 进行对消

代码：

class Solution {public int fillCups(int[] amount) {Arrays.sort(amount);
        int a = amount[0], b = amount[1], c = amount[2];
        if (a + b <= c) return c;        
        else return (a + b - c + 1) / 2 + c;
    }
}

工夫复杂度：$O(1)$
空间复杂度：$O(1)$

这是咱们「刷穿 LeetCode」系列文章的第 No.2335 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于后端:面试高频题难度-15可灵活切换数据范围的小小思维题

题目形容

排序 + 递归

贪婪 + 数学

最初