递归的进一步学习-动态规划之最少硬币问题

阶乘和斐波那契数列相信各位都很熟悉,典型的教材式递归例子,因为简单退化为循环也没啥难度。不过依赖于递归的问题并不都是那么简单的,比如最少硬币问题,需要称为动态规划(DP)的方式来实现。
所谓动态规划个人理解就是缓存一下递归的结果。比如斐波那契数列,简单的实现方式是:

假如计算fib(5),事实上计算了一次fib(4),两次fib(3),三次fib(2),四次fib(1),两次fib(0),换句话说,重复计算了(1 – 1) + (2 – 1) + (3 – 1) + (4 – 1) + (2 – 1)有7次之多。理想情况下每个fib(n)只要计算一次。改进方法很简单,增加cache,其实就是简单的映射数组:

这里用0代表fib值未知。

Read More

二叉查找树学习笔记

二叉查找树如其名是一种主要用于查找的每个非叶子节点最多有两个子节点(左右子节点)的树,其特点是:

任何a, b, c三个节点(父节点和两个子节点,左右子节点可能只有一个或者都没有)满足a < b < c。对于相等的值使用节点计数+1或者节点中的链表等不同的方式来处理。 a < b < c这个条件乍一看和二分搜索binary_search很像,实际查找元素时也是类似的,时间复杂度在O(logn)。 一般的二叉查找树(不考虑链表退化和平衡的处理)包含查找,创建树/增加节点,删除节点,前/中/后序遍历等操作,下面分别介绍。 Read More

迟到的大学数据结构作业——堆排序

时隔好几年,才发现算法的趣味性,比如堆排序。堆排序同时也是大学时自己未完成的数据结构作业之一,就像《高等数学》一样之后都是抄抄了事……

个人理解,堆排序是一个有名的排序算法,比较适合优先级队列。虽然时间复杂度是O(nlogn),论排序算法中比较快的还是快速排序。堆排序的特点是使用完全或近似完全二叉树来模拟一种父节点肯定比子节点大(最大堆)或者小(最小堆)的结果,并通过多次“删除”根节点并恢复结构来达到“模拟”排序的目的。实践中需要关注的是三点:

Read More

【算法学习】趁热打铁,插入,选择和归并排序

插入排序

插入排序最直观的解释是不断拿扑克牌时排序的动作。一开始你只有一张8,第二张是5,你把5放在8的左边。第三张是9,你放在8的右边。第四张是2,你放在最左边。拿这四张牌的过程可以认为是排序4个数字的过程。步骤可以归纳为:

  • 拿起一张牌 -> 取下一个数
  • 比较现有牌,具体来说是从右往左找到第一个不小于当前牌的位置 -> 将所有大于当前数的数字向右移动一位
  • 放入牌 -> 放置数字

形象上来讲,放置数字的过程是多个数字右移的过程,所以不需要swap。Java代码如下:

实际实现中,认为第一个数字即你只有一张牌的时候肯定是排好序的,所以插入牌的过程从第二个数字开始。注意着重看while部分,这就是大于当前数的数字右移的过程。

选择排序

现在理解起来其实不是很难的算法。之前没学好有可能是因为数据结构课太无聊,对数据结构课无爱……
核心想法是选择第一个小的数放在第一位,再在剩下的数字中选择第二小的数字放在第二位,依次类推。
理论上只看这些的话和冒泡排序很像,但是选择排序的特点是交换次数少,因为只记录下标,冒泡排序直接交换。Java代码如下:

注意选择排序只记录最小数字的下标,即min,swap理论上最多发生n次。

归并排序

如果理解了两个已排序的序列如何合并的过程的话基本上不难了。
归并排序的想法是把数组拆分为两个数组,排序这两个数组,再合并。过程中不断递归,直到只有1个元素。一个元素肯定是排序好的。然后向上回溯,由合并过程合并两个排序好的数组直到原始大小。
实际实现中,合并逻辑的两个输入数组是原始数组的两个邻接区间,其次有一个中间数组用来放置合并逻辑的输出。在回溯时要把中间数组的内容复制回原始数组。Java代码如下:

说一下合并逻辑,对两个输入数组或者一个数组的两个区间([leftBegin, leftEnd], [rightBegin, rightEnd],因为是邻接的,所以rightBegin = leftEnd + 1),取两个数组的头一个元素比较,选择小的放入输出数组(ms),提供小数字的数组位置加1,依次类推。在第一个while结束时,肯定有一个数组的数字选完了。接下来要把生下来的数字放入输出数组。
排序的递归逻辑中最后一句是必须的,否则你等于没排序……这里使用了Java的System.arrayCopy,比逐个复制速度快。

到现在为止,学习的排序都是不需要特别的数据结构的,接下来可能要“复习”一下堆结构学习堆排序。

【算法学习】快速排序(原地分区)

最近重新学习算法,先从几个排序算法开始。快速排序是比较有名的一个排序算法,基本原理我明白,但是之前只会筛选构造新序列分区的方式,现在要学的是原地分区的方式。
成果代码如下,使用Java编写(C/C++的数组和指针操作忘得差不多了)。

说明一下自己在学习原地分区核心算法时候的理解,也就是上面partition方法的逻辑。
众所周知,快速排序基于一个基准点pivot,这也就是前两行代码做的事情。

接下来就是正式的分区。分区的目地是把小于基准点的数筛选到基准点左边去,大于的到右边去(以升序序列为例)。
为此,设置一个小于基准点的数字的索引index,初始为开始位置begin。找到任何一个小于基准点的数之后都需要和这个索引位置的数字做交换,以便把小于基准点的数集中起来。
其次,在筛选之前,为了避免基准点对于分区的影响,把基准点放到最后去。
执行具体举例:

对比代码

个人认为,理解了这一快,理论上快速排序基本的东西就差不多了。

杂谈2013-11-19

早上做地铁的时候发现写点东西能让人心情稍微安定一些,虽然工作上的东西不能写在博客,但是挑着写一些平常的东西还是可以的,不便公开的还是写在自己的笔记本上吧。

fake-webapp

最近完成了一个小的web应用,和无线没关系哈,我用来方便end-to-end测试的。有这样一个场景,要测试某个系统,这个系统依赖别的系统的服务,还有远程HTTP请求。原先测试这个系统很难,别的系统服务返回的内容我们不能直接控制,远程HTTP请求更是没办法直接调试。在阅读了《How Google Test Sofeware》之后,我决定mock掉这些难以测试的系统外的依赖,自己写一个包含这些mock掉的服务的web应用。
之前,我其实考虑过远程jmock+jmx的方案,但是始终想不清楚如何入手,现在做的东西虽然简单了些,但是最终目的是类似的。实际开发到最后调试使用花了两天不到,小见成果。
当然,我明白,我之前那些做的东西,不说在外面,在公司也是没啥人感兴趣的,现在也只是写一写,记录下自己好歹做过一些东西。

dd wrt

因为更新3ds的mh4,捣鼓了一次privoxy,考虑在路由器上处理的话更方便,在买了备用的路由器后尝试了刷dd wrt。原先的路由器型号是WR841N v7,可以刷dd wrt。刷机的过程也很简单,30-30-30大法(全程按着复位键,头30秒是接着电源的,中间30秒拔掉电源,末30秒接上电源)后在web界面上传新的firmware即可。
但是刷机之后设置花了好长时间,作为second route,看了一些资料几个小时后还是gss搞定的。
最后一步VPN其实到现在还是不稳定,可能和远程服务器有关系。默认dd wrt连接VPN后路由表是有问题的,需要在管理页面设置commands,启动后执行路由表更新脚本。

MH4升级到HR4

周末第一次玩网络联机的,体会到什么是5分钟一局,如果有几个人很给力的话;什么是chat,和不认识的人联机礼貌还是很重要的。不过我也明白如果长期靠着联机,确实人会变懒,只靠装备而不是技术过活(你应该去打斗技场)。
还有一些小的点,个人感觉HR解禁的其实也有“闲人”,愿意陪我们这种低HR打打怪的。而且有趣的是会在打完之后拍手,离开之前招手。怎么说,一个人玩确实有点孤独,一起玩还是有点乐趣的。
另外,翻翻MH4论坛了解到MH4升级的主要目的还是针对营地猎人和任务,类似刷老金的感觉。这个问题是在我第一次网络联机之前出现的,不了解是什么东西。第二个是称为校服,换句话说大家都穿的那种普遍的衣服,其实我想说,可以改点颜色的好不……
关于自己HR4后的目标,个人属于慢慢玩的新手,不过现在看来重点先做点key quest,包括升级HR的,食材的,纳品的,村里面的关键任务等等。

3ds mh4 002-0120和网络问题的解决

昨天进MH4,想想要下载点东西,结果MH4说需要进eShop更新一下MH4,错误号002-0120。于是我就进eShop,结果发现连不上,老是通信错误。我的网络是没啥问题,至少MH4下载DLC的时候是这样,但是eShop我基本没进去过,所以估摸着就是网络连线问题。

作为一个以前常DIY但是最近变懒的苦逼程序员,想到了无线AP的方法,即3DS论坛上提到的那种HOTSPOT方法。以前我在笔记本上试过HOTSPOT,但是捣鼓了一两天始终没成功,心有余悸。最终本次尝试也在失败中结束。虽然我得到了ubuntu 12.04直接支持我的旧的USB无线网卡,ubuntu有图形界面直接设置HOTSPOT的消息,但是3DS无法连接这个AP,手机直接搜索不到这个AP。

这么一折腾,本来可以玩个两三局的时间就没了(1个半小时),心灰意冷之际看到3DS网络设置有个PROXY,抱着试试看的心态连接我的SSH TUNNEL,结果失败。后来想想,既然不支持PROXY类型的设置,又不是SOCKV5,那很可能就是HTTP代理。于是我就尝试HTTP OVER SOCKV5的配置,GOOGLE一下搜索到PRIVOXY,突然想到自己以前用PRIVOXY+SSH TUNNEL解决过DROPBOX的近实时更新的问题(COMET),于是就尝试用PRIVOXY架设自己的HTTP代理。

自己所做的操作其实不多,ubuntu下,sudo apt-get install privoxy安装privoxy,默认安装后启动。privoxy默认监听端口8118,我其实没看配置文件,直接这么看的……

配置(/etc/privoxy/config)中主要有两块,一块是绑定的IP,因为3DS和我的主机连接的是同一个路由器,用192.168.x.x就行了,不用开DMZ主机。默认是绑定127.0.0.1,这块肯定需要修改。

第二块看你本机的网络,如果你想在privoxy后使用SSH TUNNEL,就要用

这样的配置,类似VPN的本机环境就应该不需要这一步配置了。最终连接的服务器由SSH TUNNEL或者VPN决定。

在3DS的连接中设置好PROXY,我终于能进eShop了,完成MH4更新顺利下载了一些DLC,工会卡的背景好少啊……

海量积分排序的二分实现

简单描述下问题:有一个网站,现在有很多用户,每个用户有一个积分,要求在用户登录时显示用户的积分排名,用户的积分会有变动。注意考虑数据量比较大的场景。

原理是以树的方式来分解排名的计算。参考在这里
实际代码分为三部分:

  • 查询某个积分的排名
  • 更新积分
  • 构造积分树

查询积分排名

原理是计算所有右子树或者同级节点的和,再加1。每个节点包含当前积分或者积分段内的用户总数。右子树或者同级节点代表大于指定积分的积分节点。排名的实际含义就是计算所有大于自己积分的人的总数。最后加1是因为大于最大积分的人的总数为0,但是排名不能为0,所以实际显示是必须加1的。
这块实际依赖树的结构,可能是数组或者是链表,但通用逻辑如下(递归):

Read More