Long Luo's Life Notes

By Long Luo

一

国庆假期中午吃完饭后给老爸打了个电话，却是姐姐接的。姐姐说，老爸还在山上摘茶籽，都还没有吃饭。姐姐是回家拿蛇皮袋去装茶籽的，等下还要去山上装完茶籽再回家。那到吃饭时都还要一个多小时后了，吃完饭还要去山上摘茶籽。

想到爸爸在家干活时腿不小心受伤了，现在还拖着腿一瘸一拐在山上摘茶籽。在手机上查了下天气，老家现在还是37°的高温，而我在深圳31°时在家里都还要吹空调，心里觉得自己太不孝了。

妈妈说我国庆假期应该回老家去摘茶籽的，不吃点苦都不会体谅父母的辛苦，要不然在家都懒成啥样了。明年国庆一定要回去摘茶籽，吃吃苦，体验下生活。

突然触动起了小时候关于山茶树的一些回忆。

二

茶籽是什么？很多人是不知道的。但要说到现在大做广告的山茶油，大家就知道了，茶油就是由山茶籽压榨加工而来的，南方80后小时候日常食用的就是山茶油。

茶籽树又叫油茶树，是一种常绿的小乔木。因为它结的果实可以榨油，故叫油茶树。收割完第二季稻子之后，大概霜降时，成熟的茶籽的挂满枝头，像点缀了胭脂的玛瑙一样，沉甸甸的挂在枝头，把树枝都压弯了，煞是好看，看着就令人高兴，或许这就是丰收的喜悦吧！

茶籽树长的很慢，树杆木质十分细密，非常紧实。大多长的不高，茶籽都好摘。够得着的站在地上摘，够不着的爬上树去摘。

早晨是一天采摘中的最佳时辰，天刚亮不久全家一起出发了。采茶籽动作单一，但工作量很大。茶籽数量众多，而且太阳烤背，往往会汗如雨下。一两个小时过后，一家人就摘了几个蛇皮袋，这时到了送袋子回去做饭的时间。刚摘下来的油茶籽重，一般用自行车或者手推车运回家。

送回家之后还要做好饭菜带进山来。在山里吃饭其实是一件很诱惑人的事，吃起来特别的香。

By Long Luo

The Solutions of LeetCode热题 100 | Top 100 Liked Questions :

By Long Luo

Leetcode中 剑指Offer（专项突击版）

By Long Luo

最近在做 Leetcode学习计划 中的 2021届秋季校招笔试真题 时，在这道题上 meituan-002. 小美的仓库整理 卡了一点时间，在此记录下自己从困惑到最终解决的全过程，吸取经验教训，提高自己知识水平。

题目

这是一道Medium难度的题目，如下所示：

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

meituan-002. 小美的仓库整理

小美是美团仓库的管理员，她会根据单据的要求按顺序取出仓库中的货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界分成两堆，这样可以保证货物局部的顺序不变。
已知货物最初是按1~n的顺序堆放的，每件货物的重量为w[i] ,小美会根据单据依次不放回的取出货物。请问根据上述操作，小美每取出一件货物之后，重量和最大的一堆货物重量是多少？

格式：

	输入：
		- 输入第一行包含一个正整数 n ，表示货物的数量。
		- 输入第二行包含n个正整数，表示1~n号货物的重量w[i]。
		- 输入第三行有n个数，表示小美按顺序取出的货物的编号，也就是一个1~n的全排列。

	输出：
		- 输出包含n行，每行一个整数，表示每取出一件货物以后，对于重量和最大的一堆货物，其重量和为多少。

示例：

	输入：
		5
		3 2 4 4 5 
		4 3 5 2 1
	 
	输出：
		9
		5
		5
		3
		0

解释：
	原本的状态是{{3,2,4,4,5}}，取出4号货物后，得到{{3,2,4},{5}}，第一堆货物的和是9，然后取出3号货物得到{{3,2}{5}}，此时第一堆和第二堆的和都是5，以此类推。

提示：
	1 <= n <= 50000
	1 <= w[i] <= 100

请注意，本题需要自行编写「标准输入」和「标准输出」逻辑，以及自行import/include需要的library。了解书写规则

从题意来看，这道题目并不难，所以当时看到题目之后，马上刷刷开始做题，觉得太简单了！

By Long Luo

之前虽然知道 KMP 算法，但是一直无法深入理解其原理，最近看了 2 篇文章：从头到尾彻底理解KMP（2014年8月22日版） 和 KMP算法教程 ，然后再实际写代码，终于对 \(\textit{KMP}\) 算法有了一定了解了，下面写一写我个人的学习过程。

这篇文章主要从我个人学习过程来叙述：

为了解决什么问题？

\(\textit{KMP}\) 算法是一种字符串匹配算法，可以在 \(O(n+m)\) 的时间复杂度内实现两个字符串的匹配。

所谓字符串匹配，是这样一种问题：

1. 字符串 \(\textit{P}\) 是否为字符串 \(\textit{S}\) 的子串？
2. 如果是，\(\textit{P}\) 出现在 \(\textit{S}\) 的哪些位置？

其中 \(\textit{S}\) 称为主串；\(\textit{P}\) 称为模式串。

最常见的就是经常要用的搜索功能，比如要在一大段文字中找到某个句子或者找到出现的全部位置。在这种场景下，要找的句子就是给定的模式 \(\textit{P}\) ，而大段文字就是目标字符串 \(\textit{S}\) 。

从暴力法开始

我们先从最直观的地方开始：

1. 两个字符串 \(\textit{A}\) ， \(\textit{B}\) 的比较？
2. 如果 \(\textit{P}\) 是 \(\textit{S}\) 的字串，第一个出现的位置在哪里？

所谓字符串比较，就是问两个字符串是否相等。

最朴素的思想，就是从前往后逐字符比较，一旦遇到不相同的字符，就返回 \(\textit{false}\) ；如果两个字符串都结束了，仍然没有出现不对应的字符，则返回 \(\textit{true}\) 。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static int Search_BruteForce(String targetStr, String patternStr) {
    int targetLen = targetStr.length();
    int patLen = patternStr.length();

    for (int i = 0; i < targetLen; i++) {
        if (targetStr.charAt(i) == patternStr.charAt(i)) {
            for (int j = 1; j < patLen; j++) {
                if (targetStr.charAt(i + j) != patternStr.charAt(j)) {
                    break;
                }

                if (j == patLen - 1) {
                    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

public static int ViolentMatch(String targetStr, String patternStr) {
    int targetLen = targetStr.length();
    int patLen = patternStr.length();

    int i = 0;
    int j = 0;
    while (i < targetLen && j < patLen) {
        if (targetStr.charAt(i) == patternStr.charAt(j)) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == patLen) {
        return i - j;
    } else {
        return -1;
    }
}

暴力解法复杂度分析

刚才我们成功实现了暴力算法，那么其时间复杂度如何？

记 \(n\) 为串 \(\textit{S}\) 的长度，\(m\) 为串 \(\textit{P}\) 的长度。

考虑“字符串比较”这个小任务的复杂度。最坏情况发生在：两个字符串唯一的差别在最后一个字符。这种情况下，字符串比较必须走完整个字符串，才能给出结果，因此复杂度是 \(O(len(str))\) 的。

由此，不难想到暴力算法所面对的最坏情况：

主串形如 “AAAAAAAAAAAAA…B” ，而模式串形如 “AAAAA…B” 。每次字符串比较都需要付出 \(O(m)\) 次字符比较的代价，总共需要比较 \(n\) 次，因此总时间复杂度是 \(O(nm)\) 。

那么如何改进呢？

信息熵冗余

我们很难降低字符串比较的复杂度（因为比较两个字符串，真的只能逐个比较字符）。因此，我们考虑降低比较的趟数。如果比较的趟数能降到足够低，那么总的复杂度也将会下降很多。

要优化一个算法，首先要回答的问题是“我手上有什么信息？”我们手上的信息是否足够、是否有效，决定了我们能把算法优化到何种程度。请记住：尽可能利用残余的信息，是 \(\textit{KMP}\) 算法的思想所在。

很明显在暴力算法中，模式字符串每次都需要比较，非常复杂，那么这里面有没有优化的时间呢？