给定一个整数数组arr，您的任务是计算表示至少包含两个元素的锯齿形序列的连续子数组的个数。
对于arr =[9,8,7,6,5]，输出应该是countSawSubarrays(arr) = 4。由于所有元素都是按降序排列的，因此不可能形成长度为3或更多的锯齿形子数组。有4个可能的包含两个元素的子数组，所以答案是4。
对于arr =[10,10,10]，输出应该是countSawSubarrays(arr) = 0。因为所有的元素都是相等的，所以没有子数组是锯齿形的，所以答案是0。
对于arr =[1,2,1,2,1]，输出应为countSawSubarrays(arr) = 10。
所有包含至少两个元素的连续子数组满足问题的条件。有10个可能的连续子数组包含至少两个元素，所以答案是10。
解决这个问题的最好方法是什么?我在这里看到了一个可能的解决方案:https://medium.com/swlh/sawtooth-sequence-java-solution-460bd92c064但是对于[1,2,1,3,4，-2]的情况，这个代码失败，因为答案应该是9，但结果是12。
我甚至尝试过一个蛮力的方法，但我不能把我的头围绕它。任何帮助将不胜感激!
编辑:感谢Vishal的响应，经过一些调整，这里是python的更新解决方案。时间复杂度:O(n)空间复杂度:0 (1)
def samesign(a,b):
if a/abs(a) == b/abs(b):
return True
else:
return False
def countSawSubarrays(arr):
n = len(arr)
if n<2:
return 0
s = 0
e = 1
count = 0
while(e<n):
sign = arr[e] - arr[s]
while(e<n and arr[e] != arr[e-1] and samesign(arr[e] - arr[e-1], sign)):
sign = -1*sign
e+=1
size = e-s
if (size==1):
e+=1
count += (size*(size-1))//2
s = e-1
e = s+1
return count
arr1 = [9,8,7,6,5]
print(countSawSubarrays(arr1))
arr2 = [1,2,1,3,4,-2]
print(countSawSubarrays(arr2))
arr3 = [1,2,1,2,1]
print(countSawSubarrays(arr3))
arr4 = [10,10,10]
print(countSawSubarrays(arr4))
结果:49100
在做类似的实践问题之前，我被困在这个问题上一段时间了，然后终于有了一个"啊!然后得到一个简洁优雅的解决方案。
- 当我们迭代时，每次我们在子数组长度2的增减之间翻转时，连续数组的数量就会随着当前在一行中翻转的次数而增加。例如，
[1, 2, 1, 2, 1]连续4次翻转，所以1 + 2 + 3 + 4 = 10 - 当我们打破锯齿条纹时，也就是说，当我们在一行中增加两次或在一行中减少两次时，最长的连续子数组现在只是2，所以如果两个值不相等，我们将计数器重置为1(因为这是一个有效的锯齿)，如果值相同，我们将计数器重置为0。
- 具有条纹和破碎条纹的示例:
[1, 7, 3, 4, 5]。当我们迭代([1, 7],[7, 3],[3, 4])时，我们保持3的连胜，然后[4, 5]打破了这条连胜，因为[3, 4]也在增加，所以我们最终的计数为(3 + 2 + 1)+ 1 = 7个可能的锯齿。
def solution(arr):
if len(arr) < 2:
return 0
count = 0
streak = 0
prev_increasing = None
for i in range(1, len(arr)):
if arr[i] == arr[i-1]:
prev_increasing = None
streak = 0
else:
curr_increasing = arr[i] > arr[i-1]
if curr_increasing != prev_increasing:
# keep track of streak of flips between increasing and decreasing
streak += 1
prev_increasing = curr_increasing
else:
# when we break out of a streak, we reset the streak counter to 1
streak = 1
# number of sawtooth contiguous subarrays goes up by the current streak
count += streak
return count
这可以通过将数组拆分为多个锯齿序列来解决…这是O(n)操作。例如[1,2,1,3,4，-2]可以分成两个序列[1,2,1,3]和[3,4，-2]现在我们只需要对这两个部分进行C(size,2)运算。
下面是解释这个想法的伪代码(没有处理所有的极端情况)
public int countSeq(int[] arr) {
int len = arr.length;
if (len < 2) {
return 0;
}
int s = 0;
int e = 1;
int sign = arr[e] - arr[s];
int count = 0;
while (e < len) {
while (e < len && arr[e] - arr[e-1] != 0 && isSameSign(arr[e] - arr[e-1], sign)) {
sign = -1 * sign;
e++;
}
// the biggest continue subsequence starting from s ends at e-1;
int size = e - s;
count = count + (size * (size - 1)/2); // basically doing C(size,2)
s = e - 1;
e = s + 1;
}
return count;
}
这是我使用动态规划的解决方案。对我来说，这比公认的答案(或OP中添加的答案)更容易读懂，尽管可能仍有改进的余地。
O(n)时间，O(1)空间。
def solution(arr):
# holds the count of sawtooths at each index of our input array,
# for sawtooth lengths up to that index
saws = [0 for x in range(0, len(arr))]
# the resulting total sawtooth counts
totalSawCounts = 0
previousCount = 0
for currIdx in range(1, len(arr)):
currCount = 0
before = currIdx -1
if (arr[currIdx] > arr[before]):
goingUp = True
elif (arr[currIdx] < arr[before]):
goingUp = False
else:
break
# if we made it here, we have at least one sawtooth
currCount = 1
# see if there was a previous solution (the DP part)
# and if it continues our current sawtooth
if before >= 1:
if goingUp:
if arr[before-1] > arr[before]:
currCount = previousCount + currCount
else:
if arr[before-1] < arr[before]:
currCount = previousCount + currCount
previousCount = currCount
totalSawCounts = totalSawCounts + currCount
return totalSawCounts
测试用例:
arr = [9,8,7,6,5]
print(solution(arr)) # 4
arr2 = [1,2,1,3,4,-2]
print(solution(arr2)) # 9
arr3 = [1,2,1,2,1]
print(solution(arr3)) # 10
arr4 = [10,10,10]
print(solution(arr4)) # 0
# from medium article comments
arr5 = [-442024811,447425003,365210904,823944047,943356091,-781994958,872885721,-296856571,230380705,944396167,-636263320,-942060800,-116260950,-126531946,-838921202]
print(solution(arr5)) # 31
我认为这是一个简单的DP问题。这个想法是知道以i结尾的子数组的数量，这些子数组可以从之前的交替状态(增加/减少)扩展。如果当前元素比前一个元素低，它可以促成已经在增加的子数组以前一个状态结束(i-1)，反之亦然。
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> arr) {
int n = arr.size(), ans = 0;
// vector<vector<int>> dp(n, vector<int>(2, 0));
int inc = 0, dec = 0;
for(int i = 1; i < n; i++) {
if (arr[i] > arr[i-1]) {
// dp[i][0] = dp[i-1][1] + 1;
inc = dec + 1;
dec = 0;
} else if (arr[i] < arr[i-1]) {
// dp[i][1] = dp[i-1][0] + 1;
dec = inc + 1;
inc = 0;
} else {
inc = 0, dec = 0;
}
// ans += dp[i][0] + dp[i][1];
ans += (inc + dec);
}
cout << ans << endl;
}
int main() {
auto inp = {-442024811,447425003,365210904,823944047,943356091,-781994958,872885721,-296856571,230380705,944396167,-636263320,-942060800,-116260950,-126531946,-838921202};
solve(inp);
return 0;
}
下面是一个非常简单直接的解决方案，使用一个for循环
import math
def comb(x):
st = 0
total_comb = 0
if len(x) < 2: #edge case
return 0
if len(x) == 2: #edge case
return 2
seq_s = 0
for i in range(1, len(x)-1):
if (x[i]<x[i-1] and x[i]<x[i+1]) or (x[i]>x[i-1] and x[i]>x[i+1]):
continue
else:
print(x[seq_s:i+1])
if i+1-seq_s == 2 and x[i] == x[i-1]: #means we got two same nums like 10, 10
pass
else: total_comb+=math.comb(i+1-seq_s,2)
seq_s=i
i+=1
print(x[seq_s:])
if i+1-seq_s == 2 and x[i] == x[i-1]: #means we got two same nums like 10, 10
pass
else: total_comb+=math.comb(len(x)-seq_s,2)
return total_comb
x= [1,2,1,3,4,-2]
print(comb(x))
使用渐变方法
通过所有测试用例
from math import comb
def solution(arr):
n=len(arr)
if arr[1]!=arr[0]:
l=2
else:
l=0
pre=arr[1]-arr[0]
ans=0
for i in range(2,n):
cur=arr[i]-arr[i-1]
if cur*pre<0:
l+=1
else:
if l==2:
ans+=1
elif l==0:
ans+=0
else:
ans+=comb(l,2)
if cur!=0:
l=2
else:
l=0
pre=cur
if l==2:
ans+=1
elif l==0:
ans+=0
else:
ans+=comb(l,2)
return ans
我认为这里的技巧是要意识到:假设您有一个长度为x的有效锯齿序列，添加一个额外的有效元素也会使子序列的数量增加x。
的例子:
-
[1,2,1]是一个有效的锯齿序列 -
在
[1,2,1]的有效序列上加上2形成[1,2,1,2]。我们在这里看到，向长度为3的有效序列中添加一个新元素会增加3个新的有效子序列，它们是:[1,2,1,2],[2,1,2]和[1,2]。 -
相应地，在
[1,2,1,2]上再增加一个有效元素，如-1，将增加4个新的子序列，分别是:[1,2,1,2,-1]、[2,1,2,-1]、[1,2,-1]和[2,-1]。
因此，我们可以使用带有左右指针l和r的移动窗口来跟踪有效序列的长度，当检测到无效序列时重置l指针。
.
def solution(arr: list) -> int:
'''
for every char, check if still current sawtooth
if still currently sawtooth, numberOfWays += length
else reset temp counter
'''
l, r = 0, 1
ways = 0
while r < len(arr):
# check if current char + past 2 chars are sawtooth
if r-l > 1 and (arr[r-2] < arr[r-1] > arr[r] or
arr[r-2] > arr[r-1] < arr[r]):
ways += r-l
# check if current char + past 1 chars are sawtooth
elif arr[r-1] != arr[r]:
ways += 1
l = r-1
else:
# reset left pointer
l = r
r += 1
return ways
我做了一些非常简单的事情，但它给出了您提供的所有测试用例的正确答案:
function sawtooth(arr) {
if (arr.length < 2) return 0;
let previousLongest = 1;
let result = 0;
for (let i = 1; i < arr.length; i++) {
if (i >= arr.length) break;
if (arr[i - 1] === arr[i]) continue;
if (arr[i - 1] > arr[i] && arr[i] < arr[i + 1] || arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
previousLongest += 1;
} else {
previousLongest = 1;
}
result += previousLongest;
}
return result;
}