相邻数最大差值

今天群里有人问了一道面试题,题目是N个未排序的整数,在线性时间内,求N个整数在数轴上相邻两个数之间的最大差值。

首先我想吐槽(莫怪~)群里某同学给出的一个解法,用桶排序+线性扫描,按照那位同学的意思,桶排序是O(n),所以整个过程是O(n)。然而并没有什么卵用,这位同学可能不是很了解桶排序的脾气,因为桶排序最乐观情况下才是O(n),而这道题如果使用排序,那结果应该是O(nlogn)。

然后我给出了我的解题思路:

  1. 求 N 个数最大值 MAX,最小值 MIN
  2. 把 [MIN, MAX) 之间平均分成 N 桶,并且补一个桶 [MAX, MAX + AVG),把所有数字放到对应桶里,并且求出每个桶最大值 BMIN 最小值 BMAX
  3. MAX_INTERVAL=MAX(MAX_INTERVAL, 非空桶.BMIN - 前一个非空桶.BMAX)

观点如下:

  1. 如果桶内有多个数,桶内任意数间差值必然小于平均值
  2. 如果两非空桶之间存在空桶,当前非空桶BMIN的值 - 前一个非空桶.BMAX >=平均值
  3. 有N+1个桶,不存在每个桶正好分到一个,必然存在至少一个空桶

最后Talk is cheap, but no comment

...

- 阅读全文 -

epoll ET 笔记

虽然关于epoll的文章很多了,但我还是写一点最近学习epoll的笔记吧。
epoll是Linux下高性能IO通知机制,相对于其他Linux的IO机制,epoll支持LT(level-triggered,水平触发)和ET(edge-triggered,边缘触发),能监控fd(file descriptor,文件描述符)数量不受FD_SETSIZE限制(但最大能打开的fd还是会受到限制),并且在空闲连接数多的时候更高效,还支持ET模式。

关于LT和ET,在我的理解,LT是在可用状态时一直通知,直到状态变成不可用,ET是状态从不可用到可用时,通知一次并不再通知,直到状态再次变成不可用。所以LT更可靠,ET更高效。对fd来说,不可用就是fd不可读(读缓存区空)或不可写(写缓存区满),反之,当fd变得可读(读缓存区读入数据)或可写(写缓存区不满),fd状态就是可用的,然后当读缓存区被读完但没有新数据读入读缓存区,或写缓存区写满但写缓存区数据还没有输出,状态又变成了不可用。

关于epoll的更详细的信息和使用,我就不再多说了,其他人的博客写的都比我好,我也是一知半解,不过我推荐先去man epoll一下,也许有很大收获也说不定。

我觉得在使用epoll ET的时候可能需要注意几个问题:

  1. EAGAIN
...

- 阅读全文 -

Kubuntu 14.04 编译 cocos2d-x 3.6

这是我第三次在linux发行版编译cocos2d-x。
首先是一些必要的依赖库,比如gl,glu,X*之类的,这类基本上在缺失的时候都会有提示。
然后是一些官方已经编译好的依赖,可以使用download-deps.py脚本下载。
重点介绍3个库:glew3, glfw3, libcurl
这三个库我都是从源代码安装的,前两个是因为ubuntu的源里没有(fedora和archlinux的源里都有),最后一个是因为安装时候有4个可选,我有选择困难癌,所以选择了自己从源代码安装。

  1. glew3
    glew3从github获取代码后,先到auto目录下执行
...

- 阅读全文 -