Guide to series of articles
Open source project
All articles in this series will be included in GitHub for unified collection and management. Welcome ISSUE and Star.
GitHub portal: Kiner algorithm
preface
After understanding the core concept of search algorithm, knowing what problem solving tree is, and mastering the characteristics and implementation ideas of deep search and wide search, we will brush the questions for deep search and wide search respectively.
Programming skills extension
Direction / offset array
// As shown in the following two-dimensional array, there are four possibilities to move $one step: // 1. Move up one step, i.e. y coordinate - 1, x coordinate unchanged (0, - 1) // 2. Move one step to the left, that is, the x coordinate is - 1, and the y coordinate remains unchanged (- 1,0) // 3. Move down one step, that is, y coordinate + 1, and x coordinate remains unchanged (0,1) // 4. Move one step to the right, that is, the x coordinate + 1, and the y coordinate remains unchanged (1,0) const arr = [ [ *, (0,-1), * ], [(-1,0), $, (1,0) ], [ *, (0,1), * ], ]; // According to the above, we can get a direction array or offset array, which is the offset of the current node to reach the next node x and y const direction = [ [0,-1], [-1,0], [0,1], [1,0] ]; // With this direction array, we can traverse and solve the behavior of any point moving
Deep search
993. Cousin node of binary tree
Problem solving ideas
This problem can use both depth first search and breadth first search. We first use depth first to solve this problem, and then use breadth first search when it comes to breadth first search.
First, to judge whether two nodes are cousins, we need to meet the following two conditions
- The level of the two nodes is the same, that is, the generation is the same
- The parent nodes of two nodes are different and cannot be siblings
After the purpose is clear, we will start to design the depth first search function:
First, we need to confirm the status of our problem solving tree: the level of the target node and the parent of the target node.
After clarifying the status of the problem solving tree, we only need to implement a depth first method that allows us to clearly obtain the target node level and parent node. See the code implementation for the specific implementation logic.
code implementation
/*
* @lc app=leetcode.cn id=993 lang=typescript
*
* [993] Cousin node of binary tree
*
* https://leetcode-cn.com/problems/cousins-in-binary-tree/description/
*
* algorithms
* Easy (55.74%)
* Likes: 222
* Dislikes: 0
* Total Accepted: 47.8K
* Total Submissions: 85.8K
* Testcase Example: '[1,2,3,4]\n4\n3'
*
* In the binary tree, the root node is at depth 0, and the child node of each node with depth k is at depth k+1.
*
* If two nodes of a binary tree have the same depth but different parent nodes, they are a pair of cousin nodes.
*
* We give the root node of a binary tree with unique values, and the values x and y of two different nodes in the tree.
*
* true is returned only if the node corresponding to the values x and y is a cousin node. Otherwise, false is returned.
*
*
*
* Example 1:
*
*
*
* Input: root = [1,2,3,4], x = 4, y = 3
* Output: false
*
*
* Example 2:
*
*
*
* Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
* Output: true
*
*
* Example 3:
*
*
*
*
* Input: root = [1,2,3,null,4], x = 2, y = 3
* Output: false
*
*
*
* Tips:
*
*
* The number of nodes in the binary tree is between 2 and 100.
* The value of each node is a unique integer ranging from 1 to 100.
*
*
*
*
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
// Define an auxiliary structure to store the reference of the parent node of the node
type InfoStruct = {
father: TreeNode | null
};
/**
* Depth first search
* @param root Root node
* @param x Target value to be found
* @param info Helper object, used to store the reference of the parent node of the current node during recursive search
* @returns
*/
function dfs(root: TreeNode | null, x: number, info: InfoStruct): number {
// When the root node is empty, it is impossible to find the target node, and - 1 is returned
if(!root) return -1;
// When the root node is the target value, it returns 0, which means that the target node is found in layer 0, followed by the layer where the root node is located, that is, 1. Therefore, it can be marked as 0 here
if(root.val === x) return 0;
// Prepare the recursive left subtree. In order to always store the reference of the parent node of the current node, borrow the info object to store
info.father = root;
// Recursive search left subtree
const l = dfs(root.left, x, info);
// If the target node can be found in the left subtree, the number of layers where the target node is found in the left subtree plus the number of layers of the root node 1 will be returned
if(l>=0) return l+1;
// After searching the left subtree, prepare to search the right subtree for backtracking reset
info.father = root;
const r = dfs(root.right, x, info);
if(r>=0) return r+1;
// If the left and right subtrees are not found, return - 1
return -1;
}
function isCousins(root: TreeNode | null, x: number, y: number): boolean {
// To determine whether the two nodes are cousins, you need to determine the following two points:
// 1. The two nodes have the same level
// 2. The parent nodes of the two nodes are different
// We need to use depth first search to search the target node and return to the level of the target node
let d1,d2;
// Define two helper objects to store the parent node reference of the target node
const info1: InfoStruct = {
father: null
}
const info2: InfoStruct = {
father: null
}
// Use depth first search to obtain the target node level respectively
d1 = dfs(root, x, info1);
d2 = dfs(root, y, info2);
// If the level is the same and the parent node is different, it means it is a cousin node
return d1 === d2 && info1.father !== info2.father;
};
// @lc code=end
130. Surrounding areas
Problem solving ideas
We need some reverse thinking in this problem. The problem requires us to find all o surrounded by X and mark it as X. then, we can think in turn, what o is not surrounded by X? Is it the o on our four sides and the o connected to it? In fact, we can find these o not surrounded by X and mark them as o first. Then, all the remaining o is surrounded by X. So, next, let's see how to use deep search to solve this problem.
code implementation
/*
* @lc app=leetcode.cn id=130 lang=typescript
*
* [130] Surrounded area
*
* https://leetcode-cn.com/problems/surrounded-regions/description/
*
* algorithms
* Medium (43.50%)
* Likes: 554
* Dislikes: 0
* Total Accepted: 107.5K
* Total Submissions: 247.1K
* Testcase Example: '[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]'
*
* Give you a matrix board of m x n, which consists of several characters' X 'and' O ', find all areas surrounded by' X ', and use' X 'for all' O 'in these areas
* fill.
*
*
*
*
* Example 1:
*
*
* Input: board=
* [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
* Output: ["X", "X", "X", "X"], ["X", "X", "X"], ["X", "X", "X"], ["X", "O", "X", "X"]]
* Explanation: the enclosed interval will not exist on the boundary. In other words, the 'O' on any boundary will not be filled with 'X'. Any 'O' that is not on or connected to the 'O' on the boundary
* Will eventually be filled with 'X'. If two elements are adjacent horizontally or vertically, they are said to be "connected".
*
*
* Example 2:
*
*
* Input: board = [["X"]]
* Output: ["X"]]
*
*
*
*
* Tips:
*
*
* m == board.length
* n == board[i].length
* 1
* board[i][j] Is' X 'or' O '
*
*
*
*
*/
// @lc code=start
/**
Do not return anything, modify board in-place instead.
*/
// The direction array is used to solve the possibility of taking one step in any coordinate, that is, the offset possibility of taking one step in any coordinate
const direction: number[][] = [
[0, 1],// Take a step down
[1, 0],// Take a step to the right
[-1, 0],// Take a step to the left
[0, -1]// Take a step up
];
// The number of rows and columns of the global record matrix
let row: number, col: number;
function dfs(i: number, j: number, board: string[][]) {
// If you can enter this method, it indicates that it is the o of the four sides or the o connected to the four sides. Directly mark this o as O
board[i][j] = 'o';
// Radiate up, down, left and right with the current node, find all o's connected to the O's of the four sides and mark them as O
for (let k = 0; k < direction.length; k++) {
// Calculate the coordinates of the next state
const x = i + direction[k][0];
const y = j + direction[k][1];
// Legitimacy judgment of next state coordinates
if (x < 0 || x >= row) continue;
if (y < 0 || y >= col) continue;
if (board[x][y] !== 'O') continue;
// Recursively process the next state
dfs(x, y, board);
}
}
function solve(board: string[][]): void {
// Initialize rows and columns
row = board.length, col = board[0].length;
// The next step is to search for O on four sides
// Traverse the first and last columns of each row to find the coordinates of O, and then use dfs to continue to search for the o connected to it
for (let i = 0; i < row; i++) {
if (board[i][0] === 'O') dfs(i, 0, board);
if (board[i][col - 1] === 'O') dfs(i, col - 1, board);
}
// Traverse the first and last rows of each column to find the coordinates of O, and then use dfs to continue to search the o connected to it
for (let i = 0; i < col; i++) {
if (board[0][i] === 'O') dfs(0, i, board);
if (board[row - 1][i] === 'O') dfs(row - 1, i, board);
}
// Above, we have marked the points on the four edges as O and the points connected with O on the edge as O, and then scan the whole matrix again to mark all the nodes marked as O
// Mark it as X, and then mark all nodes marked as o as O
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (board[i][j] === 'O') board[i][j] = 'X';
else if (board[i][j] === 'o') board[i][j] = 'O';
}
}
};
// @lc code=end
494. Objectives and objectives
Problem solving ideas
Because the title allows the use of + and - operations, a key point of our goal sum is how to calculate the state of i+1 from the ith state and when to terminate the program. The termination procedure is very simple. It has been done before Sum of two numbers We should all have ideas. If we add, we need to eliminate the current number from the target value target every time. If it is subtraction, we need to add the current number back to the target value target every time. When the array traversal ends and the target is 0, it means that we have found a set of solutions, otherwise the current solution is incorrect.
Code demonstration
/*
* @lc app=leetcode.cn id=494 lang=typescript
*
* [494] Objectives and
*
* https://leetcode-cn.com/problems/target-sum/description/
*
* algorithms
* Medium (49.62%)
* Likes: 809
* Dislikes: 0
* Total Accepted: 121.5K
* Total Submissions: 244.8K
* Testcase Example: '[1,1,1,1,1]\n3'
*
* Give you an integer array nums and an integer target.
*
* Add '+' or '-' before each integer in the array, and then concatenate all integers to construct an expression:
*
*
* For example, nums = [2, 1], you can add '+' before 2 and '-' before 1, and then concatenate them to get the expression "+ 2-1".
*
*
* Returns the number of different expressions that can be constructed by the above method and whose operation result is equal to target.
*
*
*
* Example 1:
*
*
* Input: num = [1,1,1,1,1], target = 3
* Output: 5
* Explanation: there are 5 ways to make the final goal and 3.
* -1 + 1 + 1 + 1 + 1 = 3
* +1 - 1 + 1 + 1 + 1 = 3
* +1 + 1 - 1 + 1 + 1 = 3
* +1 + 1 + 1 - 1 + 1 = 3
* +1 + 1 + 1 + 1 - 1 = 3
*
*
* Example 2:
*
*
* Input: num = [1], target = 1
* Output: 1
*
*
*
*
* Tips:
*
*
* 1
* 0
* 0
* -1000
*
*
*/
// @lc code=start
function dfs1(i: number, target: number, nums: number[]): number {
// When traversing to the end, if target===0, it indicates that a group of solutions have been found, and 1 is returned; otherwise, 0 is returned
if(i === nums.length) return +(target===0);
// Accumulation scheme
let res = 0;
// When processing the + sign, you should subtract this number from the target value
res += dfs1(i+1, target - nums[i], nums);
// When processing the - sign, you should add this number to the target value
res += dfs1(i+1, target + nums[i], nums);
return res;
}
function findTargetSumWays(nums: number[], target: number): number {
return dfs1(0, target, nums);
};
// @lc code=end
However, you can find that although the above method is easy to understand, it is inefficient. I wonder if you still remember that when we talked about the bisection algorithm, we talked about the concept that functions are compressed arrays and arrays are expanded functions. Students who do not understand it can go and have a look 10.1 - binary search Now, let's use this concept to optimize our program.
Let's think about it. The function for solving the target value in our above method is res = f(i,target). In fact, the num of the function is only used to get data, which has nothing to do with our problem solving tree. Then, according to the concept that an array is a compressed function, can we have an array such that res = arr[i,target], that is, i pass in the values of i and target. If there are values in the array, we will return them directly. This will reduce a lot of unnecessary branching operations, which is what we said before. The following code uses a map < i ^ target, res > (as we said before, the bottom layer of the map is a hash table, and the hash table is to map an arbitrary type of data to the array subscript. The actual data is still stored in the array.) Such a hash table is used to cache our calculation results. If it can be found through i and target, it will be returned directly. If not, after calculation, we will store the results in the map. To sum up: we can use the subtle relationship between the function and the array to exchange space for time in the form of memorization, so as to improve the running efficiency of the program. In this problem, memorization helps us cut out the repeated branches of the calculated results before
/*
* @lc app=leetcode.cn id=494 lang=typescript
*
* [494] Objectives and
*
* https://leetcode-cn.com/problems/target-sum/description/
*
* algorithms
* Medium (49.62%)
* Likes: 809
* Dislikes: 0
* Total Accepted: 121.5K
* Total Submissions: 244.8K
* Testcase Example: '[1,1,1,1,1]\n3'
*
* Give you an integer array nums and an integer target.
*
* Add '+' or '-' before each integer in the array, and then concatenate all integers to construct an expression:
*
*
* For example, nums = [2, 1], you can add '+' before 2 and '-' before 1, and then concatenate them to get the expression "+ 2-1".
*
*
* Returns the number of different expressions that can be constructed by the above method and whose operation result is equal to target.
*
*
*
* Example 1:
*
*
* Input: num = [1,1,1,1,1], target = 3
* Output: 5
* Explanation: there are 5 ways to make the final goal and 3.
* -1 + 1 + 1 + 1 + 1 = 3
* +1 - 1 + 1 + 1 + 1 = 3
* +1 + 1 - 1 + 1 + 1 = 3
* +1 + 1 + 1 - 1 + 1 = 3
* +1 + 1 + 1 + 1 - 1 = 3
*
*
* Example 2:
*
*
* Input: num = [1], target = 1
* Output: 1
*
*
*
*
* Tips:
*
*
* 1
* 0
* 0
* -1000
*
*
*/
// @lc code=start
function dfs1(i: number, target: number, nums: number[]): number {
// When traversing to the end, if target===0, it indicates that a group of solutions have been found, and 1 is returned; otherwise, 0 is returned
if(i === nums.length) return +(target===0);
// Accumulation scheme
let res = 0;
// When processing the + sign, you should subtract this number from the target value
res += dfs1(i+1, target - nums[i], nums);
// When processing the - sign, you should add this number to the target value
res += dfs1(i+1, target + nums[i], nums);
return res;
}
const map: Map<number, number> = new Map<number, number>();
function dfs2(i: number, target: number, nums: number[]): number {
// When traversing to the end, if target===0, it indicates that a group of solutions have been found, and 1 is returned; otherwise, 0 is returned
if(i === nums.length) return +(target===0);
// Get the result from the hash table. If you can get the result, you can return it directly without calculation
// As we said before, the bottom layer of the map in js is a hash table. Now we need to
// Our state i and target generate a unique value as a key for the hash function to generate an index map
// Here, we directly use bitwise operation: the result of bitwise and operation on two numeric types as the key value
const ans = map.get(i ^ target);
if(ans) {
return ans;
}
// Accumulation scheme
let res = 0;
// When processing the + sign, you should subtract this number from the target value
res += dfs1(i+1, target - nums[i], nums);
// When processing the - sign, you should add this number to the target value
res += dfs1(i+1, target + nums[i], nums);
// Store the results to facilitate the subsequent memory retrieval of previous answers. This method is similar to using the cache method to calculate the Fibonacci number
map.set(i ^ target, res);
return res;
}
function findTargetSumWays(nums: number[], target: number): number {
map.clear();
return dfs2(0, target, nums);
};
// @lc code=end
473. Match square
Problem solving ideas
This problem requires us to make a square with matches. Then, let's assume that there are four matchboxes. The capacity of each Matchbox n = the total length of matches m / 4. We can try to put each match into the matchbox in turn. If all four matchboxes can be filled when all matches are used up, it means that they can be made into a square, otherwise they can't be made. When placing matches in the matchbox, we try to put the longer matches first. When there is still room for matches in a matchbox, we have to see if the remaining space can hold our shortest matches. If the shortest matches can't be put, we don't need to try. We can't make a square. In this way, we can prune some explicit search branches without solutions. The state of the problem solving tree of this problem is actually composed of the index of the current match and the remaining capacity of the matchbox.
Code demonstration
/*
* @lc app=leetcode.cn id=473 lang=typescript
*
* [473] Match square
*
* https://leetcode-cn.com/problems/matchsticks-to-square/description/
*
* algorithms
* Medium (41.37%)
* Likes: 185
* Dislikes: 0
* Total Accepted: 17.6K
* Total Submissions: 42.4K
* Testcase Example: '[1,1,2,2,2]'
*
*
* Remember the fairy tale little match girl? Now, you know how many matches the little girl has. Please find a way to use all the matches to make a square. You can't break matches, you can connect them, and each match needs to be used.
*
* Enter the number of matches that the little girl has. Each match is expressed by its length. The output is whether all matches can be used to make a square.
*
* Example 1:
*
*
* Input: [1,1,2,2,2]
* Output: true
*
* Explanation: it can make a square with 2 sides and two matches on each side.
*
*
* Example 2:
*
*
* Input: [3,3,3,3,4]
* Output: false
*
* Explanation: you can't make a square with all matches.
*
*
* be careful:
*
*
* The given match length and are between 0 and 10 ^ 9.
* The length of the match array does not exceed 15.
*
*
*/
// @lc code=start
/**
* Deep search
* @param idx Which match is it now
* @param arr Matchbox array
* @param ms Original match array
*/
function dfs(idx: number, arr: number[], ms: number[]): boolean {
// If all the matches are finished, it means that we can fill all the matchboxes (because the total capacity of the matchbox is equal to the total length of the matches)
// If the matches are over and the matchbox is not full, it means that the total capacity of the matchbox is not equal to the total length of the matches, which is different from what we just started
// Contrary to the design, it is impossible
if(idx < 0) return true;
// We put matches into the matchbox in turn
for(let i=0;i<arr.length;i++) {
// If the current match cannot be put into the current matchbox, try the next matchbox
if(arr[i] < ms[idx]) continue;
// If the current match can be put into the current Matchbox or after the current match is put into the matchbox, the matchbox can hold at least the shortest match
// Then we put the matches in the current matchbox. Why should the margin be at least greater than the shortest match? Because if the margin of the matchbox is the shortest
// If we can't put all the matches, we can't fill this matchbox, so we can abandon this attempt and search and prune
if(arr[i] === ms[idx] || arr[i] >= ms[idx] + ms[0]) {
// Put the match into the matchbox. The capacity of the matchbox reduces the length of the match
arr[i] -= ms[idx];
// Continue the next round of attempts. If the matches can be put into subsequent attempts normally, it indicates that this attempt is correct and returns true directly
if(dfs(idx - 1, arr, ms)) return true;
// If the later attempt fails, we should take the current match out of the matchbox and try other matches
arr[i] += ms[idx];
}
}
// If all matchboxes cannot be filled after the above attempts, it means that they cannot be spliced into a square
return false;
}
function makesquare(matchsticks: number[]): boolean {
// If the number of matches is less than 4, there is no solution
if(matchsticks.length<4) return false;
// Find the capacity of a single matchbox
const sum = matchsticks.reduce((a,b) => a+b, 0);
// If the total length of the match is not 0 with the modulus of 4, because the title says that the match cannot be broken, it is certainly impossible to splice it into a square
if(sum % 4) return false;
// Initialize four matchboxes. Each Matchbox contains the remaining matches of the current matchbox
const arr: number[] = new Array(4);
const v = sum / 4;
// Initialize the capacity of each matchbox
arr.fill(v);
// In order to put the longer matches into the matchbox as much as possible, we first sort the original match array from small to large
// Then the match from the back to the front
matchsticks.sort((a, b) => a-b);
// Because our matches are sorted from short to long, we first take out the longest match to try
return dfs(matchsticks.length - 1, arr, matchsticks);
};
// @lc code=end
39. Combination sum
Problem solving ideas
We still use deep search to solve this problem, so what is the status of this problem? It should be a state composed of the number currently in use and the current target and value. Note that each time you select a number, there are two options: use the current number and not use the current number
Code demonstration
/*
* @lc app=leetcode.cn id=39 lang=typescript
*
* [39] Combined sum
*
* https://leetcode-cn.com/problems/combination-sum/description/
*
* algorithms
* Medium (72.49%)
* Likes: 1393
* Dislikes: 0
* Total Accepted: 273.3K
* Total Submissions: 376.9K
* Testcase Example: '[2,3,6,7]\n7'
*
* Given an array of candidates without duplicate elements and a target number target, find all combinations in candidates that can make the sum of numbers target.
*
* candidates The numbers in can be selected repeatedly without limit.
*
* explain:
*
*
* All numbers (including target) are positive integers.
* The solution set cannot contain duplicate combinations.
*
*
* Example 1:
*
* Input: candidates = [2,3,6,7], target = 7,
* The solved set is:
* [
* [7],
* [2,2,3]
* ]
*
*
* Example 2:
*
* Input: candidates = [2,3,5], target = 8,
* The solved set is:
* [
* [2,2,2,2],
* [2,3,3],
* [3,5]
* ]
*
*
*
* Tips:
*
*
* 1 <= candidates.length <= 30
* 1 <= candidates[i] <= 200
* candidate Each element in is unique.
* 1 <= target <= 500
*
*
*/
// @lc code=start
function dfs(idx: number, target: number, buff: number[], nums: number[], res: number[][]){
// Because all numbers are positive, if the target is less than zero, there is no solution in this round of search
if(target < 0) return
// If the target is exactly 0, a set of answers has been found and added to the result array
if(target === 0) {
// Note that because the js array is a reference relationship, you can't directly push the buff array, but copy a new array
res.push([...buff]);
return;
}
// If the array traverses to the end and the target is still not 0, there is no solution
if(idx === nums.length) return;
// At this point, we have to try to either use the current number or not use the current number
// If the current number is not used, the index is directly increased by 1, and the target value remains unchanged
// Why not make any judgment here and use dfs recursive calls twice?
// Because the first case is not to use the current number, we directly recursively match the next number. If there is a result of the matching, our result has been changed
// Added to the result array. If there is no result, the result array will not change, so it will not affect the following recursive calls using the current number
dfs(idx + 1, target, buff, nums, res);
// Using the current number
buff.push(nums[idx]);
dfs(idx, target - nums[idx], buff, nums, res);
// After use, pop up the current number and continue to try the next number
buff.pop();
}
function combinationSum(candidates: number[], target: number): number[][] {
const buff: number[] = [];
const res: number[][] = [];
dfs(0, target, buff, candidates, res);
return res;
};
// @lc code=end
Wide search
993. Cousin node of binary tree
Problem solving ideas
Above, we use deep search to realize the method of judging whether the two nodes are cousins. Next, we use wide search to realize it. First, the first step is to define the status:
When using search solution, we define a user-defined Data structure Data as our state. This self-defined structure contains the desired node depth, the current node, the parent node of the current node and other information.
Code demonstration
/*
* @lc app=leetcode.cn id=993 lang=typescript
*
* [993] Cousin node of binary tree
*
* https://leetcode-cn.com/problems/cousins-in-binary-tree/description/
*
* algorithms
* Easy (55.74%)
* Likes: 222
* Dislikes: 0
* Total Accepted: 47.8K
* Total Submissions: 85.8K
* Testcase Example: '[1,2,3,4]\n4\n3'
*
* In the binary tree, the root node is at depth 0, and the child node of each node with depth k is at depth k+1.
*
* If two nodes of a binary tree have the same depth but different parent nodes, they are a pair of cousin nodes.
*
* We give the root node of a binary tree with unique values, and the values x and y of two different nodes in the tree.
*
* true is returned only if the node corresponding to the values x and y is a cousin node. Otherwise, false is returned.
*
*
*
* Example 1:
*
*
*
* Input: root = [1,2,3,4], x = 4, y = 3
* Output: false
*
*
* Example 2:
*
*
*
* Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
* Output: true
*
*
* Example 3:
*
*
*
*
* Input: root = [1,2,3,null,4], x = 2, y = 3
* Output: false
*
*
*
* Tips:
*
*
* The number of nodes in the binary tree is between 2 and 100.
* The value of each node is a unique integer ranging from 1 to 100.
*
*
*
*
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
// Define an auxiliary structure to store the reference of the parent node of the node
type InfoStruct = {
father: TreeNode | null
};
// Define problem solving tree status
type Data = {
node: TreeNode | null,// Current node
father: TreeNode | null,// Parent node
depth: number// The level of the current node
};
function isCousins(root: TreeNode | null, x: number, y: number): boolean {
// To determine whether the two nodes are cousins, you need to determine the following two points:
// 1. The two nodes have the same level
// 2. The parent nodes of the two nodes are different
let d1,d2;
// This is the status of breadth first search
const info: Data = {
father: null,
node: root,
depth: 0
}
// Define two helper objects to store the parent node reference of the target node
const info1: InfoStruct = {
father: null
}
const info2: InfoStruct = {
father: null
}
// Set a queue to assist breadth first search
const queue: Data[] = [];
// Add the root node to the queue first
queue.push(info);
// As long as the queue is not empty, it will loop all the time
while(queue.length) {
// Pop up team leader element
const cur = queue.shift();
// Judge whether the currently popped node value matches x or y. if yes, update x and Info1 respectively Father and y, info2 father
if(cur.node.val === x) d1 = cur.depth,info1.father = cur.father;
if(cur.node.val === y) d2 = cur.depth,info2.father = cur.father;
// When the answer is found during the cycle, there is no need to continue the cycle and end it directly
if(d1 === d2 && info1.father !== info2.father) return true;
// If there is a left subtree, press the root node of the left subtree into the queue
if(cur.node.left) queue.push({
node: cur.node.left,
depth: cur.depth+1,
father: cur.node
});
// If there is a right subtree, press the root node of the right subtree into the queue
if(cur.node.right) queue.push({
node: cur.node.right,
depth: cur.depth+1,
father: cur.node
});
}
// Determine whether the same level and different parents
return d1 === d2 && info1.father !== info2.father;
};
// @lc code=end
542.01 matrix
Problem solving ideas
When you see the nearest distance in the topic, you should be able to respond. What we want is the optimal solution. Without saying a word, let's use extensive search. As for the distance between each element and the nearest 0 in the title, we can change our thinking. The distance between the nearest 0 of each element is actually the same as that between each 0 and the nearest non-0 element. In this way, we can take each 0 as the starting point of the problem solving tree and keep looking down. However, in the process of searching, we need to judge the duplicate operation, because we may have visited some points, so we don't need to repeat the operation. Here, we use the programming skills of a direction (offset) array. For a detailed explanation, see the extension of programming skills in the head of this article.
Code demonstration
/*
* @lc app=leetcode.cn id=542 lang=typescript
*
* [542] 01 matrix
*
* https://leetcode-cn.com/problems/01-matrix/description/
*
* algorithms
* Medium (45.66%)
* Likes: 439
* Dislikes: 0
* Total Accepted: 53.8K
* Total Submissions: 117.8K
* Testcase Example: '[[0,0,0],[0,1,0],[0,0,0]]'
*
* Given a matrix consisting of 0 and 1, find the distance from each element to the nearest 0.
*
* The distance between two adjacent elements is 1.
*
*
*
* Example 1:
*
*
* Input:
* [[0,0,0],
* [0,1,0],
* [0,0,0]]
*
* Output:
* [[0,0,0],
* [0,1,0],
* [0,0,0]]
*
*
* Example 2:
*
*
* Input:
* [[0,0,0],
* [0,1,0],
* [1,1,1]]
*
* Output:
* [[0,0,0],
* [0,1,0],
* [1,2,1]]
*
*
*
*
* Tips:
*
*
* The number of elements of a given matrix does not exceed 10000.
* At least one element in the given matrix is 0.
* The elements in the matrix are adjacent in only four directions: up, down, left and right.
*
*
*/
// @lc code=start
type Data = {
x: number,// The x coordinate of the current element
y: number,// The y coordinate of the current element
k: number,// The distance from the current element to the nearest non-0 element
};
function initQueue(queue: Data[], n: number, m: number, visited: number[][], mat: number[][]){
for(let i=0;i<n;i++) {
visited.push([]);
for(let j=0;j<m;j++) {
// If the element of the current position is not 0, each bit of the judgment array is initially set to - 1
if(mat[i][j]){
visited[i][j] = -1;
} else {
// If the current location element is 0, it is initialized to 0
visited[i][j] = 0;
// And add the elements of the current location to the wide search queue
queue.push({
x: i,
y: j,
k: 0
});
}
}
}
}
function updateMatrix(mat: number[][]): number[][] {
// Defines the direction array, which is used to solve the result of moving any point one step
const direction = [
[0,-1],
[-1,0],
[0,1],
[1,0]
];
// Because the optimal solution is required, breadth search is used to define a Data type queue
const queue: Data[] = [];
// Due to the need for array duplication, we use an additional two-dimensional array. When an element is accessed out of date, we will mark it as 1
const visited: number[][] = [];
const n = mat.length, m = mat[0].length;
// Initialize the wide search queue and add all nodes originally 0 to the wide search queue
initQueue(queue, n, m, visited, mat);
// Circular search queue when the search queue is not empty
while(queue.length) {
const cur = queue.shift();
// Loop direction array to find each node that the current node can reach
for(let i=0;i<direction.length;i++) {
const x = cur.x + direction[i][0];
const y = cur.y + direction[i][1];
// Judge the legitimacy of the node coordinates we calculated that the current node may arrive in one step
if(x<0||x>=n) continue;
if(y<0||y>=m) continue;
if(visited[x][y]!==-1) continue;
// After the above three cases are excluded, it means that our x and y are legal and non repeated access coordinates, and we can calculate the next state
queue.push({
x,
y,
k: cur.k + 1
});
// Remember to mark in the visited array that the current node has been accessed to facilitate the next round robin judgment
visited[x][y] = cur.k + 1;
}
}
// When the whole search queue is traversed, in fact, what is stored in our visited array is the deployment that we want each node to go from the nearest 0
return visited;
};
// @lc code=end
1091. Shortest path in binary matrix
Problem solving ideas
The starting idea of this problem is the same as that of the previous problem, but it can only go up and down, left and right, and four directions of upper left, upper right, lower left and lower right have been added. A total of 8 directions can be moved. Others are similar to the previous question. Look at the code directly
Code demonstration
/*
* @lc app=leetcode.cn id=1091 lang=typescript
*
* [1091] Shortest path in binary matrix
*
* https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/description/
*
* algorithms
* Medium (37.21%)
* Likes: 105
* Dislikes: 0
* Total Accepted: 20.2K
* Total Submissions: 54.3K
* Testcase Example: '[[0,1],[1,0]]'
*
* Give you a binary matrix grid of n x n, and return the length of the shortest unblocked path in the matrix. If no such path exists, - 1 is returned.
*
* The unblocked path in the binary matrix is from the upper left cell (i.e., (0,0)) to the lower right cell (i.e., (n - 1,n)-
* 1))The path meets the following requirements at the same time:
*
*
* All cells the path passes through have a value of 0.
* All adjacent cells in the path should be connected in one of the eight directions (that is, two adjacent cells are different from each other and share an edge or corner).
*
*
* The length of the unblocked path is the total number of cells that the path passes through.
*
*
*
* Example 1:
*
*
* Input: grid = [[0,1],[1,0]]
* Output: 2
*
*
* Example 2:
*
*
* Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
* Output: 4
*
*
* Example 3:
*
*
* Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
* Output: - 1
*
*
*
*
* Tips:
*
*
* n == grid.length
* n == grid[i].length
* 1
* grid[i][j] Is 0 or 1
*
*
*/
// @lc code=start
type Data = {
x: number,
y: number,
k: number// What is the shortest path to the target point at the current time
}
function shortestPathBinaryMatrix(grid: number[][]): number {
// Offset array
const direction: number[][] = [
[0,-1],// Upward
[-1,0],// towards the left
[0,1],// down
[1,0],// towards the right
[-1,-1],// Upper left
[1,-1],// Upper right
[-1,1],// Lower left
[1,1],// lower right
];
// Define search queue
const queue: Data[] = [];
// Matrix boundary
const n = grid.length,m = grid[0].length;
// Accessed element array
const visited: number[][] = [];
for(let i=0;i<n;i++){
const tmp = new Array(m);
tmp.fill(0);
visited.push(tmp);
}
// Initialize wide search matrix
// If the point in the upper left corner itself is a non-zero number, it means that we can't start from the upper left corner, and there must be no solution
if(grid[0][0]) return -1;
// If the (0,0) point is legal, mark it
visited[0][0] = 1;
queue.push({
x: 0,
y: 0,
k: 1,// Since the topic requires a total of several steps, it should be 1 at the beginning
});
// If the wide search queue is not empty, it will enter the loop
while(queue.length) {
const cur = queue.shift();
// If the current node is already the target node, you can directly return its shortest path
if(cur.x === n - 1 && cur.y === m - 1) return cur.k;
for(let i=0;i<direction.length;i++) {
const x = cur.x + direction[i][0];
const y = cur.y + direction[i][1];
// Coordinate validity verification
if(x<0||x>=n) continue;
if(y<0||y>=m) continue;
// Yes, it's illegal
if(visited[x][y]) continue;
// The current point is not 0, which is illegal
if(grid[x][y]) continue;
// Adds the current coordinates to the accessed array
visited[x][y] = 1;
// Add the current coordinates to the search queue
queue.push({
x,
y,
k: cur.k + 1
});
}
}
// After traversing the wide search queue, there is no target point, indicating that there is no such path
return -1;
};
// @lc code=end
752. Open the turntable lock
Problem solving ideas
For this kind of unlocking problem, we should make clear what our state is. The state is actually a password string. Each time we toggle the password lock, there may be eight possibilities. Which eight? There are four locking discs in total. You can move one of them arbitrarily. These are four kinds. However, don't forget that the locking disc can be moved up and down. When you move down, it becomes larger and when you move up, it decreases. Therefore, for each locking disc, there are two state changes during one operation, so there are eight changes in total. After clarifying the state and the possibility of change, we only need to use the idea of wide search to eliminate duplicate password strings and password strings in the death list in the search process until the target password is found or the wide search queue is empty.
Code demonstration
/*
* @lc app=leetcode.cn id=752 lang=typescript
*
* [752] Open the turntable lock
*
* https://leetcode-cn.com/problems/open-the-lock/description/
*
* algorithms
* Medium (49.55%)
* Likes: 263
* Dislikes: 0
* Total Accepted: 43.9K
* Total Submissions: 88.5K
* Testcase Example: '["0201","0101","0102","1212","2002"]\n"0202"'
*
* You have a turntable lock with four round dials. Each dial wheel has 10 numbers: '0', '1', '2', '3', '4', '5', '6', '7', '8',
* '9' . Each dial wheel can rotate freely: for example, change '9' to '0', and '0' to '9'. Each rotation can only rotate one digit of one dial wheel.
*
* The initial number of the lock is' 0000 ', a string representing the number of four dials.
*
* The list deands contains a set of death numbers. Once the number of the dial wheel is the same as any element in the list, the lock will be permanently locked and can no longer be rotated.
*
* The string target represents the number that can be unlocked. You need to give the minimum number of rotations. If it cannot be unlocked anyway, return - 1.
*
*
*
* Example 1:
*
*
* Input: deands = ["0201", "0101", "0102", "1212", "2002"], target = "0202"
* Output: 6
* Explanation:
* The possible moving sequence is "0000" - > "1000" - > "1100" - > "1200" - > "1201" - > "1202" - > "0202".
* Note that sequences such as "0000" - > "0001" - > "0002" - > "0102" - > "0202" cannot be unlocked,
* Because the lock will be locked when you dial "0102".
*
*
* Example 2:
*
*
* Input: deands = ["8888"], target = "0009"
* Output: 1
* Explanation:
* Rotate the last bit in reverse once to "0000" - > "0009".
*
*
* Example 3:
*
*
* Input: deands = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"],
* target = "8888"
* Output: - 1
* Explanation:
* Cannot rotate to target number and is not locked.
*
*
* Example 4:
*
*
* Input: deands = ["0000"], target = "8888"
* Output: - 1
*
*
*
*
* Tips:
*
*
* The length range of death list deands is [1, 500].
* The target number target will not be in deands.
* The number of strings in each deands and target will be generated in 10000 possible cases' 0000 'to' 9999 '.
*
*
*/
// @lc code=start
type Data = {
pass: string,// Cipher sequence
k: number// How many steps does it take to reach this password sequence
};
// String used to calculate the next state
function getNextStr(str: string, i: number, j: number): string {
const res = str.split('').map(str=>parseInt(str));
// When j is 0, it means that the locking disc is turned up and becomes smaller; when j is 1, it means that the locking disc is turned down and becomes larger
switch(j){
case 0: res[i] -= 1; break;
case 1: res[i] += 1; break;
}
// Deal with the border situation
if(res[i] > 9) res[i] = 0;
if(res[i] < 0) res[i] = 9;
return res.join('');
}
function openLock(deadends: string[], target: string): number {
// Define search queue
const queue: Data[] = [];
// Define a set for judging illegal transmission. As long as the password sequence in this set is not used
const set: Set<string> = new Set<string>();
// Add the password sequence in the death list to set
deadends.forEach(s => set.add(s));
// If the password sequence 0000 is in the death list, it means that it can never be unlocked, and - 1 is returned
if(set.has('0000')) return -1;
// If 0000 is not in the death list, 0000 will be added to the search queue
queue.push({
pass: '0000',
k: 0
});
// Enter the loop when the search queue is not empty
while(queue.length) {
const cur = queue.shift();
if(cur.pass === target) return cur.k;
// Since each position of our locking disc can be up or down, there are 4 locking discs in total, so there are 8 cases
for(let i=0;i<4;i++) {
for(let j=0;j<2;j++) {
// Get next status
const nextStr = getNextStr(cur.pass, i, j);
// If the next calculated state is in set, it is ignored
if(set.has(nextStr)) continue;
// Otherwise, the calculated state is added to the set macro
set.add(nextStr);
// And push the next status into the queue
queue.push({
pass: nextStr,
k: cur.k + 1
});
}
}
}
return -1;
};
// @lc code=end
Sword finger Offer 13 Range of motion of robot
Problem solving ideas
There is nothing in this problem. Except for the boundary condition of the sum of digits, the other is the standard wide search solution. I won't repeat it. See the code implementation for details.
code implementation
type Data = {
x: number,
y: number
};
// Used to obtain the sum of row coordinates and column coordinates
function numItem(num1: number, num2:number): number{
const str = `${num1}${num2}`;
const arr = str.split('');
return arr.reduce((a, b)=>a + parseInt(b),0)
}
function movingCount(m: number, n: number, k: number): number {
// Wide search queue
const queue: Data[] = [];
// Visited nodes
const visited: number[][] = [];
for(let i=0;i<m;i++) {
const tmp = new Array(n);
tmp.fill(0);
visited.push(tmp);
}
// Direction / offset array
const direction: number[][] = [
[-1,0],
[0,1],
[1,0],
[0,-1]
];
// If the sum of the coordinate digits of (0,0) is greater than k, there is no need to continue. Return 1 directly according to the meaning of the question
if(numItem(0,0) > k) return 1;
// Mark the (0,0) coordinates as accessed
visited[0][0] = 1;
// Add (0,0) coordinates to the search queue
queue.push({
x: 0,
y: 0
});
// Used to count the total number of grids
let res = 0;
// If the wide search queue is not empty, it will enter the loop
while(queue.length) {
const cur = queue.shift();
// The number of results without entering a cycle is increased by 1
res += 1;
// Cycle to judge the legitimacy of the coordinates calculated in each direction. If the coordinate compliance rule is marked as accessed and added to the wide search queue
for(let i=0;i<direction.length;i++) {
const x = cur.x + direction[i][0];
const y = cur.y + direction[i][1];
if(x<0||x>=m) continue;
if(y<0||y>=n) continue;
if(visited[x][y]) continue;
if(numItem(x, y) > k) continue;
queue.push({
x,
y
});
visited[x][y] = 1;
}
}
return res;
};