495.提莫攻击

LeetCode LeetCode 数组 模拟
发布时间 :
字数:2.9k 阅读 : 评论:
  1. 495.提莫攻击
    1. 495.1 题目
    2. 495.2 题解
      1. 方法一：遍历计算中毒总秒数
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：使用 LINQ 求和计算中毒总秒数
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 495.3 代码
    4. 495.4 运行结果

495.提莫攻击

495.1 题目

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个非递减的整数数组 timeSeries，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration。

返回艾希处于中毒状态的总秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：

  • 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
  • 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
    艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：

  • 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
  • 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
    艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3。

提示：

  • 1 <= timeSeries.length <= 10^4
  • 0 <= timeSeries[i], duration <= 10^7
  • timeSeries 按非递减顺序排列

495.2 题解

方法一：遍历计算中毒总秒数

思路

遍历攻击时间序列，计算相邻两次攻击的时间间隔。如果间隔小于中毒持续时间，则累加间隔值；否则累加完整的持续时间。最后一次攻击总是累加完整的持续时间。

核心思想：累加每次攻击的中毒时间，注意重叠部分只算一次。

具体步骤：

  1. 如果攻击序列为空或持续时间为0，返回0。
  2. 遍历攻击序列（除最后一次）：
    • 计算与下一次攻击的时间间隔
    • 累加 min(间隔, duration)
  3. 最后一次攻击累加完整的 duration。

举例：对于 timeSeries = [1,4], duration = 2：

  • 攻击1：间隔 4-1=3 > 2，累加 2
  • 攻击2：最后一次，累加 2
  • 结果：4

复杂度分析

  • 时间复杂度：O(n)，遍历一次数组。
  • 空间复杂度：O(1)，只使用常数额外空间。

代码

// 方法一：遍历计算中毒总秒数
// 遍历计算当前攻击时间与上一次攻击时间的时间间隔，将当前攻击的中毒持续时间与duration中的较小值累加到总中毒秒数
static int TotalPoisonDuration1(int[] timeSeries, int duration)
{
    // 如果提供的数组为空或中毒持续时间为0，直接返回中毒总秒数为0
    if (timeSeries.Length == 0 || duration == 0) return 0;

    // 初始化中毒总秒数
    int totalPoisonDuration = 0;

    // 遍历提莫攻击时间序列，从第二次攻击开始计算中毒总秒数
    for (int i = 1; i < timeSeries.Length; i++)
    {
        // 计算当前攻击时间与上一次攻击时间的时间间隔
        int gap = timeSeries[i] - timeSeries[i - 1];

        // 将当前攻击的中毒持续时间与duration中的较小值累加到总中毒秒数
        totalPoisonDuration += Math.Min(gap, duration);
    }

    // 加上最后一次攻击的中毒时间，因为最后一次攻击后并没有计算中毒持续时间
    totalPoisonDuration += duration;

    // 返回计算得到的总中毒秒数
    return totalPoisonDuration;
}

方法二：使用 LINQ 求和计算中毒总秒数

思路

使用 Zip 方法将相邻的攻击时间配对，对每对相邻时间计算间隔与 duration 的较小值，用 Sum 方法求和，最后加上最后一次攻击的 duration。

函数式编程风格，代码简洁。

举个例子：timeSeries = [1,4], duration = 2

  • 相邻间隔：4 - 1 = 3，第一次中毒覆盖 [1,2]，第二次在 4 开始，两段不重叠
  • 循环里累加 min(3, 2) = 2（表示「到下一次攻击前」这一段里新贡献的中毒秒数，与 duration 取小避免把间隔全算满）
  • 再加上最后一次攻击的 duration：2 + 2 = 4 秒

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

// 方法二：使用 LINQ 求和计算中毒总秒数
// Zip 方法：
// 用途： 将两个序列的元素配对成一个元素对的单一序列。
// 参数：
// timeSeries：原始攻击时间序列。
// timeSeries.Skip(1)：跳过 timeSeries 的第一个元素，创建一个从第二个元素开始的新序列。
// (prev, curr) => CalculateInterval(prev, curr, duration)：一个 lambda 表达式，指定如何组合两个序列的元素。它调用 CalculateInterval 方法，并将两个序列的先前和当前元素作为参数。
// 返回值： 返回应用指定 lambda 表达式到输入序列的对应元素的结果序列。
// Skip 方法：
// 用途： 跳过序列中指定数量的元素，并返回剩余的元素。
// 参数：
// 1：要跳过的元素数量（在这里，跳过第一个元素）。
// 返回值： 返回一个新序列，该序列从跳过指定数量的元素后开始。
// Sum 方法：
// 用途： 计算序列中所有元素的和。
// 参数： 无。
// 返回值： 返回序列中所有元素的和。
static int TotalPoisonDuration2(int[] timeSeries, int duration)
{
    // 使用 Zip 方法将相邻的攻击时间对应起来，然后计算相邻攻击的时间间隔中的最小值
    var intervals = timeSeries.Zip(timeSeries.Skip(1), (prev, curr) => CalculateInterval(prev, curr, duration));

    // 对这些最小值进行求和，再加上中毒持续时间，得到总中毒秒数
    return intervals.Sum() + duration;
}

// 具名函数，计算相邻攻击的时间间隔中的最小值
static int CalculateInterval(int prev, int curr, int duration)
{
    return Math.Min(curr - prev, duration);
}

495.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

        // 当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

        // 正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。
        // 如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。

        // 给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，
        // 以及一个表示中毒持续时间的整数 duration 。

        // 返回艾希处于中毒状态的 总 秒数。

        // 示例 1：
        // 输入：timeSeries = [1,4], duration = 2
        // 输出：4
        // 解释：提莫攻击对艾希的影响如下：
        // - 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
        // - 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
        // 艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

        // 示例 2：
        // 输入：timeSeries = [1,2], duration = 2
        // 输出：3
        // 解释：提莫攻击对艾希的影响如下：
        // - 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
        // - 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
        // 艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

        // 提示：
        // 1 <= timeSeries.length <= 104
        // 0 <= timeSeries[i], duration <= 107
        // timeSeries 按 非递减 顺序排列

        #endregion

        #region 测试

        // 示例 1
        int[] timeSeries1 = { 1, 4 };
        int duration1 = 2;
        int result1_1 = TotalPoisonDuration1(timeSeries1, duration1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = TotalPoisonDuration2(timeSeries1, duration1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] timeSeries2 = { 1, 2 };
        int duration2 = 2;
        int result2_1 = TotalPoisonDuration1(timeSeries2, duration2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = TotalPoisonDuration2(timeSeries2, duration2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：遍历计算中毒总秒数
    // 遍历计算当前攻击时间与上一次攻击时间的时间间隔，将当前攻击的中毒持续时间与duration中的较小值累加到总中毒秒数
    static int TotalPoisonDuration1(int[] timeSeries, int duration)
    {
        // 如果提供的数组为空或中毒持续时间为0，直接返回中毒总秒数为0
        if (timeSeries.Length == 0 || duration == 0) return 0;

        // 初始化中毒总秒数
        int totalPoisonDuration = 0;

        // 遍历提莫攻击时间序列，从第二次攻击开始计算中毒总秒数
        for (int i = 1; i < timeSeries.Length; i++)
        {
            // 计算当前攻击时间与上一次攻击时间的时间间隔
            int gap = timeSeries[i] - timeSeries[i - 1];

            // 将当前攻击的中毒持续时间与duration中的较小值累加到总中毒秒数
            totalPoisonDuration += Math.Min(gap, duration);
        }

        // 加上最后一次攻击的中毒时间，因为最后一次攻击后并没有计算中毒持续时间
        totalPoisonDuration += duration;

        // 返回计算得到的总中毒秒数
        return totalPoisonDuration;
    }

    // 方法二：使用 LINQ 求和计算中毒总秒数
    // Zip 方法：
    // 用途： 将两个序列的元素配对成一个元素对的单一序列。
    // 参数：
    // timeSeries：原始攻击时间序列。
    // timeSeries.Skip(1)：跳过 timeSeries 的第一个元素，创建一个从第二个元素开始的新序列。
    // (prev, curr) => CalculateInterval(prev, curr, duration)：一个 lambda 表达式，指定如何组合两个序列的元素。它调用 CalculateInterval 方法，并将两个序列的先前和当前元素作为参数。
    // 返回值： 返回应用指定 lambda 表达式到输入序列的对应元素的结果序列。
    // Skip 方法：
    // 用途： 跳过序列中指定数量的元素，并返回剩余的元素。
    // 参数：
    // 1：要跳过的元素数量（在这里，跳过第一个元素）。
    // 返回值： 返回一个新序列，该序列从跳过指定数量的元素后开始。
    // Sum 方法：
    // 用途： 计算序列中所有元素的和。
    // 参数： 无。
    // 返回值： 返回序列中所有元素的和。
    static int TotalPoisonDuration2(int[] timeSeries, int duration)
    {
        // 使用 Zip 方法将相邻的攻击时间对应起来，然后计算相邻攻击的时间间隔中的最小值
        var intervals = timeSeries.Zip(timeSeries.Skip(1), (prev, curr) => CalculateInterval(prev, curr, duration));

        // 对这些最小值进行求和，再加上中毒持续时间，得到总中毒秒数
        return intervals.Sum() + duration;
    }

    // 具名函数，计算相邻攻击的时间间隔中的最小值
    static int CalculateInterval(int prev, int curr, int duration)
    {
        return Math.Min(curr - prev, duration);
    }

    #endregion
}

495.4 运行结果

示例1 方法1 输出：4
示例1 方法2 输出：4
示例2 方法1 输出：3
示例2 方法2 输出：3
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏