0%

By Long Luo

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

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

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

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

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

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

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

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

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

阅读全文 »

By Long Luo

LeetCode 热题 HOT 100:

Leetcode题目 难度 解答 Source Code
1. 两数之和 Easy 1. 两数之和 Two Sum Java
2. 两数相加 Medium 2. 两数相加 Java
4. 寻找两个正序数组的中位数 Hard 4. 寻找两个正序数组的中位数 Java
22. 括号生成 Medium 22. 括号生成 Java
155. 最小栈 Easy 155. 最小栈 Java
172. 阶乘后的零 Medium 172. 阶乘后的零 Java
230. 二叉搜索树中第K小的元素 Medium 230. 二叉搜索树中第K小的元素 Java

By Long Luo

Leetcode中 剑指Offer(专项突击版)


Leetcode题目 难度 解答 Source Code
剑指Offer II 001. 整数除法 Easy Java
剑指Offer II 002. 二进制加法 Easy Java
剑指Offer II 003. 前 n 个数字二进制中 1 的个数 Easy Java
剑指Offer II 004. 只出现一次的数字 Medium Java
剑指Offer II 005. 单词长度的最大乘积 Medium Java
剑指Offer II 006. 排序数组中两个数字之和 Easy Java
剑指Offer II 007. 数组中和为 0 的三个数 Medium Java
剑指Offer II 008. 和大于等于target的最短子数组 Medium Java
剑指Offer II 011. 0 和 1 个数相同的子数组 Medium Java
剑指Offer II 012. 左右两边子数组的和相等 Easy Java
剑指Offer II 081. 允许重复选择元素的组合 Easy Java
剑指Offer II 085. 生成匹配的括号 Medium Java

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),而全部结果计算的时间复杂度为O(N2)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/

美团 题目 难度 Solution 题解
Day 1 meituan-001. 小美的用户名 简单 Java
Day 1 meituan-002. 小美的仓库整理 中等 Java
Day 2 meituan-003. 小美的跑腿代购 简单 Java
Day 2 meituan-004. 小团的复制粘贴 困难 Java
Day 3 meituan-006. 小团的神秘暗号 简单 Java
Day 3 meituan-005. 小美的区域会议 困难 Java
Day 4 meituan-007. 小团的选调计划 简单 Java
Day 4 meituan-008. 小团无路可逃 中等 Java
Day 4 meituan-008. 小团无路可逃 中等 Java
Day 4 meituan-008. 小团无路可逃 中等 Java
Day 4 meituan-008. 小团无路可逃 中等 Java
Day 4 meituan-008. 小团无路可逃 中等 Java
Day 6 meituan-011. 搭配出售 中等 Java
Day 6 meituan-008. 小团无路可逃 中等 Java
Day 7 meituan-014. 小团的AB队 中等 Java
Day 7 meituan-015. 十字路口 中等 Java 题解

By Long Luo

Leetcode题目 难度 解答 Source Code
2. 两数相加 Medium 2. 两数相加 Java
4. 寻找两个正序数组的中位数 Hard 4. 寻找两个正序数组的中位数 Java
89. 格雷编码 Medium 89. 格雷编码 Java
148. 排序链表 Medium 148. 排序链表 Java
155. 最小栈 Easy 155. 最小栈 Java
206. 反转链表 Easy 206. 反转链表 Java
230. 二叉搜索树中第K小的元素 Medium 230. 二叉搜索树中第K小的元素 Java
236. 二叉树的最近公共祖先 Medium 236. 二叉树的最近公共祖先 Java

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,2330, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

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

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

F(n)=F(n1)+F(n2)F(n)=F(n-1)+F(n-2)

算法一: 递归(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(n1)+T(n2)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)O(n),函数递归栈。

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

因为斐波那契数列存在递推关系,因为也可以使用动态规划来实现。动态规划的状态转移方程即为上述递推关系,边界条件为F(0)F(0)F(1)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)
空间复杂度: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)
空间复杂度: O(n)O(n)

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

算法二时间复杂度和空间复杂度都是O(n)O(n),但由于F(n)F(n)只和F(n1)F(n-1)F(n2)F(n-2)有关,因此可以使用滚动数组思想把空间复杂度优化成O(1)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(n)
空间复杂度:O(1)O(1)

阅读全文 »