在亚马逊采访中我问过这个问题 -
给定一个正整数数组,您必须找到无法从数组中的数字之和形成的最小正整数.
例:
Array:[4 13 2 3 1]
result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }
我做的是:
但这是nlog(n)解决方案.
采访者对此并不满意,并在不到O(n log n)时间内提出解决方案.
arrays algorithm dynamic-programming subset-sum data-structures
以下代码来自Pathikrit的动态编程存储库.我的美丽和独特使我感到困惑.
def subsetSum(s: List[Int], t: Int) = {
type DP = Memo[(List[Int], Int), (Int, Int), Seq[Seq[Int]]]
implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)
lazy val f: DP = Memo {
case (Nil, 0) => Seq(Nil)
case (Nil, _) => Nil
case (a :: as, x) => (f(as, x - a) map {_ :+ a}) ++ f(as, x)
}
f(s, t)
}
该类型Memo在另一个文件中实现:
case class Memo[I <% K, K, O](f: I => O) extends (I => …有一个数字列表.
该列表将分为2个相等大小的列表,总和之间的差异最小.必须打印总和.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
在某些情况下,以下代码算法是否存在错误？
我如何优化和/或pythonize这个？
def make_teams(que):
que.sort()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
val = (que.pop(), que.pop())
if sum(t1)>sum(t2):
t2.append(val[0])
t1.append(val[1])
else:
t1.append(val[0])
t2.append(val[1])
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
python algorithm np-complete knapsack-problem dynamic-programming
这是我需要解决的计算机视觉问题的低调版本.假设给你参数n,q并且必须计算将整数0 ..(q-1)分配给n-by-n网格的元素的方式的数量,以便对于每个赋值,以下都是真的
由于没有给出(i,j,k,l),输出应该是上面的一个评估数组,每一个有效设置为(i,j,k,l)
蛮力方法如下.目标是获得一个有效的算法,适用于q <= 100和n <= 18.
def tuples(n,q):
return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]
def isvalid(t,n):
grid=[t[n*i:n*(i+1)] for i in range(n)];
for r in range(n):
for c in range(n):
v=grid[r][c]
left=grid[r][c-1] if c>0 else -1
right=grid[r][c-1] if c<n-1 else -1
top=grid[r-1][c] if r > 0 else -1
bottom=grid[r+1][c] if r < n-1 else -1
if v==left or v==right or v==top or v==bottom:
return …我从各种在线编码论坛中发现,有一种叫做"AC"的技术,看起来像"动态编程"或"后退跟踪",但不知道它是如何使用的.
有人有建议吗？
谢谢Joni:按照他/她的说法,它是"接受".现在它更有意义.
我在一次训练中遇到了这个问题.即我们给出了N不同的值(N<= 100).让我们命名这个数组A[N],这个数组A,我们确信,我们有数组1 A[i]≤10 9.其次,我们已经给数S ,其中S≤10 9.
现在我们必须用这个值来解决经典硬币问题.实际上我们需要找到最小数量的元素,它们将完全相加S.每个元素A都可以无限次使用.
时间限制:1秒
内存限制:256 MB
例:
S = 1000, N = 10
A[] = {1,12,123,4,5,678,7,8,9,10}. The result is 10.
1000 = 678 + 123 + 123 + 12 + 12 + 12 + 12 + 12 + 12 + 4
我试过了什么
我试图用经典的动态编程硬币问题技术来解决这个问题,但是它使用了太多内存并且超出了内存限制.
我无法弄清楚我们应该保留这些价值观.提前致谢.
以下是经典dp硬币问题无法解决的几个测试用例.
S = 1000000000 N = 100
1 373241370 973754081 826685384 491500595 765099032 823328348 462385937
251930295 …我正在寻找关于项目欧拉的问题三十一,请问,有多少不同的方法可以使用任意数量的1p,2p,5p,10p,20p,50p,£1(100p)和£的硬币赚2英镑2(200p).
有递归解决方案,例如Scala中的这个解决方案(由Pavel Fatin提供)
def f(ms: List[Int], n: Int): Int = ms match {
case h :: t =>
if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
case _ => 0
}
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)
虽然运行速度足够快,但它的效率相对较低,调用f函数大约560万次.
我看到了其他用Java编写的动态编程解决方案(来自葡萄牙的wizeman)
final static int TOTAL = 200;
public static void main(String[] args) {
int[] coins = {1, 2, 5, 10, 20, …使用动态编程可以解决许多问题,例如最长的增加子序列.这个问题可以通过使用2种方法来解决
我的问题是哪种方法在时间和空间复杂性方面更好？
给定一个整数数组和一个范围(低,高),找到数组中所有连续的子序列,它们在该范围内具有和.
有没有比O(n ^ 2)好的解决方案？
我尝试了很多,但找不到比O(n ^ 2)更好的解决方案.请帮我找到更好的解决方案或确认这是我们能做的最好的.
这就是我现在所拥有的,我假设范围被定义为[lo, hi].
public static int numOfCombinations(final int[] data, final int lo, final int hi, int beg, int end) {
int count = 0, sum = data[beg];
while (beg < data.length && end < data.length) {
if (sum > hi) {
break;
} else {
if (lo <= sum && sum <= hi) {
System.out.println("Range found: [" + beg + ", " + end + "]");
++count;
}
++end;
if (end < …将字符串拆分成单词的正确方法是什么？(字符串不包含任何空格或标点符号)
例如:"stringintowords" - >"String into Words"
你能告诉我这里应该使用什么算法吗？
!更新:对于那些认为这个问题仅仅是为了好奇的人.该算法可用于动态域名("sportandfishing .com" - >"SportAndFishing .com"),此算法目前由aboutus dot org用于动态执行此转换.
algorithm nlp dynamic-programming string-split text-segmentation
algorithm ×6
arrays ×3
python ×2
scala ×2
backtracking ×1
java ×1
memoization ×1
nlp ×1
np-complete ×1
recursion ×1
string-split ×1
subset-sum ×1
sum ×1