我在子阵列,子序列和子集之间有点困惑
如果我有 {1,2,3,4}
然后
子序列可以是{1,2,4}OR {2,4}等.所以基本上我可以省略一些元素但保持顺序.
子阵列(比如3号子阵)
{1,2,3}
{2,3,4}
那么子集是什么？
我对这3个人感到有点困惑.
String.subSequence() 有以下javadoc:
返回一个新的字符序列,它是该序列的子序列.
调用此方法的形式
Run Code Online (Sandbox Code Playgroud)str.subSequence(begin, end)行为与调用完全相同
Run Code Online (Sandbox Code Playgroud)str.substring(begin, end)定义此方法,以便String类可以实现CharSequence接口.
谁能解释一下？
Google编程面试中提到了这个问题.我想到了两种相同的方法:
找到所有长度的子序列.这样做的同时计算两个元素的和,并检查它是否等于k.如果是的话,打印是,否则继续搜索.这是一种蛮力的方法.
以非递减顺序对数组进行排序.然后从右端开始遍历数组.假设我们有排序数组{3,5,7,10},我们希望总和为17.我们将从元素10开始,索引= 3,让我们用'j'表示索引.然后包括当前元素并计算required_sum = sum - current_element.之后,我们可以在数组[0-(j-1)]中执行二进制或三进制搜索,以查找是否存在其值等于required_sum的元素.如果我们找到这样一个元素,我们可以打破,因为我们找到了长度为2的子序列,其总和是给定的总和.如果我们没有找到任何这样的元素,那么减小j的索引并重复上述步骤以得到长度=长度为1的子阵列,即在这种情况下通过排除索引3处的元素.
在这里,我们认为数组可能有负整数和正整数.
你能提出比这更好的解决方案吗？DP解决方案可能吗？一种可以进一步降低时间复杂度的解决方案.
arrays algorithm dynamic-programming time-complexity subsequence
最近,我在接受采访时被问到以下问题.
给定字符串S,我需要找到另一个字符串S2,使得S2是S的子序列,并且S是S2 +反向的子序列(S2).这里'+'表示连接.我需要为给定的S输出最小可能的S2长度.
我被告知这是一个动态编程问题,但我无法解决它.有人可以帮我解决这个问题吗？
编辑-
有没有办法在O(N 2)或更少的情况下执行此操作.
我正在练习算法,我的任务之一是计算给定0 <n <= 10 ^ 6个数字的所有最长增长子序列的数量.解决方案O(n ^ 2)不是一个选项.
我已经实现了查找LIS及其长度(LIS算法),但是该算法将数字切换到尽可能低的数字.因此,我不可能确定具有先前数字(较大的数字)的子序列是否能够实现最长的长度,否则我可以计算这些开关.
任何关于如何在O(nlogn)中得到这个的想法？我知道它应该使用动态编程来解决.
我实现了一个解决方案,它运行良好,但它需要两个嵌套循环(i in 1..n)x(j in 1..i-1).
所以它是O(n ^ 2)我认为,但它太慢了.
我试图甚至那些从数字阵列移动到一个二叉树(因为在每次我迭代i寻找所有更小的数字,然后数[I] -经历元件I-1..1),但它是更慢.
示例测试:
1 3 2 2 4
result: 3 (1,3,4 | 1,2,4 | 1,2,4)
3 2 1
result: 3 (1 | 2 | 3)
16 5 8 6 1 10 5 2 15 3 2 4 1
result: 3 (5,8,10,15 | 5,6,10,15 …我不明白O(2^n)最长公共子序列算法的递归函数的复杂性。
通常，我可以将这个符号与算法的基本操作（在这种情况下是比较）的数量联系起来，但这一次在我看来没有意义。
例如，有两个长度相同的字符串5. 在最坏的情况下，递归函数计算251比较。并且2^5甚至不接近该值。
谁能解释这个函数的算法复杂性？
def lcs(xstr, ystr):
global nComp
if not xstr or not ystr:
return ""
x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:]
nComp += 1
#print("comparing",x,"with",y)
if x == y:
return x + lcs(xs, ys)
else:
return max(lcs(xstr, ys), lcs(xs, ystr), key=len)
在线整数序列百科全书支持搜索包含您的查询作为子序列的序列,例如.搜索subseq:212,364,420,428将返回8*n+4序列.(http://oeis.org/search?q=subseq:212,364,420,428)
这个惊人的功能显然是由Russ Cox实现的http://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Features实现的,但是没有用它实现的算法来指定.
我想知道它是如何完成的.对于搜索引擎来说,每次搜索显然要经过近一百万个序列是不切实际的.只保留一个索引(这是同一个Russ Cox对谷歌代码正则表达式搜索的方式)的第一个数字和暴力强迫其余的也不起作用,因为数字0几乎在所有序列中.实际上,一些查询0 1匹配总数据库的高百分比,因此算法需要对所需输出大小敏感的运行时间.
有谁碰巧知道这个功能是如何实现的？
如何找到最长的重复（不重叠）子序列（不是子串）？
约束：
字符串 S 最多由 100.000 个小写字符“a”-“z”组成。
例子：
字符串hanadwomehanudsiome具有最长的重复（非重叠）子序列beautiful。
预期时间复杂度为 O(|S| log |S|) 或更好（|S| 是字符串 S 的长度）。
有哪些好方法可以找到两个字符串长度的所有常见子k序列？
例:
s1= AAGACC
s2= AGATAACCAGGAGCTGC
所有常见的长度为5的子序列: AAGAC AAACC AGACC AAGCC
在这个问题的几个dp解决方案中,一个更简单的解决方案是反转给定的字符串并计算原始和反向字符串的LCS.
我的问题是这种方法每次会产生正确的结果吗？
例如,ACBAC及其反向CABCA的最长公共子序列是ABC,它不是回文,但由于其他LCS是回文ACA,CAC,这仍然给出了正确的结果.
那么,即使可能存在非回文LCS,这种方法每次都能产生正确的结果吗？
dp表,如果有帮助的话.
A C B A C
0 0 0 0 0 0
C 0 0 1 1 1 1
A 0 1 1 1 2 2
B 0 1 1 2 2 2
C 0 1 2 2 2 3
A 0 1 2 2 3 3