LC222周赛前三题 - 《算法》

/*
@author _ * @date 2021/1/3 12:13 下午
* @since
请你将一些箱子装在一辆卡车上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：

numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载箱子的最大数量。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。

返回卡车可以装载单元的最大总数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-units-on-a-truck
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/
思路：贪心即可，按照提示，只对箱子数有限制，但是却对单元数量没有任何限制，想要得到单元的最大总数，就很简单了。先对单元数进行排序，之后贪心算法coding即可。

public class KaChe {
    // 贪心算法思想
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int res = 0;
        // 按照boxTypes[i][1] 排序
        Arrays.sort(boxTypes, (a,b)->(b[1]-a[1]));
        for (int i = 0; i < boxTypes.length && truckSize>0; i++) {
            int cur = Math.min(boxTypes[i][0],truckSize);
            res += cur * boxTypes[i][1];
            truckSize -= boxTypes[i][0];
        }
        return res;
    }
}

/*
@author
* @date 2021/1/3 4:51 下午
* @since 大餐是指恰好包含两道不同餐品的一餐，其美味程度之和等于 2 的幂。

你可以搭配任意两道餐品做一顿大餐。

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同大餐的数量。结果需要对 1e9 + 7 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。
1 <= deliciousness.length <= 1e5
0 <= deliciousness[i] <= 2^20
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-good-meals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
如题目要求，判断美味程度之和，是否为2的幂。可以使用枚举法，依次遍历数组里的数字（21次）。

public class Count {
    public int countPairs(int[] deliciousness) {
        long res = 0;
        double mod = 1e9 + 7;
        HashMap<Integer, Integer> existMap = new HashMap<>();
        for (int x : deliciousness) {
            for (int i = 0; i <= 21; i++) {
                int temp = (1 << i) - x;
                if (existMap.containsKey(temp)) {
                    res = (res + (long) existMap.get(temp)) % (long) mod;
                }
            }
            existMap.put(x, existMap.getOrDefault(x, 0) + 1);
        }
        return (int) res;
    }
}

/*
@author
* @date 2021/1/3 5:08 下午
* @since
我们称一个分割整数数组的方案是好的，当它满足：

数组被分成三个非空连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。
给你一个非负整数数组 nums ，请你返回好的分割 nums 方案数目。由于答案可能会很大，请你将结果对 109 + 7 取余后返回。
示例 1：

输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。

3 <= nums.length <= 1e5
0 <= nums[i] <= 1e4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：前缀和+双指针击败100%
数组被分为三部分，中间将有两个节点作为分界点，枚举第二个端点，因为数组中的元素都是非负的，
当右端点确定时，求出在满足s(mid)<=s(right)的条件下，第一个端点的最小值，然后在求出满足s(left)<=s(mid)的情况下，第一个端点的最大值。
最后判断下求出的两个值是否是符合条件的，如果符合条件的话，将这段区间的个数累加到答案中。
因为随着枚举的数不断右移，第一个端点一定不会向左移动，所以可以采用双指针的做法。细节需要仔细扣一下
*/

public class DoublePoint {
    public int waysToSplit(int[] nums) {
        long res = 0;
        int n = nums.length;
        double mod = 1e9+7;
        // 构造前缀和
        int sum[] = new int[n+1];
        for (int i=1;i<=n;i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        for (int i = 3,j = 2, k = 2; i <= n; i++ ){
            // 中间总和大于右侧总和,确定第一个端点的最小值
            while (j < i && sum[i-1]-sum[j-1] > sum[n] - sum[i-1]) {
                j++;
            }
            // 确定第一个端点的最大值情况 之后k-j+1代表最终case
            while (k+1 < i && sum[i-1] - sum[k] >= sum[k]){
                k++;
            }
            if (j<=k && sum[i-1]-sum[j-1] <= sum[n] - sum[i-1] && sum[i-1] - sum[k-1] >=sum[k-1]){
                res = (res + k - j + 1)% (long)mod;
            }
        }
        return (int)res;
    }
}