Month: November 2013

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

    阶乘和斐波那契数列相信各位都很熟悉,典型的教材式递归例子,因为简单退化为循环也没啥难度。不过依赖于递归的问题并不都是那么简单的,比如最少硬币问题,需要称为动态规划(DP)的方式来实现。 所谓动态规划个人理解就是缓存一下递归的结果。比如斐波那契数列,简单的实现方式是: public int fib(int n) { if(n == 0 || n == 1) return 1; return fib(n – 2) + fib(n – 1); } 假如计算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,其实就是简单的映射数组: public int fib(int n) { if(fib_cache[n] > 0) return fib_cache[n]; //…

  • Dijkstra非负加权有向图最短路径算法

    成果在这里,前天完成的,花了大约半天的时间。参考资料主要是维基百科和一篇博客。 在分析自己代码前,先写一点自己对于Dijkstra算法的理解。 u s v

  • 二叉查找树学习笔记

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

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

    时隔好几年,才发现算法的趣味性,比如堆排序。堆排序同时也是大学时自己未完成的数据结构作业之一,就像《高等数学》一样之后都是抄抄了事…… 个人理解,堆排序是一个有名的排序算法,比较适合优先级队列。虽然时间复杂度是O(nlogn),论排序算法中比较快的还是快速排序。堆排序的特点是使用完全或近似完全二叉树来模拟一种父节点肯定比子节点大(最大堆)或者小(最小堆)的结果,并通过多次“删除”根节点并恢复结构来达到“模拟”排序的目的。实践中需要关注的是三点:

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

    插入排序 插入排序最直观的解释是不断拿扑克牌时排序的动作。一开始你只有一张8,第二张是5,你把5放在8的左边。第三张是9,你放在8的右边。第四张是2,你放在最左边。拿这四张牌的过程可以认为是排序4个数字的过程。步骤可以归纳为: 拿起一张牌 -> 取下一个数 比较现有牌,具体来说是从右往左找到第一个不小于当前牌的位置 -> 将所有大于当前数的数字向右移动一位 放入牌 -> 放置数字 形象上来讲,放置数字的过程是多个数字右移的过程,所以不需要swap。Java代码如下: public void sort(int[] xs) { int len = xs.length; if (len <= 1) return; for (int i = 1; i < len; i++) { int x = xs[i]; int j = i; while (j > 0 && xs[j – 1] > x) {…

  • IE compatible mode 和 Boilertemplate

    之前有写过一篇毫无技术含量的文章,现在要来纠正一些概念。

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

    最近重新学习算法,先从几个排序算法开始。快速排序是比较有名的一个排序算法,基本原理我明白,但是之前只会筛选构造新序列分区的方式,现在要学的是原地分区的方式。 成果代码如下,使用Java编写(C/C++的数组和指针操作忘得差不多了)。 private void swap(int[] array, int i, int j) { if (i == j) return; System.out.println(String.format(“%d <-> %d”, i, j)); int a = array[i]; array[i] = array[j]; array[j] = a; } private int partition(int[] ns, int begin, int end) { int pivotIndex = (begin + end) / 2; int pivot = ns[pivotIndex]; swap(ns, pivotIndex,…

  • 杂谈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,我其实没看配置文件,直接这么看的…… sudo netstat -anp | fgrep privoxy 配置(/etc/privoxy/config)中主要有两块,一块是绑定的IP,因为3DS和我的主机连接的是同一个路由器,用192.168.x.x就行了,不用开DMZ主机。默认是绑定127.0.0.1,这块肯定需要修改。 listen-address 192.168.1.55:8118 第二块看你本机的网络,如果你想在privoxy后使用SSH TUNNEL,就要用 forward-socks5 / 127.0.0.1:7070 . 这样的配置,类似VPN的本机环境就应该不需要这一步配置了。最终连接的服务器由SSH TUNNEL或者VPN决定。 在3DS的连接中设置好PROXY,我终于能进eShop了,完成MH4更新顺利下载了一些DLC,工会卡的背景好少啊……

  • 海量积分排序的二分实现

    简单描述下问题:有一个网站,现在有很多用户,每个用户有一个积分,要求在用户登录时显示用户的积分排名,用户的积分会有变动。注意考虑数据量比较大的场景。 原理是以树的方式来分解排名的计算。参考在这里。 实际代码分为三部分: 查询某个积分的排名 更新积分 构造积分树 查询积分排名 原理是计算所有右子树或者同级节点的和,再加1。每个节点包含当前积分或者积分段内的用户总数。右子树或者同级节点代表大于指定积分的积分节点。排名的实际含义就是计算所有大于自己积分的人的总数。最后加1是因为大于最大积分的人的总数为0,但是排名不能为0,所以实际显示是必须加1的。 这块实际依赖树的结构,可能是数组或者是链表,但通用逻辑如下(递归): in: current node, score if current node is score node if current node is left leaf return count of right sibling else # current node is right node, no right sibling return 0 else # current node is score range node if score in left subtree…