文章目录
- 【LeetCode热题100】打卡第37天：岛屿数量&反转链表
- ⛅前言
- 岛屿数量
- 🔒题目
- 🔑题解
- 反转链表
- 🔒题目
- 🔑题解
【LeetCode热题100】打卡第37天：岛屿数量&反转链表
⛅前言
大家好，我是知识汲取者，欢迎来到我的LeetCode热题100刷题专栏！
精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。在此专栏中，我们将会涵盖各种类型的算法题目，包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等，并会提供详细的解题思路以及Java代码实现。如果你也想刷题，不断提升自己，就请加入我们吧！QQ群号：827302436。我们共同监督打卡，一起学习，一起进步。
博客主页💖：知识汲取者的博客
LeetCode热题100专栏🚀：LeetCode热题100
Gitee地址📁：知识汲取者 (aghp) - Gitee.com
Github地址📁：Chinafrfq · GitHub
题目来源📢：LeetCode 热题 100 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
PS：作者水平有限，如有错误或描述不当的地方，恳请及时告诉作者，作者将不胜感激
岛屿数量
🔒题目
原题链接：200.岛屿数量
🔑题解
-
解法一：DFS
对于这种搜索类的题目，DFS和BFS是一个比较直接的思想
- 我们需要遍历每一个节点，每一个节点都有可能成为搜索的起始点
- 然后将每一个搜索过的点，进行标记，下一次搜索就直接跳过
- 我们需要遍历前后左右四点
/** * @author ghp * @title * @description */ class Solution { public int numIslands(char[][] grid) { int n = grid.length; int m = grid[0].length; int count = 0; boolean[][] vis = new boolean[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!vis[i][j] && grid[i][j] != '0') { // 当前节点没有遍历过，并且不是水，则进行深度搜索 dfs(grid, vis, i, j); count++; } } } return count; } private void dfs(char[][] grid, boolean[][] vis, int i, int j) { if (i < 0 || i > grid.length-1 || j < 0 || j > grid[0].length-1 || grid[i][j] == '0') { // 超出范围或遇到水，结束搜索 return; } if (vis[i][j]){ // 节点已遍历 return; } // 将已遍历的节点标记为true vis[i][j] = true; // 往右遍历 dfs(grid, vis, i, j + 1); // 往左遍历 dfs(grid, vis, i, j - 1); // 往下遍历 dfs(grid, vis, i + 1, j); // 往上遍历 dfs(grid, vis, i - 1, j); } }复杂度分析：
- 时间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)，需要遍历每一个节点
- 空间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)，vis数组空间占用 n ∗ m n*m n∗m，递归调用如果全是陆地，则需要递归 n ∗ m n*m n∗m次，如果全是水，或者水和陆地均衡分布，只需要递归1次
其中 n n n 为数组的行， m m m为数组的列
代码优化：空间优化
前面我们使用一个vis数组来记录节点是否遍历，由于我们对于每一个节点只需要遍历一遍，所以可以直接将遍历过的节点置为0，即可，所以可以直接省略掉vis数组
class Solution { public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] != '0') { dfs(grid, i, j); count++; } } } return count; } private void dfs(char[][] grid, int i, int j) { if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[0].length - 1 || grid[i][j] == '0') { // 超出范围或遇到水，结束搜索 return; } grid[i][j] = '0'; // 往右遍历 dfs(grid, i, j + 1); // 往左遍历 dfs(grid, i, j - 1); // 往下遍历 dfs(grid, i + 1, j); // 往上遍历 dfs(grid, i - 1, j); } } -
解法二：BFS
一般能用DFS的题目都可以使用BFS来解决，实现思路也比较简单，本题是一个很规范的BFS和DFS的题
import java.util.LinkedList; import java.util.Queue; /** * @author ghp * @title * @description */ class Solution { public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] != '0') { // 不是水，则可以进行搜索 bfs(grid, i, j); count++; } } } return count; } private void bfs(char[][] grid, int i, int j) { // 方向数组：上、下、左、右 int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; Queue<int[]> queue = new LinkedList<>(); // 搜索起始节点 queue.add(new int[]{i, j}); // 开始广度搜索 while (!queue.isEmpty()) { // 回到上一个点的位置 int[] cur = queue.poll(); i = cur[0]; j = cur[1]; // 遍历四个方向 for (int k = 0; k < 4; k++) { int a = i + direction[k][0]; int b = j + direction[k][1]; if (0 <= a && a < grid.length && 0 <= b && b < grid[0].length && grid[a][b] != '0') { queue.add(new int[]{a, b}); grid[a][b] = '0'; } } } } }复杂度分析：
- 时间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)
- 空间复杂度： O ( m i n ( n , m ) ) O(min(n,m)) O(min(n,m))，即使最坏情况，整个网格都是陆地，队列的中的元素最多是 min(n,m)
其中 n n n 为数组的行， m m m为数组的列
-
解法三：并查集（详情看LeetCode官网）
这题我们只需要掌握好前面两种解法即可
class Solution { class UnionFind { int count; int[] parent; int[] rank; public UnionFind(char[][] grid) { count = 0; int m = grid.length; int n = grid[0].length; parent = new int[m * n]; rank = new int[m * n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1') { parent[i * n + j] = i * n + j; ++count; } rank[i * n + j] = 0; } } } public int find(int i) { if (parent[i] != i) parent[i] = find(parent[i]); return parent[i]; } public void union(int x, int y) { int rootx = find(x); int rooty = find(y); if (rootx != rooty) { if (rank[rootx] > rank[rooty]) { parent[rooty] = rootx; } else if (rank[rootx] < rank[rooty]) { parent[rootx] = rooty; } else { parent[rooty] = rootx; rank[rootx] += 1; } --count; } } public int getCount() { return count; } } public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int nr = grid.length; int nc = grid[0].length; int num_islands = 0; UnionFind uf = new UnionFind(grid); for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { grid[r][c] = '0'; if (r - 1 >= 0 && grid[r-1][c] == '1') { uf.union(r * nc + c, (r-1) * nc + c); } if (r + 1 < nr && grid[r+1][c] == '1') { uf.union(r * nc + c, (r+1) * nc + c); } if (c - 1 >= 0 && grid[r][c-1] == '1') { uf.union(r * nc + c, r * nc + c - 1); } if (c + 1 < nc && grid[r][c+1] == '1') { uf.union(r * nc + c, r * nc + c + 1); } } } } return uf.getCount(); } } 作者：LeetCode 链接：https://leetcode.cn/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
反转链表
🔒题目
原题链接：206.反转链表
🔑题解
-
解法一：暴力
public class Solution { public ListNode reverseList(ListNode head) { if (head == null){ return null; } List<Integer> list = new ArrayList<>(); while (head != null){ list.add(head.val); head = head.next; } Collections.reverse(list); ListNode newHead = new ListNode(list.remove(0)); ListNode p = newHead; while (!list.isEmpty()){ p.next = new ListNode(list.remove(0)); p = p.next; } return newHead; } }复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
其中 n n n 为链表节点的数量
-
解法二：双指针迭代实现
public class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null){ ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } }复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)
其中 n n n 为数组中元素的个数
-
解法三：双指针递归实现
public class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null){ return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } }
