统计已测试设备

难度:

标签:

题目描述

You are given a 0-indexed integer array batteryPercentages having length n, denoting the battery percentages of n 0-indexed devices.

Your task is to test each device i in order from 0 to n - 1, by performing the following test operations:

If batteryPercentages[i] is greater than 0:
- Increment the count of tested devices.
- Decrease the battery percentage of all devices with indices j in the range [i + 1, n - 1] by 1, ensuring their battery percentage never goes below 0, i.e, batteryPercentages[j] = max(0, batteryPercentages[j] - 1).
- Move to the next device.
Otherwise, move to the next device without performing any test.

Return an integer denoting the number of devices that will be tested after performing the test operations in order.

Example 1:

Input: batteryPercentages = [1,1,2,1,3]
Output: 3
Explanation: Performing the test operations in order starting from device 0:
At device 0, batteryPercentages[0] > 0, so there is now 1 tested device, and batteryPercentages becomes [1,0,1,0,2].
At device 1, batteryPercentages[1] == 0, so we move to the next device without testing.
At device 2, batteryPercentages[2] > 0, so there are now 2 tested devices, and batteryPercentages becomes [1,0,1,0,1].
At device 3, batteryPercentages[3] == 0, so we move to the next device without testing.
At device 4, batteryPercentages[4] > 0, so there are now 3 tested devices, and batteryPercentages stays the same.
So, the answer is 3.

Example 2:

Input: batteryPercentages = [0,1,2]
Output: 2
Explanation: Performing the test operations in order starting from device 0:
At device 0, batteryPercentages[0] == 0, so we move to the next device without testing.
At device 1, batteryPercentages[1] > 0, so there is now 1 tested device, and batteryPercentages becomes [0,1,1].
At device 2, batteryPercentages[2] > 0, so there are now 2 tested devices, and batteryPercentages stays the same.
So, the answer is 2.

Constraints:

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

代码结果

运行时间: 27 ms, 内存: 16.2 MB

/*
 * Problem Description:
 * Similar to the Java solution, but utilizing Java Streams for a more functional approach.
 */

import java.util.Arrays;

public class BatteryTestStream {
    public int countTestedDevices(int[] batteryPercentages) {
        int[] count = {0};
        int n = batteryPercentages.length;
        Arrays.stream(batteryPercentages).forEach(battery -> {
            if (battery > 0) {
                count[0]++;
                for (int j = count[0]; j < n; j++) {
                    batteryPercentages[j] = Math.max(0, batteryPercentages[j] - 1);
                }
            }
        });
        return count[0];
    }
}

解释

方法:

题解中使用了一个变量 `dec` 来模拟电池百分比的递减操作。对于数组中的每个元素 `x`，如果 `x` 大于 `dec`，说明设备仍有足够的电量进行测试。随后将 `dec` 增加 1，模拟对后续设备的电池百分比递减。通过这种方式，可以在一次遍历中统计能够被测试的设备数量。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么在题解中使用递增的单个变量`dec`而不是按照题目要求逐个减少后续设备的电池百分比？这种方法有什么优点？

▷

使用递增的单个变量`dec`来模拟每个设备电池百分比的递减，而不是实际修改数组中的值，主要是为了简化问题处理和提高算法效率。这种方法避免了修改原始数据，使得算法具有更好的时间复杂度（O(n)），因为仅需遍历一次数组。此外，这种方式也减少了空间复杂度，因为不需要额外的存储空间来保存修改后的电池百分比。

🦆

题解中的方法是否考虑了数组`batteryPercentages`中可能存在的负数值？如果存在负数，算法应如何处理？

▷

题解中的方法没有直接处理数组中可能存在的负数值。理论上，电池百分比不应该是负数，这可能表示输入数据异常或错误。如果要严格处理输入验证，算法应该首先检查每个元素是否非负，若发现负数则可以忽略该设备或抛出一个错误信息。

🦆

题解提到`如果x > dec`，则测试该设备。这里`>`操作符的使用是否意味着电池百分比正好等于递减值`dec`时不会测试该设备？这与题目描述相符吗？

▷

根据题解中的逻辑，如果电池百分比`x`等于递减值`dec`，则该设备不会被测试，因为条件是`x > dec`。这可能与题目的具体要求有所不符，视具体题目描述而定。如果题目要求当电池百分比大于等于递减值时设备仍可测试，那么条件应修改为`x >= dec`。

🦆

在题解的算法中，`dec`变量的递增是否正确地模拟了题目中的电池消耗逻辑，即每当一个设备被测试，其后所有设备的电量都应该减少1？

▷

是的，`dec`变量的递增正确地模拟了题目中描述的电池消耗逻辑。通过逐步增加`dec`值，算法模拟了每次测试一个设备后，所有后续设备的电池百分比相对前一个设备减少1的效果。这种模拟方式有效地反映了设备电池百分比的递减，而无需直接修改原数组。

统计已测试设备

题目描述

代码结果

解释

代码细节讲解

相关问题