标签： medium

目标

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

示例 1：

输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。

示例 2：

输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2 。

示例 3：

输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧。

说明：

• 1 <= n == s.length <= 10^5
• s[i] 不是 '0'，就是 '1'

思路

有一个数组，其元素值不是0就是1，现在需要将所有的1都移到右边，每一步可以选择相邻的两个元素交换其位置，问移动的最小步数。

从左向右遍历数组元素，如果值为1就累加cnt，如果值为0就将移动步数加上 cnt。简单来说就是遇到1就合并，记录其个数，遇到0就整体移动 res += cnt。每次移动都贪心地将0移至其最终位置上。

有网友提到可以使用归并排序记录逆序对。

还有网友是基于下标和计算的。因为最终0都在右边，其下标和可以通过等差数列求和得到。我们只需在遍历过程中记录0的个数，并累加0的下标，然后与最终状态的下标和相减即可。

代码

package medium;

/**
 * @date 2024-06-06 0:03
 */
public class MinimumSteps2938 {

    /**
     * 将黑球视为一个整体，遇到黑球则合并到一起增加其权重，这样就可以视为将一个带权黑球从左移到右，每一步都是必要的。
     * 这其实也算是在移动的过程中统计逆序对的个数
     */
    public long minimumSteps(String s) {
        long res = 0;
        int n = s.length();
        int i = 0;
        long cnt = 0;
        while (i < n) {
            if (s.charAt(i) == '0') {
                // 遇到0就移动  累加移动步数，可以使用双指针优化
                res += cnt;
            } else {
                // 遇到1则合并
                cnt++;
            }
            i++;
        }
        return res;
    }

    /**
     * 优化
     * 使用双指针可以减少累加次数
     */
    public long minimumSteps_v1(String s) {
        long res = 0;
        int n = s.length();
        int i = 0;
        // left指向1的位置，如果第一值是0，那么left与i一起右移
        // 如果第一个值是1，仅移动i，当遇到0时，左侧1的个数就是i-left
        // 本来从下标left到i元素个数为 i - left + 1，由于i指向的不是1，所以不用加1
        int left = 0;
        while (i < n) {
            if (s.charAt(i) == '0') {
                res += i - left;
                left++;
            }
            i++;
        }
        return res;
    }
}

性能

目标

现有一份 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;
    }
}

性能

暴力解

哈希加排序