查找具有连续差异的数组中的子序列总数 = k
Finding total number of subsequences in an array with consecutive difference = k
在给定的数组中,我试图找到满足以下条件的子序列总数:
- 连续项之间的差不大于3
- 子序列的第一个元素是数组的第一个元素
- 子序列的最后一个元素是数组的最后一个元素
例如,在一个数组中:[10,13,7,8,14,200, 876, 11]
,它有5个满足上述条件的子序列。
我正在尝试一种自下而上的方法。我尝试了以下,但它没有给出所有的子序列和输出 4 而不是 5。
我该如何解决这个问题?我有一种直觉,该方法可能类似于最长递增子序列,但不确定如何。
令f(i)为满足以下条件的子序列数:
- 从 A[0] 开始
- 以A[i]结束
- 连续项之间的差不大于3
那么你问题的答案就是 f(A.length()-1).
以下是采用自下而上方法的 C++ 代码:
int A[] = {10,13,7,8,14,11};
int f[6];
int n = 6;
for (int i=0;i<n;i++) f[i] = 0;
f[0]=1;
for (int i=1;i<n;i++){
for (int j=0;j<i;j++){
if (abss(A[i] - A[j]) <= 3)
f[i] += f[j];
}
}
cout<<f[n-1]<<endl;//printing the result
这里是用 C++ 自顶向下方法编写的代码:
int A[] = {10,13,7,8,14,11};
int n = 6;
int memo[6];//initialized with -1s;
int count(int currIndex){
if (currIndex == n-1) return 1;
if (memo[currIndex] != -1) return memo[currIndex];
int res = 0;
for (int i=currIndex+1 ; i<n ; i++){
if (abss(A[currIndex] - A[i]) <= 3){
res += count(i);
}
}
memo[currIndex] = res;
return res;
}
结果将通过在第一个索引处调用计数,如下所示:
count(0);
@VFX 已经提出了 O(N^2)
的解决方案,但在大多数情况下,首选优化算法。所以这里有一个 O(K*N)
解决方案。
假设子序列中的第一个元素是 x
。下一个元素必须在 [x-k, x+k]
范围内。如果您知道该范围内所有值的有效序列数,您也可以在 O(K)
中找到当前元素的答案。
更正式地说,该算法将是:
arr = [] // your list
counter = {} // a dictionary or hashmap to keep count of sequences
counter[arr[-1]] = 1
for i in range (len(arr)-2 to 0):
curr_element = a[i]
sequences = 0
for x in range (curr_element-k to curr_element+k):
sequences += counter[x]
counter[curr_element] += sequences
final_answer = counter[arr[0]]
我刚刚注意到@Abhinav 的回答是将解决方案优化为 O(K*N)
而不是 O(N^2)
这对于小型 K
.
来说效果很好
但是,如果需要最佳解决方案,我建议使用 O(N*log2(N))
解决方案,在 [x-k,x+k]
范围内找到总和可以
使用 Segment Tree or Binary Indexed Tree(Fenwick Tree) 在 log2(N) 中完成,其中范围求和查询 (RSQ) 是这两个数据结构提供的标准操作。
如果初始数组中的值很大(如 long 或 double),可以借助 Map 进行数据压缩。
在这种方法中,您无需担心 K
即使它太大了。
在给定的数组中,我试图找到满足以下条件的子序列总数:
- 连续项之间的差不大于3
- 子序列的第一个元素是数组的第一个元素
- 子序列的最后一个元素是数组的最后一个元素
例如,在一个数组中:[10,13,7,8,14,200, 876, 11]
,它有5个满足上述条件的子序列。
我正在尝试一种自下而上的方法。我尝试了以下,但它没有给出所有的子序列和输出 4 而不是 5。
我该如何解决这个问题?我有一种直觉,该方法可能类似于最长递增子序列,但不确定如何。
令f(i)为满足以下条件的子序列数:
- 从 A[0] 开始
- 以A[i]结束
- 连续项之间的差不大于3
那么你问题的答案就是 f(A.length()-1).
以下是采用自下而上方法的 C++ 代码:
int A[] = {10,13,7,8,14,11};
int f[6];
int n = 6;
for (int i=0;i<n;i++) f[i] = 0;
f[0]=1;
for (int i=1;i<n;i++){
for (int j=0;j<i;j++){
if (abss(A[i] - A[j]) <= 3)
f[i] += f[j];
}
}
cout<<f[n-1]<<endl;//printing the result
这里是用 C++ 自顶向下方法编写的代码:
int A[] = {10,13,7,8,14,11};
int n = 6;
int memo[6];//initialized with -1s;
int count(int currIndex){
if (currIndex == n-1) return 1;
if (memo[currIndex] != -1) return memo[currIndex];
int res = 0;
for (int i=currIndex+1 ; i<n ; i++){
if (abss(A[currIndex] - A[i]) <= 3){
res += count(i);
}
}
memo[currIndex] = res;
return res;
}
结果将通过在第一个索引处调用计数,如下所示:
count(0);
@VFX 已经提出了 O(N^2)
的解决方案,但在大多数情况下,首选优化算法。所以这里有一个 O(K*N)
解决方案。
假设子序列中的第一个元素是 x
。下一个元素必须在 [x-k, x+k]
范围内。如果您知道该范围内所有值的有效序列数,您也可以在 O(K)
中找到当前元素的答案。
更正式地说,该算法将是:
arr = [] // your list
counter = {} // a dictionary or hashmap to keep count of sequences
counter[arr[-1]] = 1
for i in range (len(arr)-2 to 0):
curr_element = a[i]
sequences = 0
for x in range (curr_element-k to curr_element+k):
sequences += counter[x]
counter[curr_element] += sequences
final_answer = counter[arr[0]]
我刚刚注意到@Abhinav 的回答是将解决方案优化为 O(K*N)
而不是 O(N^2)
这对于小型 K
.
来说效果很好
但是,如果需要最佳解决方案,我建议使用 O(N*log2(N))
解决方案,在 [x-k,x+k]
范围内找到总和可以
使用 Segment Tree or Binary Indexed Tree(Fenwick Tree) 在 log2(N) 中完成,其中范围求和查询 (RSQ) 是这两个数据结构提供的标准操作。
如果初始数组中的值很大(如 long 或 double),可以借助 Map 进行数据压缩。
在这种方法中,您无需担心 K
即使它太大了。