海南省住房城乡建设厅网站首页,wordpress文章里面的菜单怎么添加,广州智能建站,如何做一个自己的网站LeetCode 827.最大人工岛
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后#xff0c;grid 中最大的岛屿面积是多…LeetCode 827.最大人工岛
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后grid 中最大的岛屿面积是多少
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
解题思路深度优先遍历
首先通过深度优先遍历将所有岛屿按片为单位全部都标记下来也就是同一片岛屿的编号相同不同岛屿的编号不同。我们用unordered_map记录下来这一片片岛屿的面积。
下一步直接通过遍历所有的海洋也就是标号为0的点去看其四周的岛屿能不能链接起来如果可以我们就将对应岛屿的编号添加到unordered_set中去并将对应的岛屿值相加到count中再和result对比取最大值即可。
class Solution {
public:int count;//count用来记录当前这片岛屿的面积int dir[4][2] {0,1,1,0,-1,0,0,-1};//mark标记岛屿编号void dfs(vectorvectorint grid,vectorvectorbool visited,int x,int y,int mark){if(visited[x][y] || grid[x][y] 0) return;visited[x][y] true;grid[x][y] mark;//标记岛屿标号count;//当前岛屿面积加一for(int i0;i4;i){int nextx dir[i][0] x;int nexty dir[i][1] y;if(nextx 0 || nexty 0 || nextx grid.size() || nexty grid[0].size())continue;dfs(grid,visited,nextx,nexty,mark);}}int largestIsland(vectorvectorint grid) {int n grid.size(),m grid[0].size();vectorvectorbool visited vectorvectorbool (n,vectorbool(m,false));//记录岛屿编号对应的岛屿面积,key是岛屿的标号value是这片岛屿的面积。//一片岛屿的标号都是一样的unordered_mapint,int gridNum;int mark 2;//标号从2开始bool isAllGrid true;//标记是否全是岛屿,全是岛屿我们直接返回m*n即可for(int i0;in;i){for(int j0;jm;j){if(grid[i][j] 0) isAllGrid false;//不全是岛屿if(!visited[i][j] grid[i][j] 1){count 0;//清空count防止多次记录同一片岛屿dfs(grid,visited,i,j,mark);gridNum[mark] count;//将对应的键值对存储进mapmark;//标号自增防止标号重复}}}if (isAllGrid) return n * m; //全是岛屿直接返回int result 0; // 记录最后结果unordered_setint visitedGrid; // 标记这次的0链接过的岛屿for (int i 0; i n; i) {for (int j 0; j m; j) {int count 1; // 记录连接之后的岛屿数量visitedGrid.clear(); // 每次使用时清空。if (grid[i][j] 0) {for (int k 0; k 4; k) {int neari i dir[k][1]; // 计算相邻坐标int nearj j dir[k][0];if (neari 0 || neari grid.size() || nearj 0 || nearj grid[0].size()) continue;//count是计数看这个岛屿对应的mark标记有没有被添加进来//没有则代表这片岛屿没有被链接过。因为只要链接我们就去取其中这片岛屿//的值只要有一个链接了别的全都不能再链接了。if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result max(result, count);}}return result;}
}; 总结
深搜和广搜的问题广搜里面写的那个思路很清奇还是得多看题目的提示可以减少一点时间和空间的损耗。
LeetCode 127- 单词接龙
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - ... - sk
每一对相邻的单词只差一个字母。对于 1 i k 时每个 si 都在 wordList 中。注意 beginWord 不需要在 wordList 中。sk endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列返回 0 。
解题思路
首先明确本题题意意思就是我们需要从字典中找到begin 到 end 的最短路径每次只能更换一个字母。
本题思路是广度优先遍历首先我们将begin和step1入队并不断取出队首元素将队首元素中每个字母都进行从a - z 的替换。如果能在set中找到替换后的元素说明可以走这一步我们就将其入队并且将set中对应的元素删除防止出现反复走这一步的情况。并且替换一个字母后我们再将其还原看替换其他字母能不能行。直到遇到队首元素为end的情况直接返回step即可。
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {//开始我们将所有单词都记录到set中s用来记录字典中的单词是否已经用过用过则直接删除unordered_setstring s;//符号 表明 i 是一个引用变量能让接下来的循环可以修改s中的内容for(auto i : wordList)s.insert(i);//队列q用来表示当前到达当前字符需要的步数queuepairstring,int q;//压入开始词和1q.push({beginWord,1});//tmp为每次我们要换的单词string tmp;//step为每次的步数int step;while(!q.empty()){//若队头元素就是最终单词则直接返回对应的步数if(q.front().first endWord){return (q.front().second);}//取出队头元素tmp q.front().first;step q.front().second;q.pop();//开始尝试ch表示当前取出来字符串的每个字符。char ch;//这里是将当前字符串的每个字符都试试看看替换成a-z中的字符能否在字典中找到。//能找到我们就入队并且还原因为每次只修改一个字符如果不能则直接还原。for(int i0;itmp.length();i){ch tmp[i];for(char ca;cz;c){if(ch c) continue;tmp[i] c;if(s.find(tmp) ! s.end()){q.push({tmp,step1});s.erase(tmp);}tmp[i] ch;}}}return 0;}
}; 总结
广度优先但不知道如何模拟广度原来就是替换字母。还是多练习多看思路才行。
