Nuggets team number online, help you Offer impromptu! Click for details
Difficulty from small to large, summed up three methods!! Reference force buckle plus
covering
★★45. Jump Game II
The difficulty of medium
Given an array of non-negative integers, you start at the first position in the array.
Each element in the array represents the maximum length you can jump at that location.
Your goal is to get to the last position in the array with the fewest hops.
Example:
Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to the last position is 2. Jump from subscript 0 to subscript 1, one step, then three steps to the last position in the array.Copy the codeDescription:
Suppose you can always get to the last place in the array.
🌟 greedy algorithm, each time from the range can be reached to calculate the next range can be reached, traversal!!
** Time complexity: O(n2)O(n^2)O(n2), ** Since the worst case is 111111 1111111, position updates from 55 to 00, and each update goes through a for loop.
Space complexity: O(1)O(1)O(1)
/ * * *@param {number[]} nums
* @return {number}* /
var jump = function(nums) {
if(nums.length<=1) return 0;
let len=nums.length;
let start=0,curMax=0,count=0;
while(true) {// Find the maximum position you can jump to
count++;
let tmp=curMax; // Keep this value for the last assignment of start
I <=curMax, curMax is changing!!
for(leti=start; i<=tmp; i++){ curMax=Math.max(curMax,i+nums[i]);
}
if(curMax>=len-1) break;
start=(++tmp); // Next start position
}
return count;
};
Copy the code🚩 uses a simplified version of the for loop
To optimize the
The code above shows that in the for loop contained in the while, I runs from beginning to end.
Just update the maximum distance you can jump next time when a jump is complete.
And updates the jump count with this moment as the timing. I can do it in a for loop.
❗ This approach has its drawbacks, not always. See link
Time complexity: O(n):
Space complexity: O(1)
/ * * *@param {number[]} nums
* @return {number}* /
var jump = function(nums) {
if(nums.length<=1) return 0;
let len=nums.length;
//maxPos represents the maximum distance that I can reach
//end represents the maximum distance that can be reached in the previous jump round
let maxPos=0,end=0,count=0;
for(let i=0; i<len; i++){ maxPos=Math.max(maxPos,i+nums[i]);
// If you reach the maximum position of the upper wheel, you have to make another jump
// We have already recorded the maximum position reached in the previous round with maxPos
// and make sure that end is not the last position, because count++ means the next jump
if(i===end&&end! ==len-1){ end=maxPos; count++; }}return count;
};
Copy the code🌟 The key is that maxPos records the maximum that can be reached currently, while end records the maximum that can be reached during the last jump. When the end is reached, the last jump is over, and the next jump is made!!
Sequence traversal is not very good in space and time, but it is the same idea as above
/ * * *@param {number[]} nums
* @return {number}* /
var jump = function(nums) {
if(nums.length<=1) return 0;
let len=nums.length;
let jump=[[0,nums[0]]]; // Position and jump distance in array
let count=0,preMax=0; //preMax represents the farthest position of the upper layer
while(jump.length){
// Take the position in the jump to make a jump
count++;
let tmp=[];
let curMax=preMax;
for(let i=0; i<jump.length; i++){let next=jump[i][0]+jump[i][1];
curMax=Math.max(curMax,next);
}
if(curMax>=len-1) break;
for(let i=preMax+1; i<=curMax; i++){ tmp.push([i,nums[i]]); } jump=tmp; }return count;
};
Copy the code★★1024. Video stitching
The difficulty of medium
You’ll get a series of video clips from a sporting event that lasts T seconds. These segments may overlap or vary in length.
Video clips[I] are represented by segments: start at clips[I][0] and end at clips[I][1]. We can even freely re-edit these fragments. For example, fragment [0, 7] can be cut into three parts: [0, 1] + [1, 3] + [3, 7].
We need to re-edit these fragments and splice the edited content into fragments covering the whole movement process ([0, T]). Returns the minimum number of fragments required, or -1 if the task cannot be completed.
Example 1:
Input: clips = [[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], T = 10 output: 3: we selected to [0, 2], [8, 10], [1, 9] these three pieces. Then, reproduce the match clip as follows: edit [1,9] to [1,2] + [2,8] + [8,9]. Now we have [0,2] + [2,8] + [8,10] and that covers the whole game [0, 10].Copy the codeExample 2:
Explanation: we can't cover the whole process of [0,5] with only [0,1] and [1,2].Copy the codeExample 3:
Input: clips = [[0, 1], [6], [0, 2], [5, 6], [0, 4], [0, 3], [6, 7], [1, 3], [4, 7], [1, 4], [2, 5], [2, 6], [3, 4], [4, 5], [5, 7], [6, 9]], T = 9 output: 3 explanation: we select fragments [0,4], [4,7] and [6,9].Copy the codeExample 4:
Note: Note that you may record a video that runs past the end of the race.Copy the codeTip:
1 <= clips.length <= 1000 <= clips[i][0] <= clips[i][1] <= 1000 <= T <= 100
🌟 thinking and jumping is the same!! Traversal is to cover the scope, not fragments!!
- Traverse according to the interval to be covered, and record the maximum distance maxPos that can be reached by 0~ I for the next jump
- To determine whether there is a vacancy, maxPos= I means that it cannot continue, that is, it cannot cut a complete movie
- End = I indicates that the longest position that can be clipped to in the previous round has been reached and the next clip needs to be selected
Time complexity: O(n)
Space complexity: O(n)
/ * * *@param {number[][]} clips
* @param {number} T
* @return {number}* /
var videoStitching = function(clips, T) {
// Similar to bucket sorting or netease's lucky number, we create an array with an interval length
// Record the farthest you can reach on the location LOC
let maxEnd=Array(T).fill(0); Math.max returns NaN if Number() is followed by NaN
// There are two differences from the previous jump
//1. There is only one maximum jump distance per position, and there may be more than one, so use a for to maximize
//2. The jump must reach the end, but not necessarily here, so consider
for(let i in clips){
maxEnd[clips[i][0]] =Math.max(maxEnd[clips[i][0]],clips[i][1]);
}
// End represents the maximum position that the current jump can reach, so we are looking for the maxPos point in this range to jump/clip
//maxEnd(I) is the farthest that the position I can reach, and maxPos is the farthest that the position before I can reach
let end=0,maxPos=0,count=0;
//★ I cannot be equal to T well, if it is equal to T then it will be added one more time at the end, because if you can reach T you shouldn't be adding more
//★ Don't worry if you can't reach T, because you will reach T-1, t-1 will judge whether to continue
for(let i=0; i<T; i++){ maxPos=Math.max(maxPos,maxEnd[i]);
// The farthest you can reach is I, which means you can't go any further, so you can't complete the task
if(i===maxPos){
return -1;
}
// We have reached the maximum of the last jump and need to select the point where the next jump is maxPos for the next jump
if(end===i){ count++; end=maxPos; }}return count;
};
Copy the codeTraversal by the given range array
/ * * *@param {number[][]} clips
* @param {number} T
* @return {number}* /
var videoStitching = function(clips, T) {
clips.sort((a,b) = >a[0]-b[0]);
let i=0,end=0,maxPos=0,count=0;
// The problem is a bit special, T may be 0, then no fragment is needed
// The following while must have a fragment by default
if(T===0) return 0;
while(i<clips.length){
while(i<clips.length&&clips[i][0]<=end){
maxPos=Math.max(maxPos,clips[i][1]);
i++;
}
Clips [I][0]>end or I >=clips.length
// The previous while has traversed all the points reached in the previous round, so it must make a jump, so ++
// Don't worry about maxPos>T, because maxPos>T affects whether the next round is jump, and this round is already determined
count++;
/ / maxPos > T satisfied conditions do not need to jump the | | I > =... Out of scope should be terminated
if(maxPos>=T||i>=clips.length) break;
end=maxPos;
// The starting point of the next fragment is farther than the current maximum distance, so it will be empty
// I is in range
if(clips[i][0]>maxPos){
return -1; }}return maxPos<T? -1:count;
};
Copy the codeTheir stupid way….
/ * * *@param {number[][]} clips
* @param {number} T
* @return {number}* /
Clips [I][0]
var videoStitching = function (clips, T) {
// It is a jump problem, but some points in the middle may not be there
// Clips [I][0] is the jumping position, and clips[I][1] is the jumping distance
clips.sort((a, b) = > a[0] - b[0]);
if (T === 0) return 0;
if (clips[0] [0]! = =0) return -1;
let end = 0, maxPos = 0, count = 0;
// The for loop is actually a case of jumping, but not sure where
// We need to determine the most greedy jump option based on maxPos
for (let i = 0; i < clips.length; i++) {
while (i < clips.length - 1 && clips[i][0] === clips[i + 1] [0]) {
clips[i + 1] [1] = Math.max(clips[i][1], clips[i + 1] [1]);
i++;
}
// It was supposed to be updated at end, but the fragment might not have an end position
if (clips[i][0] > end) {
// If you can find a position larger than the clip [I] before the end of the last round
// Then you can make up for the sequence of clips in the middle
/ / ▼ for example [0, 2] [1, 9] [5, 9] first fragment can only reach 2, but it can jump to [1, 9] first,
// jump to [5,9] or beyond, so add a jump from [0,2] to [1,9]
//❗ note that there is no increase in jumps from [1,9] to [5,9]!!
if (maxPos >= clips[i][0]) {
count++;
// Handle initialization issues, the first jump can not be directly to the end of the maxPos, maxPos has not been updated
end = maxPos;
MaxPos = maxPos = maxPos = maxPos;
maxPos = Math.max(maxPos, clips[i][1]);
// Clips [I][1] can't be greater than or equal to T, but clips[I][1] can be >=T
// maxPos=>clips[I]=>T
if (maxPos >= T) count++;
} else { // If maxPos is smaller than clips[I][0], the gap cannot be filled
return -1; }}else if (clips[i][0] === end) {
// Just equal to end is exactly the same as the previous jump problem!!
count++;
// A jump must be made between the previous maxPos and the current position I
maxPos = Math.max(maxPos, clips[i][1]);
end = maxPos;
} else {
maxPos = Math.max(maxPos, clips[i][1]);
// Clips [I][0] and clips[I][1] may also be larger than T(special case of input error)
if (maxPos >= T) count++;
}
if (maxPos >= T) break;
}
if (maxPos < T) return -1;
return count;
};
Copy the code🚀 reflection: why their own writing smelly and long need to consider all kinds of conditions, while others writing clean and neat?
I think I missed the point: This kind of scope coverage problem requires traversing the scope, but I directly want to traverse the fragment (need to consider many not easy to think of boundary cases)!! Totally forgot how I walked through the first jump…
Of course, greedy can be converted into DP, DP is also clean, the idea is as follows:
Dp [0]=0, and the rest is initialized to Infinity. Dp [I] indicates the minimum number of fragments required from [0, I]
▼ traverse all pieces at a time, if I > clips, [j] [0] clips, [j] [0] clips, [j] [0], Dp is more dp [I] [I] dp [I] and dp [clips, [j] [0]] + 1 dp [clips, [j] [0]] + 1 dp [clips, [j] [0]] + 1, because the [0, I] by [0, [j] [0] clips, clips, [j] [0] clips, [j] [0]] and [clips [j] [0] clips, [j] [0] clips, [j] [0], I], and then take the smallest
★ Why I = clips[j][0]clips[J][0] [0] If equal to, just use dp[I], do not need to jump again!! Dp [I] is Infinity. We need to make sure that we can start from [0,k] and then make sure that we can start from [k, I].
Dp = dp
Time complexity: O(n^2^)
Space complexity: O(n)
/ * * *@param {number[][]} clips
* @param {number} T
* @return {number}* /
var videoStitching = function(clips, T) {
// The question is [0,T].
//dp[I] represents the minimum number of fragments required for [0, I]. We will loop through all fragments
let dp=Array(T+1).fill(Infinity);
dp[0] =0; // An initial value of 0 also means that [0,0) does not require fragments
for (let i=1; i<=T; i++){for (let v of clips){
// v[0]< I <=v[1
// Edit to [v[0], I)
if (v[0]<i&&v[1]>=i){
dp[i]=Math.min(dp[i],dp[v[0]] +1)}}}return dp[T]===Infinity? -1 : dp[T];
};
Copy the code★★★1326. Minimum number of faucets to irrigate the garden
Difficult difficult
There’s a one-dimensional garden on the X-axis. The garden has length N, starting at point 0 and ending at point n.
There are n + 1 taps in the garden, located at [0, 1… n].
You are given an integer n and an integer array ranges of length n + 1, where ranges[I] (subscripts start from 0) represent: if the tap at point I is turned on, the area that can be irrigated is [i-ranges [I], I + ranges[I]].
Please return the minimum number of faucets that can irrigate the entire garden. If there are persistent areas of the garden that cannot be irrigated, return to -1.
Example 1:
Input: n = 5, ranges = [3,4,1,1,0,0] The faucet at point 0 can irrigate the range [-3,3] and the faucet at point 1 can irrigate the range [-3,5] and the faucet at point 2 can irrigate the range [2,4] and the faucet at point 4 can irrigate the range [4,4] and the range 5 The faucet at [5,5] can irrigate the whole garden by opening the faucet at point 1 [0,5].Copy the codeExample 2:
Input: n = 3, ranges = [0,0,0] Output: -1 Explanation: Even if you turn on all the taps, you cannot irrigate the whole garden.Copy the codeTip:
1 <= n <= 10^4ranges.length == n + 10 <= ranges[i] <= 100
🌟 is the same as before, converting data first and jumping mode
Time complexity: O(n):
/ * * *@param {number} n
* @param {number[]} ranges
* @return {number}* /
var minTaps = function(n, ranges) {
//n>=1, ranges.length=n+1
// We care about the range, not the number of taps, so n
//maxEnd[I] specifies the maximum distance that can be reached at position I
let maxEnd=Array(n).fill(0);
for(let i=0; i<ranges.length; i++){let low=Math.max(0,i-ranges[i]),
high=i+ranges[i];
maxEnd[low]=Math.max(maxEnd[low],high);
}
// Loop over coverage
let end=0,maxPos=0,count=0;
for(let i=0; i<n; i++){ maxPos=Math.max(maxPos,maxEnd[i]);
// I
if(maxPos===i) return -1;
//end= I, indicating that the last faucet covered the maximum range, need to find the next faucet
// If you have reached the maximum distance of the last jump, select the position corresponding to maxPos
// Make the next jump for the jump landing point of the previous round
if(end===i){ end=maxPos; count++; }}return count;
};
Copy the codeThis dp is not very good 😭😭😭
/ * * *@param {number} n
* @param {number[]} ranges
* @return {number}* /
var minTaps = function(n, ranges) {
//n>=1, ranges.length=n+1
//dp[I] indicates the number of taps required by [0, I]
let dp=Array(n+1).fill(Infinity);
dp[0] =0;
// handle the range first
for(let i=0; i<ranges.length; i++){let low=Math.max(0,i-ranges[i]),
high=i+ranges[i];
ranges[i]=[low,high];
}
// Loop over coverage
for(let i=1; i<=n; i++){for(let v of ranges){
if(v[0]<i&&v[1]>=i){
dp[i]=Math.min(dp[i],dp[v[0]] +1); }}}return dp[n]===Infinity? -1:dp[n];
};
Copy the codeTencent written test: Vision contention
Link: www.nowcoder.com/questionTer… Source: Niuke.com
Little Q is playing a competitive game. The key to the victory or defeat of this game is whether it can compete for a river with length L, which can be regarded as a number line [0,L].
In this competitive game, there are n items that can provide a view – true-sight guard, the I true-sight guard can cover the area [xi,yi]. Now Q wants to know that it would take at least a few true-sight guards to cover the entire length of the river.
Input description:
The input consists of n+1 lines.
The first line contains two positive integers n and L(1<=n<=10^5^,1<=L<=10^9^).
The next n lines, each with two positive integers xi,yi(0<=xi<=yi<=10^9^), represent the range covered by the i-th true-view guard.
Output description:
An integer representing the minimum number of true guards required. If there is no solution, -1 is output.Copy the codeExample 1
The input
4, 6, 6, 2, 4, 0, 2, 4, 7Copy the codeThe output
3
Copy the code🌟 this problem you > may think and before of same, but have pit!! Notice that? If the previous range coverage is calculated again, then the calculation amount will reach 10910^9109 magnitude (timeout ❗), but if the fragment traversal is used, only 10510^5105, so the fragment traversal or the range traversal depends on the situation!!
const readline=require('readline');
const rl=readline.createInterface({
input:process.stdin,
output:process.stdout
})
const arr=[]
let n,l;
rl.on('line'.function(line){
arr.push(line.split(' ').map(Number));
if(arr.length===1){
n=Number(arr[0] [0]);
l=Number(arr[0] [1]);
}else if(arr.length===n+1){
arr.shift();
arr.sort((a,b) = >a[0]-b[0]);
let end=0,maxPos=0,count=0,i=0;
while (i<arr.length){
// Find the maximum maxPos in the last jump range
// Since it is sorted,end=0 is also initialized
while (i<arr.length&&arr[i][0]<=end){
maxPos=Math.max(maxPos,arr[i][1]);
++i;
}
// Jump once
count++;
end=maxPos;
// The direct starting point is larger than the current maximum jump distance, there is a gap
if (i<arr.length&&arr[i][0]>end){
count=-1; break;
}
if (maxPos>=l) break;
}
// maxPos failed to reach l on exit
if (maxPos<l){
count=-1;
}
console.log(count);
//next
arr.length=0; }})Copy the codeI also rewrote range array traversal to 1024 after learning about this method link 1024
🌟 Summary
There are three methods of coverage:
I. Coverage traversal
- Set up an array maxEnd whose length is the length of the coverage range, traverse the fragment array, record the furthest distance that can be reached at position I maxEnd[I]maxEnd[I]maxEnd[I], initialize to 0
- The coverage is traversed and maxPos is updated to be the farthest node that can jump to [0, I][0, I]
- End = I indicates that the maximum of the last jump has been reached, and the point where the next jump is maxPos needs to be selected for the next jump
Fragment array traversal
- First sort the fragment array
- Use a while to iterate through the current round and update maxPos
- End =maxPos Makes relevant updates and determines exit conditions
Dynamic programming
Dp [I] represents the minimum number of fragments required by [0, I], and we will loop over all fragments