TeemoAttacking [source code]

public class TeemoAttacking {
static
/******************************************************************************/
public class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int sum = 0;
        for (int i = 1; i < timeSeries.length; i++) {
            if (timeSeries[i] - timeSeries[i - 1] >= duration) {
                sum += duration;
            } else {
                sum += timeSeries[i] - timeSeries[i - 1];
            }
        }
        return sum + (timeSeries.length > 0 ? duration : 0);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        TeemoAttacking.Solution tester = new TeemoAttacking.Solution();
        int[][] inputs = {
            {1, 4}, {2}, {4},
            {1, 2}, {2}, {3},
            {}, {10000}, {0},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] timeSeries = inputs[3 * i];
            int duration = inputs[1 + 3 * i][0];
            int answer = inputs[2 + 3 * i][0];
            System.out.println(Printer.seperator());
            int output = tester.findPoisonedDuration(timeSeries, duration);
            System.out.println(Printer.wrapColor(Printer.array(timeSeries) + " AND " + duration, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answer, output == answer ? "green" : "red"));
        }
    }
}

这个题目对于time unit这个东西给出了一定的解释, 这个解释还是要稍微理解一下, 而且可能可以套用到其他的类似的涉及到time unit的问题; 因为time unit这个东西毕竟跟普通的array的那种iteration还是不一样的, 需要考虑一个duration的概念;

        return sum + (timeSeries.length > 0 ? duration : 0);

三目操作符inline的时候一定要多打括号, 这个操作符的优先级很低;

总体来说是一个比较简单的题目, 磨磨蹭蹭一边看直播一边写, 写了半天; 最后的速度是9ms (62%).

如果这题就是要按照照intersection的思路来找的话, 就比较麻烦. 还是一句话, middle的题目, 读懂题目描述的是怎样的一个过程, how would a human do it是最关键的. 不要上来就各种宏观分析, 套路尝试. 先理解人逻辑之后, 再去从优化的角度去想电脑逻辑, 会轻松很多;

这个题目的人逻辑就很简单啊, 就是一个类似refreshing的需求, 你要怎么做嘛. 还是很直白的;

看了一下, discussion里面果然有不少人把这个问题想复杂了;

Algorithm:

1. Use two variable to record current start and end point.
2. If the start of new interval is greater than current end, meaning NO overlapping, we can sum the current interval length to result and then update start and end.
3. Otherwise just update the current end;

public class Solution {  
    public int findPosisonedDuration(int[] timeSeries, int duration) {  
        if (timeSeries == null || timeSeries.length == 0 || duration == 0) return 0;  

        int result = 0, start = timeSeries[0], end = timeSeries[0] + duration;  
        for (int i = 1; i < timeSeries.length; i++) {  
            if (timeSeries[i] > end) {  
                result += end - start;  
                start = timeSeries[i];  
            }  
            end = timeSeries[i] + duration;  
        }  
        result += end - start;  

        return result;  
    }  
}

大概的思路还是比较简单的, 就是维护上一个attack的终点, 然后判断就行了, 其实核心原理跟我这个算法是一样的, 只不过实现的时候想的有点复杂;

不过再怎么说, 这个题目其实也可以算作是一个intersection/overlapping的问题? 对于这一类问题收集一下思路还是有好处的;

总体来说是一个比较简单的题目, discussion里面也没有什么惊喜; 不过这个题目也真的是展示了, 在middle题目里面, 读懂题目是首先的重要性;

Problem Description

In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo's attacking ascending time series towards Ashe and the poisoning time duration per Teemo's attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

Input: [1,4], 2  
Output: 4  
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately.   
This poisoned status will last 2 seconds until the end of time point 2.   
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds.   
So you finally need to output 4.

Example 2:

Input: [1,2], 2  
Output: 3  
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned.   
This poisoned status will last 2 seconds until the end of time point 2.   
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status.   
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3.   
So you finally need to output 3.

Note:

1. You may assume the length of given time series array won't exceed 10000.
2. You may assume the numbers in the Teemo's attacking time series and his poisoning time duration per attacking are non-negative integers, which won't exceed 10,000,000.
   Difficulty:Medium
   Total Accepted:14.5K
   Total Submissions:28.1K
   Contributor: CDY_好きだ
   Companies
   riot games
   Related Topics
   array
   Similar Questions
   Merge Intervals Can Place Flowers