搜索（BFS、DFS、回溯）
2024-09-05 06:37:07
这类题是最简单的了都是一个套路，不像动态规划一类题一个套路，没做过就是不会也极难想出来。
一、BFS
解决的问题：用来初始点解决到指定点的最短路径问题，因为图的每一层上的点到初始点的距离相同。（注意是无权图）
在程序实现 BFS 时需要考虑以下问题：
- 队列：用来存储每一轮遍历得到的节点；
- 标记：对于遍历过的节点，应该将它标记，防止重复遍历。
下面这两个题都是比较典型的广度优先题
这题笔者超时了百思不得其解。
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if(grid[0][0] == 1 || grid[m-1][n-1] == 1) return -1;
int[][] dirc = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
LinkedList<int[]> queue = new LinkedList<>();
queue.add(new int[]{0,0,1});
while(!queue.isEmpty()) {
int[] p = queue.poll();
if(p[0]==m-1 && p[1]==n-1) return p[2];
grid[p[0]][p[1]] = 1;
for(int[] d : dirc) {
int x = p[0] + d[0];
int y = p[1] + d[1];
if(x<0||y<0||x>=m||y>=n||grid[x][y]==1)
continue;
queue.add(new int[]{x,y,p[2]+1});
}
}
return -1;
}
}
class Solution {
public int ladderLength(String d, String endWord, List<String> wordList) {
int ans = 0;
if(wordList.size()==0) return ans;
LinkedList<String> queue = new LinkedList<>();
boolean[] visited = new boolean[wordList.size()];
queue.add(d);
while(!queue.isEmpty()) {
int size = queue.size();
ans++;
while(size-->0) {
String p = queue.poll();
for(int i = 0; i < wordList.size(); i++) {
String s = wordList.get(i);
if(!visited[i] && f(p,s)) {
if(s.equals(endWord)) return ++ans;
queue.add(s);
visited[i] = true;
}
}
}
}
return 0;
}
private boolean f(String s1, String s2) {
int i = 0;
int j = 0;
boolean flag = true;
while(i < s1.length()) {
if(s1.charAt(i) == s2.charAt(j)) {
i++;
j++;
}else if(s1.charAt(i) != s2.charAt(j)&&flag) {
flag = false;
i++;
j++;
}else return false;
}
return true;
}
}
二、DFS
解决的问题：用来解决连通性的问题。
在程序实现 DFS 时需要考虑以下问题：
- 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
- 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。
- 判断：进栈出栈都需要判断元素是否已经被访问过，因为栈中有可能出现已经访问过的元素（找个图自己走一下）。
import javafx.util.Pair;
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};
int ans = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j]==1) {
int count = 0;
LinkedList<Pair<Integer,Integer>> queue = new LinkedList<>();
queue.add(new Pair<>(i,j));
while(!queue.isEmpty()) {
Pair<Integer,Integer> p = queue.pollLast();
if(grid[p.getKey()][p.getValue()]==1) {
count++;
grid[p.getKey()][p.getValue()] = 0;
for(int[] d : direction) {
int x = p.getKey() + d[0];
int y = p.getValue() + d[1];
if(x<0||y<0||x>=grid.length||y>=grid[0].length||grid[x][y]==0)
continue;
queue.add(new Pair<>(x,y));
}
}
}
ans = Math.max(ans,count);
}
}
}
return ans;
}
}
import javafx.util.Pair;
class Solution {
public void solve(char[][] board) {
int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
//边界O好处理一些，这里我们选择先找到边界O
if(board[i][j]=='O'&&(i==0||i==board.length-1||j==0||j==board[0].length-1)) {
LinkedList<Pair<Integer,Integer>> queue = new LinkedList<>();
queue.add(new Pair<>(i,j));
while(!queue.isEmpty()) {
Pair<Integer,Integer> p = queue.pollLast();
if(board[p.getKey()][p.getValue()]=='O') {
board[p.getKey()][p.getValue()] = 'T';
for(int[] d : direction) {
int x = p.getKey() + d[0];
int y = p.getValue() + d[1];
if(x<0||y<0||x>=board.length||y>=board[0].length||board[x][y]=='T'||board[x][y]=='X')
continue;
queue.add(new Pair<>(x,y));
}
}
}
}
}
}
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j]=='O') board[i][j] = 'X';
if(board[i][j]=='T') board[i][j] = 'O';
}
}
}
}
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> ans = new LinkedList<>();
if(matrix.length == 0||matrix[0].length == 0) return ans;
int m = matrix.length;
int n = matrix[0].length;
boolean[][] m1 = new boolean[m][n];
boolean[][] m2 = new boolean[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i==0||j==0) dfs(matrix,new int[]{i,j},m1);
if(i==m-1||j==n-1) dfs(matrix,new int[]{i,j},m2);
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(m1[i][j]&&m2[i][j])
ans.add(Arrays.asList(i,j));
}
}
return ans;
}
private void dfs(int[][] matrix, int[] s, boolean[][] m) {
LinkedList<int[]> stack = new LinkedList<>();
int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
stack.add(s);
while(!stack.isEmpty()) {
int[] p = stack.pollLast();
if(!m[p[0]][p[1]]) {
m[p[0]][p[1]] = true;
for(int[] d : dir) {
int x = p[0] + d[0];
int y = p[1] + d[1];
if(x<0||y<0||x>= matrix.length||y>=matrix[0].length||m[x][y])
continue;
if(matrix[x][y] >= matrix[p[0]][p[1]])
stack.add(new int[]{x,y});
}
}
}
}
}
三、回溯
解决的问题：排列组合问题。
回溯法其实就是一种枚举，把所有的情况都走一遍筛选出符合条件的解。有很多的题都可以用回溯解决，但是效率相差很大。回溯法适合解决，枚举出100种情况，但是有98种情况符合题意的这类问题。但是，如果枚举100种情况，只有1种情况符合题意，显示用回溯效率是极低。
因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：
- 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
- 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。
class Solution {
private HashMap<Integer,String> hash = new HashMap<>();
private LinkedList<String> ans = new LinkedList<>();
public List<String> letterCombinations(String digits) {
hash.put(2,"abc");
hash.put(3,"def");
hash.put(4,"ghi");
hash.put(5,"jkl");
hash.put(6,"mno");
hash.put(7,"pqrs");
hash.put(8,"tuv");
hash.put(9,"wxyz");
if(digits == null || digits.length() == 0) return ans;
backtrace("",digits);
return ans;
}
private void backtrace(String temp, String digits) {
if(digits.length()==0) {
ans.add(temp);
}else {
Integer key = Integer.valueOf(digits.substring(0,1));
String s = hash.get(key);
for(int i = 0; i < s.length(); i++) {
temp = temp + s.substring(i,i+1);
backtrace(temp,digits.substring(1));
temp = temp.substring(0,temp.length()-1);
}
}
}
}
class Solution {
List<String> ans = new LinkedList<>();
public List<String> restoreIpAddresses(String s) {
backtrace(0,s,"");
return ans;
}
private void backtrace(int k, String s, String temp) {
if(k==4||s.length()==0) {
if(k==4&&s.length()==0) ans.add(temp);
return;
}else {
for(int i = 0;i < s.length() &&i <= 2; i++) {
if(s.charAt(0)=='0'&&i!=0) break;
String part = s.substring(0,i+1);
if(Integer.valueOf(part)<=255) {
if(temp.length()!=0) {
part = '.' + part;
}
temp = temp + part;
backtrace(k+1,s.substring(i+1),temp);
temp = temp.substring(0,temp.length()-part.length());
}
}
}
}
}
class Solution {
private boolean[][] m = new boolean[9][10];
private boolean[][] n = new boolean[9][10];
private boolean[][] k = new boolean[9][10];
private char[][] b;
public void solveSudoku(char[][] board) {
b = board;
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(board[i][j]!='.') {
int num = board[i][j] - '0';
m[i][num] = true;
n[j][num] = true;
k[(i/3)*3+j/3][num] = true;
}
}
}
backtrace(0,0);
}
private boolean backtrace(int r, int c) {
if(r < 8 && c == 9) {
r++;
c = 0;
}
if(r == 8 && c == 9) return true;
if(b[r][c] == '.') {
for(int i = 1; i <= 9; i++) {
int x = (r/3)*3+c/3;
if(m[r][i]||n[c][i]||k[x][i]) continue;
b[r][c] = (char)('0'+i);
m[r][i] = true;
n[c][i] = true;
k[x][i] = true;
if(backtrace(r,c+1)) return true;
b[r][c] = '.';
m[r][i] = false;
n[c][i] = false;
k[x][i] = false;
}
}else return backtrace(r,c+1);
return false;
}
}
class Solution {
List<List<String>> list = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
boolean[] c = new boolean[n+1];
boolean[][] b = new boolean[n+1][n+1];
backtrace(1,n,c,b);
return list;
}
private void backtrace(int k, int n, boolean[] c, boolean[][] b) {
if(k == n+1) {
fill(b,n);
return;
}
for(int i = 1; i <= n; i++) {
if(c[i]||isHou(k,i,n,b)) continue;
b[k][i] = true;
c[i] = true;
backtrace(k+1,n,c,b);
b[k][i] = false;
c[i] = false;
}
}
private void fill(boolean[][] b, int n) {
LinkedList<String> temp = new LinkedList<>();
for(int i = 1; i <= n; i++) {
StringBuilder s = new StringBuilder();
for(int j = 1; j <= n; j++) {
if(b[i][j]) s.append('Q');
else s.append('.');
}
temp.add(new String(s));
}
list.add(temp);
}
private boolean isHou(int x, int y, int n, boolean[][] b) {
int i = x;
int j = y;
while(i<=n&&j<=n) {
if(b[i++][j++]) return true;
}
i = x;
j = y;
while(i>=1&&j>=1) {
if(b[i--][j--]) return true;
}
i = x;
j = y;
while(i>=1&&j<=n) {
if(b[i--][j++]) return true;
}
i = x;
j = y;
while(i<=n&&j>=1) {
if(b[i++][j--]) return true;
}
return false;
}
}
最新文章
- IOS编程 图片缓存模块设计
- IOS第16天(4,Quartz2D柱状图）
- [C程序设计语言]第四部分
- 树莓派学习：源码方式安装opencv
- storm的功能、三大应用
- Java库使用----xstream1.3.1
- Tomcat学习笔记 - 错误日志 - NetBeans配置tomcat出错情况总结 -- 部署错误: 启动 Tomcat 失败。-- '127.0.0.1' 不是内部或外部命令，也不是可运行的程序
- zepto的touch.js左右滑动存在一些问题，用百度的touch.js代替
- nodejs上传图片模块做法;
- 【SysML】模块定义图(BDD, Block Definition Diagram)
- countDownLatch和cyclicBarrier
- 【★】深入BGP原理和思想【第一部】
- POJ 2404 Jogging Trails [DP 状压 一般图最小权完美匹配]
- sparklyr包：实现Spark与R的接口+sparklyr 0.5
- 代码实现PHP web服务器下绝对路径到Web网址的转换
- Rich feature hierarchies for accurate object detection and semantic segmentation（理解）
- Unity 摄像机跟随
- ubuntu axel
- Hadoop JobTracker和NameNode运行时参数查看
- jave 逻辑运算 vs 位运算 + Python 逻辑运算 vs 位运算