Li Kou daily question - day 25 -495 Timo attack

2022.6.23 Did you brush the questions today ？

---

subject ：

stay 《 Hero alliance 》 In the world of , One called “ Timo ” The hero of . His attack can make enemy hero ash （ Editor's note ： Cold shooter ） Into a toxic state .

When Timo attacked ash , Ash's poisoning just continued duration second .

Formally speaking , Timo is here t Launching an attack means that ash is in a time interval [t, t + duration - 1]（ contain t and t + duration - 1） In a state of poisoning . If Timo is at the end of the poisoning effect front Attack again , The poisoning status timer will Reset , After a new attack , The toxic effect will be in duration Seconds later .

To give you one The decreasing Array of integers for timeSeries , among timeSeries[i] It means Timo is timeSeries[i] Attack ash in seconds , And an integer representing the duration of poisoning duration .

Return to ash's poisoned total Number of seconds .

analysis ：

This question means , Given an increasing array and a fixed value , Start with the first element of the array , Let it come from x Add in sequence as x+1,x+2,,x+ Set value , Then iterate over the second element of the array y, Also repeat y+1,y+2,,y+ Set value , And then add these numbers , How many in all , The number of repetitions is counted only once . for example

【1,3】,n=2    1+1,1+2,3+1,3+2, So that is 4

【1,3】,n=3    1+1,1+2,1+3,3+1,3+2,3+3, So that is 6

So we can save these numbers every time map in , Then count map Just a few of them （ But the operation timed out ！！！）

analysis ：

1. Hashtable

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        unordered_map<int, int>map;
        int res = 0;
        for (auto num : timeSeries)
        {
            int val = num;
            for (; num < val + duration; num++)
            {
                map[num]++;
            }
        }
        return map.size();
    }
    
};

2. Common solution

Thought is ： By comparing the difference between the two numbers before and after a given array and comparing the fixed value , Find the first number “ Valid values ”, And the last number “ Valid values ” Then it is the constant value , Finally, put these “ The valid values add up to the answer

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ans = duration;
        int res = 0;
        for (int i = 1; i < timeSeries.size(); i++)
        {
            res = min(timeSeries[i] - timeSeries[i - 1], duration);
            ans += res;
        }
        return ans;
    }
    
};