By Long Luo

一

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

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

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

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

二

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

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

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

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

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

By Long Luo

LeetCode 热题 HOT 100:

By Long Luo

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

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

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

解决思路

首先想到的肯定是暴力法：

2.1 暴力法

根据题意，就是求数组某个区间的区间和。求区间和最简单的方式当然是遍历了，复杂度为$O(N)$，而全部结果计算的时间复杂度为$O(N^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
33
34
35
36
37
38

public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      int n = scanner.nextInt();
      scanner.nextLine();
      int[] weight = new int[n];
      for (int i = 0; i < n; i++) {
          weight[i] = scanner.nextInt();
      }

      int[] number = new int[n];
      for (int i = 0; i < n; i++) {
          number[i] = scanner.nextInt();
      }

      int[] ans = new int[n];
      for (int i = 0; i < n; i++) {
          weight[number[i] - 1] = 0;
          ans[i] = getMax(weight, number[i]);
      }

      for (int i = 0; i < n; i++) {
          System.out.println(ans[i]);
      }
  }

  private static int getMax(int[] weight, int no) {
      int leftTotal = 0;
      int rightTotal = 0;
      for (int i = 0; i < (no - 1); i++) {
          leftTotal += weight[i];
      }

      for (int i = no; i < weight.length; i++) {
          rightTotal += weight[i];
      }

      return Math.max(leftTotal, rightTotal);
  }

这个答案只通过了示例中的测试用例，其他的都没有通过，那么问题出在什么地方呢？

通过重新读题，再加上题目给的示例的迷惑下，我明白了错在什么地方了！

By Long Luo

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

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

为了解决什么问题？

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

所谓字符串匹配，是这样一种问题：字符串P是否为字符串S的子串？如果是，它出现在S的哪些位置？

其中S称为主串；P称为模式串。

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

从暴力法开始

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

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

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

最朴素的思想，就是从前往后逐字符比较，一旦遇到不相同的字符，就返回False；如果两个字符串都结束了，仍然没有出现不对应的字符，则返回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为串S的长度，m为串P的长度。

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

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

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

那么如何改进呢？

信息熵冗余

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

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

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

By Long Luo

https://leetcode-cn.com/study-plan/algorithms/

https://leetcode-cn.com/study-plan/data-structures/?progress=97mwug6

https://leetcode-cn.com/study-plan/efficient-winning/?progress=9dtyjf2

动态规划(Dynamic Programming)

https://leetcode-cn.com/study-plan/dynamic-programming/?progress=97mv3s5

https://leetcode-cn.com/problems/fibonacci-number/

By Long Luo

By Long Luo

需求

https://mupdf.com/

MuPdf开源编译

https://mupdf.com/docs/android-sdk.html

1

git clone --recursive git://git.ghostscript.com/mupdf-android-fitz.git

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

# This is a very simple Makefile that calls 'gradlew' to do the heavy lifting.

default: debug

generate:
	if [ -f jni/Makefile ]; then make -C jni generate; fi
debug: generate
	./gradlew --warning-mode=all assembleDebug bundleDebug
release: generate
	./gradlew --warning-mode=all assembleRelease bundleRelease
install: generate
	./gradlew --warning-mode=all installDebug
lint:
	./gradlew --warning-mode=all lint
archive: generate
	./gradlew --warning-mode=all uploadArchives
sync: archive
	rsync -av --chmod=g+w --chown=:gs-priv $(HOME)/MAVEN/com/ ghostscript.com:/var/www/maven.ghostscript.com/com/

run: install
	adb shell am start -n com.artifex.mupdf.viewer.app/.LibraryActivity

tarball: release
	cp app/build/outputs/apk/release/app-universal-release.apk \
		mupdf-$(shell git describe --tags)-android-viewer.apk

clean:
	rm -rf .gradle build
	rm -rf jni/.cxx jni/.externalNativeBuild jni/.gradle jni/build jni/libmupdf/generated
	rm -rf lib/.gradle lib/build
	rm -rf app/.gradle app/build

1

make generate

编译libmupdf_java.so

Linux下NDK编译环境配置可以参考之前的文章Linux下Android开发环境搭建指南:

进入~/mupdf-android-viewer/jni/libmupdf/platform/java目录下，ndk-build编译：

1

~/mupdf-android-viewer/jni/libmupdf/platform/java$ndk-build APP_BUILD_SCRIPT=Android.mk APP_PROJECT_DIR=build/android APP_PLATFORM=android-16 APP_OPTIM=release APP_ABI=all

编译中出现下列错误：

1

ft2build.h: No such file or directory

出现上述信息需要安装字体支持软件freetype:

1

sudo apt-get install libfreetype6-dev

编译OK会在目录下生成下列文件：

1
2

https://github.com/longluo/AndroidPdfViewer

By Long Luo

斐波那契数列(Fibonacci sequence)，又称黄金分割数列，因数学家莱昂纳多·斐波那契（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)$

• 算法一: 递归(recursion)
  • 复杂度分析：
• 算法二: 动态规划(dynamic programming)
  • 复杂度分析：
• 算法三：记录值的动态规划实现
  • 复杂度分析
• 算法四: 空间优化的动态规划(Space Optimized)
  • 复杂度分析：
• 算法五：矩阵幂
  • 复杂度分析
• 算法六：矩阵快速幂(分治快速幂运算)
  • 复杂度分析
• 算法七：斐波那契数新算法求解
  • 1. 矩阵形式的通项
    • 1. 当$k=1$时：
    • 2. 当$k=n$时：
  • 2. 偶数项和奇数项
  • 3. 矩形形式求解Fib(n)
  • 复杂度分析
• 算法八：通项公式(Using Formula)
  • 复杂度分析
• 算法九：暴力法
  • 复杂度分析
• 总结

算法一: 递归(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)$，函数递归栈。

算法二: 动态规划(dynamic programming)

因为斐波那契数列存在递推关系，因为也可以使用动态规划来实现。动态规划的状态转移方程即为上述递推关系，边界条件为$F(0)$和$F(1)$。

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

class Solution {
    public static int fib(int n) {
        /* Declare an array to store Fibonacci numbers. */
        int f[] = new int[n + 2]; // 1 extra to handle case, n = 0
        int i;

        /* 0th and 1st number of the series are 0 and 1*/
        f[0] = 0;
        f[1] = 1;

        for (i = 2; i <= n; i++) {
            /* Add the previous 2 numbers in the series and store it */
            f[i] = f[i - 1] + f[i - 2];
        }

        return f[n];
    }
}	

复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(n)$。

算法三：记录值的动态规划实现

针对算法二，我们可以将计算好的值存储起来以避免重复运算，如下所示：

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

// Initialize array of dp
public static int[] dp = new int[10];

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

    // Temporary variables to store values of fib(n-1) & fib(n-2)
    int first, second;

    if (dp[n - 1] != -1) {
        first = dp[n - 1];
    } else {
        first = fib(n - 1);
    }

    if (dp[n - 2] != -1) {
        second = dp[n - 2];
    } else {
        second = fib(n - 2);
    }

    // Memoization
    return dp[n] = first + second;
}

复杂度分析

时间复杂度: $O(n)$
空间复杂度: $O(n)$

算法四: 空间优化的动态规划(Space Optimized)

算法二时间复杂度和空间复杂度都是$O(n)$，但由于$F(n)$只和$F(n-1)$与$F(n-2)$有关，因此可以使用滚动数组思想把空间复杂度优化成$O(1)$。代码如下所示:

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

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。

By LongLuo

1. 最简单的Demo

https://github.com/longluo/EbookReader/tree/demobook

2. 丰富各种界面

https://github.com/longluo/EbookReader/tree/demobook

3. 移植FBReader App

https://github.com/longluo/EbookReader/tree/fbreader