Third, the path problem
2020.10.19
No.62 Different paths
A robot is located in the upper left corner of an m x N grid (the starting point is marked “Start” in the image below).
The robot can only move one step down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).
How many different paths are there?
For example, the figure above shows a 7 x 3 grid. How many possible paths are there?
Example 1:
Input: m = 3, n = 2 Output: 3 Explanation: Starting from the upper left corner, there are a total of three paths to the lower right corner.
- To the right -> to the right -> down
- Go right -> down -> right
- Down -> right -> right
Example 2:
Input: m = 7, n = 3 Output: 28
Tip:
1 <= m, n <= 100 Question data guarantee answer is less than or equal to 2 * 10 ^ 9
Source: LeetCode link: leetcode-cn.com/problems/un… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution a:
/* * @lc app=leetcode.cn id=62 lang=javascript * * [62] different paths */
// @lc code=start
/ * * *@param {number} m
* @param {number} n
* @return {number}* /
var uniquePaths = function(m, n) {
// Use a matrix table to record the number of paths
For a 3 x 2 matrix, it can be expressed as follows: * 1 1 1 * 1 2 3 * no pruning, input all information into the matrix table, and the last digit is the path and */
let dp = new Array(n);
// Set all the elements in the first row and all the elements in the first column to 1
for(let row=0; row<n; row++) { dp[row] =new Array(m);
dp[row][0] = 1;
}
for(let col=0; col<m; col++) { dp[0][col] = 1;
}
// Dynamic programming
for(let i=1; i<n; i++) {for(let j=1; j<m; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]}}return dp[n-1][m-1];
};
Copy the codeScheme 2:
/* * @lc app=leetcode.cn id=62 lang=javascript * * [62] different paths */
// @lc code=start
/ * * *@param {number} m
* @param {number} n
* @return {number}* /
var uniquePaths = function(m, n) {
// The factorial function
const fac = (n) = > {
if(n<=1) return 1;
return fac(n-1)*n;
}
return fac(n-1+m-1) / ( fac(m-1) * fac(n-1)); };Copy the codeThere are two solutions: 1. Dynamic programming: The recursive loop invariant is dp[I][j]=dp[i-1][j]+dp[I][j-1]. Here, one-dimensional array can be used to directly replace the data of the previous layer, but the expansibility is poor and only applicable to ontology. 2. Permutation and combination: The problem can be converted to 1 to the right and 0 to the down, and there are two choices of different results each time, and then the permutation and combination of 1 or 0 can be selected from m-1+n-1, that is, Cm-1+ N-1n-1 =Cm-1+ N-1m-1
2020.10.20
No.63 Different path -II
A robot is located in the upper left corner of an m x N grid (the starting point is marked “Start” in the image below).
The robot can only move one step down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).
Now consider an obstacle in the grid. So how many different paths are there going to be from top left to bottom right?
Obstacles and empty positions in the grid are represented by 1 and 0 respectively.
Note: The values of m and n do not exceed 100.
Example 1:
Input: [[0, 0], [0, 0] to [0, 0]] output: 2:3 x3 grid right in the middle there is a barrier. There are two different paths from the top left to the bottom right:
- Right -> right -> down -> down
- Down -> down -> right -> right
Source: LeetCode link: leetcode-cn.com/problems/un… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution:
/* * @lc app=leetcode.cn id=63 lang=javascript * * [63] different path II */
// @lc code=start
/ * * *@param {number[][]} obstacleGrid
* @return {number}* /
var uniquePathsWithObstacles = function(obstacleGrid) {
const r = obstacleGrid.length,
c = obstacleGrid[0].length;
if(obstacleGrid[0] [0] = =1 || obstacleGrid[r-1][c-1] = =1) return 0;
// Build a two-dimensional array
let dp = new Array(r);
for(let row=0; row<r; row++) dp[row] =new Array(c);
dp[0] [0] = 1;
// The first column element
for(let row=1; row<r; row++) {if(obstacleGrid[row][0] = =1) {
dp[row][0] = 0;
} else if(obstacleGrid[row][0] = =0) {
dp[row][0] = dp[row-1] [0]; }};// The first row of elements
for(let col=1; col<c; col++) {if(obstacleGrid[0][col] == 1) {
dp[0][col] = 0;
} else if(obstacleGrid[0][col] == 0) {
dp[0][col] = dp[0][col-1]; }};// Dynamic programming
for(let i=1; i<r; i++) {for(let j=1; j<c; j++) {if(obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else if(obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}};return dp[r-1][c-1];
};
Copy the codeCommon problems in dynamic programming, where the state transition equation needs to be filtered after judging the value of obstacleGrid(I,j) : when the obstacleGrid(I,j) is 1, dp[I][j]=0; Otherwise, dp[I][j]=dp[i-1][J]+dp[I][J-1]. The boundary conditions also need to meet the filter conditions. You can’t just judge the filling of 0 or 1. Filling 0 or 1 in one row or column will affect the next row or column
2020.10.21
Minimum path sum of triangles
Given a triangle, find the smallest sum of paths from top to bottom. Each step can only move to adjacent nodes in the next row.
Adjacent nodes in this case are two nodes whose subscripts are the same or equal to the subscript + 1 of the node above.
For example, given a triangle:
[[2], [3, 4], [6, 5, 7], [4,1,8,3]] top-down minimum path and 11 (i.e., 2 + 3 + 5 + 1 = 11).
Description:
If you can solve this problem with just O(n) of extra space (where n is the total number of rows in the triangle), then your algorithm will be a plus.
Source: LeetCode link: leetcode-cn.com/problems/tr… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution a:
/* * @lc app=leetcode.cn id=120 lang=javascript * * [120] triangle minimum path and */
// @lc code=start
/ * * *@param {number[][]} triangle
* @return {number}* /
var minimumTotal = function(triangle) {
const r = triangle.length,
c = triangle[0].length;
// Construct the dynamic programming path
const dp = new Array(r);
for(let row=0; row<r; row++) dp[row] =new Array(c);
/ * * * state transfer equation dp [I] [j] = math.h min (dp [j], [I - 1] dp [I - 1]] [j - 1) + triangle [I] [j] * /
// Boundary condition processing
dp[0] [0] = triangle[0] [0];
for(let i=1; i<r; i++) {// dp[I][0] = dp[i-1][0] + triangle[I][0]
dp[i][0] = dp[i-1] [0] + triangle[i][0];
for(let j=1; j<i; j++) { dp[i][j] =Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j];
}
// Dp [I][I] = dp[i-1][i-1] + triangle[I][I]
dp[i][i] = dp[i-1][i-1] + triangle[i][i];
}
return Math.min(... dp[r-1]);
};
Copy the codeScheme 2:
/* * @lc app=leetcode.cn id=120 lang=javascript * * [120] triangle minimum path and */
// @lc code=start
/ * * *@param {number[][]} triangle
* @return {number}* /
const minimumTotal = (triangle) = > {
const height = triangle.length;
const width = triangle[0].length;
// Initialize the dp array
const dp = new Array(height);
for (let i = 0; i < height; i++) {
dp[i] = new Array(width);
}
for (let i = height - 1; i >= 0; i--) {
for (let j = triangle[i].length - 1; j >= 0; j--) {
if (i == height - 1) {
// base case
dp[i][j] = triangle[i][j];
} else {
// State transition equation
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]; }}}return dp[0] [0];
};
Copy the code1, from top to bottom: using dp[I][J] = Math. Min (dp[i-1][J],dp[i-1][J-1]) + triangle[I][J], pay attention to the boundary processing; 2. Bottom-up: look up from the bottom layer to layer. The minimum value in the bottom layer is determined, so its direction is basically determined, and eventually it will be reduced to a number
2020.10.22
No.864 gets the shortest path for all keys
Given a two-dimensional grid. “.” represents an empty room, “#” represents a wall, “@” is the starting point, (” A “, “b”…) For key, (“A”, “B”…) On behalf of the lock.
Let’s start at the starting point, and a movement is one unit of space in one of the four basic directions. We can’t walk outside the grid, we can’t walk through a wall. If we pass a key, we pick it up. We can’t get through the lock unless we have the right key.
Assuming K is the number of keys/locks that satisfy 1 <= K <= 6, the first K letters of the alphabet have their own lowercase and capital letters in the grid. In other words, each lock has a unique key, and each key has a unique lock. In addition, the letters representing keys and locks are case-sensitive and arranged alphabetically.
Returns the minimum number of moves required to get all keys. If all keys cannot be retrieved, -1 is returned.
Example 1:
Input: [” @a.# “,”###.#”,” B.A.B “] Output: 8 Example 2:
Input: [“@..aA”,”.. b #.”,”….b”] Output: 6
Tip:
1 < = grid. Length 30 1 < < = = grid [0]. Length < = 30 grid [I] [j] contains only ‘. ‘, ‘#’, ‘@’, ‘a’ – ‘f’ and ‘a’ – ‘f’ range of [1, 6] is the number of keys, Each key has a different letter that opens the right lock.
Source: LeetCode link: leetcode-cn.com/problems/sh… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution:
/* * @lc app=leetcode.cn id=864 lang=javascript * * [864] Get the shortest path for all keys */
// @lc code=start
/ * * *@param {string[]} grid
* @return {number}* /
var shortestPathAllKeys = function(grid) {
// Create a structure that satisfies {I,j,keybit,step}
/** * I ** j ** * keybit ** step ** * step ** *
function Step(i,j,keybit,step) {
this.i = i;
this.j = j;
this.keybit = keybit;
this.step = step;
};
const ROW = grid.length,
COL = grid[0].length,
LOWER_A = 'a'.charCodeAt(), / / 97
UPPER_A = 'A'.charCodeAt(); / / 68
let KEY_BIT = 0;
// Get all key information
let start = null;
for(let r = 0; r < ROW; r++) {
for(let c = 0; c < COL; c++) {
if(grid[r][c] == The '@') {
// Start position
start = [r,c];
} else if (grid[r][c] >= 'a' && grid[r][c] <= 'f') {
// Mark the shift xOR comparison of the judgment bits, which is a common method of ACL
KEY_BIT = KEY_BIT | ( 1 << ( grid[r][c].charCodeAt() - LOWER_A ) )
}
}
}
// The constructor has traversed the node structure
const visited = new Array(ROW);
for(let i = 0; i < ROW; i++) {
visited[i] = new Array(COL);
for( let j = 0; j < COL; j++) {
visited[i][j] = {}
}
};
visited[start[0]][start[1]] [0] = true;
// Move direction
const directions = [
[-1.0]./ / left
[1.0]./ / right
[0.1]./ /
[0, -1] / /
];
// Create a queue structure for caching
const queue = [new Step(start[0], start[1].0 ,0)];
// Circular queue for judgment
while( queue.length ! =0) {
const current = queue.shift();
if(current.keybit == KEY_BIT) {
return current.step;
}
for(let d = 0; d < directions.length; d++) {
// The next coordinate
const ni = current.i + directions[d][0],
nj = current.j + directions[d][1];
// Make different judgments about the four directions
if( ( ni >= 0 && ni < ROW ) && ( nj >= 0&& nj < COL ) && ! visited[ni][nj][current.keybit] ) {/ / is the key to it
if( grid[ni][nj] >= 'a' && grid[ni][nj] <= 'f' ) {
const _keybit = current.keybit | ( 1 << (grid[ni][nj].charCodeAt() - LOWER_A) );
queue.push(new Step(ni, nj, _keybit, current.step+1));
// We have already visited them
visited[ni][nj][current.keybit] = true;
visited[ni][nj][_keybit] = true;
} else if ( // Is an empty room, a starting point, and a lock that has not been accessed
( grid[ni][nj] == '. ' ) ||
( grid[ni][nj] == The '@' ) ||
( grid[ni][nj] >= 'A' && grid[ni][nj] <= 'F' && ( current.keybit & ( 1 << (grid[ni][nj].charCodeAt() - UPPER_A) ) ) )
) {
queue.push(new Step(ni, nj, current.keybit, current.step+1));
// Set the path status to "accessed"
visited[ni][nj][current.keybit] = true; }}}}return -1;
};
Copy the codeDijkstra shortest path algorithm: checks whether the path has been accessed. Here, bit operation is used to judge the check bit, and the shortest path is finally obtained by trying in different directions for key nodes
2020.10.23
No.1138 Path on the word board
We start from the position (0, 0) on a word board. The coordinate corresponds to the character board[0][0].
Board = [“abcde”, “fghij”, “klmno”, “PQRST “, “uvwxy”, “z”]
We can act according to the following directive rules:
If the square exists, ‘U’ means to move our position up one row; If the square exists, ‘D’ means to move our position down one row; If the square exists, ‘L’ means to move our position one column to the left; If the square exists, ‘R’ means to move our position one column to the right; ‘! ‘adds the character board[r][c] at our current position (r, c) to the answer. (Note that only alphabetic positions exist on the alphabet board.)
Return a sequence of instructions with the smallest number of actions to match the target. You can return to any path you want to take.
Example 1:
Input: target = “LEet” Output: “DDR! UURRR!! DDD!” Example 2:
Input: target = “code” Output: “RR! DDRR! UUL! R!”
Tip:
1 <= target.length <= 100 The target contains only lowercase letters.
Source: LeetCode link: leetcode-cn.com/problems/al… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution a:
/* * @lc app=leetcode.cn id=1138 lang=javascript * * [1138] Path on the font */
// @lc code=start
/ * * *@param {string} target
* @return {string}* /
var alphabetBoardPath = function(target) {
// Construct a hash table of letters
let hashTable = {},
stack = 'abcdefghijklmnopqrstuvwxyz'.split(' ').reverse();
for( let i = 0; i <= 5; i++ ) {
for( let j = 0; j <= 4; j++ ) {
let key = stack.pop();
if( key ) { hashTable[key] = [i, j]; }}};// Create a linked list structure for target
let list = [[0.0]];
target.split(' ').forEach(l= > {
list.push(hashTable[l]);
});
console.log(list);
const mapPos = ( pos1, pos2 ) = > {
// Destruct the array position
const [ x1, y1 ] = pos1,
[ x2, y2 ] = pos2,
xn = Math.abs(x1 - x2), // The absolute value of the unit of constant coordinate difference
yn = Math.abs(y1 - y2); // The absolute value of the difference unit of the ordinate
let r = ' ';
// If z is the starting point => up and then right; // If z is the starting point => up and then right; // If z is the starting point => up and then right; If z is the destination => first left and then bottom
if ( x2 - x1 < 0 ) {
r += 'U'.repeat(xn)
};
if ( y2 - y1 > 0 ) {
r += 'R'.repeat(yn)
};
if ( y2 - y1 < 0 ) {
r += 'L'.repeat(yn)
};
if( x2 - x1 > 0 ) {
r += 'D'.repeat(xn)
};
return r + '! ';
};
// Iterates through the list to get the values of adjacent spacing, and returns the final result
let result = ' ';
for(let p1=0,p2=1; p2<list.length; p1++,p2++) { result += mapPos(list[p1], list[p2]); };return result;
};
Copy the codeScheme 2:
/* * @lc app=leetcode.cn id=1138 lang=javascript * * [1138] Path on the font */
// @lc code=start
/ * * *@param {string} target
* @return {string}* /
var alphabetBoardPath = function (target) {
const mapManu = (p1, p2) = > {
// The distance from 'a'
const LETTER_A = 'a'.charCodeAt();
p1 -= LETTER_A;
p2 -= LETTER_A;
let r = ' ';
const dy = Math.floor(p1 / 5) - Math.floor(p2 / 5),
dx = p1 % 5 - p2 % 5;
if (dy > 0) r += 'U'.repeat(dy)
if (dx < 0) r += 'R'.repeat(-dx)
if (dx > 0) r += 'L'.repeat(dx)
if (dy < 0) r += 'D'.repeat(-dy)
return r + '! ';
};
let res = ' ',
p1 = 'a'.charCodeAt();
for (let i = 0; i < target.length; i++) {
res += mapManu(p1, target[i].charCodeAt());
p1 = target[i].charCodeAt();
}
return res;
};
Copy the codeThere are two main solutions: 1. Construct the hash table, search the letters in the target, get the position order coordinates, map the position of the coordinates and output the answer. Pay attention to the processing direction order of ‘z’ in the last row; 2. 2. Do not build a hash table, but use division and remainder to process the distance between each letter in target and ‘a’ to output the final answer
Conclusion:
- The path problem is mainly used in the general solution method is dynamic programming, need to consider the boundary problem and the induction of the state transition equation of each problem;
- For some special scenarios, we can consider permutation combination, Dijkstra algorithm, hash table and other data structure and algorithm deformation extension
Four, the interval problem
2020.10.28
No.56 Merge intervals
Given a set of intervals, merge all overlapping intervals.
Example 1:
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 17]] output: [[1, 6], [8, 10], [15, 17]] : interval [1, 3] and [2, 6] overlap, merge them into [1, 6]. Example 2:
Input: intervals = [[1, 4], [4, 5]] output: [[1, 5]] : interval [1, 4] and [4, 5] can be seen as overlapping range. Note: The input type changed on April 15, 2019. Reset the default code definition to get the new method signature.
Tip:
intervals[i][0] <= intervals[i][1]
Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution a:
/* * @lc app=leetcode.cn id=56 lang=javascript * * [56] Merge interval */
// @lc code=start
/ * * *@param {number[][]} intervals
* @return {number[][]}* /
var merge = function(intervals) {
// In ascending order by left boundary
intervals.sort((a,b) = > a[0] - b[0]);
// Get the desired subarray location
let rIndex = [];
for( let p = 0; p < intervals.length; p++ ) {
if ( isOverlap(intervals[p], intervals[p+1]) ) {
intervals.splice(p+1.1, mergeOverlap(intervals[p], intervals[p+1]));
} else {
rIndex.push(p)
}
};
// Return the interval that meets the requirements
let r = [];
for(let i=0; i<rIndex.length; i++) { r.push(intervals[rIndex[i]]) }return r;
// Determine whether the two arrays overlap
function isOverlap( arr1, arr2 ) {
if(! arr1 || ! arr2)return false;
const [ a1, b1 ] = arr1,
[ a2, b2 ] = arr2;
if( ( a1 <= a2 && a2 <= b1 && b1 <= b2 ) || ( a1 <= a2 && b2 <= b1 ) || ( a2 <= a1 && b1 <= b2 ) || ( a2 <= a1 && a1 <= b2 && b2 <= b1 ) ) {return true;
}
return false;
};
// Overlap the two arrays to merge
function mergeOverlap(arr1, arr2) {
const a = [...arr1, ...arr2].sort((a,b) = > a-b);
return [ a[0], a[ a.length - 1]]. }};Copy the codeScheme 2:
/* * @lc app=leetcode.cn id=56 lang=javascript * * [56] Merge interval */
// @lc code=start
/ * * *@param {number[][]} intervals
* @return {number[][]}* /
var merge = function(intervals) {
intervals.sort((a, b) = > a[0] - b[0]);
let res = [];
let idx = -1;
for (let interval of intervals) {
if (idx == -1 || interval[0] > res[idx][1]) {
res.push(interval);
idx++;
} else {
res[idx][1] = Math.max(res[idx][1], interval[1]); }}return res;
};
Copy the codeThere are two solutions: 1. Judge one by one and record the position. The overlapped interval will be replaced by the last merged position, and the original array will be changed; 2. 2. Optimization Scheme 1: For the array sorted by increasing the left boundary of the interval, only the size of the right boundary of the last bit and the previous boundary of the last bit need to be judged. For the right boundary that satisfies the overlap rule, the maximum value should be taken
2020.10.29
No.57 Insert interval
Give a non-overlapping list of intervals sorted by the beginning endpoint of the interval.
To insert a new interval in the list, you need to make sure that the intervals in the list are still ordered and do not overlap (merge the intervals if necessary).
Example 1:
Input: intervals = [[1, 3], [6, 9]], newInterval = (2, 5) output: [[1, 5], [6, 9]] example 2:
Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12 dec]], newInterval = [4, 8] output: [[1, 2], [3, 10], [12 dec]] : This is because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Note: The input type changed on April 15, 2019. Reset to the default code definition to get the new method signature.
Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution a:
/* * @lc app=leetcode.cn id=57 lang=javascript * * [57] Insert interval */
// @lc code=start
/ * * *@param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}* /
var insert = function(intervals, newInterval) {
// If the original array is empty, push the new array directly
if(! intervals.length)return [newInterval];
const [ left, right ] = newInterval;
// Set the left and right Pointers
let p1 = 0,
p2 = intervals.length - 1;
if( getPos(right, intervals[0= =])'l' ) {
return [ newInterval, ...intervals ]
} else if ( getPos(left, intervals[intervals.length-1= =])'r' ) {
return [ ...intervals, newInterval ]
}
while( p1 <= p2 ) {
if ( getPos( left, intervals[p1] ) == 'r' ) {
p1++;
} else if ( getPos( right, intervals[p2] ) == 'l' ) {
p2--;
} else {
intervals.splice(p1, p2-p1+1[Math.min(left, intervals[p1][0]),Math.max(right, intervals[p2][1]]);break; }};if( p1 > p2 ) intervals.splice(p1,0,newInterval)
return intervals;
function getPos( num, arr ) {
if( num < arr[0]) {return 'l';
} else if ( num > arr[1]) {return 'r';
} else if ( num >= arr[0] && num <= arr[1]) {return 'm'; }}};Copy the codeScheme 2:
/* * @lc app=leetcode.cn id=57 lang=javascript * * [57] Insert interval */
// @lc code=start
/ * * *@param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}* /
var insert = function(intervals, newInterval) {
intervals.push(newInterval);
// In ascending order by left boundary
intervals.sort((a,b) = > a[0] - b[0]);
// Get the desired subarray location
let rIndex = [];
for( let p = 0; p < intervals.length; p++ ) {
if ( isOverlap(intervals[p], intervals[p+1]) ) {
intervals.splice(p+1.1, mergeOverlap(intervals[p], intervals[p+1]));
} else {
rIndex.push(p)
}
};
// Return the interval that meets the requirements
let r = [];
for(let i=0; i<rIndex.length; i++) { r.push(intervals[rIndex[i]]) }return r;
// Determine whether the two arrays overlap
function isOverlap( arr1, arr2 ) {
if(! arr1 || ! arr2)return false;
const [ a1, b1 ] = arr1,
[ a2, b2 ] = arr2;
if( ( a1 <= a2 && a2 <= b1 && b1 <= b2 ) || ( a1 <= a2 && b2 <= b1 ) || ( a2 <= a1 && b1 <= b2 ) || ( a2 <= a1 && a1 <= b2 && b2 <= b1 ) ) {return true;
}
return false;
};
// Overlap the two arrays to merge
function mergeOverlap(arr1, arr2) {
const a = [...arr1, ...arr2].sort((a,b) = > a-b);
return [ a[0], a[ a.length - 1]]. }};Copy the codeThere are two schemes: 1, the first and last pointer: the new array left and right boundary and the original array of each interval for position comparison, in the interval left, interval, interval right three cases are respectively processed, maximum use of the original array to merge or increase operation; 2. First insert, then sort and then merge. Using the solution of problem 56, you only need to arrange the new array in ascending order according to the left side of the interval after insertion, and then merge the overlapped intervals
2020.10.30
No.228 Summary interval
Given an ordered integer array nums with no repeating elements.
Returns a list of the least ordered ranges that exactly cover all the numbers in the array. That is, every element of NUMS is covered by exactly some range, and there is no number X that belongs to a range but does not belong to NUMS.
Each interval range [a,b] in the list should be printed in the following format:
“A ->b”, if a! = b “a”, if a == b
Example 1:
Input: nums =,1,2,4,5,7 [0] output: [” 0 – > 2 “, “4 – > 5”, “7”] to explain: the range is: [0, 2] — > “0 – > 2” (4, 5) – > “4 – > 5 [7, 7]” – > “7” sample 2:
Input: nums =,2,3,4,6,8,9 [0] output: [” 0 “, “2 – > 4”, “6”, 8 – > “9”] : range is: [0, 0] – > “0” (2, 4] – > 2 – > 4 “[6] – > [8, 9]” 6 “- >” 8 – > 9 “example 3:
Input: nums = [] Output: [] Example 4:
Input: nums = [-1] Output: [“-1”] Example 5:
Input: nums = [0] Output: [“0”]
Tip:
Length <= 20-231 <= nums[I] <= 231-1 All values in nums are different from each other
Source: LeetCode link: leetcode-cn.com/problems/su… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Solution a:
/* * @lc app=leetcode.cn id=228 lang=javascript * * [228] Summary interval */
// @lc code=start
/ * * *@param {number[]} nums
* @return {string[]}* /
var summaryRanges = function(nums) {
if( nums.length == 0 ) {
return [];
} else if ( nums.length == 1 ) {
return [ nums[0] + ' ']}else {
let rIndex = [],
r = [],
/ / double pointer
p1 = 0,
p2 = 1;
while ( p2 < nums.length ) {
if( nums[p2] - nums[p1] == ( p2 - p1 ) ) {
p2++
} else {
rIndex.push(p2);
p1 = p2;
p2++;
}
}
rIndex.unshift(0);
rIndex.push(nums.length);
// Construct an r array
for(let t1=0,t2=1; t2<rIndex.length; t1++,t2++) { r.push(nums.slice(rIndex[t1],rIndex[t2])) } r = r.map(item= > {if(item.length==1) {return item[0] + ' '}else{ return item[0] + '- >' + item[item.length-1]}});
returnr; }};Copy the codeScheme 2:
/* * @lc app=leetcode.cn id=228 lang=javascript * * [228] Summary interval */
// @lc code=start
/ * * *@param {number[]} nums
* @return {string[]}* /
var summaryRanges = function(nums) {
const res = [];
nums.push(Infinity);
for (let i = 0, j = 1; j < nums.length; j++) {
if (nums[j] - 1! == nums[j -1]) {
res.push(i === j - 1 ? ' ' + nums[i] : `${nums[i]}->${nums[j - 1]}`); i = j; }}return res;
};
Copy the codeDouble pointer to move the window, there are two ways to write: 1, get the cut point, the cut out of the array format conversion; 2,
Conclusion:
- The common practice of interval problem is to judge the left and right position of interval by double pointer, and some boundary problems need to be dealt with.
- For some special scenarios, dynamic programming and general formula can be considered
