18 Jul 2013

Polynomial Division多项式除法

收藏到CSDN网摘





多项式除法的问题,可将字符串转为{次数:系数}的dict保存起来,然后进行四则混合运算.并将结果输出.具体与手算区别不大,唯一要注意的是:
1.±1的处理
2.0次项处理
3.空字符串处理
4.合并同次数项.

17 Jul 2013

点集凸包算法Convex Hull

收藏到CSDN网摘





求点集的凸包是经常会碰到的问题,下面是一个python实现.注意会自动忽略共线的多余点,只返回凸包的顶点坐标.

Priority Queue优先队列

收藏到CSDN网摘


Priority Queue(优先队列)是一种根据优先级对集合元素排序的数据结构,根据定义可以分为最大优先队列和最小优先队列.与之对应的有最大堆和最小堆.应用在排序算法上就是堆排序.在python中heapq包就是最小堆的具体实现,可以使用heapq.heappush()和heapq.heappop()来对堆进行操作,如果要将一个已有数组堆化,可以调用heapq.heapify()函数.在普林斯顿的数据结构与算法课程上,使用最小优先队列来解决了经典的8-Puzzle问题(就是3*3的拼图问题).下面是其具体实现,输入一个打乱顺序的拼图,可以输出求解步骤或者无法求解.(注意返回的字符串是空格子(0)的移动方向,与具体的拼图操作恰好相反).略加修改,可以实现任意规格的puzzle求解(下面包含一个4*4的board和一个3*4的board)

15 Jul 2013

Hexagon Network六边形网格距离计算

收藏到CSDN网摘


六边形网格(有时也叫蜂窝网络)在实际生活中有很多应用,例如无线基站定位,蜂窝(名字的由来),战棋游戏中人物的移动等.对于六边形网格的定位方法有很多,几何计算应该是最简单的.不过对于想要直观显示,计算的方式并不能说是最好的方法.曾经看到一个题目,对于一个从中心螺旋生长的蜂窝网格,求任意给定的2个cell的距离(看下图).此题如果是正方形网格,一个很简单的BFS(广度优先搜素)即可解决.但是对于蜂窝网格,如果不用几何的办法,最好是先定义网格cell,然后构造整个network,最后对于给定的cell按照广搜找到路径即可.

11 Jul 2013

Union Find并查集

收藏到CSDN网摘


union find并查集是数据结构与算法问题中经常碰到的典型数据结构,作为二十世纪最伟大的十个算法之一(不知道是谁评的),在很多问题中都有非常独到的应用.例如判断某2个点是否连通(迷宫路径问题).普林斯顿的在线课程数据结构与算法第一章讲的就是它,而且由浅入深,逐步实现了有一个普通的实现到最后的加权优化实现以极大压缩生成树的高度来实现高效判断.下面是python实现的代码:

5 Jul 2013

Spiral Matrix: 螺旋矩阵2

收藏到CSDN网摘


以前写过2个关于螺旋矩阵的帖子,分别是matlab方法python的模拟填空法,都是从左上角开始生长.在checkio的一道题中需要生成从中心开始螺旋生长的矩阵.方法还是类似于模拟填空法.这次需要判断的不再是到达边界转向,而是根据目前的方向,判断下一方向的位置是否为空,如果为空就转向继续写,与人工填写完全一致.需要注意的是中心位置的选取根据size的奇偶性有一些差别.

3 Jul 2013

Flatten List列表快速展开

收藏到CSDN网摘


python中有时候list会多层嵌套,需要展开成一维列表,最快速的方法是使用yield生成器.
但是针对一层嵌套的[[a,b,c],[d,e]]这种,sum(L,[])还是最快的.

Shortest path 迷宫寻路

收藏到CSDN网摘


走迷宫是acm经常出现的一类问题,有多重方法可以解决,例如A*,广度优先搜索,深度优先搜索等.广度优先搜素可以保证一旦找到路径,必定为最短路径.
广度优先搜索的实例如下(在12*12的迷宫中从(1,1)走到(10,10),边界是围墙,0为可通过,1为不可通过):

Split an array into two sets with the smallest difference

收藏到CSDN网摘


这是ACM的一个经典题目,将一个数组分成2部分,保证2部分数据和之差最小.网上有各种分析,据说动态规划(dynamic programming, DP)是最好的解决办法.
下面的分析是用0-1背包法来解决,思路是:
总数据A求和S后,问题转化为:用A中的数据填充容量为S/2的背包,得到最大价值V.那么原问题2部分元素的和的差就是: |(S-V)-V|,由于0-1背包问题时背包容量是S/2,所以可知S-V肯定不小于V,因此最后的差值是:S-2V.

Ubuntu13.10下编译安装PPS

收藏到CSDN网摘

PPS出了Linux版本,不过更新日期是2011年,但是好歹有的用了.不过官方的教程不甚明了,下载之后会发现无法使用的情况.具体debug过程记录,日后要安装再次复制即可.

1 Jul 2013

在当前位置打开命令行

收藏到CSDN网摘
在当前位置打开命令行,如果是win7,直接Shift+鼠标右键选择“Open command windows here”即可。
如果是xp,则需要额外设置: