0%

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)

阅读全文 »

By Long Luo

一、沉迷

这几天沉迷于《糖果粉碎传奇》,周末加起来玩了十多个小时。不得不承认我的自制力还需要提高。

但是除了游戏本身的魅力,认为如果想要获得《糖果粉碎传奇》的成功,对于研究玩家心理,有三个关键点,值得所有的游戏开发者学习。

阅读全文 »

By LongLuo

在PC上,绝大部分软件都是Windows应用且闭源的,Linux系统只占了很小的份额,只有专业人士才会使用。随着移动互联网的到来,在智能手机系统中,Android由于开源免费的特性,已经占据了主要份额。当然iOS App由于闭源,且Apple软硬件一体,管控严格,体验更好,比如安全、动画流程、不卡顿等。

对于开发人员来说,最佳的学习方式莫过于开源项目了,我们可以学习到App的功能是如何实现的,提高我们自身的开发能力。我收集了一些最好的开源Android App项目,这些Apps可以作为很好的示例,帮助程序员们提高其Android开发技能。

下面就开始学习吧!

UI界面

FluentUI Android

微软开发的UI框架,用于在Android上Office App中实现统一的用户界面,从中可以学习如何构建UI部件及界面。

Source Code

QMUI Android

QMUI Android是腾讯开发的一个项目,设计目的是用于辅助快速搭建一个具备基本设计还原效果的Android项目,同时利用自身提供的丰富控件及兼容处理,让开发者能专注于业务需求而无需耗费精力在基础代码的设计上。不管是新项目的创建,或是已有项目的维护,均可使开发效率和项目质量得到大幅度提升。

官网:http://qmuiteam.com/android

Source Code

相机

Open Camera

一个全功能开源Android相机App,包括自动稳定、远程拍照等,如果想开发一款相机App,请学习这个项目!

Source Code

多媒体播放器

TimberX Music Player

一个全功能Android音乐播放器,遵循Material Design风格的用户界面,同时应用了最新的工具,包括Kotlin、组件、数据绑定等。

支持跨平台,可在手机、Android Wear、Android Auto、Chromecast和其他投射设备甚至谷歌助手上运行,如果你想编写一个音乐播放器以及适配各种设备,那这个App是最好不过的了!

官网:https://namand.in/

Source Code

Sound Recorder

一个Material Design风格的简易开源录音机App,可以学习到如何在Android中集成录音和操作功能。

Source Code

LeafPic

一个全功能相册App,如果想了解如何实现一个相册,请从这个开始!

Source Code

AntennaPod

一个播客App,你可以学习到如何开发一个播客App。

官网:https://www.antennapod.org/

Source Code

阅读全文 »

By LongLuo