算法专练：深度优先搜索

文章目录

• 1.565. 数组嵌套
• 2.401. 二进制手表
• 3.1079. 活字印刷
• 4.1219. 黄金矿工

1.565. 数组嵌套

原题链接

        索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], … }且遵守以下的规则。

        假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]… 以此类推，不断添加直到S出现重复的元素。

        输入: A = [5,4,0,3,1,6,2]

        输出: 4

        提示：

        N是[1, 20,000]之间的整数。

        A中不含有重复的元素。

        A中的元素大小在[0, N-1]之间。

        没什么好说的，先建立一个判读之前是否添加过该数的数组，然后在搜索中不断加入当前数字直到重复即可。

class Solution {int max,cnt;bool hash[200005];void dfs(vector<int>&nums,int u){if(hash[u]){return ;}++cnt;hash[u]=true;dfs(nums,nums[u]);}
public:int arrayNesting(vector<int>& nums) {int n=nums.size();memset(hash,0,sizeof(hash));max=0;for(int i=0;i<n;++i){if(!hash[i]){cnt=0;dfs(nums,i);}max=cnt>max?cnt:max;}return max;}
};

2.401. 二进制手表

原题链接

        二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

        给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
小时不以零开头：

        例如，“01:00” 是无效的时间，正确的写法应该是 “1:00” 。

        分钟必须由两位数组成，可能会以零开头：

        例如，“10:2” 是无效的时间，正确的写法应该是 “10:02” 。

        示例 1：

        输入：turnedOn = 1

        输出：[“0:01”,“0:02”,“0:04”,“0:08”,“0:16”,“0:32”,“1:00”,“2:00”,“4:00”,“8:00”]

        示例 2：

        输入：turnedOn = 9

        输出：[]

        提示：

        0 <= turnedOn <= 10

        先看代码，这是最暴力的解法：

class Solution {vector<string> ans;int stk[10],top;int hv[4]={8,4,2,1};int mv[6]={32,16,8,4,2,1};string change(int h,int m){string ret="";if(h<=9){ret+=h+'0';}else {ret+=h/10+'0';ret+=h%10+'0';}ret +=":";ret+=m/10+'0';ret+=m%10+'0';return ret;}//这里是吧数字转换成题目要求的字符串void dfs(int led,int maxled,int light,int maxlight){if(led==maxled){if(light==maxlight){int h=0,m=0;for(int i=0;i<top;++i){int x=stk[i];if(x<=3){h+=hv[x];}else {m+=mv[x-4];}}if(h<=11&&m<=59){ans.push_back(change(h,m));}}return;}if(light>maxlight){return;//防止出现light>maxlight而所有的灯还没有遍历完的情况}dfs(led+1,maxled,light,maxlight);stk[top++]=led;dfs(led+1,maxled,light+1,maxlight);--top;}
public:vector<string> readBinaryWatch(int turnedOn) {ans.clear();top=0;dfs(0,10,0,turnedOn);return ans;}
};

        先介绍dfs的四个参数：led,maxled分别代表我们当前枚举到的灯号和最大灯的数目。light，maxlight代表我们已经打开的灯的数量和最多能打开的灯的数量。

        对于每号灯我们有两种选择，亮还是不亮，如果不选他的话light不变继续搜索，否则就在栈中加入当前灯号并使得light++。搜索结束的条件就是在该路径下，如果所有的灯号都搜索过并且light==turnedon的时候在答案中加入该路径下存储的时间转化成的字符串。

3.1079. 活字印刷

原题链接

        你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

        注意：本题中，每个活字字模只能使用一次。

        示例 1：

        输入：“AAB”

        输出：8

        解释：可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。

        示例 2：

        输入：“AAABBC”

        输出：188

        示例 3：

        输入：“V”

        输出：1

        提示：

        1 <= tiles.length <= 7

        tiles 由大写英文字母组成

        由于tiles.length最大只有7，所以暴力是完全可以过的。这道题的做法类似于全排列，不过他允许有重复的字母但是不允许有重复的位置出现。所以我们对位置进行标记，在搜索的过程中如果该位置没有被标记过就进行从头开始搜索，直到当层等于我们要求的最大深度即可。

        另外由于题目还要求不能出现重复的字符串，所以搜索的过程中我们要对当前路径的字符串进行记录，并在最后dep==maxd的时候进行判断之前是否添加过该字符串，如果没有就对该字符串进行标记并使答案加一。

class Solution {char stk[10];int top;int cnt=0;unordered_map<string,bool> ans;bool vis[8];void dfs(string & tiles,int dep,int maxd){if(dep==maxd){stk[top]='\0';if(ans.find(stk)==ans.end()){ans[stk]=true;++cnt;}return ;}if(dep>maxd){return ;}int i,n=tiles.size();for(i=0;i<n;++i){if(!vis[i]){vis[i]=true;stk[top++]=tiles[i];dfs(tiles,dep+1,maxd);--top;vis[i]=false;}}}
public:int numTilePossibilities(string tiles) {memset(vis,false,sizeof(vis));cnt=top=0;for(int i=1;i<=tiles.size();++i){dfs(tiles,0,i);}return cnt;}
};

4.1219. 黄金矿工

原题链接

        你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

        为了使收益最大化，矿工需要按以下规则来开采黄金：

        每当矿工进入一个单元，就会收集该单元格中的所有黄金。

        矿工每次可以从当前位置向上下左右四个方向走。

        每个单元格只能被开采（进入）一次。

        不得开采（进入）黄金数目为 0 的单元格。

        矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
示例 1：
输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
示例 2：
输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
提示：
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格中有黄金。

        bfs的模板题了，搜索出一条最长路即可，虽然格子的数目是15*15,但是黄金的个数只有25个，完全可以暴力。

class Solution {int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int row,col;bool vis[16][16];int ans;void dfs(int x,int y,vector<vector<int>> &grid,int sum){ans=max(ans,sum);for(int i=0;i<4;++i){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx==-1||ty==-1||tx==row||ty==col){continue;}if(!grid[tx][ty]){continue;}if(!vis[tx][ty]){vis[tx][ty]=1;dfs(tx,ty,grid,sum+grid[tx][ty]);vis[tx][ty]=0;}}}
public:int getMaximumGold(vector<vector<int>>& grid) {row=grid.size();col=grid[0].size();ans=0;memset(vis,false,sizeof(vis));for(int i=0;i<row;++i){for(int j=0;j<col;++j){if(grid[i][j]){vis[i][j]=1;dfs(i,j,grid,grid[i][j]);vis[i][j]=0;}}}return ans;}
};

另外介绍一种更快的方法：

int getmax(int **grid,int gridSize,int gridColSize,int i,int j)
{if(i<0||i>=gridSize||j<0||j>=gridColSize||grid[i][j]==0){return 0;}int tmp=grid[i][j];grid[i][j]=0;int left=getmax(grid,gridSize,gridColSize,i,j-1);int right=getmax(grid,gridSize,gridColSize,i,j+1);int up=getmax(grid,gridSize,gridColSize,i+1,j);int down=getmax(grid,gridSize,gridColSize,i-1,j);int max=fmax(left,fmax(right,fmax(up,down)));grid[i][j]=tmp;return max+tmp;
}
int getMaximumGold(int** grid, int gridSize, int* gridColSize)
{int max=0;for(int i=0;i<gridSize;i++){for(int j=0;j<gridColSize[0];j++){max=fmax(max,getmax(grid,gridSize,gridColSize[0],i,j));}}return max;
}

这种方法就是以当前格子为我们记录的起点，直接去搜索有黄金的格子的四个方向，得到这四个方向范围内的最大黄金数目。虽然看上去跟第一种方法一样，实际上也是如此。不过不同的是这种方法的处理效率十分的快，最后某个方向递归结束的条件是到达了该方向范围某个单个格子，这个时候计算四次就可以直接返回到上级。又由于黄金的数目最多只有25个，可想而知该方法远远到不到阶乘级别明显优于第一种。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！