标签： medium

目标

现有一份 n + m 次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。

给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。

返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。

k 个数字的 平均值 为这些数字求和后再除以 k 。

注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。

示例 1：

输入：rolls = [3,2,4,3], mean = 4, n = 2
输出：[6,6]
解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。

示例 2：

输入：rolls = [1,5,6], mean = 3, n = 4
输出：[2,3,2,2]
解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。

示例 3：

输入：rolls = [1,2,3,4], mean = 6, n = 4
输出：[]
解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。

示例 4：

输入：rolls = [1], mean = 3, n = 1
输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。

说明：

• m == rolls.length
• 1 <= n, m <= 10^5
• 1 <= rolls[i], mean <= 6

思路

已知 m+n 个投骰子的观测数据的均值 mean，以及其中 m 个观察数据 rolls，返回缺失的观测数据，如果存在多个只返回其中一组，如果不存在答案返回空数组。

我们可以很容易计算出观测数据的总和 mean * (m + n)，用它减去已知的观测数据和 sum，得到 diff。

• 如果 diff > n * 6 说明 剩余的 n 次都得到 6 点也不够，返回空数组。
• 如果 diff < n 说明 剩余的 n 次都得到 1 点也多余，返回空数组。
• 否则，问题变成选 n 个数字使其和等于 diff，每个数的取值范围是 1 ~ 6。

这让我想起了背包问题还有之前做过的硬币找零，组合总和等问题。这里只需要返回一种可能就行了，不需要动态规划。

可以先计算 val = diff / n，如果有剩余 r，就为 r 个值加1。

代码

/**
 * @date 2024-05-27 9:20
 */
public class MissingRolls2028 {

    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        int sum = 0;
        for (int roll : rolls) {
            sum += roll;
        }
        int diff = mean * (m + n) - sum;
        if (diff > n * 6 || diff < n) {
            return new int[0];
        }
        int[] res = new int[n];
        int val = diff / n;
        diff = diff - val * n;
        Arrays.fill(res, val);
        for (int i = 0; i < diff; i++) {
            res[i]++;
        }
        return res;
    }
}

性能

目标

给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。

返回一个长度为 2 的列表 answer ：

• answer[0] 是所有 没有 输掉任何比赛的玩家列表。
• answer[1] 是所有恰好输掉 一场 比赛的玩家列表。

两个列表中的值都应该按 递增 顺序返回。

注意：

• 只考虑那些参与 至少一场 比赛的玩家。
• 生成的测试用例保证 不存在 两场比赛结果 相同 。

示例 1：

输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
输出：[[1,2,10],[4,5,7,8]]
解释：
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。

示例 2：

输入：matches = [[2,3],[1,3],[5,4],[6,4]]
输出：[[1,2,5,6],[]]
解释：
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。

说明：

• 1 <= matches.length <= 10^5
• matches[i].length == 2
• 1 <= winneri, loseri <= 10^5
• winneri != loseri
• 所有 matches[i] 互不相同

思路

给定一个记录比赛结果的二维数组，数组元素为[winneri, loseri]，求没有输掉任何比赛的玩家以及仅输掉一场比赛的玩家。

简单实现可以直接利用TreeSet保存返回结果，往里面放的时候先判断是否输掉过比赛，如果后面输掉了比赛还要将其从从没输掉比赛的集合中移除。

对于仅输掉一次比赛的集合，不能根据它来判断是否输掉过比赛，因为输掉两次会从集合中移除，如何后续还会输掉比赛，判断集合中没有，就会错误地向其中添加，因此需要额外记录输掉过比赛的集合。

官网题解使用的是哈希表记录失败的次数，效率更高。

代码

/**
 * @date 2024-05-22 9:03
 */
public class FindWinners2225 {

    public List<List<Integer>> findWinners(int[][] matches) {
        List<List<Integer>> res = new ArrayList<>();
        Set<Integer> neverLose = new TreeSet<>();
        Set<Integer> loseOnce = new TreeSet<>();
        Set<Integer> lost = new HashSet<>();
        for (int[] match : matches) {
            int win = match[0];
            int lose = match[1];
            neverLose.remove(lose);
            if (!lost.contains(win)) {
                neverLose.add(win);
            }
            if (!loseOnce.contains(lose) && !lost.contains(lose)) {
                loseOnce.add(lose);
            } else {
                loseOnce.remove(lose);
            }
            lost.add(lose);
        }
        List<Integer> winner = new ArrayList<>(neverLose);
        List<Integer> loser = new ArrayList<>(loseOnce);
        res.add(winner);
        res.add(loser);
        return res;
    }

    public List<List<Integer>> findWinners_v1(int[][] matches) {
        Map<Integer, Integer> loseCnt = new HashMap<>(matches.length);
        for (int[] match : matches) {
            //可以直接在这里记录没有一次失败的
            loseCnt.merge(match[1], 1, Integer::sum);
        }
        List<List<Integer>> res = new ArrayList<>();
        Set<Integer> neverLose = new HashSet<>();
        for (int[] match : matches) {
            if(!loseCnt.containsKey(match[0])){
                neverLose.add(match[0]);
            }
        }
        List<Integer> winner = new ArrayList<>(neverLose);
        Collections.sort(winner);
        List<Integer> lostOnce = loseCnt.entrySet().stream()
                .filter((entry) -> entry.getValue() == 1)
                .map(Map.Entry::getKey).sorted()
                .collect(Collectors.toList());
        res.add(winner);
        res.add(lostOnce);
        return res;
    }
}

性能

暴力解

哈希加排序

目标

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

• difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
• worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

• 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

示例 1：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:

输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

说明:

• n == difficulty.length
• n == profit.length
• m == worker.length
• 1 <= n, m <= 10^4
• 1 <= difficulty[i], profit[i], worker[i] <= 10^5

思路

现在有一组任务，其难度与收益分别使用两个数组 difficulty 与 profit 表示，还有一个数组表示一组工人的能力。现在需要给工人分配工作，如果分配的工作难度大于工人的能力则无法获取收益，求把工人分配到岗后能够获得的最大收益。

我们只需为每个工人分配其能力范围内的收益最高的工作即可。需要注意的是，题目中没有说难度越高收益越高，并且相同难度的收益也会不同。

难度与收益是通过下标关联的，并且是无序的。

一个很自然的想法是维护一个难度与最大收益的映射，然后直接根据工人的能力二分查找相应的收益并累加。

那么如何同时对两个相关联的数组进行排序就是解题的关键。这里直接将 difficulty 与 profit 的映射通过 hashmap 保存起来，然后对 difficulty 从小到大排序。遍历排序后的 difficulty 数组，计算小于该难度的最大收益并更新到profit 中。根据工人的能力二分查找 profit 并累加即可。

容易出错的点是忘记处理相同难度收益不同的情况，二分查找结果为-1时表示无法完成任务任务，不应取难度最低的任务。

官网题解使用的是 javafx.util.Pair/awt包的Point/ 二维数组来保存映射关系。后面收益最高工作的计算，先对 worker 从小到大排序，使用双指针一个指向worker，一个指向难度，后面工人只需从前一个工人的难度开找即可，没用二分查找。

代码

/**
 * @date 2024-05-17 9:20
 */
public class MaxProfitAssignment826 {

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        int m = worker.length;
        Map<Integer, Integer> profitMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 存在难度相同的，取最大的
            if (profitMap.get(difficulty[i]) == null) {
                profitMap.put(difficulty[i], profit[i]);
            } else {
                profitMap.put(difficulty[i], Math.max(profitMap.get(difficulty[i]), profit[i]));
            }
        }
        Arrays.sort(difficulty);
        // 难度从小到大排，更新对应难度可以获得的最大收益
        profit[0] = profitMap.get(difficulty[0]);
        for (int i = 1; i < n; i++) {
            profit[i] = Math.max(profit[i - 1], profitMap.get(difficulty[i]));
        }
        for (int i = 0; i < m; i++) {
            int index = Arrays.binarySearch(difficulty, worker[i]);
            if (index >= 0) {
                res += profit[index];
            } else {
                index = -index - 2;
                if (index >= 0) {
                    // 说明没有能力完成
                    res += profit[index];
                }
            }
        }
        return res;
    }

    // 参考官网题解的答案
    public static class Point{
        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int maxProfitAssignment_v1(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        Point[] jobs = new Point[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Point(difficulty[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> a.x - b.x);
        // 根据工人技能排序
        // 越往后能力越高，可以直接接着上一次难度位置向后遍历
        Arrays.sort(worker);
        int index = 0;
        int best = 0;
        for (int capability : worker) {
            while (index < n && capability >= jobs[index].x) {
                best = Math.max(best, jobs[index++].y);
            }
            res += best;
        }
        return res;
    }
}

性能

最后计算最大收益时在循环中使用二分查找，时间复杂度为O(mlogn)，而使用双指针 difficulty 最多遍历一遍，时间复杂度是O(m + n)应该更快一点。另外使用hashMap效率不高，因为需要计算hashcode，不如直接访问。

改进后

目标

给你 n 个项目，编号从 0 到 n - 1 。同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。

你可以按下面两个规则参与项目中的工作：

• 每周，你将会完成 某一个 项目中的 恰好一个 阶段任务。你每周都 必须 工作。
• 在 连续的 两周中，你 不能 参与并完成同一个项目中的两个阶段任务。

一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将 停止工作 。注意，由于这些条件的限制，你可能无法完成所有阶段任务。

返回在不违反上面规则的情况下你 最多 能工作多少周。

示例 1：

输入：milestones = [1,2,3]
输出：6
解释：一种可能的情形是：
​​​​- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 2 中的一个阶段任务。
- 第 3 周，你参与并完成项目 1 中的一个阶段任务。
- 第 4 周，你参与并完成项目 2 中的一个阶段任务。
- 第 5 周，你参与并完成项目 1 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
总周数是 6 。

示例 2：

输入：milestones = [5,2,1]
输出：7
解释：一种可能的情形是：
- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 1 中的一个阶段任务。
- 第 3 周，你参与并完成项目 0 中的一个阶段任务。
- 第 4 周，你参与并完成项目 1 中的一个阶段任务。
- 第 5 周，你参与并完成项目 0 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
- 第 7 周，你参与并完成项目 0 中的一个阶段任务。
总周数是 7 。
注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。
因此，项目 0 中会有一个阶段任务维持未完成状态。

说明：

• n == milestones.length
• 1 <= n <= 10^5
• 1 <= milestones[i] <= 10^9

思路

给定一个数组，其元素值表示项目的任务数，每一周可以完成任一项目的一个任务，不能连续两周完成同一项目的任务，即每完成一个任务必须切换项目，问最多能完成多少任务。

观察上面的示例发现不能优先选择任务数少的项目，因为任务少的项目先完成后，任务多的项目可能由于没有项目切换被剩下。

刚开始的想法就是先从小到大排序，将个项目的任务数放入优先队列，然后每次从最大与次最大的项目中选取任务，提交之后提示超时。

然后想到没必要一次只减1，于是就直接从最大中减去次最大 next，然后累加 2 * next，提交之后发现对于max == next 时会给出错误答案，于是就记录最大值相同的个数 times，后面累加next * (times + 1) 即可。提交之后发现下面的案例给出的答案不对：

正确的处理过程可以是每次取最大与次最大：

task1：8	task2：6	task3：4	cost
7	5(end)	4	2
6	4(end)	4	2
5	3(end)	4	2
4	3	3(end)	2
3	2(end)	3	2
2	2	2(end)	2
1	1	1(end)	3
0	0	0(end)	3
-	-	-	合计：18

而提交的算法是这样处理的，违背了上面的处理原则。

task1：8	task2：6	task3：4	cost
2	0(end)	4	12
0(end)	0	2	4
0	0	1	1
-	-	-	合计：17

如果考虑第三大元素 third，一次性只减到 third，累加 2 * (next - third) 的话，后续还是要一个一个算。

task1：8	task2：6	task3：4	cost
6	4(end)	4	2
5	3(end)	4	2
4	3	3(end)	2
3	2(end)	3	2
2	2	2(end)	2
1	1	1(end)	3
0	0	0(end)	3
-	-	-	合计：18

然后还发现对于某些例子是能够计算出正确结果的，例如

task1：5	task2：2	task3：1	cost
3	0(end)	1	4
2	0	0(end)	2
1(end)	0	0	1
-	-	-	合计：7

于是发现，只要除了最大值其余元素和只要大于等于最大值就可以全部完成。

贪心算法难想，难证明，大多凭直觉，没有通用性。我没有想到这个结论竟然可以推广到多个元素的情况。感觉有点像脑筋急转弯，想通了就很简单。

考虑下面的例子：

最大值每减1，后面的元素都可以同步的减1。

8 8 8 8 8
7 7 7 7 7
......
0 0 0 0 0 
----------------

这个就不能同步减了，否则最大值消不完

8 4 3 2 1
7 3 3 2 1
6 2 3 2 1
5 2 2 2 1
4 1 2 2 1
3 1 1 2 1
2 1 1 1 1
1 1 1 1 0
0 0 0 0 0

可以想象成两个柱子，最大的是一个柱子，其余的垒成一个柱子，如果大于最大的柱子就截断，作为新的柱子如果还大接着截，不能超过最大的柱子。极端的情况就是全相同，可以全部完成。只要保证有一个柱子与最大的柱子一样高就可以来回切换来完成全部任务。而如果其余的柱子垒起来没有最大的高，那么只能完成 其余之和*2+1

代码

package medium;

/**
 * @date 2024-05-16 8:37
 */
public class NumberOfWeeks1953 {

    /**
     * 执行通过
     * 如果最大的小于等于其余之和，那么所有任务均可完成
     * 如果最大的大于其余之和，那么可以完成其余之和*2+1
     */
    public long numberOfWeeks_v2(int[] milestones) {
        long sum = 0;
        int max = 0;
        for (int milestone : milestones) {
            if (milestone > max) {
                max = milestone;
            }
            sum += milestone;
        }
        long remainder = sum - max;
        return remainder < max ? remainder * 2 + 1 : sum;
    }

    /**
     * 这个算法是调试出来的
     */
    public long numberOfWeeks_v1(int[] milestones) {
        long res = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        for (int milestone : milestones) {
            q.offer(milestone);
        }
        while (!q.isEmpty()) {
            int head = q.poll();
            // 输入数组中的值均大于0，res放在这里加，以免漏掉最后一个
            res++;
            if (q.isEmpty()) {
                // 如果后面没有任务，连续两周完成同一项目的任务会违反规则，直接返回
                return res;
            }
            int next = q.poll();
            int times = 1;
            while (!q.isEmpty() && next == head) {
                times++;
                next = q.poll();
            }
            if (q.size() == 1 && q.peek() + next > head) {
                // 处理最后三个，如果其余两个大于最大值就返回它们的和，减1是因为为了防止漏掉最后一个加了1
                return res + head * times + next + q.poll() - 1;
            }
            res += (long) next * (times + 1) - 1;
            head -= next;
            if (head > 0) {
                for (int i = 0; i < times; i++) {
                    q.offer(head);
                }
            }
        }
        return res;
    }

性能

方法一

方法二