8.算法之搜索
- 岛屿的个数
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
DFS:递归
注意：图5搜完之后，会回退到图3！
所以先判断是否在地图内，然后判断是否已经搜索过，接着判断是否为陆地，再进行探索。
BFS:队列
求地图岛屿数量：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int island_num=0;
vector<vector<int>> mark;
for(int i=0;i<grid.size();i++){
mark.push_back(vector<int>());
for(int j=0;j<grid[i].size();j++){
mark[i].push_back(0);
}
}
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[i].size();++j){
if(mark[i][j]==0&&grid[i][j]=='1'){
BFS(mark,grid,i,j);//DFS(mark,grid,i,j);
island_num++;
}
}
}
return island_num;
}
private:
void DFS(vector<vector<int>>& mark,
vector<vector<char>>& grid,
int x,int y)
{
mark[x][y]=1;
static const int dx[]={-1,1,0,0};
static const int dy[]={0,0,-1,1};
for(int i=0;i<4;i++)
{
int newx=x+dx[i];
int newy=y+dy[i];
if(newx<0||newx>=mark.size()||
newy<0||newy>=mark[newx].size()){//超过数组边界
continue;
}
if(mark[newx][newy]==0&&grid[newx][newy]=='1')
BFS(mark,grid,newx,newy);
}
}
void BFS(vector<vector<int>>& mark,
vector<vector<char>>& grid,
int x,int y){
static const int dx[]={-1,1,0,0};
static const int dy[]={0,0,-1,1};
queue<pair<int,int>> Q;
Q.push(make_pair(x,y));
mark[x][y]=1;
while(!Q.empty()){
x=Q.front().first;
y=Q.front().second;
Q.pop();
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
if(newx<0||newx>=mark.size()||
newy<0||newy>=mark[newx].size()){//超过数组边界
continue;
}
if(mark[newx][newy]==0&&grid[newx][newy]=='1'){
Q.push(make_pair(newx,newy));
mark[newx][newy]=1;
}
}
}
}
};
- 单词接龙
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: 5
解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: 0
解释: endWord “cog” 不在字典中，所以无法进行转换。
模型：
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
map<string,vector<string>> graph;
construct_graph(beginWord,wordList,graph);
return BFS_graph(beginWord,endWord,graph);
}
private:
bool connect(const string &word1,const string &word2)
{//记录word1和word2不相等字符个数
int cnt=0;
for(int i=0;i<word1.length();++i){
if(word1[i]!=word2[i])
cnt++;
}
return cnt==1;
}
void construct_graph(string &beginWord,
vector<string> &wordList,
map<string,vector<string>> &graph){
wordList.push_back(beginWord);
for(int i=0;i<wordList.size();++i){
graph[wordList[i]]=vector<string>();
}
for(int i=0;i<wordList.size();++i){
for(int j=i+1;j<wordList.size();++j){
if(connect(wordList[i],wordList[j])){
graph[wordList[i]].push_back(wordList[j]);
graph[wordList[j]].push_back(wordList[i]);
}
}
}
}
int BFS_graph(string &beginWord,string &endWord,
map<string,vector<string>>&graph){
queue<pair<string,int>> Q;
set<string> visit;
Q.push(make_pair(beginWord,1)); //添加起始点，起始点步数为1
visit.insert(beginWord);//标记起点已访问
while(!Q.empty()){
string node= Q.front().first;//取队列头部节点与步数
int step=Q.front().second;
Q.pop();
if(node==endWord)//找到终点，返回步数
return step;
const vector<string> &neighbors=graph[node];//取node得全部邻接点
for(int i=0;i<neighbors.size();i++){
if(visit.find(neighbors[i])==visit.end()){
Q.push(make_pair(neighbors[i],step+1));
visit.insert(neighbors[i]);//标记neighbors[i]已添加到队列
}
}
}
return 0;
}
};
- 单词接龙 II
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:
[
[“hit”,“hot”,“dot”,“dog”,“cog”],
[“hit”,“hot”,“lot”,“log”,“cog”]
]
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: []
解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。
struct Qitem{
string node;//搜索结点
int parent_pos;//前驱结点在队列中的位置
int step;//到达当前节点的步数
Qitem(string _node,int _parent_pos,int _step)
:node(_node),parent_pos(_parent_pos),step(_step){}
};
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
map<string,vector<string>> graph;
construct_graph(beginWord,wordList,graph);
vector<Qitem> Q;
vector<int> end_word_pos;
BFS_graph(beginWord,endWord,graph,Q,end_word_pos);
vector<vector<string>> result;
for(int i=0;i<end_word_pos.size();i++){
int pos=end_word_pos[i];
vector<string> path;
while(pos!=-1){
path.push_back(Q[pos].node);
pos=Q[pos].parent_pos;
}
result.push_back(vector<string>());
for(int j=path.size()-1;j>=0;j--){
result[i].push_back(path[j]);
}
}
return result;
}
private:
bool connect(const string &word1,const string &word2)
{//记录word1和word2不相等字符个数
int cnt=0;
for(int i=0;i<word1.length();++i){
if(word1[i]!=word2[i])
cnt++;
}
return cnt==1;
}
void construct_graph(string &beginWord,
vector<string> &wordList,
map<string,vector<string>> &graph){
int has_begin_word=0;
for(int i=0;i<wordList.size();++i){//由于wordList可能有beginWord,直接将beginWord push进入wordList,会出现重复结果
if(wordList[i]==beginWord)
has_begin_word=1;
graph[wordList[i]]=vector<string>();
}
for(int i=0;i<wordList.size();++i){
for(int j=i+1;j<wordList.size();++j){
if(connect(wordList[i],wordList[j])){
graph[wordList[i]].push_back(wordList[j]);
graph[wordList[j]].push_back(wordList[i]);
}
}
if(has_begin_word==0&&connect(beginWord,wordList[i])){
graph[beginWord].push_back(wordList[i]);
}
}
}
void BFS_graph(string &beginWord,string &endWord,
map<string,vector<string>> &graph,//使用vector实现队列，可保存所有信息
vector<Qitem>&Q,vector<int> &end_word_pos){//终点endWord所在队列得位置下标
map<string,int> visit;//单词，步数
int min_step=0;//到达endWord的最小步数
Q.push_back(Qitem(beginWord.c_str(),-1,1));//起始单词的前驱为1
visit[beginWord]=1;//标记起始单词的步数为1
int front=0;//队列头指针，指向vector的队列头
while(front!=Q.size()){//front指向Q.size()尾部时，队列为空
const string &node=Q[front].node;
int step=Q[front].step;
if(min_step!=0&&step>min_step){//step>min_step,代表所有到终点的路径都搜索完成
break;
}
if(node==endWord){//当搜索到结果时，记录到达终点的最小步数
min_step=step;
end_word_pos.push_back(front);
}
const vector<string> &neighbors=graph[node];
for(int i=0;i<neighbors.size();i++){
if(visit.find(neighbors[i])==visit.end()
||(step+1)==visit[neighbors[i]]){//结点没被访问过，或者另一条最短路径
Q.push_back(Qitem(neighbors[i],front,step+1));
visit[neighbors[i]]=step+1;//标记到达邻接点neighbors[i]的最小步数
}
}
front++;
}
}
};
回溯深搜： 当求最短时、当尝试、试探时
宽搜/深搜遍历所有的点、位置、遍历地图等，复杂度差不多
- 火柴拼正方形
还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1:
输入: [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
注意:
给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。
class Solution {
public:
bool makesquare(vector<int>& nums) {
if(nums.size()<4)//数量小于4，则无法摆正方形的四条边
return false;
int sum=0;
for(int i=0;i<nums.size();i++)
sum+=nums[i];
if(sum%4!=0)//总和若不是4的倍数也无法成功
return false;
sort(nums.rbegin(),nums.rend());//sort默认从小到大排序
int bucket[4]={0};//装火柴的桶
return generate(0,nums,sum/4,bucket);
}
private:
bool generate(int i,vector<int>& nums,int target,int bucket[])
{
if(i>=nums.size()){
return bucket[0]==target&&bucket[1]==target
&&bucket[2]==target&&bucket[3]==target;
}
for(int j=0;j<4;j++){//4个桶分别尝试
if(bucket[j]+nums[i]>target)
continue;
bucket[j]+=nums[i];//放入j桶中
if(generate(i+1,nums,target,bucket)){
return true;
}
bucket[j]-=nums[i];
}
return false;
}
};
class Solution {
public:
bool makesquare(vector<int>& nums) {
if(nums.size()<4)//数量小于4，则无法摆正方形的四条边
return false;
int sum=0;
for(int i=0;i<nums.size();i++)
sum+=nums[i];
if(sum%4!=0)//总和若不是4的倍数也无法成功
return false;
int target=sum/4;
vector<int> ok_subset;//所有满足条件的一个边代表的集合
vector<int> ok_half;//所有满足条件的两个边代表的集合
int all=1<<nums.size();//
for(int i=0;i<all;++i){
int sum=0;
for(int j=0;j<nums.size();++j){
if(i&(1<<j))//保证i和j不是同一个
sum+=nums[j];
}
if(sum==target)
ok_subset.push_back(i);
}
for(int i=0;i<ok_subset.size();++i){
for(int j=i+1;j<ok_subset.size();++j){
if((ok_subset[i]&ok_subset[j])==0)//说明集合无交集
ok_half.push_back(ok_subset[i]|ok_subset[j]);
}
}//完成两条满足要求的边的组合
for(int i=0;i<ok_half.size();++i){
for(int j=i+1;j<ok_half.size();++j){
if((ok_half[i]&ok_half[j])==0)
return true;
}
}//完成四条边（两条边组合）的边的组合
return false;
}
};
- 接雨水 II
给定一个 m x n 的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
说明:
m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。
示例：
给出如下 3x6 的高度图:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
返回 4。
如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。
下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。
拿出一个点2，当水面为2，探索该点四周的点，当发现1比2小，就可以积水，因为2此时是最低的点，所以它不可能从1再流出去，升高1的位置的水面高度为2，修改其高度。
struct Qitem
{
int x;
int y;
int h;
Qitem(int _x,int _y,int _h):x(_x),y(_y),h(_h){}
};
struct cmp{
bool operator()(const Qitem &a,const Qitem &b){
return a.h>b.h;
}
};
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
priority_queue<Qitem,vector<Qitem>,cmp> Q;
if(heightMap.size()<3||heightMap[0].size()<3)
return 0;
int row=heightMap.size();
int column=heightMap[0].size();
vector<vector<int>> mark;
for(int i=0;i<row;++i){
mark.push_back(vector<int>());
for(int j=0;j<column;++j)
mark[i].push_back(0);
}
for(int i=0;i<row;++i){
Q.push(Qitem(i,0,heightMap[i][0]));
mark[i][0]=1;
Q.push(Qitem(i,column-1,heightMap[i][column-1]));
mark[i][column-1]=1;
}
for(int i=1;i<column-1;++i){
Q.push(Qitem(0,i,heightMap[0][i]));
mark[0][i]=1;
Q.push(Qitem(row-1,i,heightMap[row-1][i]));
mark[row-1][i]=1;
}
static const int dx[]={-1,1,0,0};
static const int dy[]={0,0,-1,1};
int result=0;//最终积水量
while(!Q.empty()){
int x=Q.top().x;
int y=Q.top().y;
int h=Q.top().h;
Q.pop();
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
if(newx<0||newx>=row||
newy<0||newy>=column||mark[newx][newy]){
continue;//当新拓展的点超出边界或者已加入队列
}
if(h>heightMap[newx][newy]){//当前点的高度高于拓展点
result+=(h-heightMap[newx][newy]);
heightMap[newx][newy]=h;
}
Q.push(Qitem(newx,newy,heightMap[newx][newy]));
mark[newx][newy]=1;
}
}
return result;
}
};