ChampagneTower [source code]
public class ChampagneTower {
static
/******************************************************************************/
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[] cups = new double[query_row + 1];
cups[0] = poured;
for (int i = 0; i < query_row; i++) {
for (int j = i; j >= 0; j--) {
double overflow = Math.max (0, cups[j] - 1);
if (j + 1 <= query_row)
cups[j + 1] += overflow / 2;
cups[j] = overflow / 2;
}
}
return cups[query_glass] >= 1 ? 1 : cups[query_glass];
}
}
/******************************************************************************/
public static void main(String[] args) {
ChampagneTower.Solution tester = new ChampagneTower.Solution();
int[] inputs = {
1,1,1,
2,1,1,
4,2,0,
4,2,1,
4,2,2,
2,0,0,
1,1,0,
};
double[] answers = {
0.0,
0.5,
0.25,
0.5,
0.25,
1.0,
0,
};
for (int i = 0; i < inputs.length / 3; i++) {
System.out.println (Printer.separator ());
int poured = inputs[3 * i], query_row = inputs[3 * i + 1], query_glass = inputs[3 * i + 2];
double ans = answers[i], output = tester.champagneTower (poured, query_row, query_glass);
System.out.printf ("%d, [%d, %d] -> %s, expected: %f\n",
poured, query_row, query_glass, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
读完题目感觉有点意思, AC率也很低的好题目;
这题的一个误区是认为每一row都填满了之后才会进行下一个row; 自己脑子里面稍微想一下就知道, 并不是这个情况;
这个题目看起来完全没有任何的算法规律, 就有点类似之前做的一个chessboard的题目; 这种题目以前也总结过, 很大的可能性, 是要你自己先分析总结题目的本质和规律, 把题目给的条件简化一下, 而不是跟现在刚看到这样, 好像什么都没有办法确定;
完全没有思路, 偷瞄了一眼editorial, 好像做法是simulation, 然后大概想到思路, 基本就是一行一行的倒, 满了就往两边倒. 这个做法最后的复杂度应该是N^2; 难道这题真的就没有更好的办法了吗?
今天时间紧张, 不想仔细想了, 先用这个办法写写看;
break掉两个case之后, 过了, 速度是25ms (NA).
注意看内层j循环的顺序: 这样的写法可以保证只需要一个copy的cups就行了; 注意看往右边的溢出是用+=, 左边的溢出就直接用=就行了;
算法本身写的还是很干净的, 就是第一遍刚写完的时候, 逻辑没有理清楚; 比如, 就算是当前的这个cups, 并没有满, 你还是要适当的更新, 因为你是一个array代表所有的row, 所以就算没有满, 你最后的算法也要保证能够清零;
上面的代码是又继续优化过的, 最开始的AC代码:
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[] cups = new double[query_row + 1];
cups[0] = poured;
for (int i = 0; i <= query_row; i++) {
if (query_row == i)
return cups[query_glass] <= 1 ? cups[query_glass] : 1.0;
for (int j = i; j >= 0; j--) {
double overflow = Math.max (0, cups[j] - 1);
cups[j + 1] += overflow / 2;
cups[j] = overflow / 2;
}
}
return cups[query_glass];
}
}
小的技巧就是, 因为我每一个row的工作其实就是把溢出往外扫, 所以最后一行其实不用处理;
这题最大的教训就是一定要简单升级, 这个在面试的时候尤其重要; 一个是展现思路, 一个就是就像这题这样, 屠龙术是非常难想到的, uwi没有想到, 这都过去一个星期了, discuss也没有人想到;
结果就是最直接的模拟的办法(一开始被我认为是笨办法的办法), 就是最后最正确的办法;
editorial
Approach #1: Simulation [Accepted]
Intuition
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).
class Solution {
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]);
}
}
其实跟我的这个算法是一样的, 就是感觉他解释的方式有点奇怪; 复杂度是R^2. 注意, 不是 query_glass^2;
https://leetcode.com/problems/champagne-tower/discuss/118660/20ms-C++-Easy-understand-solution
We use a table to record the result.
Simple idea:
If the glass >=1, we should split the diff (glass - 1) into next level.
double champagneTower(int poured, int query_row, int query_glass) {
double result[101][101] = {0.0};
result[0][0] = poured;
for (int i = 0; i < 100; i++) {
for (int j = 0; j <= i; j++) {
if (result[i][j] >= 1) {
result[i + 1][j] += (result[i][j] - 1) / 2.0;
result[i + 1][j + 1] += (result[i][j] - 1) / 2.0;
result[i][j] = 1;
}
}
}
return result[query_row][query_glass];
}
下面一个跟我的类似的写法, 写的比我还简单;
double champagneTower(int poured, int query_row, int query_glass) {
double dp[101] = {0.0};
dp[0] = poured;
for(int row=1; row<=query_row; row++)
for(int i=row; i>=0; i--)
dp[i+1] += dp[i] = max(0.0, (dp[i]-1)/2);
return min(dp[query_glass], 1.0);
}
下面还有一个自称是Bottom-Up的做法:
class Solution {
public:
double champagneTower(int poured, int query_row, int query_glass) {
double result[101][101] = {0.0};
result[0][0] = poured;
update(query_row-1, max(query_glass-1, 0), min(query_glass, query_row-1), result);
return min(1.0, result[query_row][query_glass]);
}
void update(int row, int left, int right, double result[101][101])
{
if(row > 0)
update(row-1, max(left-1, 0), min(right, row-1), result);
for(int i = left; i <= right; i++)
{
if(result[row][i] <= 1)
continue;
result[row+1][i] += (result[row][i]-1)/2;
result[row+1][i+1] += (result[row][i]-1)/2;
}
}
};
算法结构实际上是类似的, 就是他非要从下往上写, 但是算上recursion, 最后实际执行的时候还是从上到下;
不过感觉这种写法的一个好处就是, declarative的角度更好解释: 在我们更新一行的时候, 假定上一行已经正确, 这个从理解角度上比较直观;
uwi:
class Solution {
public double champagneTower(int poured, int qr, int qg) {
double[][] dp = new double[100][100];
dp[0][0] = poured;
for(int i = 0;i < 100;i++){
for(int j = 0;j <= i;j++){
if(dp[i][j] > 1){
if(i < 99){
dp[i+1][j] += (dp[i][j] - 1)/2;
dp[i+1][j+1] += (dp[i][j] - 1)/2;
}
dp[i][j] = 1;
}
}
}
return dp[qr][qg];
}
}
老办法, 没有什么新的东西;
看来他们这些竞赛选手也不是很讲究, 这题uwi实际上只用了7分钟, 估计是也没有多想;
我刚开始拿到这个题目的时候的一个误区就是始终认为肯定有什么很数学的办法, 可以直接计算出来对于一个固定的点的结果;
事实上我就算是到现在我都认为应该是有数学的解法, 因为这个三角形虽然看起来很复杂, 但是所有的结果明显都是已经静态固定的, 既然静态固定, 往往就有人已经完成了数学方法上的总结; 对于这种静态的问题, 还要专门走一个循环, 总是觉得有点不是最优;
Problem 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].
Difficulty:Medium
Total Accepted:1.6K
Total Submissions:6K
Contributor:ngoc_lam