Long Luo's Life Notes

[LeetCode][334. Increasing Triplet Subsequence] Why Greedy Works?

发表于 2022-10-11 更新于 2025-05-03 分类于 Leetcode Waline：阅读次数：本文字数： 4.1k 阅读时长 ≈ 4 分钟

By Long Luo

This article is the solution Why Greedy Works? of Problem 334. Increasing Triplet Subsequence.

Intution

We can easily find that whether there exists a triple of indices \((i, j, k)\) such that \(i < j < k\) and \(nums[i] < \textit{nums}[j] < \textit{nums}[k]\) only traversing the array once, but the problem is how to make our mind into algorithms.

Brute Force

It’s easy to use Brute Force way to solve this problem, but the time complexity is \(O(n^3)\), it will TLE, so we need to find a better way.

public static boolean increasingTriplet(int[] nums) {
    if (nums == null || nums.length < 3) {
        return false;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            for (int k = j + 1; k < len; k++) {
                if (nums[i] < nums[j] && nums[j] < nums[k]) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

Time Complexity: \(O(n^3)\)
Space Complexity: \(O(1)\)

Dynamic Programming

We can also use DP method to solve it.

Let \(dp[i]\) represents the maximum length of a increasing sequence.

\[ dp[i] = \begin{cases} 1 & dp[i] \le dp[j], 0 < j < i \\ dp[j] + 1 & dp[i] > dp[j], 0 < j < i \end{cases} \]

阅读全文 »

[LeetCode] 迷宫问题(The Maze)

发表于 2022-10-03 更新于 2025-05-03 分类于 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-05-02 分类于 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-05-02 分类于 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-05-02 分类于 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)\).

阅读全文 »