网站底部源码,wordpress图像大小设置,wordpress页面文字,淄博网站建设服务商827.最大人工岛
思路一#xff1a;深度优先遍历
1.深度优先遍历#xff0c;求出所有岛屿的面积#xff0c;并且把每个岛屿记上不同标记2.使用 unordered_map 使用键值对#xff0c;标记#xff1a;面积#xff0c;记录岛屿面积3.遍历所有海面#xff0c;然后进行一次广…827.最大人工岛
思路一深度优先遍历
1.深度优先遍历求出所有岛屿的面积并且把每个岛屿记上不同标记2.使用 unordered_map 使用键值对标记面积记录岛屿面积3.遍历所有海面然后进行一次广度优先遍历使用 unordered_set 记录访问情况同时通过 unordered_map 去连接相邻岛屿更新最大面积情况
class Solution {
private:int count;int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向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 i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; // 越界了直接跳过dfs(grid, visited, nextx, nexty, mark);}}public:int largestIsland(vectorvectorint grid) {int n grid.size(), m grid[0].size();vectorvectorbool visited vectorvectorbool(n, vectorbool(m, false)); // 标记访问过的点unordered_mapint ,int gridNum;int mark 2; // 记录每个岛屿的编号bool isAllGrid true; // 标记是否整个地图都是陆地for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 0) isAllGrid false;if (!visited[i][j] grid[i][j] 1) {count 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] count; // 记录每一个岛屿的面积mark; // 记录下一个岛屿编号}}}if (isAllGrid) return n * m; // 如果都是陆地返回全面积// 以下逻辑是根据添加陆地的位置计算周边岛屿面积之和int result 0; // 记录最后结果unordered_setint visitedGrid; // 标记访问过的岛屿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;if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result max(result, count);}}return result;}
}; 127.单词接龙
分析
1.使用 unordered_set 加快查询速度2.使用 unordered_map 记录查询的次数3.使用队列去进行广度优先遍历
思路一广度优先遍历
1.通过对 beginword 每一个单词的替换寻找 set 中是否存在存在即可以直接修改到达2.并且进行修改的次数记录通过广度优先遍历每次找出所有能到达的结果只要找到 endword必然是最短路径
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {int nwordList.size();unordered_setstringset(wordList.begin(),wordList.end());//加快查找速度if(set.find(endWord)set.end()) return 0;//判断是否能找到unordered_mapstring,intmap;queuestringque;que.push(beginWord);map[beginWord]1;while(!que.empty()){string midque.front();que.pop();int pathmap[mid];//找到当前走的步数for(int i0;imid.size();i){//对每一个字符进行判断string newmidmid;for(int j0;j26;j){//对每一个字符进行修改newmid[i]ja;if(newmidendWord) return path1;//到达结果字符时//在字典中存在这个新修改的单词时还没有记录步数时if(set.find(newmid)!set.end() map.find(newmid)map.end()){map[newmid]path1;//记录步数que.push(newmid);//放入下一次广度优先遍历}}}}return 0;}
}; 841.钥匙和房间
分析
1.使用 unordered_set 记录访问过的房间2.使用 queue 进行广度优先遍历
思路一广度优先遍历
从第 0 个房间开始遍历获取钥匙放入 que 然后记录遍历过的房间将遍历过房间弹出队列
class Solution {
public:bool canVisitAllRooms(vectorvectorint rooms) {int nrooms.size();queueintque;unordered_setintset;que.push(0);while(!que.empty()){//广度优先遍历int keYque.front();que.pop();if(set.find(keY)!set.end()) continue;//遍历过的房间不再遍历for(int i0;irooms[keY].size();i) que.push(rooms[keY][i]);//遍历当前房间内的所有钥匙set.insert(keY);//记录遍历过的房间}return set.size()n;}
};
