This is the 27th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card for the 60th day 🎈!
🚀 Algorithm 🚀

🌲 : Timo attack

  • In the League of Legends world, there is a hero named Timo whose attacks can poison the enemy hero Ash.

  • Now, to give the time sequence of Timo’s attack on Ash and the duration of Timo’s attack, you need to output the total length of time Ash was poisoned.

  • You could argue that Timo attacked at a given point in time and immediately poisoned Ash.

Example:

Input:1.4].2Output:4Reason: the first1At the beginning of the second, Timo attacks Ash and poisons her immediately. The toxic state will remain2Seconds, up to number one2At the end of the second. The first4At the beginning of the second, Timo attacked Ash again, causing Ash to gain another2Poisoning time in seconds. So the final output4Seconds.Copy the code

Example 2:

Input:1.2].2Output:3Reason: the first1At the beginning of the second, Timo attacks Ash and poisons her immediately. The toxic state will remain2Seconds, up to number one2At the end of the second. But the first2At the beginning of the second, Timo again attacked Ash, who was already in a poisoned state. Since the poisoned state is not superimposed, Timo is at number one2The attack at the beginning of the second will be at number one3At the end of the second. So the final output3 。
Copy the code

Tip:

  • You can assume that the total length of the time series array is no more than 10,000.
  • You can assume that both the numbers in the Timo attack time series and the poison duration of the Timo attack are non-negative integers and do not exceed 10,000,000.

🌻C# method: one pass

  1. If the interval between two attacks is less than Duration, then the poisoning status is refreshed and the interval counts as poisoning event
  2. If the interval between attacks is longer than Duration, then the poisoning has ended once before, and Duration is counted as the poisoning time
  3. Duration will no longer refresh after the last attack

Code:

public class Solution {
    public int FindPoisonedDuration(int[] timeSeries, int duration)
    {
        var n = timeSeries.Length;
        if (n == 0) return 0;

        var sum = 0;
        for (var i = 1; i < n ; ++i) 
        sum += Math.Min(timeSeries[i] - timeSeries[i - 1], duration);
        returnsum + duration; }}Copy the code

The execution result

By execution time:128Ms, in all CBeat 55.56% of users in # submissionMemory consumption:48.6MB, in all C# beat 20.00% of users in submission
Copy the code

🌻Java method: traversal once

Thinking analytical

Code:

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int n = timeSeries.length;
        if (n == 0) return 0;

        int total = 0;
        for(int i = 0; i < n - 1; ++i)
          total += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
        returntotal + duration; }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits91.69% user memory consumption:40.1MB, beat out all Java commits66.64% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1) 
Copy the code

💬 summary

  • Today is the sixty day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!