Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.7k 阅读时长 ≈ 5 分钟

By Long Luo

200. 岛屿数量 305. 岛屿数量 II

200. 岛屿数量

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int numIslands_bfs(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    int row = grid.length;
    int col = grid[0].length;
    boolean[][] visited = new boolean[row][col];
    int ans = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                bfs(grid, visited, i, j);
                ans++;
            }
        }
    }

    return ans;
}

public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{x, y});
    visited[x][y] = true;
    while (!queue.isEmpty()) {
        int[] pos = queue.poll();
        for (int[] dir : dirs) {
            int nextX = pos[0] + dir[0];
            int nextY = pos[1] + dir[1];
            if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length
                    && !visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                queue.offer(new int[]{nextX, nextY});
                visited[nextX][nextY] = true;
            }
        }
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        boolean[][] visited = new boolean[m][n];

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, visited, i, j);
                    ans++;
                }
            }
        }

        return ans;
    }

    private void dfs(char[][] grid, boolean[][] visited, int x, int y) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        int m = grid.length;
        int n = grid[0].length;

        visited[x][y] = true;

        for (int[] dir : dirs) {
            int nextX = x + dir[0];
            int nextY = y + dir[1];

            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX][nextY] == '1' && !visited[nextX][nextY]) {
                dfs(grid, visited, nextX, nextY);
            }
        }
    }
}
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

By Long Luo

252. 会议室 253. 会议室 II
2402. 会议室 III

252. 会议室

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean canAttendMeetings_bf(int[][] intervals) {
    int len = intervals.length;
    if (len <= 1) {
        return true;
    }

    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            int[] m1 = intervals[i];
            int[] m2 = intervals[j];

            if (!(m1[1] <= m2[0] || m1[0] >= m2[1])) {
                return false;
            }
        }
    }

    return true;
}

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static boolean canAttendMeetings(int[][] intervals) {
    if (intervals == null || intervals.length <= 1) {
        return true;
    }

    Arrays.sort(intervals, (a, b) -> {
        if (a[0] == b[0]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false;
        }
    }

    return true;
}
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.2k 阅读时长 ≈ 5 分钟

By Long Luo

This article is the solution 4 Approaches: Two Pointers, Sorting, Priority Queue and Binary Search of Problem 658. Find K Closest Elements.

Here shows 4 Approaches to slove this problem: Two Pointers, Sorting, Priority Queue and Binary Search with Two Pointers.

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// TP time: O(n) space: O(1)
public static List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer> ans = new ArrayList<>();
    int len = arr.length;
    int targetPos = -1;
    int delta = Integer.MAX_VALUE;
    for (int i = 0; i < len; i++) {
        if (Math.abs(arr[i] - x) < delta) {
            delta = Math.abs(arr[i] - x);
            targetPos = i;
        }
    }

    ans.add(arr[targetPos]);
    k--;

    int left = targetPos - 1;
    int right = targetPos + 1;
    while (k > 0) {
        if (left >= 0 && right < len && Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
            ans.add(arr[left]);
            left--;
            k--;
        } else if (left >= 0 && right < len && Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
            ans.add(arr[right]);
            right++;
            k--;
        } else if (left >= 0 && right == len) {
            ans.add(arr[left]);
            left--;
            k--;
        } else if (left < 0 && right < len) {
            ans.add(arr[right]);
            right++;
            k--;
        }
    }

    Collections.sort(ans);

    return ans;
}

Analysis

  • Time Complexity: \(O(n + k \log k)\).
  • Space Complexity: \(O(n)\).
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

By Long Luo

This article is the solution 3 Approaches: Brute Force, Stack, Slow Fast Pointers with Animation of Problem 19. Remove Nth Node From End of List .

Here shows 3 Approaches to slove this problem: Brute Force, Stack, Slow Fast Pointers.

Brute Froce

It’s easy to think of the way that we traverse the linked list first, from the head node to the end node, to get the length of the linked list \(L\).

Then we traverse the linked list from the head node again. When the \(L-n+1\) th node is traversed, it is the node we need to delete.

We can traverse \(L-n+1\) nodes starting from the dummy node. When traversing to the \(L-n+1\)th node, its next node is the node we need to delete, so we only need to modify the pointer once to complete the deletion operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head.next == null && n == 1) {
        return null;
    }

    List<ListNode> nodeList = new ArrayList<>();
    ListNode pNode = head;
    int size = 0;
    while (pNode != null) {
        nodeList.add(pNode);
        size++;
        pNode = pNode.next;
    }

    if (n == size) {
        return head.next;
    } else if (n == 1) {
        pNode = nodeList.get(size - 2);
        pNode.next = null;
    } else {
        pNode = nodeList.get(size - n - 1);
        pNode.next = pNode.next.next;
    }

    return head;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.8k 阅读时长 ≈ 4 分钟

By Long Luo

This article is the solution From Brute Force to DP to Two Pointers with Detail Explaination of Problem 42. Trapping Rain Water .

Intuition

Trapping Rain Water

It’s like Leetcode 11. Container With Most Water , we can consider the black block as a wall, the blue block as water. Given an array, each element represents the height of the wall from left to right, find out how many units of water can be held.

The solution can be refered 2 Approaches: BF and Two Pointers with Image Explaination .

1. Brute Force

It’s easy to use the brute force approach. The time complexity is \(O(max^n)\) , so it will TLE.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Row time: O(max * n) space: O(1)
// TLE
public static int trap_row(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int maxHeight = 0;

    for (int x : height) {
        maxHeight = Math.max(maxHeight, x);
    }

    for (int i = 1; i <= maxHeight; i++) {
        boolean flag = false;
        int water = 0;
        for (int j = 0; j < len; j++) {
            if (flag && height[j] < i) {
                water++;
            }

            if (height[j] >= i) {
                ans += water;
                water = 0;
                flag = true;
            }
        }
    }

    return ans;
}

Analysis

  • Time Complexity: \(O(max^n)\)
  • Space Complexity: \(O(1)\)
阅读全文 »
0%