一切皆可搜索
一切皆可搜索
深度遍历搜索
深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。
leetcode695
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
res = Math.max(res, dfs(i, j, grid));
}
}
}
return res;
}
// 每次调用的时候默认num为1，进入后判断如果不是岛屿，则直接返回0，就可以避免预防错误的情况。
// 每次找到岛屿，则直接把找到的岛屿改成0，这是传说中的沉岛思想，就是遇到岛屿就把他和周围的全部沉默。
// ps：如果能用沉岛思想，那么自然可以用朋友圈思想。有兴趣的朋友可以去尝试。
private int dfs(int i, int j, int[][] grid) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0;
int num = 1;
num += dfs(i + 1, j, grid);
num += dfs(i - 1, j, grid);
num += dfs(i, j + 1, grid);
num += dfs(i, j - 1, grid);
return num;
}
}
leetcode547
class Solution {
public int findCircleNum(int[][] isConnected) {
int proviences = isConnected.length;
boolean[] visited = new boolean[proviences];
int count =0;
for(int i = 0; i <proviences; i++){
if(!visited[i]){
dfs(isConnected,visited,proviences,i);
count++;
}
}
return count;
}
public void dfs(int[][] isConnected, boolean[] visited,int proviences, int i ){
for(int j =0; j<proviences;j++){
if(isConnected[i][j]== 1 &&!visited[j]){
visited[j]= true;
dfs(isConnected,visited,proviences,j);
}
}
}
}
思路：使用visited记录已搜索得部分；
leetcode417
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
if(heights.length == 0||heights[0].length==0)
return new ArrayList<>();
int m = heights.length;
int n = heights[0].length;
int[][] pacific = new int[m][n];
int[][] atlantic = new int[m][n];
//从海洋边界开始
for(int i =0;i<m;i++){
for(int j = 0;j<n;j++){
if(i==0||j==0)
dfs(heights,pacific,i,j,heights[i][j]);
if(i==m-1||j==n-1)
dfs(heights,atlantic,i,j,heights[i][j]);
}
}
List<List<Integer>> res = new ArrayList<>();
for(int i =0;i<m;i++){
for(int j=0;j<n;j++){
if(pacific[i][j]==1&&atlantic[i][j]==1)
res.add(Arrays.asList(i, j));
}
}
return res;
}
public void dfs(int[][] matrix,int[][] aux,int i,int j,int pre){
if(i<0||j<0||i>matrix.length-1||j>matrix[0].length-1
||aux[i][j]==1||matrix[i][j]<pre)
return;
aux[i][j]=1;
dfs(matrix,aux,i-1,j,matrix[i][j]);
dfs(matrix,aux,i+1,j,matrix[i][j]);
dfs(matrix,aux,i,j-1,matrix[i][j]);
dfs(matrix,aux,i,j+1,matrix[i][j]);
}
}
回溯法
回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。
顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点状态]。
回溯法修改一般有两种情况，一种是修改最后一位输出，比如**排列组合**；一种是修改访问标记，比如矩阵里搜字符串。
回溯法三部曲
1、递归函数的返回值以及参数
在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
2、回溯函数终止条件
3、单层搜索的过程
模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}1
leetcode46
class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if(len == 0) return res;
boolean[] used = new boolean[len];
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums,len,0,path,used,res);
return res;
}
public void dfs(int[] nums, int len,int depth,Deque<Integer> path,boolean[] used,List<List<Integer>> res){
if(depth == len){
res.add(new ArrayList<>(path));
return;
}
for(int i = 0;i<len;i++){
if(!used[i]){
path.addLast(nums[i]);
used[i] = true;
dfs(nums,len,depth+1,path,used,res);
used[i] = false;
path.removeLast();
}
}
}
}
重点： path.addLast(nums[i]);
used[i] = true;
dfs(nums,len,depth+1,path,used,res);
used[i] = false;
path.removeLast();
尝试后，再将原来的状态修改回去；
leetcode 77
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if(k>n) return res;
List<Integer> path = new ArrayList<>();
dfs(n,k,1,path,res);
return res;
}
public void dfs(int n, int k ,int start,List<Integer> path,List<List<Integer>> res){
if(path.size() == k){
res.add(new ArrayList<>(path));
return;
}
for(int i = start;i<=n;i++){
path.add(i);
dfs(n,k,i + 1,path,res);
path.remove(path.size()-1);
}
}
}