动效做的好的网站,石家庄网络公司代理,一个在线做笔记的网站,石家庄新闻头条827. 最大人工岛
题目#xff1a;给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后#xff0c;grid 中最大的岛屿面积是多少#xff1f; 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 题目链接#xff1a;[827. 最大人工岛](ht…827. 最大人工岛
题目给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后grid 中最大的岛屿面积是多少 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 题目链接[827. 最大人工岛](https://leetcode.cn/problems/making-a-large-island/) 解题思路暴力解法 把每一个0改为1计算岛屿面积 复杂度改每一个0为1:n2计算岛屿最大面积n2 会超时 优化思路遍历记录所有岛屿面积 将0附近上下左右的岛屿进行联通 1.遍历记录所有岛屿面积 如何记录遍历过的岛屿标记岛屿编号从2开始 将岛屿编号和最大面积记录在set中 2. 将0附近上下左右的岛屿进行联通 如何判断0周围的面积遍历0周围的岛屿面积进行联通将周围的岛屿加入set以防重复叠加 代码如下
class Solution {public int[][] mark;public int[][] move{{0,1},{0,-1},{1,0},{-1,0}};public HashMapInteger, Integer island new HashMapInteger, Integer();public int largestIsland(int[][] grid) {//遍历岛屿并记录int maxArea0;int masknum2;marknew int[grid.length][grid[0].length];for(int i0;igrid.length;i){for(int j0;jgrid[0].length;j){if(mark[i][j]0grid[i][j]1){bfs(grid,i,j,masknum);masknum;}}}for(int value: island.values()) {if(valuemaxArea){maxAreavalue;}}//修改岛屿并记录面积for(int i0;igrid.length;i){for(int j0;jgrid[0].length;j){if(grid[i][j]0){HashSetInteger sites new HashSet();for(int p0;p4;p){int nextximove[p][0];int nextyjmove[p][1];if(nextx0||nextxgrid.length||nexty0||nextygrid.length){continue;}if(mark[nextx][nexty]!0){sites.add(mark[nextx][nexty]);}}//计算面积int area1;for(int p:sites){areaisland.get(p);}if(areamaxArea){maxAreaarea;}}}}return maxArea;}public void bfs(int[][] grid,int i,int j,int masknum){int area1;Queueint[] queuenew LinkedList();queue.offer(new int[]{i,j});mark[i][j]masknum;while(!queue.isEmpty()){int[] nodequeue.poll();for(int p0;p4;p){int nextxnode[0]move[p][0];int nextynode[1]move[p][1];if(nextx0||nextxgrid.length||nexty0||nextygrid.length){continue;}if(mark[nextx][nexty]0grid[nextx][nexty]1){queue.offer(new int[]{nextx,nexty});mark[nextx][nexty]masknum;area;}}}island.put(masknum,area);}
}217 单词接龙
题目字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - … - sk 每一对相邻的单词只差一个字母。 对于 1 i k 时每个 si 都在 wordList 中。注意 beginWord 不需要在 wordList 中。 sk endWord 给你两个单词 beginWord 和 endWord 和一个字典 wordList 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列返回 0 。 题目链接217 单词接龙
解题思路 为了保证从 beginWord 到 endWord 的转换序列是最短路径我们使用广度优先搜索BFS算法。BFS 有一个重要特性它首先访问距离源点在这个场景中是 beginWord最近的节点。因此当我们首次到达 endWord 时我们可以确信找到的路径是最短的。 我们使用队列进行广度优先搜索 每次从队列中取出一个单词查找与其相差一个字母的所有单词并将这些单词加入队列 为了防止重复处理相同的单词我们需要从 wordList 中移除已经处理过的单词。具体是将其与对应路径长度加入map中 代码如下
class Solution {public int ladderLength(String beginWord, String endWord, ListString wordList) {if (!wordList.contains(endWord)) {return 0;}if (!wordList.contains(beginWord)) {wordList.add(beginWord);}HashSetString wordSet new HashSet(wordList);QueueString queue new LinkedList();queue.offer(beginWord);MapString, Integer visited new HashMap();visited.put(beginWord, 1);while (!queue.isEmpty()) {String currentWord queue.poll();int currentLength visited.get(currentWord);for (String word : wordSet) {if (isOneLetterDiff(currentWord, word)) {if (word.equals(endWord)) {return currentLength 1;}if (!visited.containsKey(word)) {queue.offer(word);visited.put(word, currentLength 1);}}}}return 0;}private boolean isOneLetterDiff(String word1, String word2) {if (word1.length() ! word2.length()) {return false;}int diffCount 0;for (int i 0; i word1.length(); i) {if (word1.charAt(i) ! word2.charAt(i)) {diffCount;if (diffCount 1) {return false;}}}return diffCount 1;}
}
