void dfs(step)
{
判断边界
尝试每一种可能 for(int i=0;i
DFS力扣例题
695.岛屿的最大面积
分析：
对是陆地的位置向四个方向进行深度优先搜索，如果下一个位置仍然是陆地，则加上由新陆地向四个方向搜索的值。遍历过的陆地应该设置为0，以避免重复被计入。
题解：
class Solution {
public static int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for(int i=0;i=grid.length || j>=grid[i].length || grid[i][j]==0){
//超出边界，返回0
//当前位置是水，返回0
return 0;
}
else {
//计入当前陆地面积1
int sum = 1;
//当前陆地已经计算过，设为0
grid[i][j] = 0;
sum += dfs(grid, i+1,j);
sum += dfs(grid, i-1,j);
sum += dfs(grid, i,j+1);
sum += dfs(grid, i,j-1);
return sum;
}
}
}
547. 省份数量
分析：
本题拥有的行数即是节点的个数，列数即是每行的边。以此转换为图的模型进行深度优先搜索。同时需要一个数组标记该节点是否被访问过。
题解：
**class Solution {
public int findCircleNum(int[][] isConnected) {
int count = 0;
boolean[] isVisited = new boolean[isConnected.length];
Arrays.fill(isVisited,false);
for(int i=0;i
417. 太平洋大西洋水流问题
分析：
考虑到如果对每个点进行深度优先搜索复杂度较高，因此采用从两个大洋逆流的想法进行搜索，设置代表两个大洋搜索结果的两个数组。这样只需要搜索四个边界即可。搜索完后，只需要遍历一遍矩阵，如果当前位置的两个大洋都能到达，即为题目所求。
题解：
class Solution {
public List> pacificAtlantic(int[][] heights) {
List> result = new ArrayList>();
if (heights.length==0 || heights[0].length==0){
return result;
}
//判断是否能够的布尔型数组
int m = heights.length;
int n = heights[0].length;
boolean[][] reachPacific = new boolean[m][n];
boolean[][] reachAtlantic = new boolean[m][n];
for(int i=0;i temp = new ArrayList<>();
temp.add(i);
temp.add(j);
result.add(temp);
}
}
}
return result;
}
private void dfs(int[][] heights, boolean[][] reach, int start, int end) {
if (reach[start][end]){
return;
}
//能够流经的位置记为true
reach[start][end] = true;
//向四个方向开始搜索
int x = start-1;
int y = end;
if (x>=0 && x=0 && y=0 && x=0 && y=0 && x=0 && y=0 && x=0 && y
二、回溯法
回溯法是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。在搜索到某一结点的时候，如果我们发现目前节点不是需求目标时，需要回退到原来的节点，并且把目前节点修改的状态还原。
通常有两个小窍门：1. 按引用传状态；2. 所有的状态修改在递归完成后回改。
回溯的修改有两种情况：1. 修改最后一位输出，如排列组合；2. 修改访问标记
46. 全排列
分析：
对于每一个当前位置i，我们可以将其于之后的任意位置交换，然后继续处理位置i+1，，直到处理到最后一位。为了防止每次遍历时都要创建一个子数组存储位置i之前已经交换好的数字，可以利用回溯法，只对原数组进行修改，在递归完成后再改回来。
题解：
class Solution {
public List> permute(int[] nums) {
List> result = new ArrayList>();
backtracking(nums, 0, result);
return result;
}
public void backtracking(int[] nums, int level, List> result){
//处理到最后一位，进行结果的保存
if (level == nums.length-1){
List temp = new ArrayList<>();
for(int i:nums){
temp.add(i);
}
result.add(temp);
return;
}
for (int i=level;i
77. 组合
分析：
声明一个待选列表，回溯遍历所有可能的搜索起点，如果加入待选列表的数已经有了k个，则将其加入最后的结果。因为组合数不能有重复的数出现，因此每次搜索的起点要+1。回溯算法在进入递归前后要改变状态和恢复状态。
在上述算法的基础上，可以进行剪枝，也即是在每次进行递归时，当待选列表的长度加上剩余未判断区间的长度小于k，则不可能构造出最后的结果，直接结束该次递归即可。
题解：
class Solution{
List> result = new ArrayList>();
List temp = new ArrayList<>();
public List> combine(int n,int k){
backtracking(1, n, k);
return result;
}
private void backtracking(int current, int n, int k) {
//如果待选列表的长度加上剩余未确定区间的长度小于k
//则不可能构造出长度为k的结果
if (temp.size()+(n-current+1)(temp));
return;
}
//回溯遍历所有可能的搜索起点
for (int i=current;i<=n;++i){
//将当前的数加入待选列表中
temp.add(i);
//从下一个数开始搜索
backtracking(i+1,n,k);
//回溯，将加入的数从待选数列中删除
temp.remove(temp.size()-1);
}
}
}
79. 单词搜索
分析：
为每个访问的节点设置一个访问位，来表示是否被访问过。然后在递归过程中，分别向四个方向进行深搜，该节点为起点的深搜结束后，要进行回溯。
在传递结果find的时候容易犯错，Java的boolean类型是值传递不是引用传递，因此作为全局变量使用。
题解：
class Solution {
boolean find = false;
public boolean exist(char[][] board, String word) {
if (board.length==0||board[0].length==0){
return false;
}
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for(int i=0;i=board.length || j>=board[0].length){
return;
}
//找到单词、该位置被访问、当前位置不等于需要的单词字母
//满足上述任一项返回
if (find || visited[i][j] || board[i][j]!=word.charAt(position)){
return;
}
//找到该单词，返回结果
if (position+1==word.length()){
find = true;
return;
}
//修改当前节点状态
visited[i][j] = true;
//递归子节，深搜向四个方向拓展
backtracking(board, word, visited, i+1, j, position+1);
backtracking(board, word, visited, i-1, j, position+1);
backtracking(board, word, visited, i, j+1, position+1);
backtracking(board, word, visited, i, j-1, position+1);
//回改当前节点状态
visited[i][j] = false;
}
}
51. N皇后问题
分析：
判断皇后在一个位置能放置的条件，即当前列没有其他皇后，当前左右斜对角线上没有其他皇后。然后每行有且只能存在一个皇后，所以进行逐行遍历，当每行都放置了皇后时，说明当前是题解之一，否则进行回溯，验证其他的放置策略。
题解：
class Solution {
public List> solveNQueens(int n) {
List> result = new ArrayList>();
//表示皇后所在的列数
int[] queens = new int[n];
Arrays.fill(queens,-1);
//表示有皇后在的列的集合
Set columns = new HashSet<>();
//表示有皇后所在的左对角线的集合
//特别的有性质：同一左对角线上，行数-列数=常数
Set leftDialog = new HashSet<>();
//表示有皇后所在的右对角线的集合
//特别的有性质：同一右对角线上，行数+列数=常数
Set rightDialog = new HashSet<>();
//进入深度搜索遍历的过程
backtracking(result, queens, columns, leftDialog, rightDialog, n, 0);
return result;
}
private void backtracking(List> result, int[] queens, Set columns, Set leftDialog, Set rightDialog, int n, int row) {
//如果每行都放置了皇后，得到一个可行的结果
if (row==n){
//将可行的结果构造为最后的题解之一
List board = new ArrayList<>();
for (int i=0;i
三、广度优先搜索
基本模型：基于队列的循环
while(队不为空)
{
根据队头尝试每一种拓展的可能
for(int i=0;i
BFS力扣例题
934. 最短的桥
分析：
首先找到一座岛，然后将它不断向外延伸，直到到达另一座岛。即用DFS找到岛屿，用BFS搜索最短的距离。
题解：
class Solution {
int[] direction = new int[]{-1,0,1,0,-1};
public int shortestBridge(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue queue = new linkedList<>();
//DFS寻找第一个岛屿，并把1赋值为2
boolean flag = false;
for (int i=0;i=0 && y>=0 && x queue, int[][] grid, int m, int n, int i, int j) {
//超出边界或遇到已经遍历过的点就结束方法
if (i<0 || j<0 || i==m || j==n || grid[i][j]==2){
return;
}
//如果遇到海洋，将其加入队列
if (grid[i][j]==0){
queue.offer(new Node(i,j));
return;
}
//如果就是该岛屿的土地，则以此为起点继续搜索
grid[i][j] = 2;
for (int k=0;k<4;++k) {
dfs(queue, grid, m, n, i + direction[k], j + direction[k + 1]);
}
}
static class Node{
int row;
int column;
Node(int row, int column){
this.row = row;
this.column = column;
}
}
}
126. 单词接龙2
分析：
运用BFS构建图，遍历每一种单词修改的情况，将其和单词表中的单词联系在一起，形成双向边。最后DFS找到最短路径。
题解：
class Solution {
public List> findLadders(String beginWord, String endWord, List wordList) {
List> result = new ArrayList<>();
//哈希表加快查找速率
Set dict = new HashSet<>(wordList);
//判断目标单词不在单词表中的情况
if (!dict.contains(endWord)){
return result;
}
//将起始单词从单词表中移除
dict.remove(beginWord);
//---------广度优先遍历构建图---------
//记录节点在BFS中的深度
Map depths = new HashMap<>();
depths.put(beginWord, 0);
//记录与每个节点相连的节点列表
Map> contact = new HashMap<>();
//构建BFS所需的队列
Queue queue = new linkedList<>();
queue.offer(beginWord);
//过程辅助变量
int depth = 1; //遍历的深度
boolean find = false; //标记是否已经找出一条路径
int wordLength = beginWord.length();//单词的长度
while (!queue.isEmpty()){
int size = queue.size();
for (int i=0;i());
contact.get(modifyWord).add(frontWord);
//记录修改单词的深度
depths.put(modifyWord, depth);
//若与目标单词相等，则说明已经找到了一条路径
if (modifyWord.equals(endWord)){
find = true;
}
}
//回溯，改回状态
charArrays[j] = origin;
}
}
//一次遍历后深度增加
depth++;
if (find){
break;
}
}
//---------深度优先遍历找到所有解---------
if (find){
Deque path = new ArrayDeque<>();
path.add(endWord);
backtracking(contact, path, beginWord, endWord, result);
}
return result;
}
private void backtracking(Map> contact, Deque path, String beginWord, String currentWord, List> result) {
if (currentWord.equals(beginWord)){
result.add(new ArrayList<>(path));
return;
}
for (String word:contact.get(currentWord)){
path.addFirst(word);
backtracking(contact, path, beginWord, word, result);
path.removeFirst();
}
}
}
