Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

This article is the solution Two Heaps with the Follow Up’s Solution of Problem 295. Find Median from Data Stream.

Intuition

We can simply use a \(\texttt{ArrayList}\) to record the number and sort the list, then we can easily get the median element of the list. However, the Time Complexity will be \(O(n^2logn)\) and the Space Complexity is \(O(n)\).

It surely will be TLE and we have to find a better solution.

Heap

We can use Two Priority Queues (Heaps) to maintain the data of the entire data stream.

The min Heap denoted as \(\textit{queueMin}\) is used to maintain the number \(\textit{num} \leq \textit{median}\). The max Heap denoted as \(\textit{queueMax}\) is used to maintain the number \(\textit{num} \gt \textit{median}\).

  • When the total number of data stream elements is Even: \(\texttt{queueMax.size()} = \texttt{queueMin.size()}\), the dynamic median is \(\frac{\texttt{queueMax.peek()} + \texttt{queueMin.peek()}}{2}\);

  • When the total number of data stream elements is Odd: \(\texttt{queueMin.size()} = \texttt{queueMin.size()} + 1\), the dynamic median is \(\texttt{queueMin.peek()}\).

阅读全文 »

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

By Long Luo

今天 LeetCode CN 的每日一题是 1668. 最大重复子字符串 ，本文是该题的题解，同时发表在 这里 。

思路

这道题有好几个方法：

  1. API：使用 \(String\) \(API\) \(\texttt{contains(CharSequence s)}\) 来判断 \(\textit{sequence}\) 中是否存在拼接的 \(N\) 个 \(\textit{word}\) 字符串；
  2. KMP: 使用 KMP 算法判断 \(\textit{sequence}\) 中是否存在拼接的 \(N\) 个 \(\textit{word}\) 字符串；
  3. 暴力：判断是否存在拼接的 \(N\) 个 \(\textit{word}\) ，虽然很简单，但代码要写的优雅简洁有难度。

API 方法最简单，但 KMP 算法比较复杂。看了一些题解里的暴力解法，大多数人的暴力解法写的太复杂。我自己写该题暴力解法也写了 \(3\) 个版本，前 \(2\) 个版本也很复杂，逐渐优化为目前的简洁优雅版本。

暴力解法使用 \(2\) 个循环，第 \(1\) 个循环，遍历 \(\textit{sequence}\) 中的每个字符，判断是否和 \(\texttt{word.charAt(0)}\) 相同，相同的话的进入下一步；

使用一个索引 \(j\) ，\(0 \le j \le len - i\) ，而这里 \(\textit{word}\) 字符索引可以使用 \(j \mod wLen\) 来获取，这是暴力解法中最优雅的地方。如果遇到不相同的字符，跳出循环。

最后更新最大重复子字符串，就是 \(\textit{ans}\) 和 \(j / wLen\) 的更大值。

中间其实还可以剪枝，但由于数据量比较小，就不加了。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxRepeating(String sequence, String word) {
        int sLen = sequence.length();
        int wLen = word.length();

        int ans = 0;

        for (int i = 0; i < sLen; i++) {
            if (sequence.charAt(i) != word.charAt(0)) {
                continue;
            }
            
            int j = 0;
            while (i + j < sLen && sequence.charAt(i + j) == word.charAt(j % wLen)) {
                j++;
            }

            ans = Math.max(ans, j / wLen);
        }

        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n^2)\) ，其中 \(n\) 是字符串 \(\textit{sequence}\) 长度，存在 \(2\) 个循环，所以总时间复杂度为 \(O(n^2)\) 。
  • 空间复杂度：\(O(1)\) 。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

发表于 更新于 分类于 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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} \]

阅读全文 »

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

By Long Luo

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

490. The Maze

490 The Maze
490 The Maze 2

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
40
41
42
43
44
45
46
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;
    }
}
阅读全文 »

发表于 更新于 分类于 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);
            }
        }
    }
}
阅读全文 »
0%