矩阵行列式的求值
19 Jul 2013
18 Jul 2013
Polynomial Division多项式除法
收藏到CSDN网摘
多项式除法的问题,可将字符串转为{次数:系数}的dict保存起来,然后进行四则混合运算.并将结果输出.具体与手算区别不大,唯一要注意的是:
1.±1的处理
2.0次项处理
3.空字符串处理
4.合并同次数项.
多项式除法的问题,可将字符串转为{次数:系数}的dict保存起来,然后进行四则混合运算.并将结果输出.具体与手算区别不大,唯一要注意的是:
1.±1的处理
2.0次项处理
3.空字符串处理
4.合并同次数项.
17 Jul 2013
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)
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按照广搜找到路径即可.
六边形网格(有时也叫蜂窝网络)在实际生活中有很多应用,例如无线基站定位,蜂窝(名字的由来),战棋游戏中人物的移动等.对于六边形网格的定位方法有很多,几何计算应该是最简单的.不过对于想要直观显示,计算的方式并不能说是最好的方法.曾经看到一个题目,对于一个从中心螺旋生长的蜂窝网格,求任意给定的2个cell的距离(看下图).此题如果是正方形网格,一个很简单的BFS(广度优先搜素)即可解决.但是对于蜂窝网格,如果不用几何的办法,最好是先定义网格cell,然后构造整个network,最后对于给定的cell按照广搜找到路径即可.
11 Jul 2013
Union Find并查集
收藏到CSDN网摘
union find并查集是数据结构与算法问题中经常碰到的典型数据结构,作为二十世纪最伟大的十个算法之一(不知道是谁评的),在很多问题中都有非常独到的应用.例如判断某2个点是否连通(迷宫路径问题).普林斯顿的在线课程数据结构与算法第一章讲的就是它,而且由浅入深,逐步实现了有一个普通的实现到最后的加权优化实现以极大压缩生成树的高度来实现高效判断.下面是python实现的代码:
union find并查集是数据结构与算法问题中经常碰到的典型数据结构,作为二十世纪最伟大的十个算法之一(不知道是谁评的),在很多问题中都有非常独到的应用.例如判断某2个点是否连通(迷宫路径问题).普林斯顿的在线课程数据结构与算法第一章讲的就是它,而且由浅入深,逐步实现了有一个普通的实现到最后的加权优化实现以极大压缩生成树的高度来实现高效判断.下面是python实现的代码:
5 Jul 2013
Spiral Matrix: 螺旋矩阵2
收藏到CSDN网摘
以前写过2个关于螺旋矩阵的帖子,分别是matlab方法与python的模拟填空法,都是从左上角开始生长.在checkio的一道题中需要生成从中心开始螺旋生长的矩阵.方法还是类似于模拟填空法.这次需要判断的不再是到达边界转向,而是根据目前的方向,判断下一方向的位置是否为空,如果为空就转向继续写,与人工填写完全一致.需要注意的是中心位置的选取根据size的奇偶性有一些差别.
以前写过2个关于螺旋矩阵的帖子,分别是matlab方法与python的模拟填空法,都是从左上角开始生长.在checkio的一道题中需要生成从中心开始螺旋生长的矩阵.方法还是类似于模拟填空法.这次需要判断的不再是到达边界转向,而是根据目前的方向,判断下一方向的位置是否为空,如果为空就转向继续写,与人工填写完全一致.需要注意的是中心位置的选取根据size的奇偶性有一些差别.
3 Jul 2013
Flatten List列表快速展开
收藏到CSDN网摘
python中有时候list会多层嵌套,需要展开成一维列表,最快速的方法是使用yield生成器.
但是针对一层嵌套的[[a,b,c],[d,e]]这种,sum(L,[])还是最快的.
python中有时候list会多层嵌套,需要展开成一维列表,最快速的方法是使用yield生成器.
但是针对一层嵌套的[[a,b,c],[d,e]]这种,sum(L,[])还是最快的.
Shortest path 迷宫寻路
收藏到CSDN网摘
走迷宫是acm经常出现的一类问题,有多重方法可以解决,例如A*,广度优先搜索,深度优先搜索等.广度优先搜素可以保证一旦找到路径,必定为最短路径.
广度优先搜索的实例如下(在12*12的迷宫中从(1,1)走到(10,10),边界是围墙,0为可通过,1为不可通过):
走迷宫是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.
这是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.
1 Jul 2013
Subscribe to:
Posts
(
Atom
)