月度归档： 2024 年 5 月

2391.收集垃圾的最少总时间

目标

给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 'M' ，'P' 和 'G' ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。

同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。

城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。

任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。

请你返回收拾完所有垃圾需要花费的 最少 总分钟数。

示例 1：

输入：garbage = ["G","P","GP","GG"], travel = [2,4,3]
输出：21
解释：
收拾纸的垃圾车：
1. 从房子 0 行驶到房子 1
2. 收拾房子 1 的纸垃圾
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
1. 收拾房子 0 的玻璃垃圾
2. 从房子 0 行驶到房子 1
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的玻璃垃圾
5. 从房子 2 行驶到房子 3
6. 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。

示例 2：

输入：garbage = ["MMM","PGM","GP"], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。

说明：

  • 2 <= garbage.length <= 10^5
  • garbage[i] 只包含字母 'M' ，'P' 和 'G' 。
  • 1 <= garbage[i].length <= 10
  • travel.length == garbage.length - 1
  • 1 <= travel[i] <= 100

思路

暴力解法，计算每个房子的垃圾数以及回收各种垃圾需要到达的最远距离。

官网题解给出了一次遍历的解法。没时间看了。// todo

代码

/**
 * @date 2024-05-11 8:37
 */
public class GarbageCollection2391 {

    public int garbageCollection(String[] garbage, int[] travel) {
        int res = 0;
        int n = garbage.length;
        int[] m = new int[n];
        int[] p = new int[n];
        int[] g = new int[n];
        int[] t = new int[n-1];
        t[0] = travel[0];
        for (int i = 1; i < travel.length; i++) {
            t[i] = t[i - 1] + travel[i];
        }
        for (char c : garbage[0].toCharArray()) {
            if (c == 'M') {
                m[0]++;
            } else if (c == 'P') {
                p[0]++;
            } else if (c == 'G') {
                g[0]++;
            }
        }
        int mEnd = 0;
        int pEnd = 0;
        int gEnd = 0;
        for (int i = 1; i < n; i++) {
            char[] chars = garbage[i].toCharArray();
            for (char c : chars) {
                if (c == 'M') {
                    m[i]++;
                } else if (c == 'P') {
                    p[i]++;
                } else if (c == 'G') {
                    g[i]++;
                }
            }
            m[i] += m[i - 1];
            p[i] += p[i - 1];
            g[i] += g[i - 1];
            if (m[i] != m[i - 1]) {
                mEnd = i;
            }
            if (p[i] != p[i - 1]) {
                pEnd = i;
            }
            if (g[i] != g[i - 1]) {
                gEnd = i;
            }
        }
        res += m[mEnd] + p[pEnd] + g[gEnd];
        if (mEnd > 0) {
            res += t[mEnd - 1];
        }
        if (pEnd > 0) {
            res += t[pEnd - 1];
        }
        if (gEnd > 0) {
            res += t[gEnd - 1];
        }

        return res;
    }

}

性能

2960.统计已测试设备

目标

给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。

你的任务是按照顺序测试每个设备 i，执行以下测试操作：

  • 如果 batteryPercentages[i] 大于 0：
    • 增加 已测试设备的计数。
    • 将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
    • 移动到下一个设备。
  • 否则，移动到下一个设备而不执行任何测试。

返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。

示例 1：

输入：batteryPercentages = [1,1,2,1,3]
输出：3
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [1,0,1,0,2] 。
在设备 1 上，batteryPercentages[1] == 0 ，移动到下一个设备而不进行测试。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 变为 [1,0,1,0,1] 。
在设备 3 上，batteryPercentages[3] == 0 ，移动到下一个设备而不进行测试。
在设备 4 上，batteryPercentages[4] > 0 ，现在有 3 个已测试设备，batteryPercentages 保持不变。
因此，答案是 3 。

示例 2：

输入：batteryPercentages = [0,1,2]
输出：2
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] == 0 ，移动到下一个设备而不进行测试。
在设备 1 上，batteryPercentages[1] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [0,1,1] 。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 保持不变。
因此，答案是 2 。

说明：

  • 1 <= n == batteryPercentages.length <= 100
  • 0 <= batteryPercentages[i] <= 100

思路

如果设备的剩余电量大于0，已测试设备加1且后续设备的所有电量减1。

简而言之，后续设备需要减去的电量为已检测的设备数。

题解上说这是差分的思想。我们没必要检测一个设备就向后循环并将电量减1，当前设备需要减去的电量等于上一个设备需要减去的电量+1。

代码

/**
 * @date 2024-05-10 8:43
 */
public class CountTestedDevices2960 {
    public int countTestedDevices(int[] batteryPercentages) {
        int res = 0;
        for (int i = 0; i < batteryPercentages.length; i++) {
            if (batteryPercentages[i] > res) {
                res++;
            }
        }
        return res;
    }
}

性能

2105.给植物浇水II

目标

Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。

每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：

  • Alice 按 从左到右 的顺序给植物浇水，从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水，从植物 n - 1 开始。他们 同时 给植物浇水。
  • 如果没有足够的水 完全 浇灌下一株植物，他 / 她会立即重新灌满浇水罐。
  • 不管植物需要多少水，浇水所耗费的时间都是一样的。
  • 不能 提前重新灌满水罐。
  • 每株植物都可以由 Alice 或者 Bob 来浇水。
  • 如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水更多的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。

给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。

示例 1：

输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5
输出：1
解释：
- 最初，Alice 和 Bob 的水罐中各有 5 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。
- Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。

示例 2：

输入：plants = [2,2,3,3], capacityA = 3, capacityB = 4
输出：2
解释：
- 最初，Alice 的水罐中有 3 单元水，Bob 的水罐中有 4 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在都只有 1 单元水，并分别需要给植物 1 和植物 2 浇水。
- 由于他们的水量均不足以浇水，所以他们重新灌满水罐再进行浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 1 + 1 + 0 = 2 。

示例 3：

输入：plants = [5], capacityA = 10, capacityB = 8
输出：0
解释：
- 只有一株植物
- Alice 的水罐有 10 单元水，Bob 的水罐有 8 单元水。因此 Alice 的水罐中水更多，她会给这株植物浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 。

说明：

  • n == plants.length
  • 1 <= n <= 10^5
  • 1 <= plants[i] <= 10^6
  • max(plants[i]) <= capacityA, capacityB <= 10^9

思路

两个人同时从左右两边开始浇水，如果水不够可以立即装满，浇水耗时都相同，如果同时到达相同的植物则剩余水多的浇，问总重新灌水的次数。

由于不计算装水时间，浇水耗时又相同，两人同时从左右开始浇水，同时到达同一植物只有在总植物数量为奇数时才会发生。

先计算二人各自需要重新灌水的次数然后再考虑是否存在同时到达以及是否需要重新灌水即可。

需要注意，无论n的奇偶性， for (int i = 0; i < (n >> 1); i++) {} 与 for (int i = n - 1; i > (n - 1 >> 1); i--) {} 都不会访问到中间节点。

代码

/**
 * @date 2024-05-09 8:40
 */
public class MinimumRefill2105 {
    public int minimumRefill(int[] plants, int capacityA, int capacityB) {
        int n = plants.length;
        int remainderA = capacityA;
        int remainderB = capacityB;
        int res = 0;
        for (int i = 0; i < (n >> 1); i++) {
            if (remainderA < plants[i]) {
                remainderA = capacityA - plants[i];
                res++;
            } else {
                remainderA -= plants[i];
            }
        }
        for (int i = n - 1; i > (n - 1 >> 1); i--) {
            if (remainderB < plants[i]) {
                remainderB = capacityB - plants[i];
                res++;
            } else {
                remainderB -= plants[i];
            }
        }
        if (n % 2 == 1) {
            int remainder = Math.max(remainderA, remainderB);
            if (remainder < plants[n >> 1]) {
                res++;
            }
        }

        return res;
    }
}

性能

2079.给植物浇水

目标

你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。x = -1 处有一条河，你可以在那里重新灌满你的水罐。

每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：

  • 按从左到右的顺序给植物浇水。
  • 在给当前植物浇完水之后，如果你没有足够的水 完全 浇灌下一株植物，那么你就需要返回河边重新装满水罐。
  • 你 不能 提前重新灌满水罐。

最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位 都需要 一步 。

给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的 步数 。

示例 1：

输入：plants = [2,2,3,3], capacity = 5
输出：14
解释：从河边开始，此时水罐是装满的：
- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。
- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。
- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。
- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。
- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。
需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。

示例 2：

输入：plants = [1,1,1,4,2,3], capacity = 4
输出：30
解释：从河边开始，此时水罐是装满的：
- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。
- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。
- 走到植物 5 (6 步) ，浇水。
需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。

示例 3：

输入：plants = [7,7,7,7,7,7,7], capacity = 8
输出：49
解释：每次浇水都需要重新灌满水罐。
需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。

说明：

  • n == plants.length
  • 1 <= n <= 1000
  • 1 <= plants[i] <= 10^6
  • max(plants[i]) <= capacity <= 10^9

思路

简单的动态规划。

代码

/**
 * @date 2024-05-08 0:01
 */
public class WateringPlants2079 {
    public int wateringPlants(int[] plants, int capacity) {
        int n = plants.length;
        int[] dp = new int[n];
        int remainder = capacity - plants[0];
        dp[0] = 1;
        for (int i = 1; i < plants.length; i++) {
            if (remainder >= plants[i]) {
                remainder -= plants[i];
                dp[i] = dp[i - 1] + 1;
            } else {
                remainder = capacity - plants[i];
                dp[i] = dp[i - 1] + (i << 1) + 1;
            }
        }
        return dp[n - 1];
    }
}

性能

857.雇佣K名工人的最低成本

目标

有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：

  1. 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
  2. 工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10^-5 以内的答案将被接受。

示例 1：

输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。

示例 2：

输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。

说明：

  • n == quality.length == wage.length
  • 1 <= k <= n <= 10^4
  • 1 <= quality[i], wage[i] <= 10^4

思路

从quality中选k个，按照工作质量比例支付工资，并且每人的工资不能低于wage中的最低期望工资，问雇佣这k个人的最低成本是多少。

// todo

代码

/**
 * @date 2024-05-02 20:44
 */
public class MincostToHireWorkers857 {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = wage.length;
        PriorityQueue<double[]> wqq = new PriorityQueue<>(Comparator.comparingDouble(x -> x[0]));
        double[][] wq = new double[n][2];
        for (int i = 0; i < wage.length; i++) {
            wq[i][0] = (double) wage[i] / quality[i];
            wq[i][1] = i;
            wqq.offer(wq[i]);
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((x, y) -> y - x);
        int sum = 0;
        int ri = 0;
        for (int i = 0; i < k; i++) {
            double[] choose = wqq.poll();
            int index = (int) choose[1];
            sum += quality[index];
            q.offer(quality[index]);
            ri = (int) choose[1];
        }
        double res = (double) sum * wage[ri] / quality[ri];
        while (!wqq.isEmpty()) {
            double[] choose = wqq.poll();
            int index = (int) choose[1];
            if (q.peek() > quality[index]) {
                sum = sum - q.peek() + quality[index];
                double resTmp = (double)sum * wage[index] / quality[index];
                q.poll();
                q.offer(quality[index]);
                if (res > resTmp) {
                    res = resTmp;
                }
            }
        }
        return res;
    }
}

性能