Typescript 编程编年史：拥有最多糖果的孩子

php中文网 2024-10-15 11:12:42

问题陈述：

有 n 个拿着糖果的孩子。给你一个整数数组 candies，其中每个 candies[i] 代表第 i 个孩子拥有的糖果数量，以及一个整数 extracandies，表示你拥有的额外糖果数量。

返回一个长度为 n 的布尔数组结果，其中，如果给第 i 个孩子所有额外的糖果后，他们将获得所有孩子中最多的糖果，则 result[i] 为 true，否则为 false。

请注意，多个孩子可以拥有最多数量的糖果。

示例1：

输入：candies = [2,3,5,1,3], extracandies = 3
输出：[真，真，真，假，真]
说明：
- 孩子1：2 + 3 = 5颗糖果，这是孩子们中最大的。
- 孩子2：3 + 3 = 6 颗糖果，这是孩子们中最大的。
- 孩子3：5 + 3 = 8 颗糖果，这是孩子们中最大的。
- 4号孩子：1 + 3 = 4颗糖果，这不是孩子们中最大的。
- 5号孩子：3 + 3 = 6颗糖果，是孩子们中最大的。

示例2：

输入：candies = [4,2,1,1,2], extracandies = 1
输出：[真，假，假，假，假]
说明：
- 孩子 1 总是拥有最多数量的糖果，即使给了另一个孩子额外的糖果。

示例3：

输入：candies = [12,1,12]，extracandies = 10
输出：[真，假，真]

限制条件：

n == candies.length
2
1
1

初步思考过程：

基本方法是：

找出任何孩子目前拥有的最大糖果数量。
迭代每个孩子，检查给他们所有额外的糖果是否会使他们的糖果总数大于或等于当前最大糖果数量。
返回一个布尔数组，其中每个元素表示该孩子是否可以拥有最大数量的糖果。

基本解决方案：

代码：

function kidswithcandiesbasic(candies: number[], extracandies: number): boolean[] {
    let maxcandies = math.max(...candies);
    let result: boolean[] = [];

    for (let i = 0; i = maxcandies) {
            result.push(true);
        } else {
            result.push(false);
        }
    }

    return result;
}

时间复杂度分析：

时间复杂度： o(n)，其中n是孩子的数量。找到最大糖果需要 o(n)，迭代糖果数组也需要 o(n)。
空间复杂度： o(n)，对于布尔值的结果数组。

限制：

考虑到限制，该解决方案是有效的。它在允许的时间和空间复杂度内工作。

优化方案：

基本解决方案在时间复杂度上已经是最优的。不过，我们可以专注于让代码更加简洁和干净。

代码：

function kidswithcandiesoptimized(candies: number[], extracandies: number): boolean[] {
    const maxcandies = math.max(...candies);
    return candies.map(candy =&gt; candy + extracandies &gt;= maxcandies);
}

时间复杂度分析：

时间复杂度： o(n)，其中n是孩子的数量。找到最大糖果需要 o(n)，通过糖果数组进行映射也需要 o(n)。
空间复杂度： o(n)，对于布尔值的结果数组。

基本解决方案的改进：

优化后的方案使用了array.prototype.map，使得代码更加简洁，可读性强。

边缘情况和测试：

边缘情况：

糖果数组有最小值和最大值。
extracandies 等于糖果最多的孩子拥有的糖果数量。
extracandies 比糖果最多的孩子拥有的糖果数量要少得多。

测试用例：

console.log(kidsWithCandiesBasic([2,3,5,1,3], 3)); // [true, true, true, false, true]
console.log(kidsWithCandiesBasic([4,2,1,1,2], 1)); // [true, false, false, false, false]
console.log(kidsWithCandiesBasic([12,1,12], 10)); // [true, false, true]

console.log(kidsWithCandiesOptimized([2,3,5,1,3], 3)); // [true, true, true, false, true]
console.log(kidsWithCandiesOptimized([4,2,1,1,2], 1)); // [true, false, false, false, false]
console.log(kidsWithCandiesOptimized([12,1,12], 10)); // [true, false, true]