Blog Entries all / by tag / by year

之前一直以为Python中and、or 这两个表达式的返回值是True 或者 False，今早帮同学解答问题时才发现之前的理解是错误的。

想要运行一个Java程序需要经过三个阶段：编写源代码—编译—在JVM上运行。那么一个字符串在以上三个阶段的编码方式是怎样的呢？另外，如果Java程序中要输出字符串，那么输出的字符串的编码又是什么呢？

一个源文件怎么会生成这么多的.class文件呢？下面通过问答的形式阐述Java在编译内部类的私有构造函数时采用的策略。JDK版本为1.8.0_111

我们需要实现这样的一个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大的元素