By Long Luo

今天 LeetCode 第320场周赛 中第一题是 2475. 数组中不等三元组的数目 ，本文是该题的题解，同时发表在 这里 。

参考了 @灵茶山艾府 的题解 非暴力做法 ，实际上我们可以不用先排序，而是先用 \(\texttt{HashMap}\) 统计数组 \(\textit{num}\) 元素频率。

之后遍历 \(\texttt{HashMap}\) ，结果为：

\[ \sum_{j = 0}^{n} (map[0] + \cdots + map[i]) \times map[j] \times (map[k] + \cdots + map[n - 1]) \]

，其中 \(n\) 为 \(\textit{nums}\) 的长度。

证明如下：

对于数组中的元素 \(x\) ，可以得到：

• 小于 \(x\) 的数有 \(a\) 个；
• 等于 \(x\) 的数有 \(b\) 个；
• 大于 \(x\) 的数有 \(c\) 个。

那么 \(x\) 对最终答案的贡献是 \(abc\) 。

即使 \(x\) 是三元组中的最大或最小值，由于 \(i, j, k\) 的对称性，很明显其实和 \(x\) 是中间值都是同一个答案。

证毕！

By Long Luo

This article is the solution It is Literally a Graph: DFS and Union Find of Problem 947. Most Stones Removed with Same Row or Column .

Intuition

We can find that this is a graph theory problem with analysis.

Imagine the stone on the 2D coordinate plane as the vertex of the graph, If the x-coord or the y-coord of two stones are the same, there is an edge between them.

This can be show as follows:

According to the rule that stones can be removed, we should remove those points that are in the same row or column with other points as late as possible. That is, the more points in the same row or column with point A, the later point A should be removed. In this way, we can delete as many points as possible through point A.

It can be found that all vertices in a connected graph can be deleted to only one vertex.

Since these vertices are in a connected graph, all vertices of the connected graph can be traversed by DFS or BFS.

Therefore: the maximum number of stones that can be removed = the number of all stones - the number of connected components.

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()}\).

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. 😉😃💗

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} \]