月度归档： 2024 年 6 月

目标

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

说明：

• 1 <= people.length <= 5 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4

思路

给定一个数组，数组元素是待救援人员的体重，每条救生艇最多载两人且体重不超过限制，问最少需要多少救生艇。

尽可能多地让两人乘一艇，将体重轻的与重的搭配，如果都是轻的则造成运力浪费。

因此先按体重从小到大排序，然后使用双指针将重的与轻的搭配即可。

代码

/**
 * @date 2024-06-10 21:18
 */
public class NumRescueBoats881 {

    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        Arrays.sort(people);
        int end = Arrays.binarySearch(people, limit);
        if (end < 0) {
            end = -end - 1;
        }
        // [end,n) 下标小于end的元素均比limit小，end 为0则可直接返回n
        int res = n - end;
        int start = 0;
        while (start < end) {
            // 如果start == end -1 即仅剩start一个元素 不再重复累加
            // start < end 防止end - 1为负即end==0
            // 由于取开区间，不包括end，因此从end-1开始
            while (start < end - 1 && people[start] + people[end - 1] > limit) {
                end--;
                res++;
            }
            start++;
            end--;
            res++;
        }
        return res;
    }
}

性能

目标

桌子上有 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;
    }
}

性能