Record 2 algorithm problems
The exclusive time of the function
Leetcode-cn.com/problems/ex…
Function exclusive time is the time that each function is executing on its own. If nested, the execution time of the nested function does not count as the exclusive time of the external function. It is the exclusive time of the internally nested function itself.
Requirements:
* Provide an array of logs with the information ID: location: time. 0:start:3 * Calculates the exclusive time for each function. Save as an array. Order is the order in which a function is called. * If it is the same function, time will be added together. The last output is the total time a function was called.Copy the codeWhen you see the title, the execution call stack of the function. The obvious solution is to use a stack. First, extract the information. We can split(‘:’) to get the data.
And then the time, from the example I gave you, 1 is 1 unit of time. 3 -> 4 is 2 seconds, is occupied 3 seconds, 4 seconds, these two seconds. One exception is nested calls where 0:start:0, 0:start: 4 takes 4. The first function is executed in 0 seconds, 1 second, 2 seconds, 3 seconds, and the fourth second starts counting the time of the nested function. So the rule is that when nested functions, the execution time is last minus first. For start and end of a function, the execution time is end-start + 1
Next is how to save time. The time before the nested function starts calling exists and needs to be added.
Use an object to store the task information, and then as the execution is pushed onto the stack, wait for the next push, based on the time difference between the next time and the top of the stack of tasks to calculate the exclusive time of the previous function, and save to the previous task object. To solve the problem of storing the pop-up task data. To keep the order. Use another array to hold objects. Also use the characteristics of the object, you can modify the content of the object to carry out the update time.
while(logs.length) {
const m = logs.shift()
let [id, status, _time] = m.split(':')
_time = +_time
// The time in the task data is the record exclusive time, not the start time.
const data = { id, status, time: 0 }
...do something
}
Copy the codeIn order to better record the time, use a variable time, because time is always forward, so use this variable to record the time point of the last log, and calculate with the log point of this cycle, get the exclusive time of the last function to the present, and then save in the time of the last task information.
At the same time, to handle whether the current task is nested or terminated according to the status of the current task information is start or end.
// The state of the previous task information is always start, because end is not pushed on the stack.
const prev = stack[stack.length - 1]
if (status === 'start') {
// The nesting time does not need +1
prev.time = prev.time + _time - time
time = _time
stack.push(data)
} else {
// The task is complete
prev.time = prev.time + _time - time + 1
// The end time of the task is also the exclusive time of the function
// that is, 3 -> 4, starting from the fifth second after the task is finished is the time of another function
time = _time + 1
stack.pop()
}
Copy the codeAll you have to do is string them together, add in the task of checking the same ID, and add up the time.
The complete code is as follows, which is certainly not the only solution, because the official parameter n is not used.
function exclusiveTime(n, logs) {
const stack = []
const result = []
let time = 0
while (logs.length) {
const m = logs.shift()
let [id, status, _time] = m.split(':')
_time = +_time
const data = { id, status, time: 0 }
// To collect function calls in the correct order, the internal values are changed by the object
if (status === 'start') {
result.push(data)
}
const prev = stack[stack.length - 1]
// The stack is empty the first time or clean. And then you just push it in
if(! prev) { stack.push(data) time = _timecontinue
}
if (status === 'start') {
prev.time = _time - time
time = _time
stack.push(data)
} else {
prev.time = prev.time + _time - time + 1
time = _time + 1
stack.pop()
}
}
// Count the number of times, then convert to an array
const map = {}
for (let i = 0; i < result.length; i++) {
const m = result[i]
// map[m.id] is undefined, initialize to m.time
map[m.id] = map[m.id] + m.time || m.time
}
return Object.values(map)
}
Copy the codeMaximum period of good behavior
Leetcode-cn.com/problems/lo…
It’s a little hard to be true, and at first it looks like hell, prefix and monotone stack, greed. I don’t know.
The prefix sum is slightly simpler, like the Fibonacci sequence, where each term equals the sum of the preceding term and itself.
If [1,2,3,4] is greater than 3, we can simplify it to [-1, -1, -1, 1], and then we can sum it up, and the interval greater than 0 is the effective interval. And then we want to figure out what the longest interval is.
The role of the prefix sum here is if [a, b, c, d, e] wants to calculate the longest interval that adds up to greater than 0. Is a + b, a + b + c, a + b + c + d,… D + e. The length of equal probability is the longest and greater than 0. The prefix and [z, y, x, w, s], z = a + b, y = a + b + C, x = a + b + C + D
When x minus z, it’s a plus b plus c plus d minus a plus b, c plus d.
So that’s the beauty of prefixes and sums. Others to understand and then supplement.
The full code for this problem is below
function longestWPI(hours) {
// Generate the array [1, -1]
const arr = Array.from(hours, v= > (v > 8 ? 1 : -1))
// Generate prefixes and arrays
const prefix = arr.reduce(
(total, curr, index) = > {
total.push(curr + total[index])
return total
},
[0])let count = 0
let m = prefix.length
// Use a double loop to calculate the difference between the prefix sum, the longest interval greater than 0
for (let i = 0; i < m; i++) {
for (let j = i + 1; j < m; j++) {
if (prefix[j] - prefix[i] > 0) {
count = Math.max(count, j - i)
}
}
}
return count
}
` `
Copy the code