香槟塔(Leetcode 799)

题目分析

   给大家介绍一个模拟题，香槟塔大家在电影里都应该见到过，本题是求倒了n杯香槟时，第i行，第j列个杯子有多少百分比的香槟。

模拟

遇到这种题目，我们一定要先模拟一下。

什么情况下会溢出到下一层呢？会溢出到下一层的哪些杯子呢？

答：当杯子中香槟的数量超过1时，会将超出1的部分溢出到下一层。且溢出到下一层的该位置和下一个位置。

如当前杯子是m行，n列，那么溢出后会流到m + 1行，n列和n + 1列中。

因为行数和列数最大为99，那么可能会流到第100个杯子中，所以创建长度为101的二维数组即可。

算法的时间复杂度为O(mn)，空间复杂度为O(mn)。本题可以使用标志位优化空间变成一维，但是不利于阅读，这里不过多赘述，感兴趣的小伙伴可以尝试。

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        if (query_row == 0 && query_glass == 0) {
            return Math.min(poured, 1);
        }
        double[][] nums = new double[101][101];
        nums[0][0] = poured;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j <= i + 1; j++) {
                if (nums[i][j] > 1) {
                    double over = nums[i][j] - 1;
                    nums[i][j] = 1;
                    double avg = over / 2;
                    nums[i + 1][j] += avg;
                    nums[i + 1][j + 1] += avg;
                }
                if (i + 1 == query_row && j == query_glass) {
                    return Math.min(nums[i + 1][j], 1);
                }
            }
        }
        return 1;
    }
}

刷题总结

  做类似这种题目，就需要先模拟，然后在模拟的过程中就会想到答案。