[LeetCode] 迷宫问题(The Maze)

发表于 2022-10-03 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 8.6k 阅读时长 ≈ 8 分钟

By Long Luo

490. 迷宫 Medium
505. 迷宫 II Medium 499. 迷宫 III Hard

490. The Maze

BFS

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

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

        if (m * n <= 2) {
            return true;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);

        boolean[][] visited = new boolean[m][n];
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();

            int x = curPos[0];
            int y = curPos[1];

            if (x == destination[0] && y == destination[1]) {
                return true;
            }

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

                while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0) {
                    nextX += dir[0];
                    nextY += dir[1];
                }

                if (!visited[nextX - dir[0]][nextY - dir[1]]) {
                    visited[nextX - dir[0]][nextY - dir[1]] = true;
                    queue.offer(new int[]{nextX - dir[0], nextY - dir[1]});
                }
            }
        }

        return false;
    }
}

阅读全文 »

[LeetCode] 岛屿数量问题(Number of Islands)

发表于 2022-10-02 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 5.7k 阅读时长 ≈ 5 分钟

By Long Luo

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

200. 岛屿数量

BFS

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

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);
            }
        }
    }
}

阅读全文 »

[LeetCode] 会议室问题(Meeting Rooms)

发表于 2022-10-01 更新于 2025-02-13 分类于 Leetcode Waline：阅读次数：本文字数： 1.7k 阅读时长 ≈ 2 分钟

By Long Luo

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

252. 会议室

暴力

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;
}

排序

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;
}

阅读全文 »

[LeetCode][658. Find K Closest Elements] 4 Approaches: Two Pointers, Sorting, Priority Queue and Binary Search

发表于 2022-09-29 更新于 2025-02-13 分类于 Leetcode 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

// 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)\).

阅读全文 »

[LeetCode][19. Remove Nth Node From End of List] 3 Approaches: Brute Force, Stack, Slow Fast Pointers with Animation

发表于 2022-09-28 更新于 2025-02-13 分类于 Leetcode 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.

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)\)

阅读全文 »