Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

卷积(Convolution)是什么？

卷积 1 \((\textit{Convolution})\) 2 是数学分析中一种重要的运算。

设：\(f(x)\) 、\(g(x)\) 是 \(\mathbb{R}\) 上的两个可积函数，作积分：

\[ \int _{-\infty }^{\infty }f(\tau)g(x-\tau)\,\mathrm{d}\tau \]

可以证明，关于几乎所有的 \(x \in (-\infty, \infty)\)，上述积分是存在的。这样，随着 \(x\) 的不同取值，这个积分就定义了一个新函数 \(h(x)\)，称为函数 \(f\) 与 \(g\) 的卷积，记为 \(h(x)=(f*g)(x)\)。

我们可以轻易验证： \((f \star g)(x)=(g \star f)(x)\)，并且 \((f \star g)(x)\) 仍为可积函数。这就是说，把卷积代替乘法，\(L^{1}(R^{1})\) 空间是一个代数，甚至是巴拿赫代数。

虽然这里为了方便我们假设 \(f, g\in L^{1}(\mathbb{R} )\)，不过卷积只是运算符号，理论上并不需要对函数 \(f,g\) 有特别的限制，虽然常常要求 \(f, g\) 至少是可测函数(measurable function) (如果不是可测函数的话，积分可能根本没有意义)，至于生成的卷积函数性质会在运算之后讨论。

卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换，利用此一性质，能简化傅里叶分析中的许多问题。

由卷积得到的函数 \(f \star g\) 一般要比 \(f\) 和 \(g\) 都光滑。特别当 \(g\) 为具有紧支集的光滑函数，\(f\) 为局部可积时，它们的卷积 \(f \star g\) 也是光滑函数。利用这一性质，对于任意的可积函数 \(f\)，都可以简单地构造出一列逼近于 \(f\) 的光滑函数列 \(f_{s}\)，这种方法称为函数的光滑化或正则化。

卷积的概念还可以推广到数列、测度以及广义函数上去。

性质

各种卷积算子都满足下列性质：

交换律 \(f \star g = g \star f\)

结合律 \(f \star (g \star h)=(f \star g) \star h\)

分配律 \(f \star (g+h)=(f \star g)+(f \star h)\)

数乘结合律 \(a(f \star g)=(af) \star g=f \star (ag)\)

其中 \(a\) 为任意实数（或复数）。

微分定理 \((f \star g)={\mathcal{D}}f \star g=f \star {\mathcal{D}}g\)，

其中 \(Df\) 表示 \(f\) 的微分，如果在离散域中则是指差分算子，包括前向差分与后向差分两种：

前向差分：\({\mathcal{D}}^{+}f(n)=f(n+1)-f(n)\)

后向差分：\({\mathcal{D}}^{-}f(n)=f(n)-f(n-1)\)

卷积定理

函数卷积的傅里叶变换是函数傅里叶变换的乘积。即，一个域中的卷积相当于另一个域中的乘积，例如时域中的卷积就对应于频域中的乘积。

\(\textit{F}(f \star g) = \textit{F}(f) \cdot {\textit{F}}(g)\)

其中 \(\textit{F}(f)\) 表示 \(f\) 的傅里叶变换。

卷积定理 3 指出，函数卷积的傅里叶变换是函数傅里叶变换的乘积。即一个域中的卷积对应于另一个域中的乘积，例如时域中的卷积对应于频域中的乘积 4。

\[ \mathcal{F}\{f \star g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\} \]

其中 \({\mathcal{F}}(f)\) 表示 \(f\) 的傅里叶变换。下面这种形式也成立：

\[ \mathcal{F}\{f \cdot g\}= \mathcal{F}\{f\} \star \mathcal{F}\{g\} \]

借由傅里叶逆变换 \(\mathcal{F}^{-1}\)，也可以写成

\[ f \star g= \mathcal{F}^{-1}\big\{\mathcal{F}\{f\}\cdot\mathcal{F}\{g\}\big\} \]

注意以上的写法只对特定形式定义的变换正确，变换可能由其它方式正规化，使得上面的关系式中出现其它的常数因子。

这一定理对拉普拉斯变换、双边拉普拉斯变换、Z变换、梅林变换和Hartley变换（参见Mellin inversion theorem）等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。

利用卷积定理5可以简化卷积的运算量。对于长度为 \(n\) 的序列，按照卷积的定义进行计算，需要做 \(2n-1\) 组对位乘法，其计算复杂度为 \(O(n^{2})\) ；而利用傅里叶变换将序列变换到频域上后，只需要一组对位乘法，利用傅里叶变换的快速算法之后，总的计算复杂度为 \(O(nlogn)\)。这一结果可以在快速乘法计算中得到应用。

阅读全文 »

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

By Long Luo

Leetcode 1705. 吃苹果的最大数目 题目如下：

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
1705. 吃苹果的最大数目

有一棵特殊的苹果树，一连$n$天，每天都可以长出若干个苹果。在第$i$天，树上会长出apples[i]个苹果，这些苹果将会在days[i]天后（也就是说，第i + days[i]天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用apples[i] == 0且days[i] == 0表示。
你打算每天**最多**吃一个苹果来保证营养均衡。注意，你可以在这$n$天之后继续吃苹果。
给你两个长度为$n$的整数数组days和apples，返回你可以吃掉的苹果的最大数目。

示例 1：
输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉7个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。

示例 2：
输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出：5
解释：你可以吃掉5个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。
 

提示：
apples.length == n
days.length == n
1 <= n <= 2 * 10^4
0 <= apples[i], days[i] <= 2 * 10^4
只有在 apples[i] = 0 时，days[i] = 0 才成立

下面记录下我做这道题的思考过程：

暴力

很明显，每过一天，可能就有苹果过期，那么最好的方法是每天挑选最临近过期的苹果吃，这样才能吃到最多的苹果，于是新建一个二维数组，分别存储苹果个数和过期时间。

之后遍历这个数组，使用一个指针指向数组下标，一个 \(time\) 变量表示时间，时间每日递增，当苹果数 \(> 0\) 和未过期时苹果数 \(-1\)，如果不满足，数组下标\(idx++\)，代码如下所示：

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
public int eatenApples(int[] apples, int[] days) {
    int len = apples.length;
    int ans = 0;
    int[][] sorted = new int[len][2];
    for (int i = 0; i < len; i++) {
        sorted[i][0] = apples[i];
        sorted[i][1] = i + days[i];
    }

    Arrays.sort(sorted, (o1, o2) -> o1[1] - o2[1]);
    int time = 0;
    int idx = 0;
    while (idx < len) {
        while (idx < len && (sorted[idx][0] <= 0 || sorted[idx][1] <= time)) {
            idx++;
        }

        if (idx < len && sorted[idx][1] > time) {
            sorted[idx][0]--;
            ans++;
        }

        time++;
    }

    return ans;
}

但是，这个方法只通过了 \(50\) 个test cases，遇到下列用例就不适用了：

1
2
[2,1,1,4,5]
[10,10,6,4,2]

那么问题出在什么地方呢？

因为排序结果会导致我们先吃了还没有长出来的果实，所以此方法不可行，需要修改。

阅读全文 »

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

By Long Luo

Leetcode 1044. 最长重复子串 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1044. 最长重复子串

给你一个字符串s，考虑其所有重复子串：即，s的连续子串，在s中出现2次或更多次。这些出现之间可能存在重叠。

返回**任意一个**可能具有最长长度的重复子串。如果s不含重复子串，那么答案为""。


示例 1：
输入：s = "banana"
输出："ana"

示例 2：
输入：s = "abcd"
输出：""
 

提示：
2 <= s.length <= 3 * 10^4
s由小写英文字母组成

这是一道Hard难度的题，我们将展示这道题的几种解决方法：

方法一：从暴力到二分

思路与算法：

首先想到的是暴力法，用一个哈希表存储每个字母的出现次数，那么答案字符串的首字母至少出现 \(2\) 次，中间字符至少出现一次。

  1. 第一层循环 \(0 < i < len - 1\)，遍历整个字符串；
  2. 第二层循环，子字符串长度，\(i < j < len - i\)；
  3. 第三层循环，判断第二层循环的字符串在后续字符串中是否出现。

于是写出了下列Ver 1的代码：

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
public String longestDupSubstring(String s) {
	if (s == null || s.length() <= 1) {
		return "";
	}

	Map<Character, Integer> freq = new HashMap<>();
	for (char ch : s.toCharArray()) {
		freq.put(ch, freq.getOrDefault(ch, 0) + 1);
	}
	StringBuilder sb = new StringBuilder();
	int len = s.length();
	int maxLen = 0;
	String ans = "";
	for (int i = 0; i < len; i++) {
		sb.delete(0, sb.length());
		char ch = s.charAt(i);
		if (freq.getOrDefault(ch, 0) <= 1) {
			continue;
		}
		for (int j = i; j < len - sb.length(); j++) {
			sb.append(s.charAt(j));
			for (int k = i + 1; k < len; k++) {
				String str = s.substring(k, len);
				if (str.contains(sb.toString())) {
					if (sb.length() >= maxLen) {
						ans = sb.toString();
					}
					maxLen = Math.max(maxLen, sb.length());
					break;
				}
			}
		}
	}

	return ans;
}

上述代码，时间复杂度为 \(O(n^4)\)，会超时。

通过观察，发现Ver 1代码有很多改进地方，于是更新到Ver 2：

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
// BF Opt time: O(n^3) space: O(n)
// Timeout
public static String longestDupSubstring_bf_opt(String s) {
    int len = s.length();
    int[] cnt = new int[26];
    for (char ch : s.toCharArray()) {
        cnt[ch - 'a']++;
    }

    int maxLen = 0;
    String ans = "";
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len - 1; i++) {
        char ch = s.charAt(i);
        if (cnt[ch - 'a'] <= 1) {
            continue;
        }

        for (int segLen = len - i; segLen > maxLen; segLen--) {
            sb.delete(0, sb.length());
            sb.append(s, i, i + segLen);
            String str = s.substring(i + 1, len);
            if (str.contains(sb.toString()) && sb.length() > maxLen) {
                ans = sb.toString();
                maxLen = Math.max(maxLen, sb.length());
                break;
            }
        }
    }

    return ans;
}

Ver 2时间复杂度降低到 \(O(n^3)\)，但仍然会超时，所以还需要优化！

很明显，题目要求的子字符串的长度范围为 \([0, n - 1]\)，那么枚举每个位置作为起点，二分搜索以找到最大长度，于是有了下面的Ver 3代码：

阅读全文 »

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

By Long Luo

Leetcode 686. 重复叠加字符串匹配 题目如下：

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
686. 重复叠加字符串匹配

给定两个字符串a和b，寻找重复叠加字符串a的最小次数，使得字符串b成为叠加后的字符串a的子串，如果不存在则返回-1。

注意：字符串"abc"重复叠加0次是""，重复叠加1次是"abc"，重复叠加2次是"abcabc"。

示例 1：
输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为"ab**cdabcdab**cd", 此时b是其子串。

示例 2：
输入：a = "a", b = "aa"
输出：2

示例 3：
输入：a = "a", b = "a"
输出：1

示例 4：
输入：a = "abc", b = "wxyz"
输出：-1
 
提示：
1 <= a.length <= 10^4
1 <= b.length <= 10^4
a 和 b 由小写英文字母组成

分析

可以分为下面\(3\)种情况：

  1. \(\textit{A}\) ==\(\textit{B}\)，复制 \(1\) 次；

  2. \(lenA > lenB\)，直觉是只需要复制 \(2\) 次；

  3. \(lenA < lenB\)，首先至少将 \(\textit{A}\) 复制几次后长度 \(>=lenB\)，然后至多再复制 \(\textit{A}\) 一次。

下面简单证明下，也就是复制次数的下限和上限：

  1. 至少将字符串 \(\textit{A}\) 复制 \(N\) 次之后主串 \(\textit{S}\)，那么 \(lenS >= lenB\) ，才有可能匹配，至此我们得到了复制次数的下限：\(\frac{lenB}{lenA}+1\)；

  2. 如果从主串 \(\textit{S}\) 中找到子串 \(\textit{B}\)，因此可以明确子串的起始位置，不会超过 \(lenA\)；因为如果起始匹配位置 \(>= lenA\)，那么说明在之前已经被匹配过了。

综上分析可知：

\[ \frac{lenB}{lenA} + 1 \le repeatedTimes \le \frac{lenB}{lenA} + 2 \]

方法一：暴力

思路与算法：

首先想到的是暴力法。最开始没有去分析复制次数上下限时，使用了一个朴素的想法：

  1. \(\textit{B}\) 中含有 \(\textit{A}\) 中没有的字母，那么直接返回 \(-1\)；
  2. 最少复制次数：\(\textit{B}\) 中字母出现次数 \(\textit{A}\) 中字母次数的最大值。

使用 \(\texttt{HashMap}\) 存储字母出现次数。

代码如下所示：

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
public int repeatedStringMatch(String a, String b) {
    if (a.equals(b) || a.contains(b)) {
        return 1;
    }

    int min = 1;
    Map<Character, Integer> mapA = new HashMap<>();
    Map<Character, Integer> mapB = new HashMap<>();
    for (char ch : a.toCharArray()) {
        mapA.put(ch, mapA.getOrDefault(ch, 0) + 1);
    }
    for (char ch : b.toCharArray()) {
        mapB.put(ch, mapB.getOrDefault(ch, 0) + 1);
    }
    
    for (char ch : mapB.keySet()) {
        if (!mapA.containsKey(ch)) {
            return -1;
        } else {
            int times = mapB.get(ch) / mapA.get(ch);
            min = Math.max(min, times);
        }
    }

    StringBuilder res = new StringBuilder(a);
    for (int i = 2; i <= min + 1; i++) {
        res.append(a);
        if (res.toString().contains(b)) {
            return i;
        }
    }

    return -1;
}

因为字符串均由小写英文字母组成，所以可以直接用数组进行计数，速度提高了很多。

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
public int repeatedStringMatch(String a, String b) {
    if (a.equals(b) || a.contains(b)) {
        return 1;
    }

    int[] cntA = new int[26];
    int[] cntB = new int[26];

    for (char ch : a.toCharArray()) {
        cntA[ch - 'a']++;
    }
    for (char ch : b.toCharArray()) {
        cntB[ch - 'a']++;
    }

    int min = 1;

    for (int i = 0; i < 26; i++) {
        if (cntB[i] > 0 && cntA[i] == 0) {
            return -1;
        }

        if (cntA[i] > 0) {
            int times = cntB[i] / cntA[i];
            min = Math.max(min, times);
        }
    }

    StringBuilder res = new StringBuilder(a);
    for (int i = 2; i <= min + 1; i++) {
        res.append(a);
        if (res.toString().contains(b)) {
            return i;
        }
    }

    return -1;  
}

值得一提的是，如果不用比较 \(\textit{A}\), \(\textit{B}\) 字母的话，直接进行比较的话，那么耗时会成倍增加，所以预先排除一些test case有很大帮助。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int repeatedStringMatch(String a, String b) {
    if (a.equals(b) || a.contains(b)) {
        return 1;
    }

    int minRepeatTimes = Math.max(1, b.length() / a.length() + 1);

    StringBuilder res = new StringBuilder(a);
    for (int i = 2; i <= minRepeatTimes + 1; i++) {
        res.append(a);
        if (res.toString().contains(b)) {
            return i;
        }
    }

    return -1;
}

复杂度分析：

  • 时间复杂度：\(O(n + m + nm)\)，其中 \(n\) 为 \(\textit{A}\) 的长度，\(m\) 为 \(\textit{B}\) 的长度。
  • 空间复杂度：\(O(26)\)。
阅读全文 »

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

By Long Luo

Leetcode 997. 找到小镇的法官 题解。

方法一：图论

思路与算法：

  1. 如果存在法官，那么所有人都会信任法官，在结合条件\(1\)，可以得出信任法官的人数为\(n - 1\)；
  2. 如果不存在法官，那么也可能存在某些人被所有人信任，这个人的信任人数也为\(n - 1\)，但是他也会信任别人；
  3. 可以以此作为区分other和judge的条件，假设每个人都有信任值，那么定义一个数组长度为\(n\)，用来存放\(n\)个人的信任值:
  • 如果一个人信任了别人，那么这个人的信任值\(-1\)
  • 如果一个人被别人信任，那么这个人的信任值\(+1\)

所以：

  1. 当一个人被所有人信任，并且他没有信任其它人时，这个人的信任值就是\(n - 1\)，那么此人就是法官；
  2. 当一个人被所有人信任，但是他也信任了其他人时，这个人的信任值\(< n - 1\)。 其它情况下，每个人的信任值都会小于\(n - 1\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findJudge(int N, int[][] trust) {
	if (N <= 0) {
		return -1;
	} else if (N == 1) {
		return 1;
	}

	// [0]: In  [1]: Out
	int[][] count = new int[N][2];
	for (int[] item : trust) {
		count[item[0] - 1][1]++;
		count[item[1] - 1][0]++;
	}

	for (int i = 0; i < N; i++) {
		if (count[i][0] == N - 1 && count[i][1] == 0) {
			return i + 1;
		}
	}

	return -1;
}
阅读全文 »
0%