例如,让字符串为pi的前10位,3141592653子序列为123.请注意,序列出现两次:
3141592653
1 2 3
1 2 3
这是一个我无法回答的面试问题,我想不出一个有效的算法而且它让我烦恼.我觉得应该可以使用一个简单的正则表达式,但是1.*2.*3不要返回每个子序列.我在Python中的天真实现(在每个1之后计算每个2的3个)已经运行了一个小时而且还没有完成.
我想比较2个字符串并保持匹配,在比较失败的地方分开.
所以,如果我有2个字符串 -
string1 = apples
string2 = appleses
answer = apples
另一个例子,因为字符串可能有多个单词.
string1 = apple pie available
string2 = apple pies
answer = apple pie
我确信有一种简单的Python方法可以做到这一点,但我无法解决,任何帮助和解释都表示赞赏.
在编程竞赛中,以下模式出现在很多任务中:
给定数字A和B很大(可能是20个十进制数字或更多),确定具有特定属性P的A≤X≤B的整数X
SPOJ有许多这样的任务用于练习.
有趣的属性的例子包括:
我知道如果我们将f(Y)定义为这样的整数X≤Y,那么我们问题的答案就是f(B) - f(A - 1).减少的问题是如何有效地计算函数f.在某些情况下,我们可以利用某些数学属性来提出公式,但通常属性更复杂,我们在比赛中没有足够的时间.
在很多情况下是否有更通用的方法？它是否也可以用于枚举具有给定属性的数字或计算它们上的一些聚合？
其变体是找到具有给定属性的第k个数,当然可以通过使用二进制搜索和计数函数来求解.
这不是一个功课问题.我只是觉得有人可能知道这个问题的真正解决方案.
2004年我参加了编程竞赛,出现了这个问题:
给定n,找到n!的数字之和.n可以是0到10000.时间限制:1秒.我认为每个测试集最多有100个数字.
我的解决方案非常快,但速度不够快,所以我让它运行一段时间.它构建了一组预先计算的值,我可以在我的代码中使用它.这是一个黑客攻击,但它确实有效.
但有一个人用大约10行代码解决了这个问题,它会立即给出答案.我相信它是某种动态编程,或者来自数论的东西.当时我们16岁,所以它不应该是"火箭科学".
有谁知道他可以使用什么样的算法？
编辑:如果我没有明确提出问题,我很抱歉.正如mquander所说,应该有一个聪明的解决方案,没有bugnum,只有简单的Pascal代码,几个循环,O(n 2)或类似的东西.1秒不再是约束.
我在这里发现,如果n> 5,则9除以阶乘的数字之和.我们还可以找到数字末尾有多少个零.我们可以用吗？
好的,来自俄罗斯的编程竞赛的另一个问题.给定1 <= N <= 2 000 000 000,输出N!mod(N + 1).这有点关系吗？
我想记住这个:
def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2)
println(fib(100)) // times out
所以我写了这个,这令人惊讶地编译和工作(我很惊讶,因为fib在其声明中引用自己):
case class Memo[A,B](f: A => B) extends (A => B) {
private val cache = mutable.Map.empty[A, B]
def apply(x: A) = cache getOrElseUpdate (x, f(x))
}
val fib: Memo[Int, BigInt] = Memo {
case 0 => 0
case 1 => 1
case n => fib(n-1) + fib(n-2)
}
println(fib(100)) // prints 100th fibonacci number instantly
但是当我尝试在a中声明fib时def,我得到一个编译器错误:
def foo(n: …scope scala memoization dynamic-programming forward-reference
我正在研究这个问题:
该子集和问题需要输入一个组
X = {x1, x2 ,…, xn}的n整数和另一个整数K.问题是,以检查是否存在一个子集X'的X,它的元素之和为K,并发现该子集,如果有任何.例如,如果X = {5, 3, 11, 8, 2}和K = 16那么答案是YES,因为该子集X' = {5, 11}具有的总和16.实现Subset Sum的算法,其运行时间至少为O(nK).
注意复杂性O(nK).我认为动态编程可能有所帮助.
我找到了一个指数时间算法,但它没有帮助.
有人可以帮我解决这个问题吗？
可能重复:
动态编程和记忆:自上而下与自下而上的方法
我已经阅读了很多文章,但似乎无法理解它.有时递归和动态编程看起来相同,而在其他时候,memoization和动态编程看起来很相似.有人可以向我解释有什么区别吗？
PS如果您可以使用针对同一问题的三种方法向我指出一些代码,那么它也会很有帮助.(例如Fibonacci系列问题,我认为我读过的每篇文章都使用了递归,但将其称为动态编程)
Haskell和其他函数式编程语言是在不维护状态的前提下构建的.我还不熟悉函数式编程的工作原理和概念,所以我想知道是否有可能以FP方式实现DP算法.
可以使用哪些函数式编程结构来做到这一点？
我无法弄清楚动态编程的原理,我真的很想要它.DP非常强大,它可以解决这样的问题:
那么,你能给我推荐好的书籍或文章(最好带有真实代码的例子),它可以解释我什么是动态编程？我首先想要简单的例子,然后我会继续前进.
我需要在一个充满1和0的巨型文件中找到最大的1的平方.我知道我必须使用动态编程.我将它存储在2D数组中.任何有关找到最大方块的算法的帮助都会很棒,谢谢!
示例输入:
1 0 1 0 1 0
1 0 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 1
1 1 1 1 1 1
回答:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
我的代码到目前为止:
int Square (Sq[int x][int y]) {
if (Sq[x][y]) == 0) {
return 0;
}
else {
return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
}
}
(假设已经输入数组的值)
int main() {
int Sq[5][6]; …