《五月集训》（第15天）——深度优先搜索

前言：

五月集训，前面为学习内容，想要一起学习的可以看一看，最后的才是五月集训每天的作业。

一、知识点

深度优先搜索简单来说就是“装了南墙就回头”，沿着一条路一直走，走不通就回到前一个节点换个方向走。

二、课堂习题

这里的题均出自《算法零基础100讲》
更多知识点等到暑假的集训更新，或者着急的同学可以去看英雄哥的专栏。

三、作业

565. 数组嵌套
401. 二进制手表
1079. 活字印刷
1219. 黄金矿工
解题思路：
1.简单的暴力深搜就能求解，但是会超出时间限制，因此我们需要观察题目的规律对其进行剪枝，我们能直到对于一组走完的数组元素，它会形成一个闭环，其中的任何一个元素作为头部走的都是这个环，因此我们可以对于走过环里的元素进行标注，让其不再作为头部元素进行深搜；
2.深搜枚举，当亮灯数量满足要求时，将之前存起来的时间和小时数，进行判断，符合条件的则存入答案链表中；
3.深搜模板题，简单的hash标注dfs就可以；
4.上下左右走，有满足条件的就继续走，累加价值，当无路可走时，判断这条路累计的价值是否大于答案，然后进行回溯。
代码：

class Solution {    int temp = 0;    public int arrayNesting(int[] nums) { int ans = 0; int[] hash = new int[200010]; for(int i = 0;i < nums.length;i++){     if(hash[i] == -1){  continue;     }     hash[i] = 1;     temp = 1;     dfs(nums,hash,nums[i]);     if(ans < temp){  ans = temp;     } } return ans;    }    public void dfs(int[] nums,int[] hash,int i){ if(hash[i] != 0){     return; } temp++; hash[i] = -1; dfs(nums,hash,nums[i]);    }}

class Solution {    List<String> ans = new ArrayList<>();    int[] times = {8,4,2,1,32,16,8,4,2,1};    public List<String> readBinaryWatch(int turnedOn) { if(turnedOn < 0){     return ans; } dfs(turnedOn,0,0,0); return ans;    }    public void dfs(int num,int start,int h,int min){ if(num == 0){     if(h > 11 || min > 59){  return;     }     StringBuilder temp = new StringBuilder();     temp.append(h);     temp.append(":");     if(min < 10){  temp.append(0);     }     temp.append(min);     ans.add(temp.toString());     return; } for(int i = start;i < 10;i++){     if(i < 4){  h += times[i];     }else{  min += times[i];     }     dfs(num-1,i+1,h,min);     if(i < 4){  h -= times[i];     }else{  min -= times[i];     } }    }}

class Solution {    int[] hash = new int[26];    int ans = 0;    public int numTilePossibilities(String tiles) { for(int i = 0;i < tiles.length();i++){     hash[tiles.charAt(i) - 'A']++; } dfs(hash); return ans;    }    public void dfs(int[] hash){ for(int j = 0;j < 26;j++){     if(hash[j] != 0){  hash[j]--;  ans++;  dfs(hash);  hash[j]++;     } }    }}

class Solution {    int[][] hash;    int ans = 0,temp = 0;    int m,n;    static int[][] move = {{0,1},{1,0},{0,-1},{-1,0}};    public int getMaximumGold(int[][] grid) { m = grid.length; n = grid[0].length; hash = new int[m][n]; for(int i = 0;i < m;i++){     for(int j = 0;j < n;j++){  dfs(grid,i,j);  temp = 0;     } } return ans;    }    public void dfs(int[][] grid,int x,int y){ if(x == -1 || x == m || y == -1 || y == n || grid[x][y] == 0 || hash[x][y] != 0){     if(ans < temp){  ans = temp;     }     return; } hash[x][y] = 1; temp += grid[x][y]; int newx = x,newy = y; for(int i = 0;i < 4;i++){     newx += move[i][0];     newy += move[i][1];     dfs(grid,newx,newy);     newx -= move[i][0];     newy -= move[i][1]; } temp -= grid[x][y]; hash[x][y] = 0;    }}

四、总结

对于算法的掌握还是不够熟练，需要进行反复训练！
另外，剩下的课堂训练题目留到下个月的集训啦(●ˇ∀ˇ●)