所以给了"针"和"这里有针但不是这个针干草堆"
我写
def find_needle(n,h):
count = 0
words = h.split(" ")
for word in words:
if word == n:
count += 1
return count
这是O(n),但想知道是否有更好的方法？也许不是通过使用拆分？
您将如何为此案例编写测试以检查它是否处理所有边缘情况？
假设构建了一个字典单词的一般Trie,那么在遍历期间检查4种拼写错误 - 替换,删除,转置和插入的最佳方法是什么？
一种方法是找出给定单词的n个编辑距离内的所有单词,然后在Trie中检查它们.这不是一个糟糕的选择,但这里更好的直觉似乎是使用动态编程(或递归等效)方法来确定在遍历期间修改单词后的最佳子尝试.
任何想法都会受到欢迎!
PS,会欣赏实际输入,而不仅仅是答案中的链接.
我已经做了一堆研究,找到M = 2序列的最长时间,但我想弄清楚如何为M≥2序列做到这一点
我被赋予N和M:M序列,具有N个独特元素.N是{1 - N}的集合.我已经考虑过动态编程方法,但我仍然对如何实际合并它感到困惑.
示例输入
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4
这里的最大序列可以看出来
5 3 1
预期产出
Length = 3
因此对于以下数组,其中L = 3
-5 -1 2 -3 0 -3 3
至少长度为3的最佳总和将为0,其中子序列是最后三个元素(0,-3,3)
如何以比O(NL)更快的速度计算任何数组的总和(如果L == 0)时间,实际上是O(N ^ 2)？
如果可以通过连接相同字符串的两个副本来获取字符串,则将其称为方形字符串.例如,"abab","aa"是方形字符串,而"aaa","abba"不是.给定一个字符串,该字符串的子序列有多少是方形字符串？可以通过从中删除零个或多个字符并保持剩余字符的相对顺序来获得字符串的子序列.子序列不必是唯一的.
例如,字符串'aaa'将具有3个方形子序列
例如:数组:4,3,0,1,5 {假设所有数字> = 0.数组中的每个元素也对应一个数字.即数组中的每个元素都在0到9之间.}
在上面的数组中,最大的数字是:5430 {使用数组中的数字5,4,3和0}
我的方法:
对于3的可分性,我们需要数字的总和可以被3整除.所以,
因此,主要步骤是STEP-3,即如何找到子集,使其包含MAXIMUM可能数量的元素,使得它们的和为MAX,并且可以被3整除.
我在想,也许Step-3可以通过GREEDY CHOICE来完成所有元素并继续删除集合中的最小元素,直到总和可以被3整除.
但我不相信这个贪婪的选择会起作用.
请告诉我的方法是否正确.如果是,那么请建议如何做第3步？
此外,请建议任何其他可能/有效的算法.
这是一个面试问题.计算[1,N]范围内唯一数字(十进制)的所有数字.
显而易见的解决方案是,如果其数字是唯一的,则测试范围中的每个数字.我们还可以生成具有唯一数字(作为排列)的所有数字,并测试它们是否在范围内.
现在我想知道是否有针对此问题的DP(动态编程)解决方案.
问题是
"你正在爬楼梯.每次你可以做一步或两步.楼梯有n个台阶.你有多少不同的方式可以爬楼梯？"
以下是此问题的代码解决方案,但我无法理解它.任何人都可以解释我
int stairs(int n) {
if (n == 0) return 0;
int a = 1;
int b = 1;
for (int i = 1; i < n; i++) {
int c = a;
a = b;
b += c;
}
return b;
}
谢谢,
我几乎让我的needleman-wunsch实现工作,但我对如何处理特定情况下的追溯感到困惑.
我们的想法是,为了重新构建序列(最长路径),我们重新计算以确定得分来自的矩阵.我遇到问题的边缘情况是右下方得分不在匹配矩阵中,但是在插入列矩阵中(意味着得到的跟踪序列应该有插入).
这些序列以a2m格式记录,其中序列中的插入被记录为小写字符.所以在最终输出中ZZ,AAAC应该是对齐AAac.当我用手追溯时,我最终会AAAc因为我只访问Ic矩阵一次.这是我的白板图片.如你所见,我有三个黑色箭头和一个绿色箭头,这就是我追溯给我的原因AAAc.我应该计算第一个单元格,然后停在1,1位置？我不确定如何改变我实现这一点的方式.
注意,这里使用的替换矩阵是BLOSUM62.复发关系是
M(i,j) = max(Ic(i-1,j-1)+subst, M(i-1,j-1)+subst, Ir(i-1,j-1)+subst)
Ic(i,j) = max(Ic(i,j-1)-extend, M(i,j-1)-open, Ir(i,j-1)-double)
Ir(i,j) = max(Ic(i-1,j)-double, M(i-1,j)-open, Ir(i-1,j)-extend)
编辑:这是traceback_col_seq函数重写为更清洁.请注意,score_cell现在返回thisM,thisC,thisR而不是其中的最大值.这个版本将对齐评为AaAc,仍然存在同样的问题,现在又出现了另一个问题,即为什么它会在1,2处再次进入Ic.但是这个版本更清晰.
def traceback_col_seq(self):
i, j = self.maxI-1, self.maxJ-1
self.traceback = list()
matrixDict = {0:'M',1:'Ic',2:'Ir',3:'M',4:'Ic',5:'Ir',6:'M',7:'Ic',8:'Ir'}
while i > 0 or j > 0:
chars = self.col_seq[j-1] + self.row_seq[i-1]
thisM, thisC, thisR = self.score_cell(i, j, chars)
cell = thisM + thisC + thisR
prevMatrix = matrixDict[cell.index(max(cell))]
print(cell, prevMatrix,i,j)
if prevMatrix == …问题陈述 :
在正整数上,您可以执行以下3个步骤中的任何一个.
现在问题是,给定正整数n,找到将n取为1的最小步数
例如:
我知道使用动态编程并具有整数数组的解决方案.这是代码.
public int bottomup(int n) {
//here i am defining an integer array
//Exception is thrown here, if the n values is high.
public int[] bu = new int[n+1];
bu[0] = 0;
bu[1] = 0;
for(int i=2;i<=n;i++) {
int r …