“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Since January 17, 2022, began a source of rookie algorithm growth road, thanks to Hu Yui big guy and group partners launched algorithm brush card activity, a busy week finally began.

Set a flag, one question a day for 100 days. Yuan come on!

This is the second day of a yuan “Hecate” brush growth road

A, the title

  1. Timothy attack

Subject details: Source: LeetCode link: leetcode-cn.com/problems/te…

Second, analyze the solution idea

2.1 Qingqi brain circuit (error 🙅 case)

Read the passage for the first time.

1. The number of seconds is increasing one by one

2. The corresponding timeSeries array records how many seconds an attack is launched

3, ducration is the duration of attack corresponding to poisoning

The first case:

Duration poison duration of attack, calculated backwards (1,3), poison lasts 2 seconds. Time line of seconds: 1,2, 3,4,5,6,7 1 second attack, duration "1,2" 3 seconds attack, duration "3,4", combine the interval [1,2, 3,4], the total number of seconds corresponding to poisoning is 4Copy the code

The second case:

[2,4,5,8]. Venom lasts 3 seconds. The time line is 1,2,3,4,5,6,7,8,9,10,11. 2 seconds: "2, 3, 4"; 4 seconds: "4, 5, 6"; 5 seconds: "5, 6, 7"; 8 seconds: "8,9,10" will arrange them into an array [2,3,4,4,5,6,5, 7,8,9,10]. The length of the corresponding array [2,3,4,5,6,7,8,9,10] is the total number of seconds of the corresponding poisoning state 9 after the array is de-duplicatedCopy the code

From the above analysis, the idea is:

  • Iterate through the array of attack time to get the array of duration corresponding to the number of seconds

  • Merges all poison event arrays at attack time to be de-duplicated

  • The length after weight removal is the total poison time corresponding to several attacks

  • Since the problem prompts three cases, you need to pay attention to the test case situation at the edge

Ababa Ba, wrote that much, my own seems to think clearly a lot, then try to write code, finally run the code to view (3.1 error code 🙅), found not feasible.

2.2 Further analysis (correct answer 🙆)

The previous analysis is partially correct, but the execution algorithm logic used is not feasible. Next, continue the analysis:

  • TimeSeries [t+ duration-1] time is poisoned

  • TimeSeries [I]-timerSeries[i-1] >= duration indicates that the poisoning time from the last attack to the next attack is over, and the poisoning time is duration

  • TimeSeries [I]-timerSeries[i-1]< duration, duration of the last attack is not over, timeSeries[I] -timeseries [i-1]

  • The total duration of poisoning is added up after each attack

2.3 Look at 2.1 from another perspective

In 2.1, the method of decomposition after reading the question, and then directly use the array to store the two-dimensional array is not too clever. However, it is feasible to change the thinking Angle and change the algorithm in 2.1:

  • Calculate the total time of undecaying poisoning: timesery. length * duration
  • Determine attack time, total poisoning events minus repetition time
  • TimeSerie [I] -timeserie [i-1]< duration (need to be de-duplicated), extra time: duration-(timeSeries[I] -timeseries [i-1])

Code & complexity analysis

3.1 Error code 🙅

var findPoisonedDuration = function(timeSeries, Duration) {let arr = [] // set timeSeries. ForEach (item=>{let arr1 = [] // record the poisoning time of each attack for(let I =0; i<duration; I ++){arr1.push(item+ I)} arr.push(arr1)}) arr = arr.flat() // Arr = arr.filter((item,index,arr)=>{ return arr.indexOf(item,0) === index; }) return arr.length };Copy the code

Complexity analysis:

  • O(n^2)+O(n)+O(n), so O(n^2)
  • Space complexity: O(n), so space complexity is O(n), where n is the length of arr above

Analysis:

  • As n gets bigger, the time complexity and space complexity get bigger and bigger, so the running time is out

3.2 Correct code ✅

var findPoisonedDuration = function(timeSeries, duration) { let len = timeSeries.length, timeCount = 0; for(let i=1; i<len; ++i){ let oneCount = timeSeries[i] - timeSeries[i-1]; if(oneCount>=duration){ timeCount += duration; }else{ timeCount += oneCount; } } timeCount+=duration return timeCount; };Copy the code

Complexity analysis:

  • Time complexity: O(n)
  • Space complexity: O(1)

3.3 Correct code ✅

var findPoisonedDuration = function(timeSeries, duration) { let timeCount = timeSeries.length * duration for(let i=1; i<timeSeries.length; i++){ if(timeSeries[i]-timeSeries[i-1]<duration){ timeCount -= duration-timeSeries[i]+timeSeries[i-1] } } return timeCount; };Copy the code

Complexity analysis:

  • Time complexity: O(n)
  • Space complexity: O(1)

Four,

In this problem, although the first idea is not feasible, it also times out, because it implies that the other two algorithms cause the time complexity and space complexity is not ideal, when the number is too large, it will cause the runtime timeout. Is a classic case of error.

Deeply feeling that writing also need to consider the idea of right ah, brush algorithm the second day, simple questions let me feel pressed on the ground friction!

4.1 knowledge

The subject was originally simple, but I was biased by a curious brain circuit. However, after analyzing the time complexity and space complexity, it is necessary to summarize the knowledge points involved in the above way:

  1. Converting a two-dimensional array to a one-dimensional array;
  2. How to deduplicate a one-dimensional array
  3. Array methods in JS

1 one dimensional array to one dimensional array

Arr. Reduce (callback[,initialValue])

Var arr1 = [[0,1,3],[2,3],[4,5]] var arr2 =Copy the code

2. Use ES6 map function and recursion

,1,3 var arr1 = [[0], [2, 3], [4, 5]] function flatten (arr) {return [] concat (... arr.map(x=> Array.isArray(x) ? flatten(x):x )) } var arr2 = flatten(arr1)Copy the code

3. Use Apply

,1,3 var arr1 = [[0], [2, 3], [4, 5]] var arr2 = [] concat. Apply ([] arr1);Copy the code

Split (‘,’) (disadvantage: array elements become strings)

Flat ()(ES6 array.prototype.flat ()) removes null items, but undefined and null items remain

The specific content is not explained in this paper, and the subsequent length is recorded.

For reference: JS 2d to 1d array

2 discount ️ array to repeat

1. Use ES6 Set to remove weight

2, double for loop, splice deduplicates (ES5)

3. Use indexOf to remove weights

4, use sort()

5. Use includes

Use hasOwnProperty

7. Use filter

8. Use recursion

9. Use Map data structure to remove weight

10. Use reduce+ includes

11, new Set (arr)] […

The specific content is not explained in this paper, and the subsequent length is recorded.

For reference: 12 ways to deduplicate in JS

3 Ergodic method in ️ JS

1, For () 2, while () While statement 3, forEach 4, for-in 5, for-of

MDN: loop and iteration

4.2 the optimal solution

According to the solution of the second part of the problem, the correct solution can be divided into two ways. One is to distinguish the two different duration of poisoning and add them up. The second is to calculate the total normal poisoning time, minus the repetition time.