记一道美团面试编程题的解题过程：从暴力到优化

发表于 2021-09-10 更新于 2025-05-03 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 7.6k 阅读时长 ≈ 7 分钟

By Long Luo

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

题目

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

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。了解书写规则

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

阅读全文 »

理解KMP算法：从入门到推导

发表于 2021-09-03 更新于 2025-05-02 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 5.4k 阅读时长 ≈ 5 分钟

By Long Luo

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

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

为了解决什么问题？

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

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

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

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

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

从暴力法开始

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

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

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

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

代码实现如下：

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;
}

或者双指针版:

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

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

阅读全文 »

Android App 集成 MuPdf 实现 Pdf 阅读、编辑、标记等功能

发表于 2021-08-01 更新于 2025-05-03 分类于 Android Waline：阅读次数：本文字数： 2.5k 阅读时长 ≈ 2 分钟

By Long Luo

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

Pdf解决方案

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

Andorid原生自带的Pdf解决方案，主要提供两个类 PdfRenderer 和 PdfDocument ，但是 Lollipop 才有的类，PdfRenderer 中核心代码是用的 native 方法，所以没办法将 PdfRenderer 从 SDK 中抽取出来用，局限性大，不采用。
开源 AndroidPdfViewer ，完全使用 Java 实现，但问题在于太大，性能不及原生，所以放弃。
MuPdf，一款轻量级的 pdf 框架，支持前面两者功能，同时如果是文本的 pdf 文档还支持搜索、标注等功能，使用 native C 代码实现，快，编译好的so库也只有10M大小。
调起手机中第三方支持 Pdf 阅读的应用；
通过 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 文件夹，里面主要是一些字体文件。

阅读全文 »

9种求斐波那契数(Fibonacci Numbers)的算法

发表于 2021-07-24 更新于 2025-05-02 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 7.7k 阅读时长 ≈ 7 分钟

By Long Luo

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

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 \dots$

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

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

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

算法一：暴力法

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

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)

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

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)$，可见是指数级的。

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

						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)$ ，函数递归栈。

阅读全文 »

Android电子书阅读器App

发表于 2021-07-18 更新于 2025-02-14 分类于 Android Waline：阅读次数：本文字数： 3.8k 阅读时长 ≈ 3 分钟

By LongLuo

这几天写了个Android App，实现了一个电子书阅读器，下面写下具体开发思路及过程。

主流电子书格式

目前市面上常见的电子书格式有epub、txt、mobi、azw、azw3等，如果做一个电子书阅读器的话，必须支持上述格式。

Epub

epub最开始使用的是epublib ，集成非常简单，只需要将epublib.jar拷贝到libs目录下，并在代码中调用即可，参考代码如下所示：

    try {
        EpubReader reader = new EpubReader();
        InputStream in = getAssets().open("algorithms.epub");
        book = reader.readEpub(in);


        Metadata metadata = book.getMetadata();

        StringBuffer buffer = new StringBuffer();
        for (String s : metadata.getDescriptions()) {
            buffer.append(s + " ");
        }

        String bookInfo = "作者：" + metadata.getAuthors().get(0) +
                "\n出版社：" + metadata.getPublishers().get(0) +
                "\n出版时间：" + TimeUtils.getStringData(metadata.getDates().get(0).getValue()) +
                "\n书名：" + metadata.getTitles().get(0) +
                "\n简介：" + metadata.getDescriptions().get(0) +
                "\n语言：" + metadata.getLanguage() +
                "\n\n封面图：";

        mTvText.setText(bookInfo);

        Log.i(TAG, "onCreate: bookInfo=" + bookInfo);

        // 书籍的阅读顺序，是一个线性的顺序。通过Spine可以知道应该按照怎样的章节,顺序去阅读，
        // 并且通过Spine可以找到对应章节的内容。
        Spine spine = book.getSpine();

        List<SpineReference> spineReferences = spine.getSpineReferences();
        if (spineReferences != null && spineReferences.size() > 0) {
            Resource resource = spineReferences.get(1).getResource();//获取带章节信息的那个html页面

            Log.i(TAG, "initView: book=" + resource.getId() + "  " + resource.getTitle() + "  " + resource.getSize() + " ");

            byte[] data = resource.getData();//和 resource.getInputStream() 返回的都是html格式的文章内容，只不过读取方式不一样
            String strHtml = StringUtils.bytes2Hex(data);
            Log.i(TAG, "initView: strHtml= " + strHtml);

            parseHtmlData(strHtml);
        } else {
            Log.i(TAG, "initView: spineReferences is null");
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
}

/**
 * 解析html
 */
private void parseHtmlData(String strHtml) throws IOException {
    Document doc = Jsoup.parse(strHtml);
    Log.i(TAG, "parseHtmlData:  doc.title();=" + doc.title());
    Elements eles = doc.getElementsByTag("a"); // a标签
    // 遍历Elements的每个Element
    EpubBean epubBean;
    for (Element link : eles) {
        String linkHref = link.attr("href"); // a标签的href属性
        String text = link.text();
        epubBean = new EpubBean();
        epubBean.href = linkHref;
        epubBean.tilte = text;
        indexTitleList.add(epubBean);
        Log.i(TAG, "parseHtmlData: linkHref=" + linkHref + " text=" + text);
    }
}

不过这种方法仍然看起来比较复杂，由于之后为了支持Pdf，集成了MuPdf，而MuPdf本身也支持epub格式的读写，所以在后来版本中，就只需要保留MuPdf即可，就去除了EpubLib。

阅读全文 »