Long Luo's Life Notes

每一天都是奇迹

By Long Luo

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

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

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

Fibonacci Sequences

斐波那契数的边界条件是 \(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)\) ,函数递归栈。
阅读全文 »

By LongLuo

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

主流电子书格式

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

Epub

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

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
    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。

阅读全文 »

By Long Luo

一、沉迷

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

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

二、游戏的优秀之处

2.1 设置一定难度,让玩家受挫

《糖果粉碎传奇》最开始几关,玩家都可以轻松应对。游戏主要是让玩家熟悉游戏,起新手引导作用。当关卡到达第五关时,游戏难度加大,开始出现彩色炸弹,凝胶物,以及不同的任务模式。在某一关卡,甚至需要玩家在一分钟内达到具体分数才能过关,通过应用商店彩色炸弹道具消费后,才顺利通关。前20关,并不是每一关都比前一关难度更大,玩家很容易就产生能够轻松应对游戏的心态。但是随着游戏的进行,玩家正自信满满的时候,某个关卡突然难度加大,玩家在多次尝试后,仍然未果,从而引发前后强烈对比心理,让玩家受挫,达到King的目的。游戏沮丧心理可以导致玩家做以下事情:更加努力通关;选择捷径;完全放弃。一些玩家的确在一开始会放弃游戏,甚至删掉游戏应用,但是这种沮丧感总会让玩家再次回到游戏中,并且鼓励玩家购买游戏道具,例如彩色炸弹通关。King不仅通过玩家受挫情绪,提高玩家粘性,也推动了循环转化心理。

2.2 延迟玩家满足心理

当玩家花费半个小时以上来过关时,没有什么比过关更能带给玩家满足感。但是如果在反复尝试,并且失去生命动力,更糟糕的是,还需要等待24分钟的情况下,玩家应该如何选择。有些玩家甚至会在iPhone上面设置定时器,然后选择做24分钟的家务。这种情况又揭露了该游戏的另外一个上瘾功能,鼓励玩家再次回到游戏。玩家不仅在一段时间内失去生命动力(也许会一直持续到第二天),这种情况下,玩家可能会抱怨并声称将永远放弃这款游戏,但是生命动力很快又会恢复,不需要等到第二天,因为时间非常固定,并且这个时间设置,极度容易让玩家在等待再次游戏过程中坐立难安,这个过程再次触发了玩家的受挫心理。现在,玩家不仅无法进行游戏,而且还不得不再次等待。游戏开发者们可以考虑如何对游戏延迟机制进行创新,这样就可以潜移默化地提高玩家粘性。

2.3 鼓励玩家使用道具

《糖果粉碎传奇》创造了一种模式,让玩家受挫,延迟玩家满足感,来保持玩家粘性。游戏还设计了能够帮助玩家完美通关的一切道具来“作弊”过关。King设计的游戏模式,让玩家每次失败时都可以选择是否进行道具购买,来保证通关并获取更高的积分。另外,道具购买也利用了玩家的便宜心理。当玩家长时间卡在某一关时,迫切需要通过道具来帮助通关,而只需6块钱的道具,并不足以让玩家理智纠结是否消费。但是对于King来说,就是巨大的一笔收入,King每日IAP收入达63.3万美元。

三、反沉迷

那么最后我是如何反沉迷的呢?

使用作弊系统,降低游戏难度

下载了一个破解版App玩了很久,因为是破解版,所以

休息好,多参加体育锻炼,提高自制力

指定清晰的界限,使用计时器

By Long Luo

之前我们已经实现了225. 用队列实现栈232. 用栈实现队列 。最近遇到一道手写代码面试题:用数组实现队列。

其实这道题非常之简单,但之前数据结构与算法基础知识不过关,居然没有现场写出来。

队列(Queue)

队列是一个有序列表,遵循FIFO(先入先出)的原则。

队列有头有尾,有容量。

代码如下所示:

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
39
40
41
42
43
44
45
46
47
// implement the queue use array
public class MyQueue {
int[] array;
int front;
int rear;
int capacity;

public MyQueue(int capacity) {
this.capacity = capacity;
array = new int[capacity];
front = 0;
rear = 0;
}

public void enqueue(int x) {
if (rear == capacity) {
return;
}

array[rear] = x;
rear++;
}

public void dequeue() {
if (front == rear) {
return;
}

for (int i = 0; i < rear - 1; i++) {
array[i] = array[i + 1];
}

array[rear] = 0;
rear--;
}

public int front() {
if (front == rear) {
return -1;
}
return array[front];
}

public boolean empty() {
return front == rear;
}
}

dequeue()也可以优化为 \(O(1)\),直接让front+1,但front == rear时,可能会出现还有容量的情况,但这里无法体现出来,所以要使用环形队列

阅读全文 »

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

聊天

Telegram

Telegram是最常用的加密即时通讯App之一,适用于Android和iOS。如果想了解如何实现一个即时通信App,可以认真学习其源码!

Source Code

邮件客户端

K-9 Mail App

一个全功能电子邮件客户端,支持多帐户、多文件夹同步、标记、归档、BCC 自我、签名等等。 如果想了解电子邮件客户端的工作原理,开始动手写一个邮件客户端就从吃透这个项目源码开始吧!

官网地址:https://k9mail.app/

Source Code

阅读全文 »
0%