Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 7.7k 阅读时长 ≈ 7 分钟

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 \dots\)

这个数列从第 \(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)\) ，函数递归栈。
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.8k 阅读时长 ≈ 3 分钟

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。

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

By Long Luo

一、沉迷

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

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

二、游戏的优秀之处

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

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

2.2 延迟玩家满足心理

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

2.3 鼓励玩家使用道具

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

三、反沉迷

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

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

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

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

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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

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时，可能会出现还有容量的情况，但这里无法体现出来，所以要使用环形队列。

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 3 分钟

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%