这周的刷题周记，从周三开始。

分汤

题目：有 A 和 B 两种类型的汤。一开始每种类型的汤有 N 毫升。有四种分配操作：

提供 100ml 的汤A 和 0ml 的汤B。

提供 75ml 的汤A 和 25ml 的汤B。

提供 50ml 的汤A 和 50ml 的汤B。

提供 25ml 的汤A 和 75ml 的汤B。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为0.25的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。注意不存在先分配100 ml汤B的操作。需要返回的值： 汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。

示例:
输入: N = 50
输出: 0.625
解释:
如果我们选择前两个操作，A将首先变为空。对于第三个操作，A和B会同时变为空。对于第四个操作，B将首先变为空。
所以A变为空的总概率加上A和B同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
注释:
0 <= N <= 10^9。
返回值在 10^-6 的范围将被认为是正确的。

思路：这个题怎么说呢，题目就好难读懂。而且看这个概率我都脑壳痛。。。怎么说呢，这个题的标签是dp。因为N的范围是10的9次方。所以说数据应该还挺大的。哪怕是dp。但是应该也不会是二维数组啥的。然后继续看这四种分配方式，第三种是半对半。。而重点是第二种和第四种是对应的。也就是说第二接第四。和第三种是差不多的思路了。我感觉这个绝对不是巧合。我去琢磨琢磨有啥递推公式。
我看了题解，因为实在想不出N大了怎么办。结果发现题解真的是个小机灵鬼。。其实可以这么想。B先没的概率只有用第四种方式。也就是四分之一。而且这个问题是调用1或者2都能把调用4的B多到的赚回来。所以当N比较大。轮数比较多的时候，想要B先没的条件就很苛刻。所以某些规律（我也不知道怎么算的，但是能想象到）当N超过5000的时候，B先没的那点概率几乎就没了。反正就是N大于5000，直接返回1就行了（这里返回1是说明无限接近1，因为题目是允许误差的）。
这一点明确了的话后面N比较小的时候的dp公式比较容易写出来：
因为每次分汤总和都是100.而且最小单位是25.所以我们可以把25看成1.100看成4.所以每次分汤演变成如下：
选择一： A:4 B:0
选择二： A:3 B:1
选择三： A:2 B:2
选择四： A:1 B:3
这么做的好处是可以缩小N的范围。从而让这个二维dp缩小25倍。然后这个dp公式其实是要逆推的。就是先知道汤少的时候的结果。再把汤多的时候的前四种可能（因为汤多到少只有四种分配可能。我们可以认为这四种分配可能的总结过就是当前结果）的结果统计。这样一层一层往上找。最终知道当前汤的结果。思路其实还是很明确的。下面是代码：

class Solution {
    double[][] dp;
    public double soupServings(int N) {
        if(N>=5000) return 1d;
        N = (N+24)/25;
        dp = new double[N+1][N+1];
        return divide(N, N);
    }
    private double divide(int a, int b) {
        if(a<=0 && b<=0) return 0.5d;
        if(a<=0) return 1d;
        if(b<=0) return 0d;
        if(dp[a][b]>0) return dp[a][b];
        return dp[a][b] = 0.25*(divide(a-4,b)+divide(a-3, b-1)+divide(a-2, b-2)+divide(a-1, b-3));
    }
}

因为我看的题解直接就是性能最好的代码了，所以这里也不用再去看了，总而言之我觉得这个题的难度完全就是在于N>5000。剩下的后面都比较容易想。这个题就这样了，下一题。

最大平均值和的分组

题目：我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

示例:
输入:
A = [9,1,2,3,9]
K = 3
输出: 20
解释:
A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
说明:
1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
答案误差在 10^-6 内被视为是正确的。

*思路：这个题的标签是动态规划。然後又是我的知识盲区。这个题我觉得重点是dp。分为k组。所以肯定是从一组开始往上慢慢分的。一组的最大值，2组的最大值，三组的最大值。我觉得大概是这个思路。但是具体的dp公式啥的我还得慢慢去想想。
代码实现：

class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int len = A.length;
        //当前dp是从头加到i-1的总和
        int[] sum = new int[len+1];
        for(int i = 1;i<=len;i++) sum[i] = sum[i-1]+A[i-1];
        double[] dp = new double[len];//分成k个子集合
        //这个计算是以当前节点往后作为最后一个子集和的平均值是多少
        for(int i = 0;i<len;i++) dp[i] = (sum[len]-sum[i])*1.0/(len-i);
        //因为分成1个的平均值已经知道了，就是dp[0].所以k=1开始，k-1结束。
        for(int i = 1;i<K;i++) {
            for(int j = 0;j<len;j++) {
                for(int k = j+1;k<len;k++) {
                    //算出来的结果是当前j位置的元素从当前开始分成2组能凑出来的最大平均数和
                    //比如 7，3，2,7,4那么在第一个7的位置的时候能凑出来的最大平均数和7+（3+2+7+4）/4=11.
                    //而当前元素是3的话，能凑出来的最大平均数和是（3+2）/2+（7+4）/2 = 8
                    //当前元素是2的话，能凑出来的最大平均数和是（2+7）/2+4 = 8.5
                    //总而言之计算出来的是当前位置为开始。所有元素分成2组的最大值。
                    //因为之后的每一次dp数据的值都是上一次计算过的。也就是当前位置及以后分成两个组的最大值。所以说
                    //第二次走到这个循环的时候。就变成了3个。再一次就是4个。依此类推。所以分成K个需要k-1次循环。
                    dp[j] = Math.max(dp[j], dp[k]+(sum[k]-sum[j])*1.0/(k-j));
                }
            }
        }
        return dp[0];
    }
}

因为代码中的注解写的很全了，所以多余的我就不说了。总而言之思路就是这么个思路。既有分治的思想也用到了dp。而且这个题其实应该是一个二维dp。但是因为用了状态压缩一层一层覆盖上一层的数据所以用了一维dp就实现了。总而言之这个题的思路我是看题解才会的。。。dp果然是我的死穴，太难了啊。
我去看看性能第一的代码怎么写的:

class Solution {
    double[][] dp;
    double[] sum;
    public double largestSumOfAverages(int[] A, int K) {
        int n=A.length;
        dp=new double[K+1][n+1];//分为k组，前i个数的最大结果
        sum=new double[n+1];//前缀和，方便求平均值
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1]+A[i-1];
        }
        return helper(K,n,A);
    }
    private double helper(int k,int i,int[] A){
        if(dp[k][i]>0) return dp[k][i];//记忆化递归的特点，利用了缓存
        if(k==1) return (sum[i]/i);
        for(int j=k-1;j<i;j++){
            dp[k][i]=Math.max(dp[k][i],helper(k-1,j,A)+(sum[i]-sum[j])/(i-j));
        }
        return dp[k][i];
    }
}

感觉思路是差不多的，不过是细节的处理上略有不同吧，所以我也不多说了，直接下一题了。

笨乘阶

题目：通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：
输入：4
输出：7
解释：7 = 4 * 3 / 2 + 1
示例 2：
输入：10
输出：12
解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1
提示：
1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数。）

思路：这个题是2021/4/1的每日一题。因为是个没做过的中等难度的题目所以也在此记录一下。总而言之这个题目我打算用压栈的方式。所有的乘除都直接计算。然后减号乘-1.每一个元素放到栈中最后统一加法。我去实现下试试。
第一版本代码出来了，就是我不知道为什么性能贼可怜。。。附上代码：

class Solution {
    public int clumsy(int N) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(N);
        N--;
        //顺序*/+-
        int n = 0;
        while(N != 0) {
            if(n%4 == 0) {//*
                int i = stack.pop();
                stack.push(N*i);
            }else if(n%4 == 1) {//除
                int i = stack.pop();
                stack.push(i/N);
            }else if(n%4 == 2) {//+
                stack.push(N);
            }else {// -
                stack.push(-N);
            }
            n++;
            N--;
        }
        int ans = 0;
        for(Integer i:stack) ans += i;
        return ans;
    }
}

当然了我觉得这个题可能有更好的解答。因为四个一组是很明显的情况。。。所以我换个思路。不用这些花里胡哨的东西了。直接到加号或者减号划分计算。我去试试代码。
我发现我思路问题比较大。。因为答案简单的可怕:

性能第一的代码

其实吧，我觉得也不是不能理解。我都已经看到规律了。因为乘除加减是顺序循环的。所以把所有能归并的归一起，可能是有什么规律，但是我万万没想到会这么简单！！！就一句话:

class Solution {
    public int clumsy(int N) {
        int num[] = {1, 2, 2, -1};
        return N > 4 ? N + num[N % 4] : (N > 2 ? N + 3 : N);
    }
}

总而言之这个题我的做法其实是适合解析字符串计算的那种。然後这个题真正的答案是找规律的那种。但是题目不难，挺有意思的，这个题就这样吧。下一题。

二叉树剪枝

题目：给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。返回移除了所有不包含 1 的子树的原二叉树。( 节点 X 的子树为 X 本身，以及所有 X 的后代。)

示例1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]
解释:
只有红色节点满足条件“所有不包含 1 的子树”。
右图为返回的答案。
示例2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
示例3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
说明:
给定的二叉树最多有 100 个节点。
每个节点的值只会为 0 或 1 。

题目截图

思路：这个题我觉得目前我的思路是就是遍历树。叶子节点是0则变null。非叶子节点如果发现左右节点都是null当前值还是0也变null。后续遍历先知道子节点的情况然后就知道当前节点的情况了。思路比较清晰，我去实现下试试。
第一版本代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return dfs(root);
    }
    public TreeNode dfs(TreeNode root) {
        if(root == null || (root.val == 0 && root.left == null && root.right == null)) return null;
        TreeNode left = dfs(root.left);
        TreeNode right = dfs(root.right);
        if(root.val == 0 && left == null && right == null) return null;
        root.left = left;
        root.right = right;
        return root;
    }
}

其实思路很容易想。毕竟遇到树第一反应就应该是递归遍历。而这个题只要知道规律没啥难度。这个代码性能也超过百分百了所以我就不看别的代码了，直接过。

直方图的水量

题目：给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

题目截图

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路：这个题是2021/4/2的每日一题。虽然是个困难难度的，但是看似不是很难。现在的思路是双指针。从第一个元素开始走，遇到比当前大于等于的值说明闭环了。然后计算这中间的存水量。另外如果到最后都不能闭环则取当前值往后的最大值。以尾元素的大小为闭环。下一个区间也以尾元素开始计算。思路大概是这样。因为这个题没数据范围所以也不知道能不能实现，重点就是下一个大于等于的元素。我去实现下试试。

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int len = height.length;
        for(int i = 0;i<len;i++){
            int temp = height[i];
            int max = Integer.MIN_VALUE;
            int idx = -1;
            for(int j = i+1;j<len;j++){
              if(height[j]>=temp){//这里是大于等于都可以。因为不管是大于还是等于都闭环
                  max = height[j];
                  idx = j;
                  break;
              }else if(height[j]>max){//注意这里一定要大于才替换，等于不换，相等取前面的。
                  max = height[j];
                  idx = j;
              }
            }
            //走到这里我们知道了当前的闭环。所以求值
            if(idx == -1) return ans;
            ans += sum(i,idx,height);
            i = idx-1;
        }
        return ans;
    }
    public int sum(int start,int end,int[] height){
        int min = Math.min(height[start],height[end]);
        int ans = 0;
        for(int i = start+1;i<end;i++){
            ans += min-height[i];
        }
        return ans;
    }
}

说真的，这个题一点都对不起它的难度。上面的思路没啥问题，而且实现以后我还发现这个性能挺好的。中间i = idx-1算是我第一次代码的小bug，因为我本来是i = idx。debug才发现这么设置有问题。因为i=idx以后还要走for循环的++。所以这样就跳过了idx这个数本身。但是这是小细节，别的思路没啥问题。然后上面的代码性能超过百分之九十九。我再去看看性能第一的代码：

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int l=0,r=height.length-1;
        if (r<0) {
            return 0;
        }
        int lMax=height[l],rMax=height[r];
        while (l<r) {
            if (height[l]>height[r]) {
                if (height[r]<rMax) {
                    res += (rMax-height[r]);
                } else {
                    rMax = height[r];
                }
                r--;
            } else {
                if (height[l]<lMax) {
                    res += (lMax-height[l]);
                } else {
                    lMax = height[l];
                }
                l++;
            }
        }
        return res;
    }
}

果然是写法上的优雅。因为思路差不多，而且我觉得我的代码更容易让人理解，就是写出来比较啰嗦而已。这个题就这样了，没什么好说的，下一题。

模糊坐标

题目：我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001", "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。

示例 1:
输入: "(123)"
输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
示例 2:
输入: "(00011)"
输出: ["(0.001, 1)", "(0, 0.011)"]
解释:
0.0, 00, 0001 或 00.01 是不被允许的。
示例 3:
输入: "(0123)"
输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
示例 4:
输入: "(100)"
输出: [(10, 0)]
解释:
1.0 是不被允许的。
提示:
4 <= S.length <= 12.
S[0] = "(", S[S.length - 1] = ")", 且字符串 S 中的其他元素都是数字。

思路：怎么说呢，这个字符串一共有三个可添加的东西:一个小数点。一个逗号，一个小数点。逗号是必须的，其余两个都可以在0之前和在末尾之后。然后我们只要顺序往后走，顺便判断一下数值是不是合法就行了。目前而言觉得思路比较简单。我去试试代码。
第一版本代码(中间经历了一个清明节，一次备受打击的leetcode春季赛):

class Solution {
    public List<String> ambiguousCoordinates(String S) {
        //重点就是这三个标点：. , .的位置
        int len = S.length();
        List<String> ans = new ArrayList<String>();
        //注意这个范围。因为第一层是逗号的位置。所以一定在第一个数字之后，最后一个数字之前
        for(int i = 2;i<len-1;i++) {
            //第二层是第一个小数点.第一个小数点一定在逗号前面
            for(int j = 2;j<i+1;j++) {
                String f1 = S.substring(1,j);
                String f2 = S.substring(j,i);
                //第三层是第二个小数点.一定是在逗号后面
                for(int k = i+1;k<len;k++) {
                    String s1 = S.substring(i,k);
                    String s2 = S.substring(k,len-1);
                    if(isOk(s1,s2,f1,f2)) {
                        StringBuffer sb = new StringBuffer();
                        sb.append("(");
                        if(f1.equals("")) {
                            sb.append(f2);
                        }else if(f2.equals("")) {
                            sb.append(f1);
                        }else {
                            sb.append(f1+"."+f2);
                        }
                        sb.append(", ");
                        if(s1.equals("")) {
                            sb.append(s2);
                        }else if(s2.equals("")) {
                            sb.append(s1);
                        }else {
                            sb.append(s1+"."+s2);
                        }
                        sb.append(")");
                        ans.add(sb.toString());
                    }
                }
            }
        }
        return ans;
        
    }
    public boolean isOk(String s1,String s2,String f1,String f2) {
        if((s1.length()>1 && s1.startsWith("0")) || s2.endsWith("0")) return false;
        if((f1.length()>1 && f1.startsWith("0")) || f2.endsWith("0")) return false;
        return true;
    }
}

怎么说呢，我觉得思路是简单的。但是我在这期间关于两个整数范围小数范围的临界点也一直有调整。而且前后还有括号。逗号后面还有空格。整体来说这个题细节比较多。但是细心点还是比较容易做出来。我去看看性能第一的代码：

class Solution {

    public List<String> ambiguousCoordinates(String S) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int n = S.length();
        for (int i = 1; i <= n - 3; ++i){
            // [1, i]
            // ','
            // [i + 1, n - 2] 
            for (int left = 1; left <= i; ++left){
                if (left > 1 && '0' == S.charAt(1)) continue;
                if (left < i && '0' == S.charAt(i)) continue;
                for (int right = i + 1; right <= n - 2; ++right){
                    if (right > i + 1 && '0' == S.charAt(i + 1)) continue;
                    if (right < n - 2 && '0' == S.charAt(n - 2)) continue;

                    sb.delete(0, sb.length());
                    for (int k = 0; k < n; ++k){
                        sb.append(S.charAt(k));
                        if (k == left && left != i){
                            sb.append('.');
                        }
                        if (k == i){
                            sb.append(", ");
                        }
                        if (k == right && right != n - 2){
                            sb.append('.');
                        }
                    }
                    res.add(sb.toString());
                }
            }
        }
        
        return res;
    }
}

我是觉得思路是差不多的，但是人家的处理更加优雅。我还单独写了个方法判断。总而言之我觉得思路很重要，决定这个题能不能做出来。但是细节也很重要，决定这个题能不能做的漂亮性能又好。而细节我想做的多了自然就熟了吧。这个题就过了。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利，生活健健康康~！学无止境，知道的越多越会发现自己的浅薄，愿我们在求索的道路上一往无前！