Tag: algorithm

find一组最大的连续矩形来覆盖多个区域

我正在为“ 矮人堡垒”（Dwarf Fortress）这款游戏开发一款名叫“ Quickfort ”的工具。 Quickfort将csv / xls格式的电子表格转换为一系列矮人要塞的命令，以便在游戏中绘制“蓝图”。 我目前正在尝试优化解决这个工具的2.0版本的面积绘图问题。 考虑下面的“蓝图”，它定义了二维网格的绘图命令。 网格中的每个单元格应该挖出（“d”），通道（“c”）或不保留（“。”）。 实际使用中可能会出现任意数量的不同绘图命令。 . d . dcc ddddcc . ddd . c dddddc . d . ddc 为了尽量减less需要发送给矮人堡垒的指令数量，我想find一组最大的连续矩形，它们可以形成为完全覆盖或“绘制”所有绘图单元格。 为了有效，给定矩形的所有单元必须包含相同的命令。 这是比Quickfort 1.0更快的方法：将每个单元分别绘制为1×1的矩形。 这个video显示了两个版本之间的性能差异。 对于上面的蓝图，解决scheme如下所示： . 9 . 0 3 2 8 1 1 1 3 2 . 1 1 1 . 2 7 1 1 1 4 […]

如何将浮点数整数转换为整数？

比方说，我有一个浮点数的数组，在sorting（我们说升序），其总和已知是一个整数N 我想把这些数字“整数”为整数，同时保持它们的总数不变。 换句话说，我正在寻找一种将浮点数字（称为fn ）转换为整数数组的algorithm（调用它），以便： 两个arrays具有相同的长度 整数数组的总和是N 每个浮点数fn[i]与其fn[i]相应的整数之间的差值小于1（如果您真的必须等于1） （ fn[i] <= fn[i+1] ），整数也将按sorting顺序排列（ in[i] <= in[i+1] ） 考虑到满足这四个条件，使得舍入方差最小化的algorithm（ sum((in[i] – fn[i])^2) ）是优选的，但是并不是什么大不了的。 例子： [0.02，0.03，0.05，0.06，0.07，0.08，0.09，0.1，0.11，0.12，0.13，0.14] => [0,0,0,0,0,0,0,0,0,0,1] [0.1,0.3,0.4,0.4,0.8] => [0,0,0,1,1] [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1] => [0,0,0,0,0,0,0,0,0,1] [0.4，0.4，0.4，0.4，9.2，9.2] => [0,0,1,1,9,9]是优选的 => [0,0,0,0,10,10]是可接受的 [0.5，0.5，11] => [0，1，11]很好 => [0，0，12]在技术上是不允许的，但我会把它捏在一起 回答评论中提出的一些优秀问题： 在这两个数组中都允许重复元素（尽pipe我也有兴趣知道仅在浮点数组不包含重复的情况下才有效） 没有一个正确的答案 – 对于给定的浮点数input数组，通常有多个满足四个条件的int数组。 我想到的应用程序 – 这有点奇怪 – 在MarioKart游戏中向顶尖的玩家分发点数;-)从来没有亲自玩过游戏，但在看别人的时候，我注意到有24点分布在前四名的终结者，我想知道如何根据完成时间来分配积分（所以如果有人在积分榜上领先，他们将得到更多的积分）。 游戏跟踪总数为整数，因此需要这种舍入。 为了好奇，这里是我用来确定哪些algorithm工作的testing脚本 。

如何从数字中读取值作为单词？

众所周知，数字可以用数字来表示，也可以用名字来表示。 虽然有很多例子可以把123转换为123，但是我找不到如何将其转换成另一种方式的好例子。 一些注意事项： 基数/名义或序数：“一”和“第一” 常见的拼写错误：“四十”/“四十” 数百/数千：2100 – >“二百”，还有“二千一百” 分隔符：“十一五二”，还有“一百五十二”或“十一五二”，还有什么 colloqialisms：“三十多岁” 片段：“三分之一”，“五分之二” 俗名：“一打”，“一半” 还有可能有更多的警告，可能还没有列出。 假设algorithm需要非常强大，甚至可以理解拼写错误。 我应该阅读哪些字段/论文/研究/algorithm来学习如何编写这些内容？ 信息在哪里？ PS：我最后的parsing器实际上应该理解3种不同的语言，英语，俄语和希伯来语。 也许在稍后的阶段会增加更多的语言。 希伯来文也有男/女数字，像“一个男人”和“一个女人”有不同的“一”，“ehad”和“ahat”。 俄罗斯也有其自身的一些复杂性。 Google在这方面做得很好，例如： http://www.google.com/search?q=two+thousand+and+one+hundred+plus+five+dozen+and+four+fifths+in+decimal （反过来也是http://www.google.com/search?q=999999999999+in+english ）

如何检测string列表中的常见子string

给定一组string，例如： EFgreen EFgrey EntireS1 EntireS2 J27RedP1 J27GreenP1 J27RedP2 J27GreenP2 JournalP1Black JournalP1Blue JournalP1Green JournalP1Red JournalP2Black JournalP2Blue JournalP2Green 我想能够检测到这些是三组文件： EntireS [1,2] J27 [红色，绿色] P [1,2] JournalP [1,2] [红，绿，蓝] 是否有任何已知的方法来解决这个问题 – 我可以阅读的任何已发表的论文？ 我正在考虑的方法是为每个string查看所有其他string，并查找常用字符以及不同字符的位置，试图查找具有最多共同string的string，但是我担心这不是非常有效，可能会给误报。 请注意，这与“如何检测文件名中的常用string组”是不一样的，因为它假定一个string总是有一系列的数字。

什么是最快的分解algorithm？

我已经写了一个试图findAmicable Pairs的程序。 这就要求find合适的数字除数。 这是我目前的sumOfDivisors()方法： int sumOfDivisors(int n) { int sum = 1; int bound = (int) sqrt(n); for(int i = 2; i <= 1 + bound; i++) { if (n % i == 0) sum = sum + i + n / i; } return sum; } 所以我需要做很多因子分解，并且开始成为我应用程序中的真正瓶颈。 我在MAPLE中input了一个很大的数字，并将其快速分解。 什么是更快的分解algorithm之一？

如何实现二叉树？

哪个是可以用来在Python中实现二叉树的最好的数据结构？

如何在不使用++或+或其他算术运算符的情况下添加两个数字

如何在不使用++或+或其他算术运算符的情况下添加两个数字？ 这是很久以前在一些校园访谈中提出的一个问题。 无论如何，今天有人问了一些关于操纵的问题，并且在答复中提到了斯坦福的一些小动作 。 我花了一些时间研究它，并认为实际上可能会有这个问题的答案。 我不知道，我找不到一个。 有答案吗？

C如何“绘制”二进制树到控制台

什么algorithm可以用来在控制台中绘制二叉树？ 树在C中实现。例如，控制台中将显示一个数字为2 3 4 5 8的BST，如下所示：

为什么Java的Arrays.sort方法对不同types使用两种不同的sortingalgorithm？

Java的Arrays.sort方法使用Quicksort处理基元数组，并为对象数组合并sorting。 我相信大部分时间Quicksort比合并sorting更快并且成本更低。 我的实验支持，尽pipe这两种algorithm都是O（n log（n））。 那么为什么不同的algorithm用于不同的types呢？

Java使用什么散列函数来实现Hashtable类？

从CLRS这本书（“algorithm简介”）中，有几个哈希函数，比如mod，multiply等。 Java使用什么散列函数将键映射到插槽？ 我已经看到这里有一个问题， 在Java语言中使用哈希函数 。 但是这个问题没有回答，我想这个问题的答案是错误的。 它说，hashCode（）让你做你自己的Hashtable散列函数，但我认为这是错误的。 hashCode（）返回的整数是Hashtble的真正键，然后Hashtable使用散列函数来散列hashCode（）。 这个答案意味着Java给了你一个给Hashtable一个哈希函数的机会，但不是，这是错误的。 hashCode（）提供了真正的密钥，而不是散列函数。 那么Java使用的哈希函数究竟是什么呢？