Entries from 2016 « 2015 / all / by tag / 2017»

我们需要实现这样的一个cache(key-value pair):

• 取数据时，存在则取出，不存在则返回-1
• 存数据时，若该key已存在，则更新其value。若不存在，则插入之。插入时，若cache已满，则需要先删除一个元素。删除时，使用LFU算法，将使用频率最低的元素删除；若有多个使用频率相同的元素，则对这些元素采用LRU算法，删除最久未使用的。

很显然，我们需要用map来存储key-value pair。然后记录各个元素的使用频率，以及最近访问的次序。

拿到题目之后，最先想到的就是构建NFA然后逐字符匹配。可以发现，整个题目的关键之处在于*的处理。首先画出*的状态图，如下：

在pre_end状态遇到了*，生成了入上图所示的状态转换，*的处理在tail(end)状态结束。算法如下：

1. 根据pattern生成对应的NFA
2. 依次输入待匹配的字符，进行状态转换。转换时同步匹配多个分支，不使用回溯。也就是每次输入结束后可以有多个状态满足要求，参见Regular Expression Matching Can Be Simple And Fast
3. 输入完所有字符后，检查当前停留的节点中是否有终止节点，有则匹配成功，反之不然。

怎样从一个未排序数组中找出第K大的数？最简单的方法便是先将数组排序，然后便可取出第K大的数了。显然，此方法有点“大材小用”，其实没必要将数组所有元素排序，只需要取出指定的元素即可。那么可不可以改进一下现有的排序算法，使之无需排序整个数组，就能找到第K大的元素呢？

我们可以将快速排序改进一下：每次基于pivot将元素分为大小两类后，舍弃目标元素不会存在于其中的那个部分。具体算法如下：

1. 选定一个pivot，将其余元素分成小于或等于pivot，以及大于pivot两类，分别记为smaller与greater
2. 记len( greater ∪ pivot ) = counter:
3. 若counter = K，表明pivot即为第K大的元素
4. 若counter > K，表明该元素在greater部分，那么smaller部分就可以舍弃无需考虑了；回到步骤1，在greater中再次寻找第K大的元素
5. 若counter < K，表明该元素在smaller部分，那么greater部分就可以舍弃；并在smaller中寻找第K-counter大的元素

前几天比较无聊，在知乎上看到有人问怎么写Flappy Bird，于是乎想自己造一个。一是为了打发时间，二是想随便找个游戏引擎，看看自己能不能快速写一个出来。游戏其实很简单，主要就是绘制鸟与随机长度的水管，然后加一个碰撞检测就行了。说起来挺简单的，但是做起来还是有一些小细节需要处理。对C++不熟悉，于是找了个Java写的游戏引擎libgdx。有了引擎，绘图什么的都能方便点。至于碰撞检测的话，发现该引擎提供了一个物理引擎，box2d，据说用它就可以进行碰撞检测了。好了，下面就讲讲怎么造一个Flappy Bird吧。

介绍了可靠数据传输原理之后，再来介绍一下TCP (Transmission Control Protocol) 原理（基于rdt）

在实际的网络传输中，channel（信道）是不可靠的，在其上传输的数据分组可能丢失，损坏，或者失序。因此需要一个可靠的数据传输协议，来保证从发送端发送的数据能够按序无损地交付给接收端。图中，应用层将传输协议视为可靠的；而在传输层中，通过可靠数据传输协议，在不可靠的网络层信道上，实现了数据的可靠传输。