标签: subsequence

在这个问题的几个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  

有没有办法检查字符串是否是Prolog中另一个字符串的子字符串？我尝试将字符串转换为字符列表,然后检查第一个集合是否是第二个集合的子集,这似乎不够限制.这是我目前的代码:

isSubstring(X,Y):-
        stringToLower(X,XLower),
        stringToLower(Y,YLower),
        isSubset(XLower,YLower).

isSubset([],_).
isSubset([H|T],Y):-
        member(H,Y),
        select(H,Y,Z),
        isSubset(T,Z).

stringToLower([],[]).
stringToLower([Char1|Rest1],[Char2|Rest2]):-
        char_type(Char2,to_lower(Char1)),
        stringToLower(Rest1,Rest2).

如果我测试一下

于issubstring( "测试", "tesZting").

它返回yes,但是应该返回no.

给定一个包含N个不同整数的数组,找到满足以下条件的最长子序列:

1. 子序列的start元素是子序列中最小的.
2. 子序列的结束元素是子序列中最大的元素.

例如:8,1,9,4,7.答案是1,4,7.

2,6,5,4,9,8.答案是2,6,5,4,9或2,6,5,4,8.

这是一个O(N^2)算法:

• 让我们X成为一组数字.
• 迭代X.假设我们在索引i.让Y是阵列,其中Y [j]为在元件的数量(j, i],其比X [j]的小.让z是元件的数量在[j, i]其比X [I]小.如果X [j]小于X [i],我们可以得到满足约束的长度为zY [j]的子序列.

• 设置z为1.循环j从i-1下到0.

  if X[j] < X[i]: z++; ans = max(ans, z - Y[j]); else Y[j]++;

我们可以做得更好吗？我认为应该有一个O(NlogN)算法来找到最大长度.

使用pandas/python，我想计算每组元组的最长递增子序列DTE，但有效地使用13M行。现在，使用 apply/iteration 大约需要 10 个小时。

这大概是我的问题：

import pandas as pd
pd.DataFrame({
    'DTE': [1,1,1,1,1,1,2,2,2],
    'Strike': [100,200,300,400,500,600,100,200,300],
    'Bid': [10,16,17,11,12,13,10,15,16],
    'Ask': [11,17,18,12,13,14,30,20,21],
})

我想要：

• 将这些分组DTE。这里我们有两个组（DTE 1 和 DTE 2）。然后在每个组内...
• 找到最长的成对递增子序列。排序由 确定Strike，它对于每个 DTE 组都是唯一的。所以 200 Strike 是在 100 …

我有一个大小n为整数值的数组和一个给定的 number S。

1<=n<=30

我想找到子序列的总数，使得每个子序列的元素总和小于S。 例如：让n=3，S=5和数组的元素是作为{1,2,3}然后其总的子序列是7原样

{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

但是，所需的子序列是：

{1},{2},{3},{1,2},{1,3},{2,3}

that is{1,2,3}不被采用，因为它的元素总和(1+2+3)=6大于Sthat is 6>S。之所以采用其他，是因为，对于其他子序列，元素总和小于S。因此，可能的子序列总数为6。所以我的答案是计数，即6。

我试过递归方法，但它的时间复杂度是2^n. 请帮助我们在多项式时间内完成。

今天早些时候我做了这个测试，我试图太聪明并撞上了路障。不幸的是，我陷入了这种思维模式并浪费了太多时间，未能通过这部分测试。后来我解决了它，但也许你们都可以帮助我摆脱最初的习惯。

问题定义：

给出了一个由 N 个整数（都是正数）组成的无序和非唯一序列 A。A 的子序列是通过从 A 中去除任何元素、部分或全部元素而获得的任何序列。序列的幅度是该序列中最大和最小元素之间的差值。假设空子序列的幅度为 0。

例如，考虑由六个元素组成的序列 A，使得：

A[0] = 1
A[1] = 7
A[2] = 6
A[3] = 2
A[4] = 6
A[5] = 4

如果数组 A 的子序列幅度不超过 1，则称其为准常数。在上面的例子中，子序列 [1,2]、[6,6] 和 [6,6,7] 是准常数。子序列 [6, 6, 7] 是 A 的最长可能准常数子序列。

现在，找到一个解决方案，给定一个由 N 个整数组成的非空零索引数组 A，返回数组 A 的最长准常数子序列的长度。例如，给定上面列出的序列 A，函数应该返回 3 ，如解释。

现在，我在 python 3.6 中使用了没有类的基于排序的方法解决了这个问题（我的代码在下面），但我最初不想这样做，因为对大列表进行排序可能非常慢。作为广度优先的基于树的类，这似乎应该有一个相对简单的公式，但我无法正确理解。对此有何想法？

我的无类基于排序的解决方案：

def amp(sub_list):
    if len(sub_list) <2:
        return 0
    else:
        return max(sub_list) - min(sub_list)

def solution(A):
    A.sort()
    longest = 0
    idxStart = 0
    idxEnd …

我想知道是否有任何O(n ^ 2)复杂度算法用于生成数组的所有子序列.我知道一个算法,但它需要O((2 ^ n)*n)时间.

int main() {
    int n; 
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) 
        cin >> a[i];
    int64_t opsize = pow(2,n);
    for (int counter = 1; counter < opsize; counter++) {
        for (int j = 0; j < n; j++) {
           if (counter & (1 << j))
                 cout << a[j] << " ";
        }
        cout << endl;
    }
}

我正在尝试修改 Kadane 算法以解决更具体的问题。

def max_Sum(arr, length, k):
if length < k:
    print('length of array should be greater than k')

res = 0
for i in range(0, k):
    res += arr[i]

current_sum = res

for i in range(k, n):
    if k == n:
        for j in range(0, k-1):
            res += arr[j]
        current_sum = res
    else:
        current_sum += arr[i] - arr[i-k]
        print(res, current_sum)
        res = max(res, current_sum)

return res

这是最大子数组问题的代码。我想要做的是找到长度最多为 K 的最大子数组。

示例：我们有一个数组 A = [3,-5 1 2,-1 4,-3 1,-2]，我们想要找到长度最多为 K = …

我希望从第一个元素开始提取向量的增加子序列.例如,从这个向量:
a = c(2, 5, 4, 0, 1, 6, 8, 7)

我想回来:
res = c(2, 5, 6, 8).

我以为我可以使用循环,但我想避免它.另一种尝试sort:

a = c(2, 5, 4, 0, 1, 6, 8, 7)
ind = sort(a, index.return = TRUE)$ix
mat = (t(matrix(ind))[rep(1, length(ind)), ] - matrix(ind)[ , rep(1, length(ind))])
mat = ((mat*upper.tri(mat)) > 0) %*% rep(1, length(ind)) == (c(length(ind):1) - 1)
a[ind][mat]

基本上我对输入向量进行排序并检查索引是否验证条件"右侧没有索引较低",这意味着事先没有更大的值.

但它似乎有点复杂,我想知道是否有更容易/更快的解决方案,或R中的预建功能.

谢谢

我试图解决这个问题，我们必须找到子序列的最大长度，使得每个连续元素的 XOR 等于 keg ：Array = [3,2,4,3,5] 和 k=1。答案是 3。 subsequence = [3,2,3]

到目前为止，我已经尝试过这些方法：

1. 朴素的双循环解决方案，我们将使用两个循环并找到 XOR 等于 k ​​的子序列。这种方法让我超时，因为数组中的元素数量可以达到 10^5。伪代码：

int finalAns=0;
loop (i=0...n):
  int xortillnow = array[i], count=1;  // since we have already selected one element
  loop(j=i+1..n):
      if((xortillnow ^ array[i])==k):
          count++;
          xortillnow = xortillnow ^ array[i];
   finalAns = max(count,finalAns);

2.Second 我正在考虑动态编程，我可以在其中存储已经计算出的子序列的异或，但我无法完成算法。

有人可以告诉一些解决这个问题的其他方法。