Problem A

Apple Redistribution into Boxes

思路

求和-算所有苹果的和 然后将箱子从大到小排序 贪心即可

代码

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        int sum = 0;
        for(int num:apple){
            sum+=num;
        }
        
        Arrays.sort(capacity);
        for(int i = capacity.length-1;i>=0;--i){
           
                sum-=capacity[i];
            if(sum<=0){
                return  capacity.length-1-i+1;
            }
        }
        return capacity.length;
    }
}

Problem B

Maximize Happiness of Selected Children

思路

贪心 最优解为从大到小选人 开暴

代码

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        int n = happiness.length;
        long sum = 0;
        int cnt = 0;
        int i = n-1;
        while(cnt<k){
            sum = (sum+Math.max(0,happiness[i--]-cnt));
            cnt++;
            
        }
        return sum;
    }
}

Problem C

Shortest Uncommon Substring in an Array

思路

数据结构题 按照题意直接开暴就完事了

代码

class Solution {
    public String[] shortestSubstrings(String[] arr) {
        int n = arr.length;
        Map<String,Integer> map = new HashMap<>();
        List<Map<String,Integer>> l = new ArrayList<>();
        for(int i = 0;i<n;++i){
            l.add(new HashMap<String,Integer>());
            int m = arr[i].length();
            for(int j = 0;j<m;++j){
                StringBuilder sb = new StringBuilder("");
                for(int k = j;k<m;++k){
                    sb.append(arr[i].charAt(k));
                    String s = sb.toString();
                    l.get(i).put(s,l.get(i).getOrDefault(s,0)+1);
                    map.put(s,map.getOrDefault(s,0)+1);
                }
            }
            
        }
        String[] ans = new String[n];
        for(int i = 0;i<n;++i){
            String s = arr[i];
            if(map.get(s)>1){
                ans[i] = "";
                continue;
            }
            ans[i] = s;
            for(String t:l.get(i).keySet()){
                int cnt = map.get(t);
                int cnt2 = l.get(i).get(t);
                if(cnt==cnt2){
                    if(t.length()<ans[i].length()||(t.length()==ans[i].length()&&t.compareTo(ans[i])<0)){
                        ans[i] = t;
                    }
                }
               
            }
        }
        return ans;
    }
}
        

Problem D

Maximum Strength of K Disjoint Subarrays

思路

动态规划
考虑定义dp数组dp[j][i] 表示前i个元素划分为j段的最大值
接下来考虑转移过程
因为不需要全覆盖，因此转移有两种情况

• 不选当前元素 dp[j][i] = dp[j][i-1]
• 选当前元素，则最终结果应该表示为如下的格式
  $$ dp[j][i] = \max{dp[j-1][k]+weight(nums[k+1:i])} $$
  其中weight函数是计算题目中所说的权重

不难发现 因为转移状况中的需要枚举k，所以目前的时间复杂度为$o(n^3)$ 明显不符合题目的要求 因此考虑对转移方程进行优化

原有的weight函数可以表示为如下所示
$$(-1)^{i+1}sum[i](x-i+1)$$
其中使用前缀和优化可得
$$sum[i] = pre[i]-pre[k]$$
带入可得
$$(-1)^{i+1}sum[i](x-i+1) = (-1)^{i+1}(pre[i]-pre[k])(x-i+1)$$
$$ = (-1)^{i+1}(pre[i]-pre[k])(x-i+1)$$
其中$ (-1)^{i+1}(x-i+1) $ 和 $pre[i] $ 与枚举的k无关 可以直接将转移情况2中的方程改写为如下形式
$$ dp[j][i] = \max_{k=j}^{i-1} { {dp[j-1][k]-wpre[k]} }+wpre[i] $$
现在考虑固定j 在求解dp[j][i]和dp[j][i-1]时 求最大值枚举的k分别为
i = i-1,i-2,....,j
i-1 = i-2,....,j-1
可以发现在枚举过程中，新增的枚举项只有i-1的情况，其他在直接已经计算过，因此可以考虑从小到大遍历i 维护一个变量保存最大值，每次使用wpre[j-1]更新最大值即可
由此，我们可以在O(1)时间内获取到第二种情况的转移结果。

接下来 考虑初始化的问题，因为不能为空 所以要将dp[j][j-1]设置为无穷小 因为j-1个数不能分为j段

转移顺序也不难得出 需要j从小到大 i也从小到大

最终结果应该为dp[k][n]

注意下面的代码中i,j是互换的

代码

补题代码

class Solution {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[][] dp = new long[k+1][n+1];
        long[] pre = new long[n+1];
        for(int i = 0;i<n;++i){
            pre[i+1] = nums[i]+pre[i];
        }
        for(int i = 1;i<=k;++i){
            dp[i][i-1] = Long.MIN_VALUE;
            long mx = Long.MIN_VALUE;
            long w = i%2==0?-1:1;
            w = w*(k-i+1);
            for(int j = i;j<=n;++j){
                mx = Math.max(mx,dp[i-1][j-1]-pre[j-1]*w);
                dp[i][j] = Math.max(dp[i][j-1],mx+w*pre[j]);
            }
        }
        return dp[k][n];
    }
}

总结

本场简单 成功AK 但是第四题的思路不清晰 补学了下树状数组