Simple learning notes of search algorithm
1. Algorithm interpretation
Common first search algorithms: depth first search (DFS) and breadth first search (BFS), which are widely searched in structures such as graphs and trees
Summary:
- DFS is to catch a matching element and recurse wildly until it does not meet the conditions, requiring auxiliary functions
- BFS is done layer by layer, without auxiliary functions
- However, it is often necessary to combine the two to complete part of the calculation
2. Depth first search
Always call traversal on new nodes, which seems to be moving in the direction of "depth"
- After searching for a new node, traverse the new node immediately
- Traverse the stack that needs to be input first and then output; You can also use stack equivalent recursion
Stack works the same way as recursive calls
- Recursion is easy to implement and backtracking is also convenient (recommended)
- Stack is easy to understand, and recursive stack is not easy to be full (recommended for Engineering)
It can be used to detect the loop
- Record the parent node of each traversed node
- If a node is traversed again and the parent node is different, it indicates that there is a ring
Mark the nodes that have been searched to prevent repeated search for a node during traversal - state record or memory
method
- It is generally divided into main function and auxiliary function
- The main function is used to traverse all search positions to determine whether the search can be started. If so, search in the auxiliary function
- The auxiliary function is responsible for the recursive call of depth first search
- The most important thing is to determine the recursive boundary
① Maximum area of LeetCode 695 Island
Problem solving ideas
- From top to bottom, from left to right, judge whether it is an island one by one
- First, determine the boundary condition, that is, the size of the two-dimensional array cannot be exceeded
- The traversed island is set to zero to prevent recalculation
- The main function is used from top to bottom and from left to right; The auxiliary function is used to judge the surrounding position of the current island
Java solution
class Solution {
// Main function
public int maxAreaOfIsland(int[][] grid) {
int ans = 0;
if(grid.length == 0 || grid[0].length == 0) return 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1) {
ans = Math.max(ans, IslandDFS(grid, i, j));
}
}
}
return ans;
}
// Auxiliary function
public int IslandDFS(int[][] grid, int r, int c){
if((r < grid.length) && (r >= 0) && (c < grid[0].length) && c >= 0){
if(grid[r][c] == 0){
return 0;
} else {
grid[r][c] = 0;
return 1 + IslandDFS(grid, r-1, c) + IslandDFS(grid, r+1, c) + IslandDFS(grid, r, c-1) + IslandDFS(grid, r, c+1);
}
} else {
return 0;
}
}
}
② LeetCode 547 number of provinces
Problem solving ideas
- Traverse from left to right and from top to bottom
- For each column, judge whether to connect from top to bottom, and mark Unicom as true
- Each time a column is changed, the count is incremented by one
- The main function is used to replace columns and count; The auxiliary function is used to judge how many connections the column has and set it to true
Java solution
class Solution {
// Main function
public int findCircleNum(int[][] isConnected) {
int provinces = isConnected.length;
boolean[] visited = new boolean[provinces];
int circles = 0;
for (int i = 0; i < provinces; i++) {
if (!visited[i]) {
dfs(isConnected, visited, provinces, i);
circles++;
}
}
return circles;
}
// Auxiliary function
public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
for (int j = 0; j < provinces; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(isConnected, visited, provinces, j);
}
}
}
}
③ LeetCode 417 Pacific Atlantic current problem
Problem solving ideas
- Converging from the direction of the two oceans to the middle
- Mark the common place where both oceans will pass
- The main function is responsible for the direction of distribution from the two oceans; The auxiliary function is responsible for judging the size of each block
Java solution
class Solution {
// Return value used to return
private List<List<Integer>> ans = new ArrayList<>();
// Array of direction conversions
private int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
// Atlantic and Pacific shared access array
private boolean[][] visited = null;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int n = heights.length, m = heights[0].length;
visited = new boolean[n][m];
// temp is used to record the points visited by the current depth first search
boolean[][] temp = new boolean[n][m];
// First, start from the Pacific Ocean and see what points you can meet
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
// X = = 0 | y = = 0 indicates the conditions to be met for departure from the Pacific Ocean, and flag == false means departure from the Pacific Ocean
if ((x == 0 || y == 0) && !temp[x][y]) dfs(heights, x, y, temp, n, m, false);
}
}
// As above, temp is used to mark the points accessed by the current depth first search
temp = new boolean[n][m];
// Then start from the Atlantic Ocean to see what points you can meet. If the points you encounter have been marked as true in visited, it means that both sides can reach
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
// X = = n - 1 | y = = m - 1 indicates departure from the Atlantic Ocean
if ((x == n - 1 || y == m - 1) && !temp[x][y]) dfs(heights, x, y, temp, n, m, true);
}
}
return ans;
}
/**
* @param x Starting point coordinate x of depth first search
* @param y Starting point coordinate y
* @param temp Used to mark which points have been visited by the current depth first search
* @param flag true means it's from the Atlantic Ocean, and false means it's from the Pacific Ocean
*/
private void dfs(int[][] heights, int x, int y, boolean[][] temp, int n, int m, boolean flag) {
// If it's from the Atlantic Ocean and the Pacific Ocean has visited {x, y}, put it in the return value
if (flag && visited[x][y]) {
List<Integer> buf = new ArrayList<>();
buf.add(x);
buf.add(y);
ans.add(buf);
// By the way, set this point to false to prevent duplicate records
visited[x][y] = false;
}
// If it is from the Pacific Ocean, you need to mark {x, y} as having been here
if (!flag) visited[x][y] = true;
// Then switch the four directions and check them one by one
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i][0];
int ny = y + dirs[i][1];
// Check whether the new coordinates are legal, whether the current depth first search has come, and finally meet the reverse conditions
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !temp[nx][ny] && heights[nx][ny] >= heights[x][y]) {
temp[nx][ny] = true; // Then mark it as past in the current depth first search
dfs(heights, nx, ny, temp, n, m, flag); // Continue depth first search
}
}
}
}
3. Backtracking method (DFS special case)
The special case of priority search, also known as heuristic method
- Used for depth first search elements that need to record node status
- It is often used to arrange, combine and select classes
Two tips
- Pass status by reference
- All state modifications are changed back after recursion is completed
- Modify the last bit output, such as arrangement and combination;
- Or modify access marks, such as searching prime strings in the matrix
① LeetCode 46 Full Permutation
Problem solving ideas
- Each time you traverse to the end of the array, add it to the list
- From the back to the front, after the two elements exchange positions, the traversal starts from the position pointed by the current pointer
Java solution
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null) return res;
permute(nums, 0, res);
return res;
}
public void permute(int[] nums, int index, List<List<Integer>> res) {
// When the pointer points to the end at this time, it indicates that the elements of the num array have been shifted
// Add the num that has changed the position of the element to the list
if (index == nums.length - 1) {
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < nums.length; i++) {
ans.add(nums[i]);
}
res.add(ans);
}
// The following is the depth traversal array for position exchange and backtracking after completion
// It's equivalent to a pairwise exchange from back to front
for(int i = index; i < nums.length; i++) {
swap(nums, i, index);
permute(nums, index + 1, res);
swap(nums, i, index);
}
}
public void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
Problem solving ideas
- If n=4, k=2, select two from [1, 2, 3, 4]
- [1]—>[1, 2]—>[1]—>[1, 3]—>[1]—>[1, 4]—>[2]—>[2, 3]—>[2]—>[2, 4]—>[3]—>[3, 4]
- Add a sufficient number of elements in sequence from front to back; Remove the end element and replace with the next one
Java solution
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
if(k <= 0 || n < k){
return res;
}
dfs(n, k, 1, new ArrayList<>());
return res;
}
public void dfs(int n, int k, int index, List<Integer> ans) {
if(k == 0) {
res.add(new ArrayList<>(ans));
return;
}
for (int i = index; i <= n - k + 1; i++) {
ans.add(i);
System.out.println(ans);
dfs(n, k-1, i+1, ans);
ans.remove(ans.size()-1);
}
}
}
Problem solving ideas
- Double loop through the board two-dimensional array to find the same elements as the word string (converted to array)
- For the same element, judge its surroundings when considering the boundary
Java solution
class Solution {
public boolean exist(char[][] board, String word) {
int row = board.length, col = board[0].length;
boolean[][] visited = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
boolean flag = check(board, visited, i, j, word, 0);
if(flag){
return true;
}
}
}
return false;
}
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int index){
if(board[i][j] != s.charAt(index)){
return false;
} else if (index == s.length()-1){
return true;
}
visited[i][j] = true;
int[][] directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};
boolean res = false;
for (int[] dir : directions) {
int new_i = i + dir[0], new_j = j + dir[1];
if(new_i >= 0 && new_i < board.length && new_j >= 0 && new_j < board[0].length){
if(!visited[new_i][new_j]){
boolean flag = check(board, visited, new_i, new_j, s, index+1);
if(flag){
res = true;
break;
}
}
}
}
visited[i][j] = false;
return res;
}
}
Problem solving ideas
- Set all checkerboards to "."
- Set it on a line and judge whether each chessboard of the line is suitable for 'Q'
- By judging whether the horizontal, vertical and oblique chessboard has' Q '
- If it is appropriate, set it to 'Q' (there must be one appropriate space in each line)
- When a cell of the row is set to 'Q', recursion to the next row; Repeat to last line
- When the 'Q' of the last line is set, add this solution to the list
- If a placement has no solution, it will go back to the last recursion and set a lattice originally set as' Q 'to', In this way, multiple sets of solutions can be tried in reverse order
Java solution
public List<List<String>> solveNQueens(int n) {
char[][] chess = new char[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
chess[i][j] = '.';
List<List<String>> res = new ArrayList<>();
solve(res, chess, 0);
return res;
}
private void solve(List<List<String>> res, char[][] chess, int row) {
if (row == chess.length) {
res.add(construct(chess));
return;
}
for (int col = 0; col < chess.length; col++) {
if (valid(chess, row, col)) {
chess[row][col] = 'Q';
solve(res, chess, row + 1);
chess[row][col] = '.';
}
}
}
//Row indicates the row and col indicates the column
private boolean valid(char[][] chess, int row, int col) {
//Judge whether there is a queen in the current column, because he goes down line by line,
//We only need to check the number of lines we have passed. Generally speaking, it is to judge the current
//Is there a queen above the coordinate position
for (int i = 0; i < row; i++) {
if (chess[i][col] == 'Q') {
return false;
}
}
//Judge whether there is a queen in the upper right corner of the current coordinate
for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
if (chess[i][j] == 'Q') {
return false;
}
}
//Judge whether there is a queen in the upper left corner of the current coordinate
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chess[i][j] == 'Q') {
return false;
}
}
return true;
}
//Convert array to list
private List<String> construct(char[][] chess) {
List<String> path = new ArrayList<>();
for (int i = 0; i < chess.length; i++) {
path.add(new String(chess[i]));
}
return path;
}
4. Breadth first search
Traverse layer by layer
- A first in first out queue is required
- Often deal with the shortest path problem
Both DFS and BFS can deal with the problem of reachability - can you go from one node to another
- DFS can be implemented quickly by recursion, but it is rarely used in software engineering
- On the one hand, it is difficult to understand
- On the other hand, stack overflow may occur
- There is not much difference between DFS and BFS in solving problems
① LeetCode 934 shortest Bridge
Problem solving ideas
- Deep search: search the location of two islands
- Breadth search: extend outward to find the path
Java solution
class Solution {
private int[] direction = {-1, 0, 1, 0, -1};
private int res = 0;
public int shortestBridge(int[][] grid) {
int row = grid.length, col= grid[0].length;
// 1. First dfs find the first island, change 1 to 2, and insert 0 next to the island into the queue
// 2. Then the while loop will judge whether the queue is empty, and the loop body will judge whether the second island is found
Queue<int[]> queue = new LinkedList<>();
// DFS
boolean dfsFlag = false;
for (int i = 0; i < row; i++) {
if (dfsFlag) {
break;
}
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1) {
dfs(grid, queue, i, j, row, col);
dfsFlag = true;
break;
}
}
}
// BFS searches for the next island and assigns all zeros to 2 when traversing
while (!queue.isEmpty()){
res++;
int queueSize = queue.size();
while (queueSize-- > 0){
int[] root = queue.poll();
for (int i = 0; i < direction.length - 1; i++) {
int new_x = root[0] + direction[i];
int new_y = root[1] + direction[i+1];
if(new_x >= 0 && new_x < row && new_y >= 0 && new_y < col){
if(grid[new_x][new_y] == 1){
return res;
} else if (grid[new_x][new_y] == 2){
continue;
}
grid[new_x][new_y] = 2;
queue.add(new int[]{new_x, new_y});
}
}
}
}
return res;
}
private void dfs(int[][] grid, Queue<int[]> queue, int x, int y, int row, int col) {
// Insert all element coordinates with 0 into the queue
// If it is 1, it changes to 2 and continues to traverse 4 directions
// If it is 2, exit directly
if(x < 0 || x == row || y < 0 || y == col || grid[x][y] == 2){
return;
}
if(grid[x][y] == 0){
queue.add(new int[]{x, y});
return;
}
grid[x][y] = 2;
for (int i = 0; i < direction.length-1; i++) {
int new_x = x + direction[i];
int new_y = y + direction[i+1];
dfs(grid, queue, new_x, new_y, row, col);
}
}
}
② LeetCode 126 word Solitaire II
important
Problem solving ideas
- Shortest path: DFS + BFS
Java solution
// Method 1: DFS
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> ans = new ArrayList<>();
if (!wordList.contains(endWord)) {
return ans;
}
// Use BFS to get all neighbor nodes
HashMap<String, ArrayList<String>> map = new HashMap<>();
bfs(beginWord, endWord, wordList, map);
ArrayList<String> temp = new ArrayList<String>();
// temp is used to save the current path
temp.add(beginWord);
findLaddersHelper(beginWord, endWord, map, temp, ans);
return ans;
}
private void findLaddersHelper(String beginWord, String endWord, HashMap<String, ArrayList<String>> map,
ArrayList<String> temp, List<List<String>> ans) {
if (beginWord.equals(endWord)) {
ans.add(new ArrayList<String>(temp));
return;
}
// Get all the next nodes
ArrayList<String> neighbors = map.getOrDefault(beginWord, new ArrayList<String>());
for (String neighbor : neighbors) {
temp.add(neighbor);
findLaddersHelper(neighbor, endWord, map, temp, ans);
temp.remove(temp.size() - 1);
}
}
public void bfs(String beginWord, String endWord, List<String> wordList, HashMap<String, ArrayList<String>> map) {
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
boolean isFound = false;
int depth = 0;
Set<String> dict = new HashSet<>(wordList);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
while (!queue.isEmpty()) {
int size = queue.size();
depth++;
Set<String> subVisited = new HashSet<>();
for (int j = 0; j < size; j++) {
String temp = queue.poll();
// Get all the next nodes at once
ArrayList<String> neighbors = getNeighbors(temp, dict);
Iterator<String> it = neighbors.iterator();//Import elements into iterators
while (it.hasNext()) {
String neighbor = it.next();
if (!visited.contains(neighbor)) {
if (neighbor.equals(endWord)) {
isFound = true;
}
queue.offer(neighbor);
subVisited.add(neighbor);
}else{
it.remove();
}
}
map.put(temp, neighbors);
}
visited.addAll(subVisited);
if (isFound) {
break;
}
}
}
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch)
continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
}
// Method 2: BFS
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> ans = new ArrayList<>();
// If there is no ending word, end it directly, otherwise it will cause a dead cycle
if (!wordList.contains(endWord)) {
return ans;
}
bfs(beginWord, endWord, wordList, ans);
return ans;
}
public void bfs(String beginWord, String endWord, List<String> wordList, List<List<String>> ans) {
Queue<List<String>> queue = new LinkedList<>();
List<String> path = new ArrayList<>();
path.add(beginWord);
queue.offer(path);
boolean isFound = false;
Set<String> dict = new HashSet<>(wordList);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
while (!queue.isEmpty()) {
int size = queue.size();
Set<String> subVisited = new HashSet<>();
for (int j = 0; j < size; j++) {
List<String> p = queue.poll();
//Gets the last word of the current path
String temp = p.get(p.size() - 1);
// Get all the next nodes at once
ArrayList<String> neighbors = getNeighbors(temp, dict);
for (String neighbor : neighbors) {
//Consider only words that have not appeared before
if (!visited.contains(neighbor)) {
//End word reached
if (neighbor.equals(endWord)) {
isFound = true;
p.add(neighbor);
ans.add(new ArrayList<String>(p));
p.remove(p.size() - 1);
}
//Add current word
p.add(neighbor);
queue.offer(new ArrayList<String>(p));
p.remove(p.size() - 1);
subVisited.add(neighbor);
}
}
}
visited.addAll(subVisited);
if (isFound) {
break;
}
}
}
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch)
continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
}
// Method 3: DFS+BFS
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> ans = new ArrayList<>();
// If there is no ending word, end it directly, otherwise it will cause a dead cycle
if (!wordList.contains(endWord)) {
return ans;
}
bfs(beginWord, endWord, wordList, ans);
return ans;
}
public void bfs(String beginWord, String endWord, List<String> wordList, List<List<String>> ans) {
Queue<List<String>> queue = new LinkedList<>();
List<String> path = new ArrayList<>();
path.add(beginWord);
queue.offer(path);
boolean isFound = false;
Set<String> dict = new HashSet<>(wordList);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
while (!queue.isEmpty()) {
int size = queue.size();
Set<String> subVisited = new HashSet<>();
for (int j = 0; j < size; j++) {
List<String> p = queue.poll();
//Gets the last word of the current path
String temp = p.get(p.size() - 1);
// Get all the next nodes at once
ArrayList<String> neighbors = getNeighbors(temp, dict);
for (String neighbor : neighbors) {
//Consider only words that have not appeared before
if (!visited.contains(neighbor)) {
//End word reached
if (neighbor.equals(endWord)) {
isFound = true;
p.add(neighbor);
ans.add(new ArrayList<String>(p));
p.remove(p.size() - 1);
}
//Add current word
p.add(neighbor);
queue.offer(new ArrayList<String>(p));
p.remove(p.size() - 1);
subVisited.add(neighbor);
}
}
}
visited.addAll(subVisited);
if (isFound) {
break;
}
}
}
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch)
continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
}
// Less time-consuming solution
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
// Result set
List<List<String>> res = new ArrayList<>();
Set<String> words = new HashSet<>(wordList);
// The dictionary does not contain the target word
if (!words.contains(endWord)) {
return res;
}
// Storage relationship: the lower level words that can be reached by each word
Map<String, List<String>> mapTree = new HashMap<>();
Set<String> begin = new HashSet<>(), end = new HashSet<>();
begin.add(beginWord);
end.add(endWord);
if (buildTree(words, begin, end, mapTree, true)) {
dfs(res, mapTree, beginWord, endWord, new LinkedList<>());
}
return res;
}
// Two way correspondence of each word level, BFS
private boolean buildTree(Set<String> words, Set<String> begin, Set<String> end, Map<String, List<String>> mapTree, boolean isFront){
if (begin.size() == 0) {
return false;
}
// Always explore with less
if (begin.size() > end.size()) {
return buildTree(words, end, begin, mapTree, !isFront);
}
// Remove from accessed word set
words.removeAll(begin);
// Mark whether this layer has reached the target word
boolean isMeet = false;
// Record the words accessed by this layer
Set<String> nextLevel = new HashSet<>();
for (String word : begin) {
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char temp = chars[i];
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String str = String.valueOf(chars);
if (words.contains(str)) {
nextLevel.add(str);
// Add hierarchical correspondence according to the access order: always maintain the storage relationship from the upper layer to the lower layer
// true: explore from top to bottom: Word - > str
// false: explore from bottom to top: str - > word (the found str is the word on the upper layer of word)
String key = isFront ? word : str;
String nextWord = isFront ? str : word;
// Determine whether the target word is encountered
if (end.contains(str)) {
isMeet = true;
}
if (!mapTree.containsKey(key)) {
mapTree.put(key, new ArrayList<>());
}
mapTree.get(key).add(nextWord);
}
}
chars[i] = temp;
}
}
if (isMeet) {
return true;
}
return buildTree(words, nextLevel, end, mapTree, isFront);
}
// DFS: combined path
private void dfs (List<List<String>> res, Map<String, List<String>> mapTree, String beginWord, String endWord, LinkedList<String> list) {
list.add(beginWord);
if (beginWord.equals(endWord)) {
res.add(new ArrayList<>(list));
list.removeLast();
return;
}
if (mapTree.containsKey(beginWord)) {
for (String word : mapTree.get(beginWord)) {
dfs(res, mapTree, word, endWord, list);
}
}
list.removeLast();
}
}
5. Practice
① Area surrounded by LeetCode 130
Problem solving ideas
- First traverse the periphery, and then traverse the rest
Java solution
// Method 1: DFS
// Traverse the outermost circle and assign O as A. when assigned as A, search deeply and set all of them as A (because they are connected)
// Finally, traverse the entire two-dimensional array, assign all O to X, and then assign all A to O
class Solution {
private int row, col;
private int[] directions = new int[]{-1,0,1,0,-1};
public void solve(char[][] board) {
row = board.length;
col = board[0].length;
for (int i = 0; i < row; i++) {
dfs(board, i, 0);
dfs(board, i, col-1);
}
for (int i = 1; i < col-1; i++) {
dfs(board, 0, i);
dfs(board, row-1, i);
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'A'){
board[i][j] = 'O';
} else if (board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int x, int y) {
if(x < 0 || x >= row || y < 0 || y >= col || board[x][y] != 'O'){
return;
}
board[x][y] = 'A';
dfs(board, x-1, y); // left side
dfs(board, x, y-1); // upper
dfs(board, x, y+1); // right
dfs(board, x+1, y); // Below
}
}
// Method 2: BFS
class Solution {
private int[] dx = {1,-1,0,0};
private int[] dy = {0,0,1,-1};
public void solve(char[][] board){
int row = board.length;
int col = board[0].length;
// Record the position of the outermost O
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O') {
queue.offer(new int[]{i, 0});
}
if (board[i][col-1] == 'O') {
queue.offer(new int[]{i, col-1});
}
}
for (int i = 0; i < col; i++) {
if (board[0][i] == 'O') {
queue.offer(new int[]{0, i});
}
if (board[row-1][i] == 'O') {
queue.offer(new int[]{row-1, i});
}
}
// Assign the outermost O position and its adjacent O as A
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
board[x][y] = 'A';
for (int i = 0; i < 4; i++) {
int new_x = x + dx[i], new_y = y + dy[i];
if (new_x < 0 || new_x >= row || new_y < 0 || new_y >= col || board[new_x][new_y] != 'O') {
continue;
}
// Used to update the latest 'O' indicated by the pointer
queue.offer(new int[]{new_x, new_y});
}
}
// Assign O to X and A to O
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'A'){
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
}
② LeetCode 257 all paths of binary tree
Problem solving ideas
- If the current node is not a leaf node, add the node at the end of the current path and continue to recursively traverse each child node of the node.
- If the current node is a leaf node, after adding this node at the end of the current path, we will get a path from the root node to the leaf node. Just add this path to the answer.
Java solution
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root, "", res);
return res;
}
private void dfs(TreeNode root, String s, List<String> res) {
if (root != null) {
StringBuffer sb = new StringBuffer(s);
sb.append(Integer.toString(root.val));
if (root.left == null && root.right == null) {
res.add(sb.toString());
} else {
sb.append("->");
dfs(root.left, sb.toString(), res);
dfs(root.right, sb.toString(), res);
}
}
}
}
③ LeetCode 47 Full Permutation II
Java solution
class Solution {
private boolean[] visited;
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> ans = new ArrayList<>();
visited = new boolean[nums.length];
Arrays.sort(nums);
backtrack(nums, res, 0, ans);
return res;
}
private void backtrack(int[] nums, List<List<Integer>> res, int index, List<Integer> ans) {
if (index == nums.length) {
res.add(new ArrayList<>(ans));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
continue;
}
ans.add(nums[i]);
visited[i] = true;
backtrack(nums, res, index + 1, ans);
visited[i] = false;
ans.remove(index);
}
}
}
④ LeetCode 40 combination sum II
Java solution
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Arrays.sort(candidates);
Deque<Integer> path = new ArrayDeque<>(len);
dfs(candidates, len, 0, target, path, res);
return res;
}
private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// Proof: a + B + C > target
if (target - candidates[i] < 0) {
break;
}
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
path.addLast(candidates[i]);
dfs(candidates, len, i+1, target-candidates[i], path, res);
path.removeLast();
}
}
}
Problem solving ideas
Java solution
class Solution {
private boolean[][] line = new boolean[9][9];
private boolean[][] column = new boolean[9][9];
private boolean[][][] block = new boolean[3][3][9];
private boolean valid = false;
private List<int[]> spaces = new ArrayList<int[]>();
public void solveSudoku(char[][] board) {
// First, traverse once and mark
// Where there are numbers, the row, column and block marked can no longer be repeated
// Where there is no number, record its location to facilitate subsequent rapid positioning and filling
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.add(new int[]{i, j});
} else {
int digit = board[i][j] - '0' - 1;
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
}
}
}
dfs(board, 0);
}
public void dfs(char[][] board, int pos) {
// When all the blanks are filled in, it means that the solution is solved
if (pos == spaces.size()) {
valid = true;
return;
}
// Get the empty space indicated by pos
int[] space = spaces.get(pos);
int i = space[0], j = space[1];
// Fill in 1 ~ 9 for the current vacancy cycle
// If the number N is added, it is found that the number N already exists in other positions of the row (or column or block)
// If it indicates that the number N cannot be filled, skip, fill in the number N+1, and cycle like this
// If it is found that the number 1 ~ 9 of the current vacancy cannot be filled in, return to the previous vacancy and change the number of the previous vacancy
for (int digit = 0; digit < 9 && !valid; ++digit) {
if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
board[i][j] = (char) (digit + '0' + 1);
dfs(board, pos + 1);
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
}
}
}
}
⑥ LeetCode 310 minimum height tree
Problem solving ideas
Java solution
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
/*
The given graph of this problem has no ring!
1. Reverse deformation BFS:
Reverse: start from leaf node to root BFS.
Leaf: at the point of degree=1, there must be leaves at the beginning without environmental protection certificate.
Deformation: here, the layer is not cut by a straight line, but by a curve. All leaf nodes are one layer.
2. Update degree
Each time a node is taken from the BFS queue, its neighbor degree --. When the neighbor node degree changes to 1, it will become a new "leaf node" and join the queue
*/
// corner case: only one node
if(n==1){
return List.of(0);
}
// edges to adjacency table and initialize degree
List<List<Integer>> adjList = new ArrayList<>();
int i = n;
while(i>0){
adjList.add(new ArrayList<>());
i--;
}
int[] degree = new int[n];
for(int[] edge: edges){
adjList.get(edge[0]).add(edge[1]);
adjList.get(edge[1]).add(edge[0]);
degree[edge[0]]++;
degree[edge[1]]++;
}
// Initialize BFS queue
Queue<Integer> queue = new LinkedList<>();
for(i=0; i<n; i++){
if(degree[i]==1){
queue.offer(i);
}
}
// BFS
List<Integer> shortestTreeRoots = new ArrayList<>();
while(!queue.isEmpty()){
shortestTreeRoots = new ArrayList<>();
int size = queue.size();
while(size>0){
size--;
int cur = queue.poll();
// Every DFS, the roots will be updated. The node that joined the roots in the last DFS is the root node
// According to the definition of layer here, if there are multiple shortest tree s, the roots of these trees will be divided into the same layer
shortestTreeRoots.add(cur);
for(int neighbor: adjList.get(cur)){
degree[neighbor]--;
if(degree[neighbor]==1){
// When the degree is reduced to 1, it indicates that neighbor is a node of a new layer
queue.offer(neighbor);
}
}
}
}
return shortestTreeRoots;
}
}