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}\) 算法的思想所在。

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

By Long Luo

之前开发 Android电子书阅读器App 时，需要支持 Pdf 文件的阅读和标记功能，经过分析和测试不同实现方案，最终选择 MuPdf 方案。

Pdf解决方案

目前手机上实现 Pdf 文件的支持，有很多解决方案：

1. Andorid原生自带的Pdf解决方案，主要提供两个类 PdfRenderer 和 PdfDocument ，但是 Lollipop 才有的类，PdfRenderer 中核心代码是用的 native 方法，所以没办法将 PdfRenderer 从 SDK 中抽取出来用，局限性大，不采用。

2. 开源 AndroidPdfViewer ，完全使用 Java 实现，但问题在于太大，性能不及原生，所以放弃。

3. MuPdf，一款轻量级的 pdf 框架，支持前面两者功能，同时如果是文本的 pdf 文档还支持搜索、标注等功能，使用 native C 代码实现，快，编译好的so库也只有10M大小。

4. 调起手机中第三方支持 Pdf 阅读的应用；

5. 通过 pdf.js 实现在线预览，需要调用网页，性能不及原生，放弃。

MuPdf

MuPdf 是一个轻量级 PDF、XPS 和 E-book 阅读器，支持全部平台。

源码下载地址：https://mupdf.com/downloads/archive/

官网提供了一个例子：MuPDF Android Viewer，下面我们来编译并实现。

MuPdf编译

下载源码：

1

$ git clone --recursive git://git.ghostscript.com/mupdf-android-viewer.git

安装Cygwin或者直接在Linux下使用：

1
2

mupdf-android-viewer$cd jni
mupdf-android-viewer/jni$make generate

会调用 make -j4 -C libmupdf generate 命令编译字体文件，然后在 libmupdf 目录下生成 generated 文件夹，里面主要是一些字体文件。

By Long Luo

斐波那契数列( \(\textit{Fibonacci Sequence}\) ) ¹，又称黄金分割数列，因数学家莱昂纳多·斐波那契( \(\textit{Leonardoda Fibonacci}\) ) ² 以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：

\(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……\)

这个数列从第 \(3\) 项开始，每一项都等于前两项之和。

斐波那契数的边界条件是 \(F(0)=0\) 和 \(F(1)=1\)。当 \(n>1\) 时，每一项的和都等于前两项的和，因此有如下递推关系：

\[ F(n)=F(n-1)+F(n-2) \]

算法一：暴力法

如果不需要求解特别大的数值，又对时间敏感的话，可以有投机取巧的方法：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    int[] fib_nums = {
            0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
            6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
            1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
            102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903
    };

    public int fib(int n) {
        return fib_nums[n];
    }
};

复杂度分析

• 时间复杂度: \(O(1)\)
• 空间复杂度: \(O(n)\)

算法二: 递归(recursion)

显而易见斐波那契数列存在递归关系，很容易想到使用递归方法来求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Solution {

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }

        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("1 ?= " + fib(1));
        System.out.println("1 ?= " + fib(2));
        System.out.println("2 ?= " + fib(3));
    }
}

复杂度分析：

• 时间复杂度：\(T(n)=T(n-1)+T(n-2)\)，可见是指数级的。

我们可以写出其实现递归树，如下所示：

1
2
3
4
5
6
7
8
9

						fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

可以看出其做了很多重复性的计算，因此对于数值比较大时，其性能是灾难性的。

• 空间复杂度：\(O(n)\) ，函数递归栈。