周赛 - 🏆 第 288 场力扣周赛 - 《学习笔记》

">
6037. 按奇偶性交换后的最大数字
6038. 向表达式添加括号后的最小结果
6039. K 次增加后的最大乘积
6040. 花园的最大总美丽值

第四题犯蠢了，wrong了6次
这场分加上就2400了，可喜可贺！！！

6037. 按奇偶性交换后的最大数字

给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。
返回交换任意次之后 num 的最大可能值。

示例 1：
输入：num = 1234 输出：3412 解释：交换数字 3 和数字 1 ，结果得到 3214 。交换数字 2 和数字 4 ，结果得到 3412 。注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。
示例 2：
输入：num = 65875 输出：87655 解释：交换数字 8 和数字 6 ，结果得到 85675 。交换数字 5 和数字 7 ，结果得到 87655 。注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。

提示：

1 <= num <= 109

思路：
贪心
分奇偶排序，再填入对应位置即可

class Solution {
    public int largestInteger(int num) {
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        List<Boolean> ll = new ArrayList<>();
        while (num > 0) {
            int x = num % 10;
            num /= 10;
            if (x % 2 == 1) {
                l1.add(x);
                ll.add(false);
            } else {
                l2.add(x);
                ll.add(true);
            }
        }
        Collections.sort(l1);
        Collections.sort(l2);
        int[] a = new int[l1.size() + l2.size()];
        int i = 0, j = 0;
        for (int k = 0; k < ll.size(); k++) {
            boolean b = ll.get(k);
            if (b) {
                a[k] = l2.get(j++);
            } else {
                a[k] = l1.get(i++);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int k = a.length - 1; k >= 0; k--)
            sb.append(a[k]);
        return Integer.parseInt(sb.toString());
    }
}

6038. 向表达式添加括号后的最小结果

给你一个下标从 0 开始的字符串 expression ，格式为 “+“ ，其中和表示正整数。
请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到最小可能值。左括号必须添加在 ‘+’ 的左侧，而右括号必须添加在 ‘+’ 的右侧。
返回添加一对括号后形成的表达式 expression ，且满足 _expression 计算得到最小可能值。_如果存在多个答案都能产生相同结果，返回任意一个答案。
生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。

示例 1：
输入：expression = “247+38” 输出：“2(47+38)” 解释：表达式计算得到 2 (47 + 38) = 2 85 = 170 。注意 “2(4)7+38” 不是有效的结果，因为右括号必须添加在 ‘+’ 的右侧。可以证明 170 是最小可能值。
示例 2：
输入：expression = “12+34” 输出：“1(2+3)4” 解释：表达式计算得到 1 (2 + 3) 4 = 1 5 4 = 20 。
示例 3：
输入：expression = “999+999” 输出：“(999+999)” 解释：表达式计算得到 999 + 999 = 1998 。

提示：

3 <= expression.length <= 10
expression 仅由数字 ‘1’ 到 ‘9’ 和 ‘+’ 组成
expression 由数字开始和结束
expression 恰好仅含有一个 ‘+’.
expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围

思路
暴力查询

class Solution {
    public String minimizeResult(String es) {
        String[] ss = es.split("\\+");
        int n = ss[0].length(), m = ss[1].length();
        int min = (int)(2e9);
        int l = -1, r = -1;
        for (int i = 0; i < n; i++) {
            int a = 1, b = Integer.parseInt(ss[0].substring(i, n));
            if (i > 0) {
                b = Integer.parseInt(ss[0].substring(i, n));
                a = Integer.parseInt(ss[0].substring(0, i));
            }
            for (int j = 1; j <= m; j++) {
                int c = Integer.parseInt(ss[1].substring(0, j));
                int d = j == m ? 1 : Integer.parseInt(ss[1].substring(j, m));
                if (a * (b + c) * d < min) {
                    min = a * (b + c) * d;
                    l = i;
                    r = j;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(ss[0].substring(0, l));
        sb.append("(");
        sb.append(ss[0].substring(l, n));
        sb.append("+");
        sb.append(ss[1].substring(0, r));
        sb.append(")");
        sb.append(ss[1].substring(r, m));
        return sb.toString();
    }
}

6039. K 次增加后的最大乘积

给你一个非负整数数组 nums 和一个整数 k 。每次操作，你可以选择 nums 中任一元素并将它增加 1 。
请你返回至多 k 次操作后，能得到的_ _nums的 最大乘积 。由于答案可能很大，请你将答案对 109 + 7 取余后返回。

示例 1：
输入：nums = [0,4], k = 5 输出：20 解释：将第一个数增加 5 次。得到 nums = [5, 4] ，乘积为 5 4 = 20 。可以证明 20 是能得到的最大乘积，所以我们返回 20 。存在其他增加 nums 的方法，也能得到最大乘积。
示例 2：
输入：nums = [6,3,3,2], k = 2 输出：216 解释：将第二个数增加 1 次，将第四个数增加 1 次。得到 nums = [6, 4, 3, 3] ，乘积为 6 4 3 3 = 216 。可以证明 216 是能得到的最大乘积，所以我们返回 216 。存在其他增加 nums 的方法，也能得到最大乘积。

提示：

1 <= nums.length, k <= 105
0 <= nums[i] <= 106

思路：
贪心
每次将最小的数加一
证明：设最小的数为a，用其它数中任意数字b替换a，除a, b外其余数字乘积为c
因为a <= b
故a * (b * c) + b * c <= b * (a * c) + a * c恒成立
故每次将最小的数加一

class Solution {
    int MOD = (int)(1e9 + 7);
    public int maximumProduct(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int x : nums) {
            q.offer(x);
        }
        while (k > 0) {
            int x = q.poll();
            q.offer(x + 1);
            k--;
        }
        long mul = 1;
        while (!q.isEmpty()) {
            int x = q.poll();
            mul *= x;
            mul %= MOD;
        }
        return (int)(mul);
    }
}

6040. 花园的最大总美丽值

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。
给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花不能移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。
如果一个花园有至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之和：

完善花园数目乘以 full.
剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。

请你返回 Alice 种最多 newFlowers 朵花以后，能得到的最大总美丽值。

示例 1：
输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1 输出：14 解释：Alice 可以按以下方案种花 - 在第 0 个花园种 2 朵花 - 在第 1 个花园种 3 朵花 - 在第 2 个花园种 1 朵花 - 在第 3 个花园种 1 朵花花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。只有 1 个花园是完善的。不完善花园里花的最少数目是 2 。所以总美丽值为 1 12 + 2 1 = 12 + 2 = 14 。没有其他方案可以让花园总美丽值超过 14 。
示例 2：
输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6 输出：30 解释：Alice 可以按以下方案种花 - 在第 0 个花园种 3 朵花 - 在第 1 个花园种 0 朵花 - 在第 2 个花园种 0 朵花 - 在第 3 个花园种 2 朵花花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。有 3 个花园是完善的。不完善花园里花的最少数目为 4 。所以总美丽值为 3 2 + 4 6 = 6 + 24 = 30 。没有其他方案可以让花园总美丽值超过 30 。注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。

提示：

1 <= flowers.length <= 105
1 <= flowers[i], target <= 105
1 <= newFlowers <= 1010
1 <= full, partial <= 105

思路：
枚举完善花园的数目 + 二分

class Solution {
    public long maximumBeauty(int[] flowers, long off, int target, int full, int partial) {
        int n = flowers.length;
        if (n == 1) {
            if (flowers[0] >= target)
                return full;
            int minus = target - flowers[0];
            if (off >= minus) {
                return Math.max(1L * partial * (target - 1), full);
            } else {
                return 1L * partial * (off + flowers[0]);
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (flowers[i] >= target) {
                flowers[i] = target;
                sum ++;
            }
        }
        Arrays.sort(flowers);
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int t = flowers[i];
            flowers[i] = flowers[j];
            flowers[j] = t;
        }
        // System.out.println(Arrays.toString(flowers));
        long[] s = new long[n + 1];
        for (int i = 1; i <= n; i++)
            s[i] = s[i - 1] + flowers[i - 1];
        long max = 0;
        for (int len = sum; len <= n; len++) {
            long minus = 1L * target * len - s[len];
            if (minus > off) break;
            minus = off - minus;
            // long need = 1L * (target - 1) * (n - len) - (s[n] - s[len]);
            int l = flowers[n - 1], r = target - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                long need = 0;
                int ll = len, rr = n - 1;
                while (ll < rr) {
                    int mm = ll + rr >> 1;
                    if (flowers[mm] >= mid)
                        ll = mm + 1;
                    else
                        rr = mm;
                }
                if (ll < n && flowers[ll] >= mid)
                    ll++;
                if (ll < n) {
                    int c = n - ll;
                    need = 1L * mid * c - (s[n] - s[n - c]);
                }
                if (need <= minus)
                    l = mid;
                else
                    r = mid - 1;
            }
            if (len == n)
                max = Math.max(max, 1L * len * full);
            else
                max = Math.max(max, 1L * len * full + 1L * partial * l);
        }
        return max;
    }
}