Massive Algorithms: LeetCode 799

LeetCode 799 - Champagne Tower

https://leetcode.com/problems/champagne-tower/description/

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup (250ml) of champagne.

Then, some champagne is poured in the first glass at the top. When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has it's excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)

Example 1:
Input: poured = 1, query_glass = 1, query_row = 1
Output: 0.0
Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:
Input: poured = 2, query_glass = 1, query_row = 1
Output: 0.5
Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Note:

poured will be in the range of [0, 10 ^ 9].
query_glass and query_row will be in the range of [0, 99].

X. DP

Instead of keeping track of how much champagne should end up in a glass, keep track of the total amount of champagne that flows through a glass. For example, if poured = 10 cups are poured at the top, then the total flow-through of the top glass is 10; the total flow-through of each glass in the second row is 4.5, and so on.

Algorithm

In general, if a glass has flow-through X, then Q = (X - 1.0) / 2.0 quantity of champagne will equally flow left and right. We can simulate the entire pour for 100 rows of glasses. A glass at (r, c) will have excess champagne flow towards (r+1, c) and (r+1, c+1).

Time Complexity: $O(R^2)$ , where $R$ is the number of rows. As this is fixed, we can consider this complexity to be $O(1)$ .
Space Complexity: $O(R^2)$ , or $O(1)$ by the reasoning above.

public double champagneTower(int poured, int query_row, int query_glass) {
double[][] A = new double[102][102];
A[0][0] = (double) poured;
for (int r = 0; r <= query_row; ++r) {
for (int c = 0; c <= r; ++c) {
double q = (A[r][c] - 1.0) / 2.0;
if (q > 0) {
A[r+1][c] += q;
A[r+1][c+1] += q;
}
}
}

return Math.min(1, A[query_row][query_glass]);
}

https://leetcode.com/problems/champagne-tower/discuss/118711/JavaC%2B%2BPython-1D-DP-O(R)-space

Time O(R^2) Time, Space O(R), where R = query_row

    public double champagneTower(int poured, int query_row, int query_glass) {
        double[] res = new double[query_row + 2];
        res[0] = poured;
        for (int row = 1; row <= query_row; row++)
            for (int i = row; i >= 0; i--)
                res[i + 1] += res[i] = Math.max(0.0, (res[i] - 1) / 2);
        return Math.min(res[query_glass], 1.0);
    }

https://leetcode.com/problems/champagne-tower/discuss/118692/9ms-5-Lines-Code-C%2B%2BJava

public double champagneTower(int poured, int query_row, int query_glass) {
    double[] dp = new double[101]; dp[0] = poured;
    for(int row=1; row<=query_row; row++)
        for(int i=row; i>=0; i--)
            dp[i+1] += dp[i] = Math.max(0.0, (dp[i]-1)/2);
    return Math.min(dp[query_glass], 1.0);
}

http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-799-champagne-tower/

define dp[i][j] as the volume of champagne will be poured into the j -th glass in the i-th row, dp[i][j] can be greater than 1.

Init dp[0][0] = poured.

Transition: if dp[i][j] > 1, it will overflow, the overflow part will be evenly distributed to dp[i+1][j], dp[i+1][j+1]

if dp[i][j] > 1:
dp[i+1][j] += (dp[i][j] – 1) / 2.0
dp[i+1][j + 1] += (dp[i][j] – 1) / 2.0

Answer: min(1.0, dp[query_row][query_index])

double champagneTower(int poured, int query_row, int query_glass) {
  constexpr int kRows = 100;
  vector<vector<double>> dp(kRows, vector<double>(kRows));
  dp[0][0] = poured;
  for (int i = 0; i < kRows - 1; ++i)
    for (int j = 0; j <= i; ++j)
      if (dp[i][j] > 1) {
        dp[i + 1][j    ] += (dp[i][j] - 1) / 2.0;
        dp[i + 1][j + 1] += (dp[i][j] - 1) / 2.0;
        dp[i][j] = 1.0;
      }
  return std::min(1.0, dp[query_row][query_glass]);
}

Pull:

double champagneTower(int poured, int query_row, int query_glass) {
   constexpr int kRows = 100;
  vector<vector<double>> dp(kRows, vector<double>(kRows));
  dp[0][0] = poured;
  for (int i = 1; i < kRows; ++i)
    for (int j = 0; j <= i; ++j) {
      if (j > 0) dp[i][j] += max(0.0, (dp[i - 1][j - 1] - 1) / 2.0);
      if (j < i) dp[i][j] += max(0.0, (dp[i - 1][j    ] - 1) / 2.0);
    }
  return std::min(1.0, dp[query_row][query_glass]);
}

https://www.cnblogs.com/grandyang/p/9286537.html

这道题用高脚杯摆了个金字塔，貌似在电影里见过这种酷炫的效果，不过好像还是3D的，组了个立体的酒杯金字塔。这道题中的金字塔是2D的，降低了一些难度。在我们最开始没有什么思路的时候，我们就从最简单的开始分析吧：

当只倒一杯酒的时候，只有最顶端的酒杯被填满。

当倒二杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯各自装了一半。

当倒三杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯也被填满。

当倒四杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯也被填满，第三层的三个酒杯分别被填了四分之一，二分之一，和四分之一。

当倒五杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯也被填满，第三层的三个酒杯分别被填了二分之一，填满，和二分之一。

...

如果酒是无限的，那么最终每个酒杯就会被填满，所以难点就是怎么知道在倒K杯酒后，当前的酒杯还剩多少。不管酒量又多大，当前酒杯最多只能装一杯，多余的酒都会流到下一行的两个酒杯。那么比如我们总共倒了五杯酒，那么最顶端的酒杯只能留住一杯，剩下的四杯全部均分到下行的酒杯中了，而离其最近的下一行的两个酒杯会平均分到其多出来的酒量。那么第二层的酒杯分别会得到(5-1)/2=2杯。而第二层的两个酒杯也分别只能留住一杯，各自多余的一杯还要往第三层流，那么第三层的第一个杯子接住了第二层的第一个杯子流下的半杯，而第三层的第二个杯子接住了第二层的两个杯子各自流下的半杯，于是填满了。第三层的第三个杯子接住了第二层的第二个杯子流下的半杯。那么我们的思路应该就是处理每一个杯子，将多余的酒量均分到其下一层对应的两个酒杯中，我们只需要处理到query_row那一行即可，如果地query_glass中的酒量超过一杯了，那么我们返回1就行了，因为多余的还会往下流，但我们不需要再考虑了。

我们建立一个二维的dp数组，其中dp[i][j]表示第i行第j列的杯子将要接住的酒量（可能大于1，因为此时还没有进行多余往下流的处理），那么我们就逐个遍历即可，将多余的酒量均分加入下一行的两个酒杯中即可

double champagneTower(int poured, int query_row, int query_glass) {
    vector<vector<double>> dp(101, vector<double>(101, 0));
    dp[0][0] = poured;
    for (int i = 0; i <= query_row; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (dp[i][j] >= 1) {
                dp[i + 1][j] += (dp[i][j] - 1) / 2.0;
                dp[i + 1][j + 1] += (dp[i][j] - 1) / 2.0;
            }
        }
    }
    return min(1.0, dp[query_row][query_glass]);
}

我们可以对上面的代码进行空间上的优化，只用一个一维数组即可

double champagneTower(int poured, int query_row, int query_glass) {
    vector<double> dp(101, 0);
    dp[0] = poured;
    for (int i = 1; i <= query_row; ++i) {
        for (int j = i; j >= 0; --j) {
            dp[j + 1] += dp[j] = max(0.0, (dp[j] - 1) / 2.0);
        }
    }
    return min(1.0, dp[query_glass]);
}

X. https://leetcode.com/problems/champagne-tower/discuss/191677/java-simulation

    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] g = new double[1 + query_row][1 + query_row];
        g[0][0] = poured;
        for (int i = 0; i < query_row; i++){
            for (int j = 0; j <= i; j++){
                if (g[i][j] > 1){
                    double p = (g[i][j] - 1.0) / 2;
                    g[i + 1][j] += p;
                    g[i + 1][j + 1] += p;
                }
            }
        }
        return Math.min(1.0, g[query_row][query_glass]);
    }

X. Videos
花花酱 LeetCode 799. Champagne Tower - 刷题找工作 EP173

LeetCode 799 - Champagne Tower

Labels

Popular Posts