逐日一题-香槟塔
本题 Leetcode 链接[1]
标题分析
我们把玻璃杯摆成金字塔的外形，此中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯 (250ml) 将盛有香槟。
从顶层的第一个玻璃杯开头倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都市立刻等流量的流向支配两侧的玻璃杯。当支配两边的杯子也满了，就会等流量的流向它们支配两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）
比如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时统共有三个满的玻璃杯。在倒第四杯后，第三层正中的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。
如今当倾倒了非负整数杯香槟后，前往第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（ i 和 j 都从0开头）。
输入输入
- 示例 1:
- 输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的地点数) = 1, query_row(行数) = 1
- 输入: 0.00000
- 表明: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此一切在顶层以下的玻璃杯都是空的。
- 示例 2:
- 输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的地点数) = 1, query_row(行数) = 1
- 输入: 0.50000
- 表明: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯中分了这一杯香槟，以是每个玻璃杯有一半的香槟。
- 示例 3:
- 输入: poured = 100000009, query_row = 33, query_glass = 17
- 输入: 1.00000
解题思绪
- 每层杯子的数目是query_row + 1，其对应的流量都是总流量减去表层一切流量后的均匀值
- 可以先盘算从第 i 行开头的溢出量 others
- 持续模仿将第 i+1 行的一切杯子装满所流经的流量
- 前往其比例轻重 ratio，假如 ratio 大于 1，则前往 1，由于它最大容量为 1，多余的流量已流到下一层
代码完成
function champagneTower(poured: number, query_row: number, query_glass: number): number {
let arr = [poured], ratio = 0
for (let i = 1; i < query_row + 1; i++) {
let others = Math.max(0, arr[0] - 1)
arr[0] = 0
for (let j = 0; j < i; j++) {
let half = others / 2
arr[j] += half
others = Math.max(0, arr[j + 1] - 1)
arr[j + 1] = half
}
}
ratio = arr[query_glass]
if (ratio > 1) return 1
return ratio
};
参考材料
[1]
本题 Leetcode 链接: https://leetcode.cn/problems/champagne-tower/
