Determinant行列式求值

收藏到CSDN网摘


矩阵行列式的求值

Polynomial Division多项式除法

收藏到CSDN网摘

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

点集凸包算法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)

Hexagon Network六边形网格距离计算

收藏到CSDN网摘


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

Union Find并查集

收藏到CSDN网摘


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